基于內存云的自適應數(shù)據(jù)恢復策略

盧學遠，錢育蓉，英昌甜

(1.新疆大學軟件學院，新疆 烏魯木齊 830008；2.新疆大學電氣工程學科博士后流動站，新疆 烏魯木齊 830046)

0 引言

鑒于傳統(tǒng)硬件緩慢的讀寫特性，基于內存價格驟降的基礎上，純內存存儲方式被提出.與此同時由于內存價格的急速降低，從1980年的19 200美元/MB(SRAM，Static Random Access Memory，靜態(tài)隨機存儲器)和8 000美元/MB(DRAM，Dynamic Random Access Memory，動態(tài)隨機存儲器)到2010年的60美元/MB(SRAM)和0.06美元/MB(DRAM)[1]，基于存儲硬件由純內存組成的計算系統(tǒng)SPA HANA[2]和結合目前熱點話題——云計算組成的內存云(RAMCloud)[3]被提出.其中SPA HANA是一種根據(jù)系統(tǒng)本身實時地獲取用戶數(shù)據(jù)并進行實時分析和實時存儲的純內存計算系統(tǒng).RAMCloud[4]為斯坦福大學的開源項目，其主要目的是建立由純內存硬件構成的高效內存存儲系統(tǒng).在2009年至2016年間，斯坦福大學的專家和學者們針對RAMCloud項目展開了一系列的深入研究[5-9]，在2015年正式提出RAMCloud存儲系統(tǒng)[5].同時，在國內不少研究者對RAMCloud的帶寬負載均衡[11]、存儲優(yōu)化[12]和數(shù)據(jù)遷移[13]等方面進行了研究.

但是由于目前大數(shù)據(jù)時代下，大型數(shù)據(jù)中心跨域恢復數(shù)據(jù)方式的固定性、單一性、數(shù)據(jù)跨域恢復需求的高效率性以及數(shù)據(jù)恢復方式效能的波動性，RAMCloud存儲系統(tǒng)的數(shù)據(jù)備份恢復能力的自適應性存在問題.

本文對大型內存存儲數(shù)據(jù)中心RAMCloud數(shù)據(jù)恢復控制調度中心進行調度算法優(yōu)化.算法結合增強學習智能多臂老虎機Softmax算法(在監(jiān)督學習中，Softmax算法用作最終的模型分類器；在增強學習中，用作權衡各個操作之間的概率權值)，根據(jù)數(shù)據(jù)恢復耗時記憶，在極短的時間內，完成自我調整.使得算法能夠智能調度數(shù)據(jù)恢復機制，使得任意一步所選擇的數(shù)據(jù)恢復機制所消耗的時間達到局部最優(yōu)解，從而達到降低全局數(shù)據(jù)恢復耗時的目的.

1 RAMCloud架構

RAMCloud作為云計算的延伸研究，其主要底層技術原理與云計算存在共性，同樣是通過數(shù)據(jù)中心多臺服務器的虛擬化對整體物理資源的整合，并通過云系統(tǒng)[14]對其資源切分，形成單體用戶專屬的單體資源虛擬客戶端，其原理類似于Docker，在某些虛擬客戶端長期不運行的狀態(tài)下，對計算資源進行回收，以達到云資源合理利用的目的.

RAMCloud存儲系統(tǒng)在架構上與Google所提出的HDFS有所區(qū)別.HDFS是由少數(shù)的主節(jié)點namenode(之所以不是單個主節(jié)點是為了防止單點故障)和多個數(shù)據(jù)節(jié)點datanode組成的.而RAMCloud[10]是由多個應用服務器(Application Servers)、與應用服務器數(shù)量對應的存儲服務器(Storage Servers)、兩個協(xié)調器(Coordinator，Standby Coordinator為備用協(xié)調器)和一個額外存儲系統(tǒng)(External Storage，即Zookeeper)組成.其整體架構如圖1所示.

圖1 RAMCloud整體架構圖

1.1 RAMCloud低延遲

在小集群中，對于簡單的遠程過程調用(例如讀取一個小對象)端到端之間的延遲低于5 μs；在大型的數(shù)據(jù)中心，簡單的遠程過程調用延遲低于10 μs[3].基層網絡架構是完成RAMCloud低延遲特性最大的困難點.在2009年，RAMCloud項目初步啟動之時，在大型數(shù)據(jù)中心中簡單的遠程過程調用延遲高達幾百微秒.絕大部分延遲都是網絡交換機的緣故，每增加一臺網絡交換機將增加10～30 μs的延遲[6]，任一個數(shù)據(jù)包一次傳輸需要經過5個交換機.此外，整體的傳輸時間同樣受限于操作系統(tǒng)的性能(內核調用、網絡堵塞、中斷處理等)，甚至受限于CPU和網絡接口控制器之間的傳遞性能.而且，大部分數(shù)據(jù)中心網絡通常超載100倍甚至更大，所以網絡堵塞通常由頂級連接的不充足帶寬增加了額外的延遲所造成的.

2009年，網絡架構得到提升，在無限帶寬的網絡環(huán)境下，低延遲性能得以實現(xiàn).[3]新型10 GB以太網接口芯片提供了RAMCloud所需的低延遲和廉價帶寬.RAMCloud基于低延遲網絡帶寬將在5～10 a之間得到廣泛利用的假設基礎上建立起來的.

1.2 RAMCloud內核迂回和選舉

RAMCloud基于內核迂回和選舉[5]兩個底層技術來達到低延遲效果.內核迂回是指一個應用不需要通過內核調用來接收和發(fā)送數(shù)據(jù)包.NIC硬件注冊后會在應用的地址空間對其進行內存映射，使得應用能夠直接連接NIC.不同的應用使用其對應的不同內存映射集合來注冊.應用了溝通數(shù)據(jù)包緩沖地址與NIC虛擬使用地址(NIC必須知曉虛擬地址到物理地址的映射).這要求緩沖內存能夠洞穿物理內存.內核迂回要求NIC具有某種特性(這種特性通常不會使用，但是現(xiàn)在越來越普及，其類似特性需要虛擬機管理I/O虛擬化的支持).內核迂回闡述了操作系統(tǒng)負載跌至零的緣由.目前在無限帶寬下的NIC支持內核迂回.

RAMCloud實現(xiàn)低延遲的第2個底層技術是使用內存選舉(忙碌等待)來處理事件的等待問題[4].例如，當客戶端線程等待遠程過程調用請求回復時，客戶端線程處于激活狀態(tài)；反之，客戶端線程反復選擇NIC檢查回復是否到達.在這種情況下鎖定線程將降低原有的效果.CPU能夠并行運行其他任務，遠程過程調用將有可能完成，這種選舉方式權衡了中斷的代價和喚醒已鎖定線程的代價(使用一種條件變量來喚醒線程耗時大約2 μs).RAMCloud服務器同樣使用選舉方式去等待正在輸入的請求：即使RAMCloud沒有請求發(fā)出，一臺服務器也需要使用一核處理器來等待選舉，這使得RAMCloud對請求能夠快速地產生響應.

2 RAMCloud數(shù)據(jù)恢復耗時模型

2.1 數(shù)據(jù)恢復耗時定義及模型

數(shù)據(jù)恢復耗時分布式集群中單位數(shù)據(jù)塊丟失后，通過自適應算法選擇，某種數(shù)據(jù)恢復機制恢復數(shù)據(jù)所負載服務器的總耗時.其定義公式為

(1)

2.2 RAMCloud期望耗時建模

對于RAMCloud集群的數(shù)據(jù)恢復機制的耗時，存在一個大致的期望值，使得集群通過某些方式最小化該值.其建模公式為

(2)

2.3 自適應策略期望耗時模型

自適應RAMCloud期望耗時模型，其建模公式為

(3)

(4)

式中：S(a)為一個取得函數(shù)值最小化情況下的參數(shù)值的函數(shù)[14-15]，S(a)的值域為[0，1]；‖a‖為到目前為止程序記憶中數(shù)據(jù)恢復途徑為a的歷史集合的大?。籥i為a集合中的一個元素；e為exp函數(shù).因此，S(a)為根據(jù)任意數(shù)據(jù)恢復途徑的歷史期望exp函數(shù)值占全局exp函數(shù)值的比例，選取比例最小時的數(shù)據(jù)恢復機制為a.(4)式將根據(jù)數(shù)據(jù)的不斷更新與迭代，在算法迭代中不斷記憶與收集新的數(shù)據(jù)恢復耗時數(shù)據(jù)，并在整個算法運算過程中不斷地權衡各個數(shù)據(jù)恢復機制之間的耗時分值.

為了降低算法的時間復雜度與盡可能地降低空間復雜度，開始對算法部分公式進行化簡.其公式為

(5)

設φ(at)為在t時刻，數(shù)據(jù)恢復機制a根據(jù)exp函數(shù)對歷史所有已發(fā)生過a機制的數(shù)據(jù)恢復耗時函數(shù)值的期望.其中‖at‖為截止t時刻機制a的執(zhí)行次數(shù).可得到

(6)

在t+1時刻，(6)式在(5)式的基礎上，對‖at‖進行了擴展，其中‖at‖≤‖at+1‖≤‖at‖+1，即‖at‖與‖at+1‖兩者之差不超過1.同時在計算exp函數(shù)可能性地增加eat+1，之所以為可能性是由于t+1時刻并不一定是a機制.根據(jù)以上推斷，對(6)式進行化簡，得

(7)

根據(jù)(7)式，φ(at+1)可表示為只與t時刻的‖at‖和φ(at)、t+1時刻的機制at+1和‖at+1‖與其耗時權值eat+1有關.(7)式減免了任意一個時刻對歷史0時刻至t-1時刻的所有值的重復計算.(7)式降低了(5)式的計算時間復雜度，從O(n)降低至O(1).同時，根據(jù)(7)式，減免了(5)式長序列地存儲一系列n個ea值，因此將空間復雜度從O(n)降低至O(1).

(7)式中，φ(at+1，a)為指示函數(shù)，取值范圍為0與1，其公式為

(8)

在(8)式中，當at+1=a時，φ(at+1，a)為1；當at+1≠a時，φ(at+1，a)為0.

結合(7)式與(8)式，對(7)式進一步化簡，得到

(9)

(9)式中，φ(at+1)可表示為只與t時刻的‖at‖和φ(at)、t+1時刻的機制at+1與其耗時權值eat+1有關.因此在(7)式的基礎上，降低了少量的空間復雜度.

根據(jù)(9)式生成最終的算法計算公式與邏輯代碼.

3 自適應數(shù)據(jù)恢復策略

為了讓數(shù)據(jù)恢復機制具有一定的智能，同時滿足算法能夠通過不斷地記憶、迭代統(tǒng)計歷史數(shù)據(jù)恢復信息，本文引入增強學習的多臂老虎機Softmax算法，同時為了使得Softmax算法更適用于耗時模型，對算法進行了更改.最終使得數(shù)據(jù)恢復選擇機制能夠在任意一步選擇中，綜合歷史經驗，有傾向性地選擇當前最優(yōu)的數(shù)據(jù)恢復機制.

3.1 自適應RAMCloud數(shù)據(jù)恢復策略流程

圖2 自適應數(shù)據(jù)恢復策略流程

自適應RAMCloud數(shù)據(jù)恢復策略流程主要由歷史結算、各個機制權重總體占比結算、獲取權值占比最小的機制、運行被選機制、獲取機制運行耗時和算法記憶6個部分組成.其過程如圖2所示.

自適應數(shù)據(jù)恢復策略流程分為隨機數(shù)據(jù)塊模塊、計算歷史權重模塊、計算權重占比模塊、取權重占比最小機制模塊、運行并獲取運行耗時模塊和記憶模塊.其中，后5個模塊組成了算法模塊.

策略流程中，輸入為隨機數(shù)據(jù)塊，該數(shù)據(jù)塊滿足數(shù)據(jù)丟失以及備份數(shù)據(jù)庫中存有該數(shù)據(jù)塊內數(shù)據(jù)條件.

算法模塊第1步：計算歷史權重模塊，該模塊需要結合算法記憶模塊內的算法記憶數(shù)據(jù)以及上一步數(shù)據(jù)恢復機制選擇的結果，根據(jù)算法公式計算各個數(shù)據(jù)恢復機制的權重.

算法模塊第2步：計算權重占比模塊.該模塊為算法重點模塊之一，它根據(jù)上一模塊的計算將對各個數(shù)據(jù)塊的算法權值分布進行重新洗牌，使得算法在一定程度上具有自我學習、自我更新的能力.

算法模塊第3步：取權重占比最小機制模塊.該模塊是對計算權重占比模塊的總結，根據(jù)權重占比選擇當前占比最小的數(shù)據(jù)恢復機制.其結果并不一定與上一次入選的數(shù)據(jù)恢復機制相同，因此具有了一定的智能選擇行為.

算法模塊第4步：運行并獲取運行耗時模塊.該模塊是對入選數(shù)據(jù)恢復機制進行運行與耗時測量，以用于算法更新迭代.

算法模塊第5步：記憶模塊.該模塊同樣為算法重點模塊之一，它主要記憶各個數(shù)據(jù)恢復機制，在該策略下，歷史已執(zhí)行的數(shù)據(jù)恢復耗時以及各個數(shù)據(jù)恢復機制的被執(zhí)行次數(shù).

策略通過不斷地記憶，與不斷地對數(shù)據(jù)恢復機制權重占比的重新洗牌，達到自我更新與優(yōu)化調整的目的.

3.2 算法偽代碼

集群是根據(jù)服務器狀況以及隨機的故障發(fā)生率而發(fā)生數(shù)據(jù)塊丟失事件.因此，本文隨機地抽取集群中的數(shù)據(jù)塊進行數(shù)據(jù)恢復操作，同時根據(jù)上述公式，生成算法偽代碼為：

#隨機選定數(shù)據(jù)塊大小

data_size = random.randint(a，b)，

data_batch = random.sample(data_batchs，data_size).

#初始化記憶空間

cost_times = 0，

Softmax = {‘RAMCloud’：1.0，‘Hive’：1.0，‘Spark’：1.0}，

counter = {‘RAMCloud’：1，‘Hive’：1，‘Spark’：1}，

machines =[‘RAMCloud’，‘Hive’，‘Spark’].

#數(shù)據(jù)塊迭代

for data in data_batch：

S = {}

#算法計算

for machine in machines：

S[machine] = Softmax[machine] / counter[machine]，

machine = min(weight，key=weight.get())，

cost_time = run(machine)，

cost_times += cost_time，

counter[machine] += 1，

Softmax[machine] += math.exp(cost_time).

#求得機制運行期望耗時

cost_time_Expecation = getException(cost_times).

算法第一步隨機選定丟失數(shù)據(jù)塊data_batch及其數(shù)量data_size、定義數(shù)據(jù)恢復機制定義域machines、初始化exp總值空間Softmax、初始化數(shù)據(jù)恢復機制計數(shù)器counter.本文在偽代碼第一步做了拉普拉斯平滑，因為在任意機制運行0次之時，對(4)式容易觸發(fā)邊界問題.

第二步遍歷所有選定數(shù)據(jù)塊，并根據(jù)上一步迭代中的新增數(shù)據(jù)恢復機制耗時生成新的權值空間S，根據(jù)S選擇數(shù)據(jù)恢復機制machine并獲取在當前機制下恢復數(shù)據(jù)的耗時cost_time.

第三步通過getExpectation函數(shù)對所有機制恢復數(shù)據(jù)耗時的總和求期望.

4 實驗結果與分析

4.1 實驗環(huán)境

為了證明上述理論的可行性以及得到客觀數(shù)據(jù)的支持，本文進行了多組相關聯(lián)的實驗.實驗硬件環(huán)境參數(shù)見表1.

表1 實驗硬件環(huán)境參數(shù)

4.2 結果分析

實驗分別使用自適應數(shù)據(jù)恢復策略以及傳統(tǒng)數(shù)據(jù)恢復策略在RAMCloud集群上進行比較實驗，實驗總共進行100次，每次使用1～10 000之間數(shù)據(jù)塊數(shù)量樣本.根據(jù)實驗數(shù)據(jù)，得到的結果如圖3所示.

橫軸為實驗迭代的次數(shù)，縱軸為任意一次實驗中所選擇的數(shù)據(jù)恢復機制的耗時.圖3中灰色線條代表RAMCloud固有的數(shù)據(jù)恢復機制，Softmax代表本文的自適應智能算法所選擇數(shù)據(jù)恢復機制(由于核心智能算法是在增強學習Softmax基礎上進行優(yōu)化，因此借用Softmax作為圖例命名).根據(jù)圖3自適應策略耗時對比得到如下結論：

(1)自適應算法在數(shù)據(jù)恢復機制耗時方面，能夠在極端的時間內(圖3為5次實驗之內，包含5次)，形成針對性的數(shù)據(jù)恢復機制調度模型.

(2)經過自我調整后的自適應模型，對相同數(shù)據(jù)塊的數(shù)據(jù)恢復進行機制調度，其所達到的耗時相對于RAMCloud固定數(shù)據(jù)恢復機制策略平均降低97.6 s.

為了更好地檢驗2種策略的優(yōu)劣，實驗在2種策略下，對數(shù)據(jù)恢復的成功率進行部分編號，實驗結果見圖4.

圖3 自適應策略耗時對比實驗

圖4 自適應策略數(shù)據(jù)恢復成功率對比實驗

圖4橫軸為實驗迭代的次數(shù)，縱軸為數(shù)據(jù)恢復機制恢復數(shù)據(jù)的成功率.同樣，圖中灰色線條為RAMCloud固定數(shù)據(jù)恢復機制策略，黑色線條為本文自適應智能調度數(shù)據(jù)恢復機制策略.根據(jù)圖4可得到如下結論：

(1) 在RAMCloud集群架構環(huán)境下，無論是本文自適應智能調度策略還是RAMCloud傳統(tǒng)數(shù)據(jù)恢復機制調度策略(即固定數(shù)據(jù)恢復機制策略)，數(shù)據(jù)恢復機制的數(shù)據(jù)恢復成功率都存在較強的波動性.

(2) 在數(shù)據(jù)恢復成功率方面，在絕大多數(shù)時刻本文自適應智能調度數(shù)據(jù)恢復機制策略相比RAMCloud傳統(tǒng)數(shù)據(jù)恢復機制調度策略高.

(3) 本文智能策略在自我調整初期，存在數(shù)據(jù)恢復成功率低于或等于RAMCloud傳統(tǒng)數(shù)據(jù)恢復機制調度策略.

圖5 自適應策略綜合對比實驗

自適應策略綜合對比實驗見圖5，縱軸為提升率，橫軸為實驗迭代的次數(shù)，曲線time_lower_rate定義為探索式數(shù)據(jù)恢復策略相對傳統(tǒng)數(shù)據(jù)恢復策略降低耗時的比例，recovery_rate定義為探索式數(shù)據(jù)恢復策略相比傳統(tǒng)數(shù)據(jù)恢復策略提高數(shù)據(jù)恢復成功率的比例.根據(jù)圖5可得如下結果：

(1) time_lower_rate曲線與recovery_rate曲線在初期具有明顯的波動，證明自適應策略在適應與自我調整.

(2) 在自適應策略自我調整后，time_lower_rate曲線與recovery_rate曲線開始進入平穩(wěn)波動期，且波動比例皆大于0.證明自適應策略在自行調整后，其策略選擇結果皆優(yōu)于固有傳統(tǒng)式RAMCloud.

(3) 根據(jù)實驗，自適應數(shù)據(jù)恢復策略相比傳統(tǒng)數(shù)據(jù)恢復策略，相對平均提速93.6%，數(shù)據(jù)恢復相對成功率平均提高8.7%.

(4) 自適應數(shù)據(jù)恢復策略的提速以及數(shù)據(jù)恢復成功率的提高在5次實驗內就可自我調整完畢.

由實驗結果可知，自適應數(shù)據(jù)恢復策略的耗時以及數(shù)據(jù)恢復成功率皆優(yōu)于傳統(tǒng)數(shù)據(jù)恢復策略.因此，在當前RAMCloud版本以及數(shù)據(jù)恢復效率情況下，用自適應數(shù)據(jù)恢復策略替代傳統(tǒng)數(shù)據(jù)恢復策略，能夠使得服務器集群核心主節(jié)點根據(jù)數(shù)據(jù)恢復歷史記錄有效地自行調整數(shù)據(jù)恢復途徑選擇機制.

5 結語

內存云架構的提出為現(xiàn)有的硬盤式存儲架構帶來了新的變革，與此同時，其新穎性也存在著數(shù)據(jù)恢復非智能自適應多種數(shù)據(jù)恢復機制的問題.針對此類問題，本文在研究內存云整體存儲架構文件丟失后快速恢復的基礎上，提出了一種在目前RAMCloud版本下的自適應數(shù)據(jù)恢復策略，并根據(jù)公式推導與化簡，降低了算法部分計算時間復雜度與空間復雜度.經實驗驗證，該策略能有效地權衡自我記憶、自我適應、自我調整內存云各個數(shù)據(jù)恢復機制間的性能，從而在任意一次數(shù)據(jù)恢復選擇階段，根據(jù)歷史數(shù)據(jù)恢復記錄選擇最優(yōu)的數(shù)據(jù)恢復途徑，降低內存云在數(shù)據(jù)丟失后對于數(shù)據(jù)文件的恢復時間消耗，為高性能計算應用環(huán)境奠定了一定的基礎.