孔晨燕， 赵建民， 朱信忠， 徐慧英

(浙江师范大学数理与信息工程学院，浙江金华 321004)

HDFS平台下基于纠删码的一种数据放置策略*

孔晨燕， 赵建民， 朱信忠， 徐慧英

(浙江师范大学数理与信息工程学院，浙江金华 321004)

数据的可靠性一直是云计算领域中的热点问题，副本备份机制作为保证数据可靠性的重要手段应用比较广泛.但随着副本个数的增加，该机制浪费存储空间这一缺陷暴露无遗.为节省存储空间，采用纠删码技术保证数据的可靠性，提出了在HDFS平台下基于纠删码的一种数据放置策略.该策略以HDFS为平台，结合HDFS的副本备份策略和纠删码技术，通过改进HDFS平台下原本的数据放置策略，使改进后的数据放置策略能够适用于基于纠删码和HDFS的云文件系统.

云计算;HDFS;副本备份;纠删码;数据放置

0 引言

数据的可靠性作为云计算领域中的热点问题一直倍受人们的关注.为保证数据的可靠性，应用比较广泛的手段是副本备份机制，它简单直观，易于实现和部署，但是需为每个数据对象创建若干相同副本，所需存储空间较大.而基于纠删码的容错方式则能够把多个数据块的信息融合到较少的冗余信息中，因而能够节省存储空间.

目前，云计算环境下分布式存储应用中的数据放置策略都比较简单，比如机架无关(rack unware)、机架相关(rack aware)、数据中心相关(datacenter aware)等策略，或者顺序放置、随机放置等策略.这些策略大都针对基于复制的容错技术［1］.本文针对基于纠删码的数据放置策略展开研究，提出了HDFS(Hadoop Distributed File System，Hadoop分布式文件系统)平台下基于纠删码的一种数据放置策略.该策略以HDFS为平台，结合HDFS的副本备份策略和纠删码技术，通过改进HDFS平台下原本的数据放置策略，使改进后的数据放置策略能够适用于基于纠删码和HDFS的云文件系统.

1 纠删码

纠删码提供了一种存储优化的冗余机制来保证数据的可靠性［2］，它可以用一个四元组(n，k，b，k')来描述，其中k为编码前的文件块数，n为编码后的文件块数，b为每块文件所含的比特数，k'是大于或者等于k的正整数.首先将要存储的文件块分为k份相等的数据块，记每份数据块的大小为b比特，则编码前的文件可以表示为F=(F1，F2，…，Fk).设纠删码的编码函数是E，解码函数是D，对原文件进行编码，文件编码后生成n个数据块，编码后的数据块大小仍为b比特.设E(F')是E(F)中任意k'(k'≥k)个文件组成的子文件，那么D(E(F'))=F.由纠删码的性质可知，当系统中部分节点失效，用户依旧可以根据余下可得的文件来恢复原文件.也就是说一定数量的节点失效并不会造成用户数据的丢失.

相关研究表明，纠删码在存储空间上和数据可用性及容错能力上优于完全复制，在容侵能力上与完全复制基本差不多［3］.

2 HDFS的数据放置策略

HDFS采用主从式的结构管理体系，集群中有一个NameNode和多个DataNode，NameNode负责数据放置节点的选择和DataNode的管理，Data－Node负责数据块的存储［4－5］.其默认情况下根据部署在集群上的默认机架感知策略［6］进行数据副本的放置，而数据放置策略是基于完全复制机制的.HDFS系统为每个数据块保存3个副本，客户节点本地机架上放置2个，第3个放置于随机远端机架的随机节点上.如果还需存放更多副本，则在整个集群中随机选取节点存放.当本地节点都失效时，HDFS系统将自动通过远端机架上的数据副本，将数据副本的数量恢复到标准值.

3 HDFS下基于纠删码的数据放置策略

3.1 相对负载

目前的HDFS版本都假设集群中的节点是同构的，而在实际的云存储系统中节点的同构性并不理想，部分节点之间还可能存在较大的性能差异.因此，给各个数据节点平均分配数据量的做法并不符合HDFS集群的特点.本文提出的数据放置策略，引入相对负载作为节点评价标准，根据数据节点的存储性能及已经存储的数据量进行节点的选择.

本文使用节点已经存储的数据量N(i)与节点的存储性能P(i)的比值表示节点的相对负载L(i)，即

其中节点已经存储的数据量N(i)表示存储的数据占用的磁盘空间大小，在HDFS启动时DadaN－ode通过org.apache.hadoop.fs.DF类来实现unix的df命令，以此获得本地磁盘的使用情况.节点存储性能P(i)包括节点CPU性能、内存大小、存储设备的存储速度、系统结构等［7］.为了提高数据放置效率，计算节点的存储性能时，主要考虑CPU性能(记为C)、内存大小(记为M)和存储设备的存储速度(记为V).则集群中某一节点i的存储性能可以表示为

δ1，δ2，δ3是各性能的权重因子(δ1+δ2+δ3=1)，取值为0～1，用户可以根据具体情况下各因素的重要程度设置权重因子.目前有很多CPU和磁盘性能的测试软件，可通过这些软件获得性能参数，从而计算出集群中节点的存储性能.

3.2 基于纠删码的数据放置策略的总体思路

客户机在上传文件时将文件分块，对分块后的文件进行编码，将编码后的文件直接上传到DataNode.在HDFS启动时，集群中的所有节点直接计算出与其他节点之间的距离，DataNode计算出本地磁盘的使用情况及本节点的存储性能，并发送给NameNode.由节点已存储数据占用的磁盘空间大小和其存储性能可以计算出节点的相对负载.DataNode会在内存中保存一个NameNode与相对负载的对照表及系统的平均相对负载，在存储数据块的过程中同步更新这个对照表，以及系统平均相对负载.在上传编码后的文件块时，NameNode选择距离上传节点最近的机架，在机架中找到相对负载最小且放置数据后系统的负载平衡不会被打破的节点作为文件块的放置节点.

本策略通过当前节点的相对负载L(i)与系统中的平均相对负载LA的差值是否大于阈值LR来判断系统的是否平衡.若L(i)－LA＞LR，则认为该节点的负载过重，系统的负载平衡被打破，反之则认为系统的负载仍然平衡.其中平均相对负载是集群中所有节点的相对负载的平均值，记为

其中TN为集群中的节点总数.

另外，根据保存的文件重要性确定HDFS集群的备份参数dfs.replication的值，将相当重要的设置为2，这就实现了每个文件的编码数据块都有2个副本保存在HDFS集群中，应用纠删码和备份双重机制保障数据的可靠性.如果保存的是普通文件，则将值设置为1，直接用纠删码保证数据的可靠性，最大程度节约HDFS集群的存储空间.

3.3 HDFS下基于纠删码的数据放置策略过程

在上传文件时，上传节点首先对文件进行分块，按照一定的比例对分块所得的数据块进行编码，然后将编码后的数据块上传到 HDFS上.HDFS下基于纠删码的数据放置策略的过程如图1所示.由图1可知，数据放置策略的过程可以描述如下:

1)当用户提交数据存储的请求时，计算网络拓扑中与客户端节点网络距离最近的机架，并返回机架ID，记为N.标记为已选择或不平衡的机架不在选择之列.若没有可用机架，则返回NULL.

2)若返回值为NULL，即已没有可用机架，则过程结束，否则继续下一步.

3)判断机架N中文件F的数据块总数是否大于或等于n－k－1，若满足条件则将该机架标记为已选择，在后续的机架选择中不再列入考虑范围.如果不满足条件，就继续下一步.

4)找出机架N中相对负载最低的节点，并返回其ID.若没有节点可选，则返回NULL.

5)若返回值为NULL，即已没有节点可选择，则将机架N标记为不平衡，在后续的机架选择中不再列入考虑范围，返回第一步.否则继续下一步.

6)若加入提交的数据块后系统的平衡被打破，则将此节点标记为不平衡，在后续的节点选择中不再列入考虑范围，返回步骤4.否则此节点即为用户提交数据块的存储节点，记为DW，继续下一步.

7)将用户提交的数据块写入节点DW.

8)将HDFS集群的备份参数dfs.replication的值赋给X，若X≠1，则将X的值减1，参照完成复制的冗余机制，随机选择除机架N外的其他机架N'，记N'为N，返回步骤4.若X=1，则继续下一步.

9)若数据上传完成，则整个过程结束.若数据上传未完成，则取消机架和节点的不平衡标记，返回步骤1，重新上传新的数据块.

图1 HDFS下基于纠删码的数据放置策略过程图

4 实验结果与分析

本文选用Reed－Solomon码作为纠删码，使用Java编写Reed Solomon编解码器模块，它包括编码和解码2个模块，应用范德萌矩阵方法实现对数据块的编码和解码操作.

为了测试系统中编解码器模块的效率，分别选取大小为64，120，250，500，1 000，1 500 MB的文件进行编码和解码，每个文件分别编码、解码5次取平均值作为结果.实验中k与n的比例为5∶8.所得编解码时间如表1所示，编解码的时间单位为s.

表1 编码器模块编解码时间 s

由表1可看出，编解码速度随着文件的增大有所下降，但是下降到一定程度即趋于稳定.当文件大小为64～1 500 MB时，系统的编码和解码速度是174～78 MB/s，能够满足系统的性能要求.

使用Hadoop－0.20.1进行实验环境的搭建，对所提出的策略进行了试验.试验集群中有3个机架(机架A、机架B、机架C)，每个机架5个节点，分别记为D1，D2，D3，D4，D5.在实验中，机架A上的D1作为提交文件的节点，不考虑存储性能，该节点一共上传1 000个数据块到集群，假设系统启动时所有的节点都处于空载状态.实验中P(i)各权重都设为1/3，阈值LR设置为20.机架A中D2到D5存储性能分别为13.9，14.7，15.3， 12.1.机架B中D1到D5存储性能分别为11.4，15.3，12.9，12.5，13.5.机架C中D1到D5存储性能分别为12.6，13.2，14.3，12.3，13.7.

首先采用HDFS默认的数据放置策略，使用相对负载的概念对集群中各数据节点的负载情况进行了统计，结果如图2(a)所示.接着采用本文的基于纠删码的数据放置策略，取k与n的比例为5∶8，实验中一共有1 000个数据块，则经过编码后有1 600个数据块，将数据块上传到HDFS后各节点的负载情况如图2(b)所示.

对比图2中的(a)与(b)可知，以相对负载为评价标准，本文提出的基于纠删码的数据放置策略能够保证机架中各数据节点的负载均衡.

图2 不同策略下集群中各节点的相对负载情况

为了检验本文提出的数据放置策略所带来的时间开销，在相同的环境下，分别使用本文提出的方法与默认放置策略向HDFS内的同一个数据节点提交同样大小的文件，记录从发出文件提交请求到文件存储完成所用的时间.由于HDFS存储的数据块默认为64 MB.因此，在实验中，分别在采用默认策略与改进策略的情况下，提交一个320 MB的文件，每个文件被分为5个大小为64 MB的数据块，统计其从NameNode接到请求到数据存储完成所需要的时间，在测试过程中进行4次相同操作，操作结果如表2所示.

由表2可知，在本试验中，本文提出的策略使用的时间少于HDFS默认策略.综上所述，本文提出的数据放置策略通过使用基于纠删码的冗余机制替换原有的基于完全复制的冗余机制，结合机架之间的网络距离和节点相对负载，选择离本地机架最近且相对负载最低的节点作为数据放置节点.此策略减少了数据副本存放的数量，不但能够减少存储空间的浪费，还能减少存放数据副本的时间开销.另一方面也可以降低数据节点之间存储负载的不平衡，特别是能够在一个机架内实现各个数据节点较为平均的数据块存储.

表2 本文的策略和默认策略的时间开销

5 结语

本文讨论了HDFS系统中关于数据放置策略的相关问题，提出了HDFS平台下基于纠删码的一种数据放置策略，从仿真实验看来，其在存储空间及时间开销方面都优于HDFS默认的数据放置策略，而且该策略降低了数据节点之间存储负载的不平衡.

［1］王意洁，孙伟东.云计算环境下的分布存储关键技术［J］.软件学报，2012，23(4):962－986.

［2］Rizzo L.Effective erasure codes for reliable computer communication protocols［J］.ACM SIGCOMM Computer Communication Review，1997，27(2):24－36.

［3］孙程，谢军.一种基于纠删码的分布式存储容灾的设计与实验［J］.中国集成电路，2009(10):38－42.

［4］Theapache software foundation.HDFS architecture Guide，2014［EB/OL］.［2014－08－10］.http://hadoop.apache.org/docs/current/hadoopproject－dist/hadoop－hdfs/HdfsDesign.html.

［5］Shvachko K，Kuang H，Radia S.The hadoop distributed file system［C］//IEEE Conference Publications.Proc.of the IEEE 26th Symp.on Mass storage Systems and Technologies(MSST).Lake Tahoe:IEEE，2010:1－10.

［6］BorthakurD.Hadoop［EB/OL］.［2011－06－15］.http://lucene.apache.org/hadoop.

［7］王永洲，茅苏.HDFS中的一种数据放置策略［J］.计算机技术与发展，2013，23(5):90－96.

(责任编辑 杜利民)

A data placement strategy based on erasure code in the platform of HDFS

KONG Chenyan， ZHAO Jianmin， ZHU Xinzhong， XU Huiying

(College of Mathematics，Physics and Information Engineering，Zhejiang Normal University，Jinhua Zhejiang 321004，China)

Reliability of data was a hot topic in the field of cloud computing.The mechanism of backup as an important mean to ensure the reliability of data had been used widely，but with the increase of the number of copies，the defect of storage space wasting in this mechanism had been exposed.To save storage space，the technology of erasure codes was used to ensure the reliability of data.It was proposed a data placement strategy in the platform of HDFS.This strategy used HDFS as the platform，combining backup strategy of HDFS and technology of erasure code.The improved data placement strategy proposed could be applied to the cloud file system based on erasure code and HDFS by improving the original data storage strategy in the HDFS platform.

cloud computing;HDFS;copy backup;erasure code;dataplacement

TP393

A

1001－5051(2015)01－0089－06

�:2014－10－27;

2014－11－19

国家自然科学基金资助项目(61272468)

孔晨燕(1991－)，女，江苏镇江人，硕士研究生.研究方向:大数据和云计算.

赵建民.E－mail:zjm@zjnu.cn

10.16218/j.issn.1001－5051.2015.01.015