王躍飛　于炯　魯亮

摘要：

針對ZooKeeper機(jī)制難以滿足內(nèi)存云（RAMCloud）低延遲、快恢復(fù)的問題，提出了一種面向內(nèi)存云的協(xié)調(diào)器選舉策略（CES）。首先根據(jù)內(nèi)存云網(wǎng)絡(luò)環(huán)境與協(xié)調(diào)器自身因素將協(xié)調(diào)器性能指標(biāo)分為個體指標(biāo)與協(xié)調(diào)器間指標(biāo)兩類并分別建立模型；然后將內(nèi)存云的運行分為正常運行期與數(shù)據(jù)恢復(fù)期兩階段并分別建立適應(yīng)度函數(shù)，再按時間比合并為總適應(yīng)度函數(shù)；最后在備選協(xié)調(diào)器（RBC）的適應(yīng)度值的基礎(chǔ)上提出一個具備穩(wěn)定擇優(yōu)性與隨機(jī)性的新算子，CES首先通過篩選來排除性能較差的個體，縮小選擇范圍后再在理想?yún)f(xié)調(diào)器的集合中采用輪盤賭方法選擇最終的個體。實驗結(jié)果表明，在NS2仿真環(huán)境下CES選擇的個體相比其他備選協(xié)調(diào)器數(shù)據(jù)處理延遲降低了19.35%；在搭建的內(nèi)存云環(huán)境中，與ZooKeeper機(jī)制相比，CES的選擇結(jié)果在快速恢復(fù)中時間減少了10.02%。在內(nèi)存云的實際應(yīng)用中，CES在處理單點失效問題上能有效選擇性能更優(yōu)的協(xié)調(diào)器，確保了低延遲、快恢復(fù)的要求。

關(guān)鍵詞：

內(nèi)存云；協(xié)調(diào)器；單點失效；適應(yīng)度函數(shù)；選舉策略

中圖分類號：

TP393.02

文獻(xiàn)標(biāo)志碼：A

Abstract：

Focusing on the issue that ZooKeeper cannot meet the requirement of low latency and quick recovery of RAMCloud， a Coordinator Election Strategy （CES） based on RAMCloud was proposed. First of all， according to the network environment of RAMCloud and factors of the coordinator itself， the performance indexes of coordinator were divided into two categories including individual indexes and coordinator indexes， and models for them were built separately. Next， the operation of RAMCloud was divided into errorfree running period and data recovery period， their fitness functions were built separately， and then the two fitness functions were merged into a total fitness function according to time ratio. Lastly， on the basis of fitness value of RAMCloud Backup Coordinator （RBC）， a new operator was proposed with randomness and the capacity of selecting an ideal target： CES would firstly eliminate poorperforming RBC by screening， as the range of choice was narrowed， CES would select the ultimate RBC from the collection of ideal coordinators by means of roulette. The experimental results showed that compared with other RBCs in the NS2 simulation environment， the coordinator selected by CES decreased latency by 19.35%； compared with ZooKeeper in the RAMCloud environment， the coordinator selected by CES reduced recovery time by 10.02%. In practical application of RAMCloud， the proposed CES can choose the coordinator with better performance， ensure the demand of low latency and quick recovery.

英文關(guān)鍵詞Key words：

RAMCloud； coordinator； singlepoint failure； fitness function； election strategy

0引言

隨著電子商務(wù)與社交網(wǎng)絡(luò)的快速發(fā)展，越來越多的企業(yè)與組織常常面臨百萬級的用戶并發(fā)訪問與每秒數(shù)以千計的并發(fā)事務(wù)處理[1]。2011年7月，《中國計算機(jī)學(xué)會通訊》針對數(shù)據(jù)密集型計算（DataIntensive Computing， DIC）展開了專題研究[2]，并將極限事務(wù)處理（Extreme Transaction Processing， XTP）作為解決密集型應(yīng)用的關(guān)鍵。斯坦福大學(xué)于2009年提出內(nèi)存云理念，使相關(guān)問題得到良好的緩解[3]：內(nèi)存云（RAMCloud）是一組以內(nèi)存為存儲媒介，所有數(shù)據(jù)均存儲在動態(tài)隨機(jī)訪問存儲器（Dynamic Random Access Memory， DRAM）內(nèi)，硬盤僅作為數(shù)據(jù)備份。由于文件數(shù)據(jù)始終存儲在內(nèi)存，系統(tǒng)的吞吐量與時延得到了高效的優(yōu)化。近年來有關(guān)內(nèi)存云的研究領(lǐng)域逐漸得到擴(kuò)展與深化：研究人員不僅對數(shù)據(jù)的管理與恢復(fù)作出了系統(tǒng)的改善[4-5]，同樣針對數(shù)據(jù)的并發(fā)容錯，存儲查詢提出了新的模型與框架[6-8]。目前國內(nèi)也開展了相關(guān)研究，對包括磁盤節(jié)能[9]、小文件合并[10]等問題作出了優(yōu)化與完善。

由于內(nèi)存云協(xié)調(diào)器（coordinator）在斷電等自然災(zāi)害情況下會不可避免地面臨由單點失效造成的系統(tǒng)癱瘓問題，針對關(guān)鍵節(jié)點再選舉，Hadoop的擴(kuò)展項目ZooKeeper開源實現(xiàn)了Google的chubby服務(wù)，通過paxos的變種算法解決了候選節(jié)點的選舉問題[11]。然而Zab（ZooKeeper atomic broadcast）協(xié)議難以支撐內(nèi)存云高效的讀取速率，Junqueira等[12]對Zab協(xié)議的延遲進(jìn)行了分析，實驗證明在單獨的一個操作中，服務(wù)器間的平均延遲在100ms以上，遠(yuǎn)高于內(nèi)存云的微秒級別[13]。另外，Zab協(xié)議更適用于競選id確定的情況下執(zhí)行[14]，內(nèi)存云網(wǎng)絡(luò)情況復(fù)雜，備選協(xié)調(diào)器（RAMCloud Backup Coordinator， RBC）數(shù)目較多，備選集合隨情況不同數(shù)目也會有所變化。

文獻(xiàn)[15]對內(nèi)存云使用Zab協(xié)議進(jìn)行了研究，結(jié)果表明：1）單點失效后內(nèi)存云僅采用隨機(jī)的方法在備選協(xié)調(diào)器集群內(nèi)選擇協(xié)調(diào)器；2）在配置文件較小的情況下單點恢復(fù)速度低于服務(wù)器恢復(fù)速度。以上問題表明傳統(tǒng)選舉機(jī)制并不適用于內(nèi)存云環(huán)境，突破延遲問題并依據(jù)網(wǎng)絡(luò)狀況才是選擇備選協(xié)調(diào)器的重要方法。

本文主要針對備選協(xié)調(diào)器（RBC）的選擇問題進(jìn)行研究，為解決該問題，提出了一種適于內(nèi)存云日志文件系統(tǒng)的協(xié)調(diào)器選舉策略（Coordinator Election Strategy， CES）。首先，根據(jù)內(nèi)存云網(wǎng)絡(luò)拓?fù)渑c協(xié)調(diào)器自身性能，將協(xié)調(diào)器指標(biāo)分為個體指標(biāo)與協(xié)調(diào)器間指標(biāo)并分別建立模型，這些模型能夠?qū)θ我鈪f(xié)調(diào)器進(jìn)行客觀評價；然后，引入遺傳算法的適應(yīng)度函數(shù)，為保證客觀，將內(nèi)存云適應(yīng)度函數(shù)分為正常運行與數(shù)據(jù)恢復(fù)兩階段，之后根據(jù)時間比合并；最后，為篩選最優(yōu)協(xié)調(diào)器，本文提出一個穩(wěn)定的新算子，該算子能在備選集里不失隨機(jī)性地選擇狀況良好的協(xié)調(diào)器作為最終選擇。

1內(nèi)存云架構(gòu)

1.1內(nèi)存云結(jié)構(gòu)

在內(nèi)存云集群中，每臺服務(wù)器既是由內(nèi)存構(gòu)造的主服務(wù)器（Master），用作數(shù)據(jù)文件的存儲；同時也是由硬盤組成的備份服務(wù)器（Backup），用來防止斷電等災(zāi)害而備份內(nèi)存中的數(shù)據(jù)，框架結(jié)構(gòu)如圖1所示。另外，集群中含一個類似Hadoop中namenode節(jié)點[16]的協(xié)調(diào)器，在集群運行與數(shù)據(jù)恢復(fù)階段負(fù)責(zé)管理服務(wù)器，記錄鍵值對日志，完成對應(yīng)功能。

1.2內(nèi)存云協(xié)調(diào)器

協(xié)調(diào)器關(guān)系到服務(wù)中心的正常運行，雖然它不涉及數(shù)據(jù)的讀寫，但作為建立檢查點、分配和調(diào)用資源、存儲數(shù)據(jù)映射信息的核心服務(wù)器，協(xié)調(diào)器在各階段承擔(dān)著監(jiān)察和統(tǒng)籌全局的重要角色?？紤]到各時期的差異，將協(xié)調(diào)器功能分為兩階段，分別是服務(wù)器正常運行時期以及數(shù)據(jù)的快速恢復(fù)時期。

1）服務(wù)器正常運行時期[17]。協(xié)調(diào)器需控制主服務(wù)器、備份服務(wù)器在線；需周期性監(jiān)測是否有任意服務(wù)器宕機(jī)；需管理數(shù)據(jù)映射服務(wù)器的信息表；當(dāng)客戶端緩存丟失時，需與客戶端連接。絕大部分時間內(nèi)，集群內(nèi)的服務(wù)器均是正常工作的，但并不排除突發(fā)故障等問題，若發(fā)生斷電等災(zāi)害問題時協(xié)調(diào)器則會啟動應(yīng)急項。

2）數(shù)據(jù)快速恢復(fù)期[18]。主服務(wù)器在宕機(jī)前，數(shù)據(jù)以段（segment）的形式復(fù)制3份，并分別存儲在不同的備份服務(wù)器中，協(xié)調(diào)器存儲了關(guān)于當(dāng)前服務(wù)器數(shù)據(jù)備份的物理位置的映射信息，作為并行恢復(fù)查找點。另外，當(dāng)恢復(fù)后所有段拼接完畢，協(xié)調(diào)器需查看拼接日志的完整性。

2協(xié)調(diào)器模型

內(nèi)存云網(wǎng)絡(luò)拓?fù)洳蛔裱瓎我唤Y(jié)構(gòu)，而是呈混合多樣化，即便容納更多服務(wù)器也能保證集群的易拓展性，圖2是一個典型的內(nèi)存云網(wǎng)絡(luò)拓?fù)浜喕?/p>

圖2中S表示交換機(jī)（Switch， S），每臺備選協(xié)調(diào)器C與多臺聚合交換機(jī)（Aggregation Switch， AS）交互，網(wǎng)絡(luò)內(nèi)部關(guān)系復(fù)雜；當(dāng)機(jī)架較多或有新的服務(wù)設(shè)備納入時，底層交換機(jī)下還可能建立新的交換網(wǎng)絡(luò)。根據(jù)內(nèi)存云日志文件系統(tǒng)的運行方法與規(guī)律，可將內(nèi)存云網(wǎng)絡(luò)抽象，為RBC設(shè)置若干參數(shù)并建立模型，并將這些參數(shù)作為選舉策略的重要依據(jù)。通過1.1節(jié)對協(xié)調(diào)器的功能分析以及內(nèi)存云網(wǎng)絡(luò)拓?fù)?，現(xiàn)將參數(shù)劃分為兩類：1）個體指標(biāo)；2）協(xié)調(diào)器間指標(biāo)。

2.1個體指標(biāo)

定義1備選協(xié)調(diào)器個體指標(biāo)。備選協(xié)調(diào)器個體指標(biāo)是指在內(nèi)存云網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，備選集內(nèi)每臺協(xié)調(diào)器個體特性以及網(wǎng)絡(luò)結(jié)構(gòu)特性，包括：RBC連通性、RBC中心性和剩余內(nèi)存空間。

2.1.1RBC連通性

協(xié)調(diào)器的連通性是指：1）與主服務(wù)器、備份服務(wù)器的連通性；2）與客戶端的連通性。內(nèi)存云中，協(xié)調(diào)器為探測集群中是否存在宕機(jī)服務(wù)器，以及為管理各類在線服務(wù)器，主服務(wù)器會周期性地向協(xié)調(diào)器發(fā)送心跳，協(xié)調(diào)器如果在一段時間內(nèi)沒有收到心跳，就會將該服務(wù)器標(biāo)記為宕機(jī)。另外，客戶端存儲了與主服務(wù)器直接連接的緩存數(shù)據(jù)，如若緩存丟失，客戶端將嘗試與協(xié)調(diào)器建立連接，并重新建立緩存。由于暫不模擬與客戶端的交互，連通性僅將與各服務(wù)器的連接關(guān)系納入考慮范圍。

針對與各服務(wù)器的連接關(guān)系，RBC連通性模型建立如下：

C（c）=λ·1n∑nk=1j·Ttk（1）

其中：C（c）表示協(xié)調(diào)器c的連通性（connectivity）；n為集群中服務(wù)器數(shù)量； j為主服務(wù)器向協(xié)調(diào)器發(fā)送心跳次數(shù)，次數(shù)較多統(tǒng)計越為準(zhǔn)確；T為系統(tǒng)設(shè)置的心跳周期；tk是協(xié)調(diào)器記錄的服務(wù)器k在j次心跳循環(huán)中總接收時間；為協(xié)調(diào)連通值與其他因素的關(guān)系，插入在最后計算適應(yīng)度值時連通性的權(quán)重λ，可依據(jù)情況改變大小。可以觀察到連通性反映了平均接收心跳時間，能夠以時間衡量影響主服務(wù)器與協(xié)調(diào)器通信路徑的因素。這是因為數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲薪尤雽?、匯聚層的光纖帶寬是相同的，當(dāng)協(xié)調(diào)器欲與某服務(wù)器通信，需經(jīng)過若干交換機(jī)到達(dá)機(jī)架交換機(jī)（TopofRank switch， ToR），再將消息轉(zhuǎn)發(fā)至目標(biāo)服務(wù)器中，如圖3。因此真正影響接收時間的實際是通信路徑中的交換機(jī)以及路徑長度等因素。

若系統(tǒng)采用雙向心跳機(jī)制時，即協(xié)調(diào)器在周期時間也向主服務(wù)器發(fā)送心跳，同樣可以采用式（1）來判斷各協(xié)調(diào)器連通性能，但需注意tk是受前若干次心跳時間影響的，需要控制心跳次數(shù)j統(tǒng)一才可判斷各協(xié)調(diào)器連通值大小。內(nèi)存云數(shù)據(jù)中心能支持混合型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以實現(xiàn)應(yīng)用廣泛、拓展靈活等特性，與協(xié)調(diào)器間存在較少交換機(jī)的服務(wù)器則具有很大的優(yōu)勢，考慮到與協(xié)調(diào)器的通信距離、強(qiáng)度等問題，這類服務(wù)器在獲得、提交數(shù)據(jù)等方面將具有更高的優(yōu)先級。

2.1.2RBC中心性

RBC中心性表示該協(xié)調(diào)器在網(wǎng)絡(luò)拓?fù)渲械淖饔煤陀绊懥?，用來評估周圍服務(wù)器節(jié)點與該協(xié)調(diào)器連接的緊密性。一般的，若某協(xié)調(diào)器連接交換機(jī)在網(wǎng)絡(luò)中所處位置占據(jù)了該網(wǎng)絡(luò)所有最短路徑中的絕大多數(shù)，則說明該協(xié)調(diào)器在網(wǎng)絡(luò)的核心位置，所發(fā)出的信息指令也能更迅速地傳遞到網(wǎng)絡(luò)中的各臺服務(wù)器內(nèi)。

為評估任意備選協(xié)調(diào)器影響力，引入節(jié)點介數(shù)[19-20]概念。包括內(nèi)存云的眾多網(wǎng)絡(luò)中，在關(guān)鍵路徑上能夠傳遞信息的節(jié)點的重要性并不亞于具備重要信息的節(jié)點。節(jié)點介數(shù)能夠客觀反映RBC中各個協(xié)調(diào)器在網(wǎng)絡(luò)拓?fù)涞闹行幕潭?，是網(wǎng)絡(luò)節(jié)點重要性的關(guān)鍵標(biāo)志。協(xié)調(diào)器介數(shù)值表示如下：

B（c）=∑s≠t≠Sσst（Sc）σst（2）

RBC中心性的計算可依照介數(shù)的計算方法。式（2）中σst表示從s到t的所有最短路徑數(shù)目；分子部分σst（Sc）表示在所有的最短路徑中，協(xié)調(diào)器c所連接交換機(jī)S經(jīng)過的數(shù)目。B（c）的值越大，表示協(xié)調(diào)器c處理的信息路徑越多，網(wǎng)絡(luò)位置也就越為核心；若協(xié)調(diào)器位于網(wǎng)絡(luò)邊緣且與服務(wù)器連接，則中心性為零。

2.1.3剩余內(nèi)存空間

剩余內(nèi)存空間指除了必須存儲的數(shù)據(jù)信息外協(xié)調(diào)器剩余空間大小。剩余空間有以下作用：1）與主服務(wù)器并行地交互數(shù)據(jù)。協(xié)調(diào)器雖不負(fù)責(zé)數(shù)據(jù)的讀寫，卻存在很高的數(shù)據(jù)吞吐量。假設(shè)集群中含1024臺主服務(wù)器，平均每臺主服務(wù)器更新并傳遞100MB數(shù)據(jù)備份信息，考慮集群中的主服務(wù)器在同一時刻發(fā)送更新數(shù)據(jù)，則協(xié)調(diào)器至少應(yīng)含有100GB剩余空間以供并行交互。2）剩余空間有效地保障了用戶與協(xié)調(diào)器的通信。絕大部分的用戶在初期需要和協(xié)調(diào)器建立通信連接服務(wù)，以獲取主服務(wù)器地址等消息，應(yīng)有足夠大內(nèi)存空間保證與用戶動態(tài)鏈接。

協(xié)調(diào)器剩余內(nèi)存空間的數(shù)學(xué)模型定義如下：

CFS=1γ{CRS-∑ni=1（maplist+iso）-∑ni=1cache-∑ni=1∑objectsbackupId}（3）

式（3）描述了協(xié)調(diào)器剩余空間（Coordinator Free Space， CFS）的計算方式，其中：γ用作在計算適應(yīng)度函數(shù)時對CFS大小的調(diào)整，可通過訓(xùn)練獲得。協(xié)調(diào)器總內(nèi)存容量（Coordinator RAM Space， CRS）中包含以下存儲信息：

1）∑ni=1（maplist+iso）表示n臺主服務(wù)器存儲的數(shù)據(jù)映射表以及備份鏡像的總空間。主服務(wù)器數(shù)據(jù)塊（object）的鍵值對一般存儲在表單中，當(dāng)用戶請求主服務(wù)器數(shù)據(jù)或該主服務(wù)器宕機(jī)后協(xié)調(diào)器均需按表單查找源數(shù)據(jù)；另外，協(xié)調(diào)器應(yīng)同樣存儲類似數(shù)據(jù)的備份鏡像，以方便RBC的數(shù)據(jù)同步。

2）∑ni=1cache表示協(xié)調(diào)器與集群內(nèi)所有主服務(wù)器通信信息的緩存空間總和協(xié)調(diào)器作為中樞節(jié)點必須存儲于各個主服務(wù)器的通信信息并建立緩存，方便用戶以及主服務(wù)器的接入。

3）∑ni=1∑objectsbackupId表示集群中每臺主服務(wù)器每個數(shù)據(jù)塊備份地址信息占用的空間總和。每臺主服務(wù)器包含任意多個數(shù)據(jù)塊，每個數(shù)據(jù)塊備份在任意3個備份服務(wù)器中。

剩余內(nèi)存大小關(guān)系到集群運行狀況，是評價RBC的重要指標(biāo)。一般備選RBC集合中剩余內(nèi)存由于初始化、網(wǎng)絡(luò)位置不同等因素大小不一，因此內(nèi)存較高的協(xié)調(diào)器更能夠保證數(shù)據(jù)交互的平穩(wěn)與存儲的安全。

2.2協(xié)調(diào)器間指標(biāo)

定義2備選協(xié)調(diào)器間指標(biāo)。備選協(xié)調(diào)器個體指標(biāo)是指在內(nèi)存云網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，備選集內(nèi)每臺協(xié)調(diào)器網(wǎng)絡(luò)結(jié)構(gòu)特性，包括：1）RBC相互關(guān)聯(lián)性；2）其他因素。

2.2.1RBC相互關(guān)聯(lián)性

若某RBC被最終選為協(xié)調(diào)器，則該協(xié)調(diào)器將與RBC時刻保持大量的信息交互，這是因為協(xié)調(diào)器需在RBC集合中同步、備份數(shù)據(jù)鏡像，以防止當(dāng)前協(xié)調(diào)器宕機(jī)后數(shù)據(jù)丟失。為表示RBC內(nèi)部的通信長度，引入平均路徑長度作為參數(shù)用以評估當(dāng)前協(xié)調(diào)器各RBC關(guān)聯(lián)程度的高低。

協(xié)調(diào)器與RBC間關(guān)聯(lián)程度表示如下：

R=1D=1/（∑Ci=1dijkstra（c，i））（4）

數(shù)據(jù)中心規(guī)模較大，消息存在多路徑選擇。式（4）中：dijkstra（c，i）表示從定點協(xié)調(diào)器到某一個RBC之間的單源最短路徑，C表示RBC集合內(nèi)的備選協(xié)調(diào)器數(shù)量。該算法的累加部分為從源點到RBC集合中全部服務(wù)器的最短路徑距離之和，距離D越長，關(guān)聯(lián)程度越低。

平均路徑長度一般用來描述內(nèi)存云數(shù)據(jù)包的通信有效性，通信路徑越短，有效性越強(qiáng)。依照內(nèi)存云網(wǎng)絡(luò)部署可以簡單有效評估該協(xié)調(diào)器與RBC間的通信能力，判斷協(xié)調(diào)器間的緊密程度。

2.2.2其他因素

目前的一些復(fù)雜網(wǎng)絡(luò)分析提供了一些判斷節(jié)點性質(zhì)的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)作為網(wǎng)絡(luò)的分析方法為內(nèi)存云協(xié)調(diào)器的網(wǎng)絡(luò)結(jié)構(gòu)分析提出了參考依據(jù)：如Google采用的PageRank算法不僅能夠排列網(wǎng)頁，同樣的原理也能定位并計算網(wǎng)絡(luò)節(jié)點的重要程度；另外，安全因素同樣也應(yīng)納入考慮范疇之內(nèi)，局部網(wǎng)絡(luò)拓?fù)涞拇嗳跣匀菀滓l(fā)惡性網(wǎng)絡(luò)攻擊，安全網(wǎng)絡(luò)下的協(xié)調(diào)器則更被優(yōu)先考慮。

3協(xié)調(diào)器選擇策略

3.1遺傳算法在RBC集合的應(yīng)用

遺傳算法是解決最優(yōu)化問題的良好途徑，通過選擇、交叉、變異處理基因與染色體，遺傳算法能夠遴選出較為滿意的個體傳遞到下一代種群里。

在內(nèi)存云數(shù)據(jù)中心集群中，可以將RBC集合看作需要被遴選的初始化種群，為選出狀態(tài)最佳的協(xié)調(diào)器，可依據(jù)第2章討論的內(nèi)容建立合適的適應(yīng)度函數(shù)，該函數(shù)能夠客觀反映理想化的協(xié)調(diào)器在任意階段的必備條件，根據(jù)適應(yīng)度函數(shù)對每臺RBC的計算，可以衡量并評價集合內(nèi)每臺RBC與最優(yōu)效果的接近程度。

3.2適應(yīng)度評估函數(shù)

為解決不同的問題，遺傳算法對適應(yīng)度函數(shù)有著不同的要求。針對大部分簡單的計算，算法始終執(zhí)行唯一的適應(yīng)度函數(shù)，處理問題雖然簡單明確，但容易引發(fā)計算初期的未成熟收斂問題以及后期的競爭區(qū)分度不高問題。內(nèi)存云協(xié)調(diào)器工作內(nèi)容按時間劃分可分為服務(wù)器運行期以及快速恢復(fù)期，兩個階段對協(xié)調(diào)器要求各不相同，為客觀分析RBC集合內(nèi)各協(xié)調(diào)器指標(biāo)，兩階段可分別創(chuàng)建不同的適應(yīng)度函數(shù)。

3.2.1運行期適應(yīng)度函數(shù)

通過第2章對RBC模型的建立與性質(zhì)的探討，并結(jié)合正常運行的協(xié)調(diào)器工作內(nèi)容，分析并建立運行期適應(yīng)度函數(shù)如下：

frun=（C+B+CFS）·R（5）

其中：C、B、CFS、R分別表示協(xié)調(diào)器的連通性、中心性、協(xié)調(diào)器剩余空間以及RBC間通信狀況。參考第2章運行期協(xié)調(diào)器任務(wù)，對評價標(biāo)準(zhǔn)討論如下：首先，協(xié)調(diào)器需要及時與主服務(wù)器、備份服務(wù)器甚至丟失緩存的客戶端發(fā)送消息，頻繁的通信不僅能夠及時探測失效節(jié)點，而且可以在第一時間獲取各主服務(wù)器數(shù)據(jù)更新信息的狀況并及時記錄，因此需將協(xié)調(diào)器的連通性C和中心性B考慮在內(nèi)；其次，內(nèi)存云工作期間協(xié)調(diào)器會不定期接受各個主服務(wù)器發(fā)送的數(shù)據(jù)，數(shù)據(jù)并行傳送時對協(xié)調(diào)器內(nèi)存大小有較高的要求，因此適應(yīng)度函數(shù)納入CFS因素；最后，RBC相關(guān)性R在運行與恢復(fù)期都起到至關(guān)重要的作用，不僅能在運行時周期地將數(shù)據(jù)鏡像復(fù)制傳遞到RBC集合中，而且恢復(fù)期間允許從其他RBC中獲取需要的數(shù)據(jù)，因此R值是參照的重要因素。

3.2.2快速恢復(fù)期適應(yīng)度函數(shù)

快速恢復(fù)期與運行期大致相同，不同的是對協(xié)調(diào)器網(wǎng)絡(luò)性能要求比正常運行時高很多。參照快速恢復(fù)機(jī)制，任意服務(wù)器宕機(jī)后需要盡快恢復(fù)完畢，而恢復(fù)的關(guān)鍵便是協(xié)調(diào)器能否將要求的數(shù)據(jù)信息快速及時地發(fā)送給主服務(wù)器并接受響應(yīng)。這不僅考量了協(xié)調(diào)器與服務(wù)器是否連通，同時檢測了協(xié)調(diào)器是否處于網(wǎng)絡(luò)核心以及其通信影響力。

另外，為防止大量服務(wù)器同時癱瘓，協(xié)調(diào)器間的關(guān)聯(lián)R也存在要求，這是因為內(nèi)存云在面對大量服務(wù)器癱瘓情況時可采用多協(xié)調(diào)器共同恢復(fù)機(jī)制。通過對快速恢復(fù)期協(xié)調(diào)器任務(wù)分析，可建立適應(yīng)度函數(shù)如下：

frecovery=C·B·R（6）

協(xié)調(diào)器對網(wǎng)絡(luò)的要求很高，在適應(yīng)度函數(shù)中表示為C·B，代表了某節(jié)點連通性與中心性的乘積，這是由內(nèi)存云即時性要求決定的。倘若某節(jié)點具有網(wǎng)絡(luò)連通優(yōu)勢且與周圍服務(wù)器連接緊密，則被選為協(xié)調(diào)器的概率也就大大提升。

3.2.3協(xié)調(diào)器適應(yīng)度函數(shù)

綜合兩階段不同要求所提出的不同適應(yīng)度函數(shù)，得到如下總適應(yīng)度函數(shù)：

F=αfrun+βfrecovery（7）

其中α， β為兩階段適應(yīng)度函數(shù)系數(shù)，α∶ β表示在內(nèi)存云集群中所有服務(wù)器正常運行與任意服務(wù)器宕機(jī)次數(shù)之比。兩階段適應(yīng)度函數(shù)之和能夠客觀評價某RBC在不同時期的綜合情況，適應(yīng)度越高的RBC越接近理想狀態(tài)。

3.3協(xié)調(diào)器選擇策略

選擇算子以RBC集合內(nèi)每臺服務(wù)器的適應(yīng)度評估值為基礎(chǔ)，按一定規(guī)律選擇一臺理想的協(xié)調(diào)器。內(nèi)存云網(wǎng)絡(luò)結(jié)構(gòu)中RBC可夠部署在核心層任意位置，若依照比例選擇采用輪盤賭的方式存在很高的不穩(wěn)定性；若僅取計算后值最高的RBC則喪失了隨機(jī)性，同樣理想的RBC可能因為特殊問題不能入選。

目前關(guān)于算子理論的發(fā)展已經(jīng)非常成熟，針對以上的特殊情況，結(jié)合擇優(yōu)與隨機(jī)特性提出一種適于內(nèi)存云環(huán)境下選擇RBC的算子方法。該方法能夠遴選出理想RBC作為新的集合，將輪盤賭的隨機(jī)選擇縮小在質(zhì)量很高的RBC集合中。

算法說明：設(shè)在RBC集合內(nèi)含N臺備選協(xié)調(diào)器，通過期望生存值（Expected Value， EV）與輪盤策略選擇最終的協(xié)調(diào)器C。

4實驗與分析

4.1實驗設(shè)計與環(huán)境

4.1.1實驗設(shè)計

實驗首先通過協(xié)調(diào)器模型與選擇策略模擬推舉出最終協(xié)調(diào)器，再根據(jù)不同協(xié)調(diào)器下消息傳遞時延、數(shù)據(jù)恢復(fù)時間選擇RBC內(nèi)實際最優(yōu)者，通過比對CES與實驗結(jié)果的一致性判斷選擇策略的優(yōu)劣。

實驗首先在NSG2包內(nèi)創(chuàng)建45個節(jié)點，其中包括C0至C4共5個協(xié)調(diào)器模擬節(jié)點，為模仿內(nèi)存云網(wǎng)絡(luò)，將環(huán)形、星形、總線三類構(gòu)成混合狀拓?fù)浣Y(jié)構(gòu)，仿真拓?fù)浜喕鐖D4所示。

配置節(jié)點與鏈路參數(shù)并生成tcl腳本文件，將文件運行在Fedora系統(tǒng)環(huán)境下的NS2.35版本平臺上，編寫協(xié)調(diào)器屬性值算法；其中連通性的精簡偽碼如下：

最后執(zhí)行仿真實驗，仿真時間60s，并對生成的trace文件進(jìn)行分析。根據(jù)第3章所討論的協(xié)調(diào)器選擇策略，對實驗中RBC內(nèi)5臺協(xié)調(diào)器計算適應(yīng)度函數(shù)frun與frecovery（忽略剩余內(nèi)存空間大小），按9∶1控制正常運行與恢復(fù)頻率，計算得到總適應(yīng)度函數(shù)F后，按選擇策略算法1執(zhí)行。根據(jù)適應(yīng)度大小和對穩(wěn)定性的控制，可對期望生存值的扣除因子作適當(dāng)調(diào)整。

協(xié)調(diào)器需要時刻獲取主服務(wù)器傳遞的數(shù)據(jù)，并向RBC傳遞備份數(shù)據(jù)。同樣大小的數(shù)據(jù)在網(wǎng)絡(luò)中傳輸，依靠網(wǎng)絡(luò)的結(jié)構(gòu)差異與路由機(jī)制的不同，延遲高低實際上是存在區(qū)別的。圖5中5個協(xié)調(diào)器的數(shù)據(jù)傳輸延遲基本上隨著數(shù)據(jù)量的增加而升高，可以觀察到，C3于RBC中基本處于最小延遲狀態(tài)。實際上NS2在模擬中存在一些非客觀因素，數(shù)據(jù)延遲的大小更依賴節(jié)點傳輸?shù)穆窂介L度，在這種情況下，C3延遲依然較低，這是由于其處于網(wǎng)絡(luò)拓?fù)渲行沫h(huán)狀處，且與節(jié)點密集區(qū)距離較近，因此延遲低于其他RBC。相應(yīng)的如C1或C4在傳輸相同數(shù)據(jù)情況下延遲較大，這是由于傳輸經(jīng)過節(jié)點多。若在內(nèi)存云真實環(huán)境下，可能會在接收、傳遞、轉(zhuǎn)發(fā)消息過程中出現(xiàn)請求高、任務(wù)排隊等情況。

4.2.2數(shù)據(jù)恢復(fù)時間分析

數(shù)據(jù)恢復(fù)時間是衡量當(dāng)前協(xié)調(diào)器性能的重要參數(shù)，然而在仿真環(huán)境下，NS2難以測試內(nèi)存云的恢復(fù)時間。本節(jié)實驗通過搭建內(nèi)存云模擬環(huán)境，建立15個節(jié)點，其中包括10臺服務(wù)器，以及構(gòu)成RBC的5臺協(xié)調(diào)器；每臺主服務(wù)器內(nèi)存16GB，硬盤100GB，內(nèi)存云版本為1.0。

當(dāng)前數(shù)據(jù)中心處理單點故障問題的主流方法為ZooKeeper和chubby。為檢驗CES效果，選擇ZooKeeper作為實驗對照。ZooKeeper是開源Hadoop中的一個子項目，能夠下載并安裝使用[21]。內(nèi)存云數(shù)據(jù)備份在備份服務(wù)器中，當(dāng)某臺服務(wù)器宕機(jī)后，備份服務(wù)器需要將存儲的數(shù)據(jù)表單提交至協(xié)調(diào)器，并將恢復(fù)數(shù)據(jù)傳遞至新的替代服務(wù)器內(nèi)，實驗通過執(zhí)行CES，選擇出最佳協(xié)調(diào)器C1，通過恢復(fù)時間比對執(zhí)行ZooKeeper后的最佳協(xié)調(diào)器C2。

圖6展示了CES與ZooKeeper選擇結(jié)果對數(shù)據(jù)恢復(fù)時間的影響。C1與C2在恢復(fù)過程中影響差異基本維持在200～300ms，在最初恢復(fù)數(shù)據(jù)小的情況下，不同協(xié)調(diào)器對恢復(fù)時間影響可以忽略不計；當(dāng)恢復(fù)數(shù)據(jù)增加時，差異變得明顯且穩(wěn)定。雖然單個主服務(wù)器容量不大，但從圖6的趨勢能夠判斷，若需恢復(fù)100GB的情況下，不同協(xié)調(diào)器對恢復(fù)時間還是有影響的。

造成差異的原因是由于CES選擇的協(xié)調(diào)器能夠更快獲取備份服務(wù)器主鍵，或者能夠更快查詢到需要數(shù)據(jù)的物理位置等信息。ZooKeeper在內(nèi)存云的處理情況是將失效節(jié)點配置信息隨機(jī)傳遞給相鄰協(xié)調(diào)器，并未將該協(xié)調(diào)器個體指標(biāo)與周圍網(wǎng)絡(luò)納入考慮范圍，因此最終選擇結(jié)果不及CES客觀。

5結(jié)語

目前的一些大型數(shù)據(jù)中心如Yahoo！等在面對單點失效問題時均采用ZooKeeper機(jī)制[22]，相似的數(shù)據(jù)中心之間，類似方法策略也具有一定的移植性。由于內(nèi)存云的存儲介質(zhì)與大部分?jǐn)?shù)據(jù)中心具有本質(zhì)差異，相關(guān)方法難以結(jié)合吞吐大、時延小等特性，因此考慮結(jié)合內(nèi)存云特殊架構(gòu)下的單點恢復(fù)策略也就顯得更加緊迫。

通過面向協(xié)調(diào)器建模并分析模型，建立雙時期適應(yīng)度函數(shù)并合并，計算函數(shù)并求解算子等一系列的執(zhí)行過程，不僅能夠在RBC集合中選舉出優(yōu)秀理想的協(xié)調(diào)器作為內(nèi)存云網(wǎng)絡(luò)中任務(wù)調(diào)度資源分配的承擔(dān)者，同樣能對選舉參與者狀態(tài)作出有效評估，對各服務(wù)器網(wǎng)絡(luò)最佳位置提供有效參考。當(dāng)然，選舉策略同樣存在一定的缺陷，表現(xiàn)如下：1）將來的完善中，可以把網(wǎng)絡(luò)安全、綠色計算等因素納入建模研究范疇。協(xié)調(diào)器作為服務(wù)中心首先不應(yīng)存在被黑客攻擊的安全隱患，另外在研究消息傳遞路徑時也應(yīng)考慮能耗因素。1）選舉策略下的框架結(jié)構(gòu)并未將網(wǎng)絡(luò)安全、綠色計算等因素納入建模研究范疇。協(xié)調(diào)器作為服務(wù)中心首先不應(yīng)存在被黑客攻擊的安全隱患，另外在研究消息傳遞路徑時也應(yīng)考慮能耗因素。2）若在最初部署時協(xié)調(diào)器網(wǎng)絡(luò)位置分布過于密集，差異較低，則CES效果并不顯著，更適宜直接采用隨機(jī)輪盤的形式。

下一步將針對優(yōu)化內(nèi)存云快速恢復(fù)網(wǎng)絡(luò)拓?fù)溥M(jìn)行探索與改進(jìn)，結(jié)合圖論、網(wǎng)絡(luò)群體演化等相關(guān)技術(shù)，對內(nèi)存云主服務(wù)器數(shù)據(jù)段的備份位置展開分析。在恢復(fù)中，數(shù)據(jù)的備份位置會影響到恢復(fù)時間、效率等關(guān)鍵指標(biāo)，因此擬劃分適當(dāng)?shù)挠虿⒃谟蛑薪h(huán)狀網(wǎng)絡(luò)結(jié)構(gòu)，使恢復(fù)性能獲得新的優(yōu)化。至于域內(nèi)服務(wù)器的建模與部署，則是下一步重點考慮的問題。

參考文獻(xiàn)：

[1]

秦秀磊，張文博，魏峻，等.云計算環(huán)境下分布式緩存技術(shù)的現(xiàn)狀與挑戰(zhàn)[J].軟件學(xué)報，2013，24（1）：50-66.（QIN X L， ZHANG W B， WEI J， et al. Progress and challenges of distributed caching techniques in cloud computing[J]. Journal of Software， 2013， 24（1）： 50-66.）

[2]

肖儂.數(shù)據(jù)密集型計算[C]// 中國計算機(jī)學(xué)會通訊，北京：中國計算機(jī)學(xué)會，2011，7（7）：6-7.（XIAO N. Dataintensive computing[C]// CCF 2011： Communications of the CCF， Beijing： CCF， 2011，7（7）：6-7.）

肖儂.數(shù)據(jù)密集型計算[J].中國計算機(jī)學(xué)會通訊，2011，7（7）：6-7.（XIAO N. Dataintensive computing[J]. Communications of the CCF， 2011，7（7）：6-7.）

[3]

OUSTERHOUT J， AGRAWAL P， ERICKSON D， et al. The case for RAMClouds： scalable highperformance storage entirely in DRAM [J]. ACM SIGOPS Operating Systems Review， 2010， 43（4）： 92-105.

[4]

RUMBLE S M， KEJRIWAL A， OUSTERHOUT J. Logstructured memory for DRAMbased storage [C] // Proceedings of the 12th USENIX Conference on File and Storage Technologies. Berkeley， CA： USENIX Association， 2014： 1-16.

[5]

OUSTERHOUT J， GOPALAN A， GUPTA A， et al. The RAMCloud storage system [J]. ACM Transactions on Computer Systems， 2015， 33（3）： Articl No. 7.1-55

[6]

STUTSMAN R， LEE C， OUSTERHOUT J. Experience with rulesbased programming for distributed， concurrent， faulttolerant code [C]// Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conference. Berkeley， CA： USENIX Association， 2015： 17-30.

[7]

TINNEFELD C， KOSSMANN D， GRUND M， et al. Elastic online analytical processing on RAMCloud [C]// Proceedings of the 16th International Conference on Extending Database Technology. New York： ACM， 2013： 454-464.

[8]

TINNEFELD C， KOSSMANN D， BOESE J H， et al. Parallel join executions in RAMCloud [C]// Proceedings of the 2014 IEEE 30th International Conference on Data Engineering Workshops. Washington， DC： IEEE Computer Society， 2014： 182-190.

[9]

魯亮，于炯，英昌甜，等.內(nèi)存云架構(gòu)的磁盤節(jié)能策略[J].計算機(jī)應(yīng)用，2014，34（9）：2518-2522.（LU L，YU J，YING C T， et al. Energyefficient strategy for disks in RAMCloud[J]. Journal of Computer Applications， 2014， 34（9）： 2518-2522.）

[10]

英昌甜，于炯，魯亮，等.基于小文件的內(nèi)存云存儲優(yōu)化策略[J].計算機(jī)應(yīng)用，2014，34（11）：3104-3108.（YING C T， YU J， LU L， et al. An optimization storing strategy based on small files in RAMCloud [J]. Journal of Computer Applications， 2014， 34（11）： 3104-3108.）

[11]

RIVETTI N， CORSARO A. State based Paxos[C]// Middleware Industry 13： Proceedings of the Industrial Track of the 13th ACM/IFIP/USENIX International Middleware Conference. New York： ACM， 2013： Article No. 4.

[12]

JUNQUEIRA F P， REED B C， SERAFINI M. Zab： highperformance broadcast for primarybackup systems [C]// DSN 11： Proceedings of the 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks. Washington， DC： IEEE Computer Society， 2011： 245-256.

[13]

RUMBLE S M， ONGARO D， STUTSMAN R， et al. Its time for low latency [C]// Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems. Berkeley， CA： USENIX Association， 2011： 11-16.

[14]

HUNT P， KONAR M， JUNQUEIRA F P， et al. ZooKeeper： waitfree coordination for Internetscale systems [C]// Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2010：11.

[15]

ONGARO D， RUMBLE S M， STUTSMAN R， et al. Fast crash recovery in RAMCloud [C]// SOSP 11： Proceedings of the 23rd ACM Symposium on Operating Systems Principles. New York： ACM， 2011： 29-41.

[16]

BORTHAKUR D. The hadoop distributed file system： architecture and design[EB/OL]. （20070701） [20151005]. http：//hadoop.apache.org/common/docs/r0.18.2/hdfs_design.pdf.

BORTHAKUR D. The hadoop distributed file system： architecture and design[EB/OL]. （20070701） [20151005]. http：//web.mit.edu/～mriap/hadoop/hadoop0.13.1/docs/hdfs_design.pdf.

[17]

RUMBLE S. Memory and object management in RAMCloud [D]. Stanford： Stanford University， 2014： 5-22.

[18]

STUTSMAN R. Durability and crash recovery in distributed inmemory storage systems [D]. Stanford： Stanford University， 2013.

OUSTERHOUT A J. Undergraduate durability and crash recovery in a distributed inmemory storage system [D]. Stanford： Stanford University， 2013： 17-47.

[19]

FREEMAN L C. Centrality in social networks conceptual clarification [J]. Social Networks， 1979， 1（3）： 215-239.2012年

[20]

王元卓，于建業(yè)，邱雯，等.網(wǎng)絡(luò)群體行為的演化博弈模型與分析方法[J].計算機(jī)學(xué)報，2015，38（2）：282-300.（WANG Y Z， YU J Y， QIU W， et al. Evolutionary game model and analysis methods for network group behavior [J]. Chinese Journal of Computers， 2015， 38（2）： 282-300.）

[21]

The Apache Software Foundation. ZooKeeper： because coordinating distributed systems is a zoo [EB/OL].[20151112]. https：//zookeeper.apache.org/doc/r3.5.1alpha/index.pdf.

[22]

JUNQUEIRA F P， REED B C. The life and times of a ZooKeeper [C]// PODC 09： Proceedings of the 28th ACM Symposium on Principles of Distributed Computing. New York： ACM， 2009： 4.