支持容錯QoS的高效分布式文件存儲算法

辛 剛 羅香玉

（1．中航工業(yè)西安航空計算技術(shù)研究所,陜西 西安 710119；

2．西安科技大學(xué)計算機(jī)學(xué)院,陜西 西安 710054；

3．西安交通大學(xué)電信學(xué)院,陜西 西安 710049）

支持容錯QoS的高效分布式文件存儲算法

辛 剛1羅香玉2,3

（1．中航工業(yè)西安航空計算技術(shù)研究所,陜西 西安 710119；

2．西安科技大學(xué)計算機(jī)學(xué)院,陜西 西安 710054；

3．西安交通大學(xué)電信學(xué)院,陜西 西安 710049）

針對現(xiàn)有存儲算法無法兼顧文件定制化可靠性保證和系統(tǒng)良好可擴(kuò)展性這一問題，提出一種全分布式的支持容錯QoS(Quality of Service)的文件存儲算法。算法允許文件被存儲副本數(shù)量與其可靠性需求相匹配，無單一故障點(diǎn)與瓶頸點(diǎn)。此外，實(shí)驗結(jié)果表明算法可保持節(jié)點(diǎn)間負(fù)載均衡，實(shí)現(xiàn)系統(tǒng)資源的高效利用。

分布式存儲；容錯QoS；副本放置；負(fù)載均衡；可擴(kuò)展性；可靠性

1．引言

隨著云計算的興起，分布式文件存儲邁入云存儲時代。云存儲向用戶提供可定制化和按需付費(fèi)的服務(wù)，用戶可根據(jù)自身實(shí)際需求購買對應(yīng)服務(wù)質(zhì)量（QoS）的存儲服務(wù)。QoS是目前云存儲領(lǐng)域的熱點(diǎn)問題[1]。

現(xiàn)有分布式文件存儲算法（如Kinesis[2]和CDRM[3]）側(cè)重系統(tǒng)整體的性能指標(biāo)，較少關(guān)注不同用戶的定制化需求。雖有研究工作（如文獻(xiàn)[4]和[5]）討論分布式文件存儲QoS滿足問題，但主要針對請求響應(yīng)延遲和訪問帶寬的定制化滿足，忽略了不同文件在可靠性需求方面的差異。此外，即使一些系統(tǒng)（如GFS[6]和HDFS[7]）允許文件存儲時設(shè)定不同的可靠性指標(biāo)，但依賴中央服務(wù)節(jié)點(diǎn)記錄各文件（包括副本）的存儲位置，存在單一故障點(diǎn)和性能瓶頸。

本文研究新的分布式文件存儲算法，以滿足用戶在可靠性方面的定制化需求，同時保證系統(tǒng)的良好可擴(kuò)展性和整體資源利用的高效性。主要貢獻(xiàn)如下：(1)提出容錯QoS的概念表示用戶對文件存儲可靠性的定制化需求；(2)提出支持容錯QoS的分布式文件存儲算法FTQoS_Oriented；(3)通過實(shí)驗驗證了算法的可擴(kuò)展性和負(fù)載均衡特性。

2．系統(tǒng)模型

2．1 容錯QoS

容錯QoS可以通過兩層模型表示：用戶容錯QoS層和系統(tǒng)容錯QoS層。其中，用戶容錯QoS層采用用戶直接可理解的可靠性指標(biāo)，比如文件的丟失概率和可訪問概率等；系統(tǒng)容錯QoS層采用容錯策略參數(shù)指標(biāo)，比如副本策略下的副本數(shù)量、糾刪碼[8]策略下的編碼參數(shù)等。

用戶容錯QoS直接反映用戶的可靠性需求，與系統(tǒng)的具體實(shí)現(xiàn)無關(guān)。系統(tǒng)容錯QoS取決于如下三個方面：用戶容錯QoS、系統(tǒng)容錯方式（比如副本策略或糾刪碼策略）和存儲節(jié)點(diǎn)自身的可靠性指標(biāo)。當(dāng)系統(tǒng)容錯方式和存儲節(jié)點(diǎn)屬性確定時，系統(tǒng)容錯QoS可由用戶容錯QoS唯一確定。

本文的用戶容錯QoS層選擇文件可訪問概率指標(biāo)，容錯方式選擇副本策略，因此系統(tǒng)容錯QoS層采用副本數(shù)量這一指標(biāo)。

2．2 分布式存儲模型

本文側(cè)重分布式文件存儲系統(tǒng)中用戶可靠性需求的滿足問題，忽略訪問特征的討論，所建立分布式存儲模型如下：

資源模型：分布式存儲系統(tǒng)M由n個節(jié)點(diǎn)構(gòu)成，即M= {N1，…，Nn}；節(jié)點(diǎn)Ni用二元組〈ci，pi＞表征（i=1，…，n），其中，ci和pi分別表示節(jié)點(diǎn)Ni的存儲容量和可靠度。

需求模型：待存儲文件集合F包含m個文件，即F= {f1，…，fm}；文件fj用二元組〈sj，qj＞表征（j=1，…，m），其中，sj和qj分別表示文件fj的大小和容錯QoS需求（這里的qj是用戶容錯QoS，表示文件fj的可訪問概率）。

從“名師”到“明師”，教師不僅要探究教與學(xué)背后的理據(jù)，提煉自己的教學(xué)思想，其生成的個人理論更要通過名師的育人表現(xiàn)出來，將教學(xué)思想內(nèi)化為教育理想情懷，實(shí)現(xiàn)對每一個學(xué)生的生命關(guān)懷與精神引領(lǐng)，這是“名師”成為“明師”的最高境界。教學(xué)風(fēng)格或教學(xué)思想本質(zhì)上講的是名師在日常教學(xué)的經(jīng)歷、探究、感悟中形成的對教與學(xué)的一種觀點(diǎn)、一種見解、一種思想，這種教學(xué)觀如果不內(nèi)化為對教育生命的關(guān)愛，只能是沒有生命力的教學(xué)思想。名師不僅要有豐富的知識、技能、實(shí)踐智慧與思想，更要用人格魅力與教育情懷感染學(xué)生。教學(xué)是教師的專業(yè)道德實(shí)踐，這種內(nèi)在的精神力量是名師獨(dú)特的專業(yè)性所在。

存儲方案模型：在副本方式的容錯策略下，存儲方案可通過矩陣Dn×m表示。該矩陣的元素dij只有0和1兩種取值。若dij=0，則表示節(jié)點(diǎn)Ni不存有文件fj的副本；否則，表示節(jié)點(diǎn)Ni存有文件fj的副本。

令rj表示文件fj的副本數(shù)量，則

rj由文件fj的容錯QoS需求qj以及節(jié)點(diǎn)的可靠度指標(biāo)pi確定。

此外，在為文件各副本確定具體存儲節(jié)點(diǎn)時，需要滿足節(jié)點(diǎn)的存儲容量約束，令Si表示節(jié)點(diǎn)Ni所存儲數(shù)據(jù)的總量，則：

最后，在滿足各文件容錯QoS需求及各節(jié)點(diǎn)容量約束的同時，各節(jié)點(diǎn)存儲空間的占用量應(yīng)大致均衡，即方差S2盡可能小，其中：

3． 存儲方案

3．1 方案框架

本文所提出方案包括兩部分：容錯QoS映射模塊和FTQoS_Oriented算法模塊。

容錯QoS映射模塊完成由用戶容錯QoS到系統(tǒng)容錯QoS的映射（由于本文采用副本容錯方式，系統(tǒng)容錯QoS由副本數(shù)量表示）。假設(shè)存儲節(jié)點(diǎn)同構(gòu)，由此各節(jié)點(diǎn)的可靠度指標(biāo)pi相同，用p表示；同時，假設(shè)用戶容錯QoS以文件可訪問概率Pj表示。因此，系統(tǒng)容錯QoS即副本數(shù)量rj可通過如下公式獲得：

rj是滿足式(2)的最小整數(shù)。

FTQoS_Oriented算法模塊假設(shè)已通過式(2)獲知各文件的副本數(shù)量rj，主要負(fù)責(zé)為各文件選定副本位置，使得各節(jié)點(diǎn)空間占用量盡可能均衡。該模塊是存儲方案的核心。

3．2 FTQoS_Oriented算法

FTQoS_Oriented算法借鑒了Kinesis算法通過多個獨(dú)立哈希函數(shù)實(shí)現(xiàn)分布式多副本存儲的思想。所不同的是，Kinesis算法為各文件存儲相同數(shù)量的副本，不考慮文件在可靠性需求方面的差異；FTQoS_Oriented算法允許文件存儲與其可靠性需求相匹配數(shù)量的副本。

FTQoS_Oriented算法將存儲節(jié)點(diǎn)劃分為若干不相交且規(guī)模大致相同的子集合，其中，所劃分的子集合數(shù)量g不小于副本數(shù)量最多節(jié)點(diǎn)的副本數(shù)，即

式(3)中rj的求解見式(2)。

FTQoS_Oriented算法為各節(jié)點(diǎn)子集合指定一個哈希函數(shù)，并且g個哈希函數(shù)相互獨(dú)立。假設(shè)各文件具有全局唯一的標(biāo)識。在存儲文件fj時，根據(jù)該文件的標(biāo)識可確定各個哈希函數(shù)下的哈希值，并由哈希值確定節(jié)點(diǎn)編號。該方式可產(chǎn)生g個節(jié)點(diǎn)編號，并且g個節(jié)點(diǎn)分別位于不同的節(jié)點(diǎn)子集合中。FTQoS_Oriented算法在g個候選的存儲節(jié)點(diǎn)中，選取當(dāng)前最空閑的前rj個節(jié)點(diǎn)存儲文件fj的副本。

算法輸入：{〈sj，qj＞|j=1，…，m}（m個文件的描述信息）；{〈ci，pi＞|i=1，…，n}（n個節(jié)點(diǎn)的描述信息）；{rj|j=1，…，m}（各文件所存儲副本的數(shù)量，已通過式(2)求出）

算法輸出：矩陣Dn×m（副本放置結(jié)果）

其它符號說明：Si表示節(jié)點(diǎn)Ni的存儲空間占用量；Hk表示第k個哈希函數(shù)（k=1，…，g）；Candidate(k)表示第k個候選節(jié)點(diǎn)；IDj表示文件fj的唯一標(biāo)識。

算法流程：

/*find_top_Candidates函數(shù)從k個候選節(jié)點(diǎn)中選出Si值最小的rj個，分別記為Nj(u)（其中u=1，…，rj）*/

4．實(shí)驗設(shè)計及結(jié)果

本文通過C++編程實(shí)現(xiàn)FTQoS_Oriented算法，并通過實(shí)現(xiàn)一個網(wǎng)路排隊系統(tǒng)對存儲系統(tǒng)各個節(jié)點(diǎn)存儲文件的狀況進(jìn)行仿真。

4．1 負(fù)載均衡性實(shí)驗

節(jié)點(diǎn)數(shù)量為100（分為10個組，每組各含10個節(jié)點(diǎn)），文件數(shù)量為1000，每個文件大小為1MB，文件副本數(shù)量服從1到10之間的等概率分布。實(shí)驗結(jié)果如圖1所示。圖中橫軸代表節(jié)點(diǎn)序號i，縱軸代表存儲完畢后各節(jié)點(diǎn)所存儲數(shù)據(jù)量Si。可見，各節(jié)點(diǎn)所存儲數(shù)據(jù)量大致均衡，均在55MB左右。

圖1 各節(jié)點(diǎn)所存儲數(shù)據(jù)量的比較

4．2 可擴(kuò)展性實(shí)驗

節(jié)點(diǎn)數(shù)量由100變化至1000，文件數(shù)量由1000變化至10000，各文件所存儲副本數(shù)量服從1到10之間的等概率分布。實(shí)驗結(jié)果如圖2所示。橫軸表示節(jié)點(diǎn)數(shù)量n，縱軸表示文件存儲完畢后各節(jié)點(diǎn)所存儲數(shù)據(jù)量的標(biāo)準(zhǔn)差S（即方差S2的平方根，S2的計算見式(1)）。可見，隨著節(jié)點(diǎn)總數(shù)和文件總數(shù)的增長，標(biāo)準(zhǔn)差S變化很小，表明本文所提出算法具有良好的可擴(kuò)展性。

圖2 節(jié)點(diǎn)數(shù)量n和標(biāo)準(zhǔn)差S的關(guān)系

5．結(jié)語

云計算向用戶提供了按需付費(fèi)使用模式，用戶可享受定制化服務(wù)。本文針對用戶對文件存儲可靠性的定制化需求，提出了支持容錯QoS的高效分布式文件存儲算法FTQoS_Oriented。該算法允許為不同文件存儲不同數(shù)量的副本，以滿足各自不同的可靠性需求。實(shí)驗結(jié)果表明，該算法還具有良好的負(fù)載均衡性和可擴(kuò)展性，可適用于大規(guī)模分布式存儲系統(tǒng)。

[1]YANG L，XU K，LIU S，LI K．Research on QoS guarantee mod-el and key technologies for cloud storage[J]．Journal of System Simulation，2013，25(11)：2678-2686．

[2]MACCORMICK，J．N．MURPHY，et al．Kinesis：A new approach to replica placement in distributed storage systems[J]．ACM Transactions on Storage，2009，4(4)：11．

[3]WEI，Q，VEERAVALLI B，et al．CDRM：A cost-effective dynamic replication management scheme for cloud storage cluster[C]//Proceedings of IEEE International Conference on Cluster Computing．Crete，IEEE，2010．

[4]GULATI A，MERCHANT A，VARMAN P J．pClock：an arrival curve based approach for QoS guarantees in shared storage systems[J]．ACM SIGMETRICS Performance Evaluation Review，2007，35(1)：13-24.

[5]XU X． The research of Quality of Service and Reliability for Cloud Storage System[D]．Hangzhou：Zhejiang University，2011．

[6]GHEMAWAT S，GOBIOFF H，LEUNG S T．The Google file system[C]//ACM SIGOPS Operating Systems Review．ACM，2003，37 (5)：29-43．

[7]http：//hadoop．a(chǎn)pache．org/docs/current/hadoop-project-dist/hadoop-hdfs/Federation．html

[8]XU G，GUO X，ZHANG H，et al．Optimization for reliable erasure coded storage allocation under multiple constraints[C]//Proceedings of IEEE International Conference and Performance Computing and Communications．San Diego：IEEE，2013：1-2．

Highly-efficient distributed file storage algorithm for supporting QoS of fault tolerance

Xin Gang1Luo Xiangyu2,3
(1.AVIC Xi'anAeronautics Computing Technique Research Institute,Xi'an 710119,Shaanxi; 2.School of Computer Science and Technology,Xi'an University of Science and Technology,Xi'an 710054,Shaanxi; 3.School of Electronic and Information Engineering,Xi'an Jiaotong University,Xi'an 710049,Shaanxi)

Existing file storage algorithms either sacrifice the ability of differentiated reliability guarantee or suffer from poor scalability.This paper proposes a completely decentralized file storage algorithm with QoS of fault tolerance guarantee.Files are allowed to be assigned with replication degrees matching with their reliability requirements.The single point of failure and bottleneck is eliminated.Besides,the experimental results show that the algorithm maintains ideal load balance among different storage nodes and ensures high efficiency in utilizing system resources.

distributed storage;QoS of fault tolerance;replica placement;load balance;scalability;reliability

辛剛，男，陜西扶風(fēng)人，碩士，工程師。研究方向：分布式存儲、系統(tǒng)可靠性設(shè)計。

陜西省自然科學(xué)基礎(chǔ)研究計劃資助項目，項目編號：2012JQ8030；高等學(xué)校博士學(xué)科點(diǎn)專項科研基金，項目編號：20120201110013。