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

辛 剛 羅香玉

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

2．西安科技大學計算機學院,陜西 西安 710054；

3．西安交通大學電信學院,陜西 西安 710049）

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

辛 剛1羅香玉2,3

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

2．西安科技大學計算機學院,陜西 西安 710054；

3．西安交通大學電信學院,陜西 西安 710049）

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

分布式存儲；容錯QoS；副本放置；負載均衡；可擴展性；可靠性

1．引言

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

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

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

2．系統(tǒng)模型

2．1 容錯QoS

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

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

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

2．2 分布式存儲模型

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

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

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

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

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

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

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

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

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

3． 存儲方案

3．1 方案框架

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

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

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

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

3．2 FTQoS_Oriented算法

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

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

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

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

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

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

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

算法流程：

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

4．實驗設計及結果

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

4．1 負載均衡性實驗

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

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

4．2 可擴展性實驗

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

圖2 節(jié)點數(shù)量n和標準差S的關系

5．結語

云計算向用戶提供了按需付費使用模式，用戶可享受定制化服務。本文針對用戶對文件存儲可靠性的定制化需求，提出了支持容錯QoS的高效分布式文件存儲算法FTQoS_Oriented。該算法允許為不同文件存儲不同數(shù)量的副本，以滿足各自不同的可靠性需求。實驗結果表明，該算法還具有良好的負載均衡性和可擴展性，可適用于大規(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

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

陜西省自然科學基礎研究計劃資助項目，項目編號：2012JQ8030；高等學校博士學科點專項科研基金，項目編號：20120201110013。