Hadoop副本放置策略

邵秀丽，王亚光，李云龙，刘一伟

(1.南开大学 信息技术科学学院，天津300071;2.北京大学数学科学学院，北京100871)

为提高系统的可靠性，解决不可预知的灾难以及硬件错误对系统造成的损失，云存储系统采用分布式副本技术来存储数据.

哥伦比亚大学的Ko等[1]提出了一种自稳定、全分布、异步可升级的算法来放置副本，算法的目标是在网络中的结点上放置数据对象的多个副本，从网络中的任意一个结点出发都能够通过最短的路径访问到任意的副本;加州大学伯克利分校的Chen等[2]开发设计了一个动态、高效及可升级的内容分发网络SCAN(sealable content aeeess network).SCAN 采用Testry进行路由和定位，使用沿路缓存算法进行副本放置;德克萨斯大学的MadhukarR等提出了一种协作的缓存放置算法[3]，即给定一组协作的缓存、缓存之间的网络距离以及从每个缓存到每个对象的访问频率的预测，决定在哪里放置对象，从而使平均访问开销最小化;Karger等[4]提出了能适应节点数量的动态变化的一致性哈希算法，但它只适用于存储节点同构的情况，当节点的存储容量和处理能力有差异时，数据将不能够均匀地分布到系统当中.

云存储系统的典型代表是Hdfs[5]，它需将每个存储数据块的副本放置在多个机架的多个节点上，存储数据块的副本放置策略将直接影响数据存储的均衡性以及访问数据块的速度.Hdfs系统采用随机选择节点的副本放置策略，该策略在系统运行一段时间后会造成数据分布不均衡的问题，降低数据的可靠性和读取性能.因此，本文提出了基于节点使用率选择存储节点的Hdfs副本放置策略的改进算法，引入了客户端存储阈值，允许副本在放置过程中穿越多个机架，以实现各节点数据存储的相对均衡，实验验证了改进策略的有效性.

1 副本放置策略的相关概念

内容为研究Hdfs的副本放置策略，先介绍相关概念如下:

1)获取集群信息:Hdfs的NetworkTopology类实现对其拓扑结构的操纵，该类中包含添加、删除和获取节点信息等函数.比如，Hdfs通过调用NetworkTopology类的chooseRandom来随机获取一个节点的信息，通过调用getNumOfLeaves来获取所有节点的数目.

2)集群拓扑(机架与节点):将Hdfs部署在多台服务器上就形成了一个Hdfs的集群.如树状拓扑结构的Hdfs集群，树根是一个大型交换机，交换机之下可以是多个二级交换机，可以把每一个二级交换机设置为一个机架，每个机架之下连接多个节点.

Hdfs管理员可编写脚本文件来配置每个节点属于哪一个机架.在进行机架配置时，应将相同交换机下的节点设置为同一个机架就可实现合理的配置.

一般把组成Hdfs集群的每一个服务器称为一个节点，对文件读写的客户端而言，其所在节点称为本地节点，其他节点为远程节点.就某一具体节点而言，称该节点所在的机架为本地机架，其他机架为远程机架.

3)随机函数:Hdfs的NetworkTopology类中有保存所有节点信息的ArrayList.Hdfs在选择副本放置位置时，调用随机选择函数chooseRandom，从n中随机选择一个数对应ArrayList中的节点就被选中为副本存储的节点.该函数是只有2个参数的重载函数，第1个参数是选择节点的范围，它可以是某个机架，默认为整个集群;第2个参数是不能选择节点的范围，默认为空，可以设置为某个机架.

4)Hdfs在进行副本选择过程中，有可能出现参数不合格或内存异常等现象，一旦出现运行异常，chooseRandom函数就会把异常信息返回客户端该函数的调用者.

2 Hdfs默认副本放置策略

如图1所示，Hdfs的副本放置策略是将每一个数据项的副本放置在多个节点上.在客户端运行的节点上放置第1个副本，在客户端的远程机架上随机选择一个节点放置第2个副本，在第2个副本所在机架上随机选择一个节点放置第3个副本.

图1 副本放置策略Fig.1 The placement policy of duplication

分布式文件系统[6-7]的副本放置策略确定每一个数据块应该存放的位置，数据块与节点之间的关联被记录在数据块与节点关联表中，数据块最终会被存放在存储层的各个节点上.

2.1 Hdfs默认副本放置策略的流程

Hdfs的分块存储文件在选择副本放置位置时，综合考虑了数据存储的可靠性、数据读写的带宽和负载均衡等因素.如将一个数据块所有副本都存储在一个节点上，则存储过程中所占用的带宽是最小的，因为这可以减少数据块的网络传输，但该方案不提供有效的冗余备份，一旦该节点发生故障，则该节点中存储的这一数据块及其所有副本都会丢失.因此，Hdfs对任意一数据块不在同一个节点上放置多个副本，而是将副本尽可能分散存放[8-9].图2给出了Hdfs默认的副本放置策略流程，其中标注了本文所实现的对副本放置策略的改进工作，Hdfs默认的副本放置策略选择3个节点，可以选择多个节点放置副本.

图2 默认副本放置策略Fig.2 The flowchart of default replica placement

1)HdFs副本放置策略是调用ReplicationTarget-Chooser类的chooseTargrt函数来实现的.开始使用NetworkTopology类的contains函数，contains函数通过判断客户端所在根节点与集群的根节点是否一致来判断客户端是否在集群中.

2)如果客户端是集群中的一个节点，则调用ReplicationTargetChooser类的 chooseLocalNode函数来尝试选择客户端节点作为第1个节点.

3)客户端存储尝试失败时则调用ReplicationTargetChooserchooser类的chooseLocalRack函数，在客户端节点所在机架随机选择一个节点作为第1个节点，然后将这个节点的信息传给ReplicationTargetChooserchooser类中的chooseTargrt函数，且将这个节点的信息记录在ReplicationTargetChooserchooser类中的一个DatanodeDescriptor类型的数组results中.

4)如果客户端不是集群中的节点，则使用ReplicationTargetChooser类的chooseRandom函数在集群中随机选择一个节点作为第1个节点，且将这个选择的节点记录在数组results中.

5)ReplicationTargetChooser类的chooseRemoteRack函数在第1个节点的远程机架上随机选择一个节点作为第2个节点.如果在远程机架上选择节点失败，则使用ReplicationTargetChooser类的chooseLocalRack函数在第1个节点的本地机架上随机选择一个节点作为第2个节点.将第2个节点记录在ReplicationTargetChooserchooser类中DatanodeDescriptor下的数组results中.

6)选择第3个节点，如果前2个节点是在同一个机架上，则使用 ReplicationTargetChooser类的chooseRemoteRack函数在前2个节点的远程机架上选择一个节点.如果所选择的前2个节点并不在同一个机架上面，则使用ReplicationTargetChooser类的chooseLocalRack函数在第2个节点的本地机架上随机选择一个节点作为第3个节点，且存储第3个节点信息在数组results中.

7)最终将results中的所有节点返回给副本选择函数的调用者.

2.2 Hdfs副本放置策略的缺陷

Hdfs默认副本放置策略综合考虑了多方面的因素，在可靠性、读写效率，负载均衡方面都做了一定的权衡，是一个比较优秀的副本放置策略，但Hdfs采用随机选择的副本放置策略.该策略没有考虑到节点负载的情况，在数据均衡方面比较薄弱，这使数据损坏时需要恢复的数据块数量可能会很多，数据读取的速度会受到影响等问题.

针对这一问题，Hdfs提供了解决方案——均衡器[10].均衡器(balancer)是一个Hdfs的守护进程，启动之后，它会将数据块从负载较高的节点移到相对空闲的节点，从而达到重新分配数据块的目的，最终达到整个集群的数据块分布均衡.在数据块重新分配的过程中，均衡器会尽量将一个数据块的复本分散到不同机架，以提高数据块的冗余，降低数据损坏的可能性.

Hdfs集群的管理员决定是否启动均衡器，启动后，会根据管理员设定的阀值来对集群进行均衡处理.阀值是每个节点的使用率(该节点上已经使用的空间和节点的空间容量之间的比值)和集群的使用率(集群中已使用的空间和集群的空间容量之间的比值)之间的差值，默认的阀值是10%，管理员在启动均衡器的时候，可以指定阀值的大小.在任何时刻，集群中只能运行一个均衡器.

均衡器虽然可以解决数据块分布不均衡的问题，但是存在着明显的问题:

1)均衡器对于集群数据块均衡的调节具有滞后性，它必须要在系统的不均衡状况超过阀值之后，才会进行调节.

2)均衡器的运行和数据块的移动需要耗费一定的资源，很可能一个数据块刚刚写入到集群中，就因为均衡性而被移动，这种情况下集群的资源使用是很低效的.

3 Hdfs副本放置策略的改进

Hdfs默认的副本放置策略存在的不足，以及Hdfs提供的均衡器存在一些不尽人意的地方，本文提出了对其改进的低使用率优先(low rate first)副本放置策略.

3.1 改进副本放置的流程

图3是副本放置改进策略的流程.

图3 基于3副本放置策略的改进Fig.3 The improved placement strategy based on three replicas

1)考虑到数据写入带宽问题，依然在客户端所在的节点上写入第1个副本，但考虑了该节点的负载情况，即如果本地节点的负载超过了管理员指定的阀值，则选择集群中使用率较低的节点来放置副本.

2)除第1个副本在阀值满足的情况下放在本地节点上之外，其余所有的副本放置位置的选择，都是采用优先选择集群中比较空闲的节点的方式，以避免在负载较高的节点上继续存储数据.

3)为提高数据块的冗余，尽可能地将数据存储在至少2个机架上，本地机架上存储第1个副本，第2个副本选择与第1个节点不同的机架进行存储.因为Hdfs是一次写入、多次读取的设计思想，在数据写入的时候穿越多个机架，虽然写入带宽可能会有所降低，但是提高了集群的数据块分布均衡，有利于文件的读取和程序的运行.

4)为提高数据的冗余，保持每个节点只存储一个副本的规则.Hdfs的默认副本放置策略是一个节点最多放置一个副本，如果副本的数量超过节点的总数，则集群中最多只放置与节点同样数目的副本.低使用率优先的放置策略依然坚持这个原则，每个节点最多只放置一个副本.

尽管当发生故障时，此策略会影响恢复数据速度，而且每存储一个副本时都需要调用函数获取节点信息，并判断该节点是否可以存储副本，这会降低运行速度及安全性.但考虑到Hdfs默认放置策略的副本放置的最终状态很难被控制，它在数据均衡方面的缺点比较明显，而这会带来一系列的问题，比如数据损坏时需要恢复的数据块数量可能会有很多，数据读取的速度可能会受到影响等因素，本文提出的对于Hdfs默认副本放置策略的改进方法有相对优势.

3.2 改进策略实现的核心类

副本放置改进策略会优先考虑在使用率比较低的节点上放置数据，这通过对Hdfs中负责副本放置节点选择的类ReplicationTargetChooser的改进来完成;该类在Hdfs中的作用是当有新增数据块或数据块位置变动的时候，NameNode会调用该类来确定数据块放置的位置.ReplicationTargetChooser类使用chooseTarget函数来选择副本放置的节点，图4描述了放置k个副本重写chooseTarget函数来实现的策略改进.

图4 基于K副本放置策略的改进Fig.4 The improved placement strategy based on K replicas

1)函数的初始化阶段:首先调用NetworkTopology类中的getNumOfLeaves函数来获取集群的大小，控制副本数目不超过集群的大小，如果设置的副本的数目超过集群的大小，则设置副本数目为集群大小.

2)管理员可设置本地节点阀值，默认值为0.1，改进后的Hdfs在配置文件中为用户设置阀值提供了接口，在 Hdfs.xml文件中可以通过为 dfs.replication.threshold设置值来实现阀值的控制，阀值的范围在0～1，0表示本地节点的使用率必须小于等于集群的使用率才会在本地节点上放置数据块的副本;1表示不考虑使用率，一定要在本地节点上放置数据块的副本.

3)使用 Configuration类的getFloat函数配置文件中的阀值.但如果用户没有设置阀值或者设置的阀值不合理，chooseTarget函数依然使用默认阀值进行副本的选择.

4)在重写的chooseTarget函数中需定义一个DataNodeDescriptor类型的数组DN来存储全部节点的信息，DataNodeDescriptor是Hdfs中用于描述DataNode信息的类，chooseTarget函数可以通过操纵DataNodeDescriptor的对象来获取一个节点的信息，包括节点ID、节点名称、节点全部存储空间和节点已经使用的存储空间等.另外，还需定义DataNode-Descriptor类型的数组results来存储已选择的节点，同时定义集群的存储空间使用率Usage.

5)使用NetworkTopology类中的getLeaf函数可以获取集群中所有节点的信息，将返回的所有节点信息存储在数组DN中，然后可以根据DN中的信息计算集群的整体存储空间的使用率Usage.在获取所有节点信息之后，并不对数组DN进行任何处理，比如排序、建堆等.虽然考虑到后面的算法中需要多次取得DN中使用率最小的节点，但考虑客户端和不同机架，因此该问题又与经典TopK问题相似且稍有不同.一般副本个数K默认为3，如果在客户端上放置一个副本，选择另外2个副本的计算复杂度为O(2N －3).

6)初始化后选择节点，先通过Hdfs调用chooseTarget函数，使用NetworkTopology类中的contains函数判断客户端节点是否在集群中，如果不在，则不在客户端上放置副本.否则还需进一步判断客户端节点的使用率与集群使用率的差值，如果差值小于阀值，则在客户端上放置第1个副本，否则不在客户端上放置副本.使用ReplicationTargetChooser类的is-GoodTarget判断客户端节点是否可用，才能确定是否在客户端节点上放置一个数据块.

7)如果客户端不可用，则在DN中选择使用率最低的节点来尝试放置副本，如节点不可用，则将该节点标记为暂时不可选择，然后继续在其他节点中选择一个使用率最低的节点，直到选择到合适的节点为止.

8)机架数目对副本放置节点的算法有一定的影响，使用NetworkTopology类的getNumOfRacks函数来获取机架的数目，则在DN中选择一个使用率最小的节点作为第1个副本放置的节点.选择第1个节点后，将其从DN中移除，加入到results数组中.

9)在选择第2个节点的时候，在DN中选择使用率最小的节点，然后使用 NetworkTopology类的isOnSameRack函数判断它与选取的第1个节点是否在相同的机架上.如果这2个节点不在一个机架上，则选择这个节点作为第2个副本存放的节点，否则，重新选择DN中其他节点中使用率最小的节点，直到找到这样的节点为止.选择第2个节点之后，将其从记录未被选择节点的数组DN中移除，加入到记录已选择节点的数组results中.

10)继续上述步骤选择其他节点.

11)函数执行过程中，使用java中的try来尝试运行，若chooseTarget函数的运行没有出现异常，则最终将存储已选择节点的数组results返回给函数的调用者.若执行过程中出现不可处理的异常，则在catch语句中处理异常，返回客户端节点.

4 实验结果与分析

为了比较Hdfs默认的和本文改进的副本放置策略，本文实现了由2部分组成的测试程序:1)负责模拟一个节点运行的DataNode类，该类记录了模拟节点的惟一标识、容量、使用量、数据块数量以及机架标识;2)模拟系统运行的NameNode类，包括对于Data-Node的初始化、设置阀值、设置副本放置策略和数据写入等内容的模拟.在模拟的过程中，并不进行真实的数据的读写，只是对于数据读写后的结果进行模拟记录.在NameNode类中初始化所有的节点，每个节点初始的容量是1 T，used和blockNum被设置为0.该程序模拟写入过程，设置写入数据块的大小和模拟数据的分块.对于每一个划分的数据块，程序运行相应的副本放置策略函数，选择3个节点用于放置划分的数据块.然后循环处理直到数据块的写入完成.

写入所有数据后，可根据模拟节点的使用情况计算不同的副本放置策略的数据存储均衡性.本文使用标准差来衡量副本放置的均衡性，所使用的数据是所有DataNode的使用率，也就是每个节点的使用容量used与总容量capacity之间的比值.设集群中一共有n个节点，所有节点的使用率分别为X1，X2，..，Xn－1，Xn.节点使用率的平均值X2+…+Xn－1+Xn)/n，标准差

本文实验一测试了机架数目对于算法的影响，分别使用默认的策略和改进后的策略，模拟测试在500个节点上写入大小不同的数据后，系统的存储均衡情况，写入文件大小为100 G条件下的节点使用率的标准差.

从图5中可以看出，对于默认的副本放置策略，机架数目在3个以内的时候，机架的个数对于系统的均衡性会有一定的影响，但是差别在0.02%以内.当机架数目超过3个以后，机架数目对于系统均衡性的影响会在0.005%以内.而对于改进后的副本放置策略，机架的数目对于集群的均衡性影响会变得更小，在0.002%以内.所以，机架的个数对于2种副本放置策略的影响都很小.通过图5可以看出，改进后的副本放置策略受到的影响更小，在不同机架个数情况下，都有更好的均衡性.

图5 机架数目对于算法的影响Fig.5 The impact of the algorithm based on the number of rack

实验二测试随着写入数据的增加，不同副本放置策略下集群存储的均衡性.实验选择在500个节点、5个机架的条件下，分别使用默认的副本放置策略和改进后的副本放置策略，写入 1 G、10 G、100 G、1 T、10 T和100 T的数据，测试集群的副本均衡情况.

根据图6显示，使用改进后的副本放置策略进行副本放置位置的选择，集群中数据块的均衡性明显好于使用默认的副本放置策略，在数据量比较小的时候这种优势还不太明显，但是在数据量比较大的时候，改进后的策略的好处就会更加明显.可见，改进后的副本放置策略，在数据块的均衡性方面有更加良好的表现.

图6 存储数据量对于算法的影响Fig.6 The impact of the algorithm based on

本文提出的放置策略需获取集群中所有节点的信息，且将其存储在一个DataNodeDescriptor数组中，从而增加了时间和空间的开销.另外要计算集群的整体使用率与选择集群中使用率较小的节点，增加了线性的开销.

5 结束语

本文基于节点存储率对Hdfs中负责副本放置节点选择的类ReplicationTargetChooser进行了改进，并部署了简单实际环境进行了实验，由于其实际环境受物理设备和其他异构条件等各种客观因素的影响不大，所以，本文所提方案提高了Hdfs的数据块放置的均衡性.但本文所提出的副本放置策略，关注的主要是集群中数据块副本放置的均衡性，所考虑的因素主要是节点的使用率，而没有考虑节点使用的价格、安全性、处理速度等.

[1]KO B J.Scalable service differentiation in a shared storage cache[C]//Proc of the 23rd International Conference on Distributed Computing Systems.Washington，DC，USA，2003:184-194.

[2]CHEN Yan.SCAN:a dynamic，scalable，and efficient content distribution network[C]//Proceedings of the International Conference on Pervasive Computing.Zürich，Switzerland，2002:282-286.

[3]KORUPOLU M R.Placement algorithms for hierarchical cooperative caching[C]//Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms.PA，USA，1999:586-595.

[4]KARGER D，LEHMAN E，LEIGHTON T，et al.Consistent hashing and random trees:distributed caching protocols for relieving hot spots on the world wide web[C]//ACM Symposium on Theory of Computing.CA，USA，1997:654-663.

[5]BORTHAKUR D.The hadoop distributed file system:architecture and design[EB/OL].[2012-11-08].http://hadoop.apache.org/core/docs.

[6]GUY L，LAURE E，STOCKINGER H，et al.Replica management in data grids，GGF5[R].Global Grid Information Document，2002.

[7]STONEBRAKER M，ABADI D J，De WITT D J，et al.MapReduce and parallel DBMSs:friends or foes[J].Communication of the ACM，2010，53(1):64-71.

[8]魏青松，卢显良，侯孟书.AdpReplica:自适应副本管理机制[J].计算机科学，2004，31(12):34-36.WEI Qingsong，LU Xianliang，HOU Mengshu.AdpRePlica:adaptive replica management mechanism[J].Computer Science，2004，31(12):34-36.

[9]杨曙锋.分布式并行文件系统的副本管理策略[D].成都:电子科技大学，2003:23-31.YANG Shufeng.The Copies’management strategy of distributed parallel file system[D].Chengdu:University of Electronic Science and Technology of China，2003:23-31.

[10]BORDAWEKAR R，LANDHERR S，CAPPS D，et al.Experimental evaluation of the Hewlett-Packard Exemplar file system[C]//ACM Sigmetric SPerformance Evaluation Review.[S.l.]1997.