盧學(xué)遠，錢育蓉，英昌甜

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

0 引言

鑒于傳統(tǒng)硬件緩慢的讀寫特性，基于內(nèi)存價格驟降的基礎(chǔ)上，純內(nèi)存存儲方式被提出.與此同時由于內(nèi)存價格的急速降低，從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]，基于存儲硬件由純內(nèi)存組成的計算系統(tǒng)SPA HANA[2]和結(jié)合目前熱點話題——云計算組成的內(nèi)存云(RAMCloud)[3]被提出.其中SPA HANA是一種根據(jù)系統(tǒng)本身實時地獲取用戶數(shù)據(jù)并進行實時分析和實時存儲的純內(nèi)存計算系統(tǒng).RAMCloud[4]為斯坦福大學(xué)的開源項目，其主要目的是建立由純內(nèi)存硬件構(gòu)成的高效內(nèi)存存儲系統(tǒng).在2009年至2016年間，斯坦福大學(xué)的專家和學(xué)者們針對RAMCloud項目展開了一系列的深入研究[5-9]，在2015年正式提出RAMCloud存儲系統(tǒng)[5].同時，在國內(nèi)不少研究者對RAMCloud的帶寬負載均衡[11]、存儲優(yōu)化[12]和數(shù)據(jù)遷移[13]等方面進行了研究.

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

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

1 RAMCloud架構(gòu)

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

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

圖1 RAMCloud整體架構(gòu)圖

1.1 RAMCloud低延遲

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

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

1.2 RAMCloud內(nèi)核迂回和選舉

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

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

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

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

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

(1)

2.2 RAMCloud期望耗時建模

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

(2)

2.3 自適應(yīng)策略期望耗時模型

自適應(yīng)RAMCloud期望耗時模型，其建模公式為

(3)

(4)

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

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

(5)

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

(6)

在t+1時刻，(6)式在(5)式的基礎(chǔ)上，對‖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‖與其耗時權(quán)值eat+1有關(guān).(7)式減免了任意一個時刻對歷史0時刻至t-1時刻的所有值的重復(fù)計算.(7)式降低了(5)式的計算時間復(fù)雜度，從O(n)降低至O(1).同時，根據(jù)(7)式，減免了(5)式長序列地存儲一系列n個ea值，因此將空間復(fù)雜度從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.

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

(9)

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

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

3 自適應(yīng)數(shù)據(jù)恢復(fù)策略

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

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

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

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

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

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

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

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

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

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

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

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

3.2 算法偽代碼

集群是根據(jù)服務(wù)器狀況以及隨機的故障發(fā)生率而發(fā)生數(shù)據(jù)塊丟失事件.因此，本文隨機地抽取集群中的數(shù)據(jù)塊進行數(shù)據(jù)恢復(fù)操作，同時根據(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ù)恢復(fù)機制定義域machines、初始化exp總值空間Softmax、初始化數(shù)據(jù)恢復(fù)機制計數(shù)器counter.本文在偽代碼第一步做了拉普拉斯平滑，因為在任意機制運行0次之時，對(4)式容易觸發(fā)邊界問題.

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

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

4 實驗結(jié)果與分析

4.1 實驗環(huán)境

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

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

4.2 結(jié)果分析

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

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

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

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

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

圖3 自適應(yīng)策略耗時對比實驗

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

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

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

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

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

圖5 自適應(yīng)策略綜合對比實驗

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

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

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

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

(4) 自適應(yīng)數(shù)據(jù)恢復(fù)策略的提速以及數(shù)據(jù)恢復(fù)成功率的提高在5次實驗內(nèi)就可自我調(diào)整完畢.

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

5 結(jié)語

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