支持容错QoS的高效分布式文件存储算法

辛 刚 罗香玉

（1．中航工业西安航空计算技术研究所,陕西 西安 710119；

2．西安科技大学计算机学院,陕西 西安 710054；

3．西安交通大学电信学院,陕西 西安 710049）

支持容错QoS的高效分布式文件存储算法

辛 刚1罗香玉2,3

（1．中航工业西安航空计算技术研究所,陕西 西安 710119；

2．西安科技大学计算机学院,陕西 西安 710054；

3．西安交通大学电信学院,陕西 西安 710049）

针对现有存储算法无法兼顾文件定制化可靠性保证和系统良好可扩展性这一问题，提出一种全分布式的支持容错QoS(Quality of Service)的文件存储算法。算法允许文件被存储副本数量与其可靠性需求相匹配，无单一故障点与瓶颈点。此外，实验结果表明算法可保持节点间负载均衡，实现系统资源的高效利用。

分布式存储；容错QoS；副本放置；负载均衡；可扩展性；可靠性

1．引言

随着云计算的兴起，分布式文件存储迈入云存储时代。云存储向用户提供可定制化和按需付费的服务，用户可根据自身实际需求购买对应服务质量（QoS）的存储服务。QoS是目前云存储领域的热点问题[1]。

现有分布式文件存储算法（如Kinesis[2]和CDRM[3]）侧重系统整体的性能指标，较少关注不同用户的定制化需求。虽有研究工作（如文献[4]和[5]）讨论分布式文件存储QoS满足问题，但主要针对请求响应延迟和访问带宽的定制化满足，忽略了不同文件在可靠性需求方面的差异。此外，即使一些系统（如GFS[6]和HDFS[7]）允许文件存储时设定不同的可靠性指标，但依赖中央服务节点记录各文件（包括副本）的存储位置，存在单一故障点和性能瓶颈。

本文研究新的分布式文件存储算法，以满足用户在可靠性方面的定制化需求，同时保证系统的良好可扩展性和整体资源利用的高效性。主要贡献如下：(1)提出容错QoS的概念表示用户对文件存储可靠性的定制化需求；(2)提出支持容错QoS的分布式文件存储算法FTQoS_Oriented；(3)通过实验验证了算法的可扩展性和负载均衡特性。

2．系统模型

2．1 容错QoS

容错QoS可以通过两层模型表示：用户容错QoS层和系统容错QoS层。其中，用户容错QoS层采用用户直接可理解的可靠性指标，比如文件的丢失概率和可访问概率等；系统容错QoS层采用容错策略参数指标，比如副本策略下的副本数量、纠删码[8]策略下的编码参数等。

用户容错QoS直接反映用户的可靠性需求，与系统的具体实现无关。系统容错QoS取决于如下三个方面：用户容错QoS、系统容错方式（比如副本策略或纠删码策略）和存储节点自身的可靠性指标。当系统容错方式和存储节点属性确定时，系统容错QoS可由用户容错QoS唯一确定。

本文的用户容错QoS层选择文件可访问概率指标，容错方式选择副本策略，因此系统容错QoS层采用副本数量这一指标。

2．2 分布式存储模型

本文侧重分布式文件存储系统中用户可靠性需求的满足问题，忽略访问特征的讨论，所建立分布式存储模型如下：

资源模型：分布式存储系统M由n个节点构成，即M= {N1，…，Nn}；节点Ni用二元组〈ci，pi＞表征（i=1，…，n），其中，ci和pi分别表示节点Ni的存储容量和可靠度。

需求模型：待存储文件集合F包含m个文件，即F= {f1，…，fm}；文件fj用二元组〈sj，qj＞表征（j=1，…，m），其中，sj和qj分别表示文件fj的大小和容错QoS需求（这里的qj是用户容错QoS，表示文件fj的可访问概率）。

从“名师”到“明师”，教师不仅要探究教与学背后的理据，提炼自己的教学思想，其生成的个人理论更要通过名师的育人表现出来，将教学思想内化为教育理想情怀，实现对每一个学生的生命关怀与精神引领，这是“名师”成为“明师”的最高境界。教学风格或教学思想本质上讲的是名师在日常教学的经历、探究、感悟中形成的对教与学的一种观点、一种见解、一种思想，这种教学观如果不内化为对教育生命的关爱，只能是没有生命力的教学思想。名师不仅要有丰富的知识、技能、实践智慧与思想，更要用人格魅力与教育情怀感染学生。教学是教师的专业道德实践，这种内在的精神力量是名师独特的专业性所在。

存储方案模型：在副本方式的容错策略下，存储方案可通过矩阵Dn×m表示。该矩阵的元素dij只有0和1两种取值。若dij=0，则表示节点Ni不存有文件fj的副本；否则，表示节点Ni存有文件fj的副本。

令rj表示文件fj的副本数量，则

rj由文件fj的容错QoS需求qj以及节点的可靠度指标pi确定。

此外，在为文件各副本确定具体存储节点时，需要满足节点的存储容量约束，令Si表示节点Ni所存储数据的总量，则：

最后，在满足各文件容错QoS需求及各节点容量约束的同时，各节点存储空间的占用量应大致均衡，即方差S2尽可能小，其中：

3． 存储方案

3．1 方案框架

本文所提出方案包括两部分：容错QoS映射模块和FTQoS_Oriented算法模块。

容错QoS映射模块完成由用户容错QoS到系统容错QoS的映射（由于本文采用副本容错方式，系统容错QoS由副本数量表示）。假设存储节点同构，由此各节点的可靠度指标pi相同，用p表示；同时，假设用户容错QoS以文件可访问概率Pj表示。因此，系统容错QoS即副本数量rj可通过如下公式获得：

rj是满足式(2)的最小整数。

FTQoS_Oriented算法模块假设已通过式(2)获知各文件的副本数量rj，主要负责为各文件选定副本位置，使得各节点空间占用量尽可能均衡。该模块是存储方案的核心。

3．2 FTQoS_Oriented算法

FTQoS_Oriented算法借鉴了Kinesis算法通过多个独立哈希函数实现分布式多副本存储的思想。所不同的是，Kinesis算法为各文件存储相同数量的副本，不考虑文件在可靠性需求方面的差异；FTQoS_Oriented算法允许文件存储与其可靠性需求相匹配数量的副本。

FTQoS_Oriented算法将存储节点划分为若干不相交且规模大致相同的子集合，其中，所划分的子集合数量g不小于副本数量最多节点的副本数，即

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

FTQoS_Oriented算法为各节点子集合指定一个哈希函数，并且g个哈希函数相互独立。假设各文件具有全局唯一的标识。在存储文件fj时，根据该文件的标识可确定各个哈希函数下的哈希值，并由哈希值确定节点编号。该方式可产生g个节点编号，并且g个节点分别位于不同的节点子集合中。FTQoS_Oriented算法在g个候选的存储节点中，选取当前最空闲的前rj个节点存储文件fj的副本。

算法输入：{〈sj，qj＞|j=1，…，m}（m个文件的描述信息）；{〈ci，pi＞|i=1，…，n}（n个节点的描述信息）；{rj|j=1，…，m}（各文件所存储副本的数量，已通过式(2)求出）

算法输出：矩阵Dn×m（副本放置结果）

其它符号说明：Si表示节点Ni的存储空间占用量；Hk表示第k个哈希函数（k=1，…，g）；Candidate(k)表示第k个候选节点；IDj表示文件fj的唯一标识。

算法流程：

/*find_top_Candidates函数从k个候选节点中选出Si值最小的rj个，分别记为Nj(u)（其中u=1，…，rj）*/

4．实验设计及结果

本文通过C++编程实现FTQoS_Oriented算法，并通过实现一个网路排队系统对存储系统各个节点存储文件的状况进行仿真。

4．1 负载均衡性实验

节点数量为100（分为10个组，每组各含10个节点），文件数量为1000，每个文件大小为1MB，文件副本数量服从1到10之间的等概率分布。实验结果如图1所示。图中横轴代表节点序号i，纵轴代表存储完毕后各节点所存储数据量Si。可见，各节点所存储数据量大致均衡，均在55MB左右。

图1 各节点所存储数据量的比较

4．2 可扩展性实验

节点数量由100变化至1000，文件数量由1000变化至10000，各文件所存储副本数量服从1到10之间的等概率分布。实验结果如图2所示。横轴表示节点数量n，纵轴表示文件存储完毕后各节点所存储数据量的标准差S（即方差S2的平方根，S2的计算见式(1)）。可见，随着节点总数和文件总数的增长，标准差S变化很小，表明本文所提出算法具有良好的可扩展性。

图2 节点数量n和标准差S的关系

5．结语

云计算向用户提供了按需付费使用模式，用户可享受定制化服务。本文针对用户对文件存储可靠性的定制化需求，提出了支持容错QoS的高效分布式文件存储算法FTQoS_Oriented。该算法允许为不同文件存储不同数量的副本，以满足各自不同的可靠性需求。实验结果表明，该算法还具有良好的负载均衡性和可扩展性，可适用于大规模分布式存储系统。

[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．apache．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

辛刚，男，陕西扶风人，硕士，工程师。研究方向：分布式存储、系统可靠性设计。

陕西省自然科学基础研究计划资助项目，项目编号：2012JQ8030；高等学校博士学科点专项科研基金，项目编号：20120201110013。