第8卷第6期 智能系统学报 Vol.8 No.6 2013年12月 CAAI Transactions on Intelligent Systems Dec.2013 D0:10.3969/j.issn.1673-4785.201210036 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20131030.1508.003.html Hadoop副本放置策略 邵秀丽，王亚光1，李云龙，刘一伟2 (1.南开大学信息技术科学学院，天津300071；2.北京大学数学科学学院，北京100871) 摘要：分布式文件系统(Hs)采用随机的副本放置策略使得系统在运行一段时间后会出现数据分布不均衡的情 况，从而降低数据的可靠性和读取速率.为解决Hds默认副本放置策略存在的问题，对Hs副本放置策略进行改进： 在副本放置选择时优先考虑存储使用率低的节点模拟实验一测试了机架数目对于算法的影响，结果显示改进后的 副本放置策略中，机架数目对集群的均衡性影响很小，显示出较好的均衡性模拟实验二测试了随着写入数据的增 加，比较了使用改进前后的副本放置策略集群中节点使用率的标准差，证实了改进后的副本放置策略在存储均衡方 面较原放置策略有着更好的表现 关键词：云存储：Hds:副本放置：存储均衡：存储节点 中图分类号：TP399文献标志码：A文章编号：1673-4785(2013)06-0489-08 中文引用格式：邵秀丽，王亚光，李云龙，等.Hado0p副本放置策略[J].智能系统学报，2013,8(6)：489-496. 英文引用格式：SHAO Xiuli,WANG Yaguang,LI Yunlong,etal.Research on the replica placement strategy of Hadoop[J].CAAL Transactions on Intelligent Systems,2013,8(6):489-496. Research on the replica placement strategy of Hadoop SHAO Xiuli',WANG Yaguang',LI Yunlong',LIU Yiwei? (1.College of Information Technology Science,Nankai University,Tianjin 300071,China;2.College of Mathematical Sciences,Pe- king University,Beijing 100871,China) Abstract:Hadoop distributed file system applies the random replica placement strategy,which causes unbalanced data distribution after the system has operated for a while,resulting in lowering the data reliability and reading speed.In order to eliminate the defect of the replica placement strategy defaulted by the Hdfs,the strategy was im- proved.When the placement location of a replica is selected,a node with a low storage and use rate will be consid- ered as a priority.The first simulation experiment tested the effects caused by the number of racks on the algorithm. The results show that,for the improved replica placement strategy,the number of racks has little impact on the e- quilibrium of the group,the equilibrium is excellent.The second simulation experiment compared the standard difference of the node usage rates between the replica placement strategy groups before and after and found an im- provement following the increase of the data input.The results verify that the improved replica placement strategy has better performance with respect to storage equilibrium. Keywords:cloud storage;Hdfs;replica placement;storage equilibrium;storage node 为提高系统的可靠性，解决不可预知的灾难以 布式副本技术来存储数据. 及硬件错误对系统造成的损失，云存储系统采用分 哥伦比亚大学的K等提出了一种自稳定、全 分布、异步可升级的算法来放置副本，算法的目标是 收稿日期：2012-10-26.网络出版日期：2013-10-30 在网络中的结点上放置数据对象的多个副本，从网络 基金项目：天津市滨海新区科技项目资助项目(12 ZCDZGX46700、 13ZCZDGX02500) 中的任意一个结点出发都能够通过最短的路径访问 通信作者：邵秀丽.E-mail:shaoxl@nankai.edu.cm 到任意的副本；加州大学伯克利分校的Chen等)开
第 ８ 卷第 ６ 期 智 能 系 统 学 报 Ｖｏｌ．８ №．６ ２０１３ 年 １２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｃ． ２０１３ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１２１００３６ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１３１０３０．１５０８．００３．ｈｔｍｌ Ｈａｄｏｏｐ 副本放置策略 邵秀丽１ ，王亚光１ ，李云龙１ ，刘一伟２ （１．南开大学 信息技术科学学院，天津 ３０００７１； ２．北京大学 数学科学学院，北京 １００８７１） 摘 要：分布式文件系统（Ｈｄｆｓ）采用随机的副本放置策略使得系统在运行一段时间后会出现数据分布不均衡的情 况，从而降低数据的可靠性和读取速率．为解决 Ｈｄｆｓ 默认副本放置策略存在的问题，对 Ｈｄｆｓ 副本放置策略进行改进： 在副本放置选择时优先考虑存储使用率低的节点．模拟实验一测试了机架数目对于算法的影响，结果显示改进后的 副本放置策略中，机架数目对集群的均衡性影响很小，显示出较好的均衡性．模拟实验二测试了随着写入数据的增 加，比较了使用改进前后的副本放置策略集群中节点使用率的标准差，证实了改进后的副本放置策略在存储均衡方 面较原放置策略有着更好的表现． 关键词：云存储；Ｈｄｆｓ；副本放置；存储均衡；存储节点 中图分类号： ＴＰ３９９ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１３）０６⁃０４８９⁃０８ 中文引用格式：邵秀丽，王亚光，李云龙，等． Ｈａｄｏｏｐ 副本放置策略［Ｊ］． 智能系统学报， ２０１３， ８（６）： ４８９⁃４９６． 英文引用格式：ＳＨＡＯ Ｘｉｕｌｉ， ＷＡＮＧ Ｙａｇｕａｎｇ， ＬＩ Ｙｕｎｌｏｎｇ， ｅｔ ａｌ． Ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ ｒｅｐｌｉｃａ ｐｌａｃｅｍｅｎｔ ｓｔｒａｔｅｇｙ ｏｆ Ｈａｄｏｏｐ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１３， ８（６）： ４８９⁃４９６． Ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ ｒｅｐｌｉｃａ ｐｌａｃｅｍｅｎｔ ｓｔｒａｔｅｇｙ ｏｆ Ｈａｄｏｏｐ ＳＨＡＯ Ｘｉｕｌｉ １ ， ＷＡＮＧ Ｙａｇｕａｎｇ １ ， ＬＩ Ｙｕｎｌｏｎｇ １ ， ＬＩＵ Ｙｉｗｅｉ ２ （１． Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ Ｓｃｉｅｎｃｅ， Ｎａｎｋａｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｔｉａｎｊｉｎ ３０００７１， Ｃｈｉｎａ； ２． Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃａｌ Ｓｃｉｅｎｃｅｓ， Ｐｅ⁃ ｋｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｂｅｉｊｉｎｇ １００８７１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｈａｄｏｏｐ ｄｉｓｔｒｉｂｕｔｅｄ ｆｉｌｅ ｓｙｓｔｅｍ ａｐｐｌｉｅｓ ｔｈｅ ｒａｎｄｏｍ ｒｅｐｌｉｃａ ｐｌａｃｅｍｅｎｔ ｓｔｒａｔｅｇｙ， ｗｈｉｃｈ ｃａｕｓｅｓ ｕｎｂａｌａｎｃｅｄ ｄａｔａ ｄｉｓｔｒｉｂｕｔｉｏｎ ａｆｔｅｒ ｔｈｅ ｓｙｓｔｅｍ ｈａｓ ｏｐｅｒａｔｅｄ ｆｏｒ ａ ｗｈｉｌｅ， ｒｅｓｕｌｔｉｎｇ ｉｎ ｌｏｗｅｒｉｎｇ ｔｈｅ ｄａｔａ ｒｅｌｉａｂｉｌｉｔｙ ａｎｄ ｒｅａｄｉｎｇ ｓｐｅｅｄ ． Ｉｎ ｏｒｄｅｒ ｔｏ ｅｌｉｍｉｎａｔｅ ｔｈｅ ｄｅｆｅｃｔ ｏｆ ｔｈｅ ｒｅｐｌｉｃａ ｐｌａｃｅｍｅｎｔ ｓｔｒａｔｅｇｙ ｄｅｆａｕｌｔｅｄ ｂｙ ｔｈｅ Ｈｄｆｓ， ｔｈｅ ｓｔｒａｔｅｇｙ ｗａｓ ｉｍ⁃ ｐｒｏｖｅｄ． Ｗｈｅｎ ｔｈｅ ｐｌａｃｅｍｅｎｔ ｌｏｃａｔｉｏｎ ｏｆ ａ ｒｅｐｌｉｃａ ｉｓ ｓｅｌｅｃｔｅｄ， ａ ｎｏｄｅ ｗｉｔｈ ａ ｌｏｗ ｓｔｏｒａｇｅ ａｎｄ ｕｓｅ ｒａｔｅ ｗｉｌｌ ｂｅ ｃｏｎｓｉｄ⁃ ｅｒｅｄ ａｓ ａ ｐｒｉｏｒｉｔｙ． Ｔｈｅ ｆｉｒｓｔ ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔ ｔｅｓｔｅｄ ｔｈｅ ｅｆｆｅｃｔｓ ｃａｕｓｅｄ ｂｙ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｒａｃｋｓ ｏｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ． Ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ， ｆｏｒ ｔｈｅ ｉｍｐｒｏｖｅｄ ｒｅｐｌｉｃａ ｐｌａｃｅｍｅｎｔ ｓｔｒａｔｅｇｙ， ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｒａｃｋｓ ｈａｓ ｌｉｔｔｌｅ ｉｍｐａｃｔ ｏｎ ｔｈｅ ｅ⁃ ｑｕｉｌｉｂｒｉｕｍ ｏｆ ｔｈｅ ｇｒｏｕｐ， ｔｈｅ ｅｑｕｉｌｉｂｒｉｕｍ ｉｓ ｅｘｃｅｌｌｅｎｔ． Ｔｈｅ ｓｅｃｏｎｄ ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔ ｃｏｍｐａｒｅｄ ｔｈｅ ｓｔａｎｄａｒｄ ｄｉｆｆｅｒｅｎｃｅ ｏｆ ｔｈｅ ｎｏｄｅ ｕｓａｇｅ ｒａｔｅｓ ｂｅｔｗｅｅｎ ｔｈｅ ｒｅｐｌｉｃａ ｐｌａｃｅｍｅｎｔ ｓｔｒａｔｅｇｙ ｇｒｏｕｐｓ ｂｅｆｏｒｅ ａｎｄ ａｆｔｅｒ ａｎｄ ｆｏｕｎｄ ａｎ ｉｍ⁃ ｐｒｏｖｅｍｅｎｔ ｆｏｌｌｏｗｉｎｇ ｔｈｅ ｉｎｃｒｅａｓｅ ｏｆ ｔｈｅ ｄａｔａ ｉｎｐｕｔ． Ｔｈｅ ｒｅｓｕｌｔｓ ｖｅｒｉｆｙ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ｒｅｐｌｉｃａ ｐｌａｃｅｍｅｎｔ ｓｔｒａｔｅｇｙ ｈａｓ ｂｅｔｔｅｒ ｐｅｒｆｏｒｍａｎｃｅ ｗｉｔｈ ｒｅｓｐｅｃｔ ｔｏ ｓｔｏｒａｇｅ ｅｑｕｉｌｉｂｒｉｕｍ． Ｋｅｙｗｏｒｄｓ：ｃｌｏｕｄ ｓｔｏｒａｇｅ； Ｈｄｆｓ； ｒｅｐｌｉｃａ ｐｌａｃｅｍｅｎｔ； ｓｔｏｒａｇｅ ｅｑｕｉｌｉｂｒｉｕｍ； ｓｔｏｒａｇｅ ｎｏｄｅ 收稿日期：２０１２⁃１０⁃２６． 网络出版日期：２０１３⁃１０⁃３０． 基金项目：天津市滨海新区科技项目资助项目（ １２ＺＣＤＺＧＸ４６７００、 １３ＺＣＺＤＧＸ０２５００）． 通信作者：邵秀丽． Ｅ⁃ｍａｉｌ：ｓｈａｏｘｌ＠ ｎａｎｋａｉ．ｅｄｕ．ｃｎ． 为提高系统的可靠性，解决不可预知的灾难以 及硬件错误对系统造成的损失，云存储系统采用分 布式副本技术来存储数据． 哥伦比亚大学的 Ｋｏ 等［１］提出了一种自稳定、全 分布、异步可升级的算法来放置副本，算法的目标是 在网络中的结点上放置数据对象的多个副本，从网络 中的任意一个结点出发都能够通过最短的路径访问 到任意的副本；加州大学伯克利分校的 Ｃｈｅｎ 等［２］ 开
·490 智能系统学报 第8卷 发设计了一个动态、高效及可升级的内容分发网络 3)随机函数：Hdfs的NetworkTopolog罗类中有保 SCAN sealable content aeeess network )SCAN 存所有节点信息的ArrayList..Hdfs在选择副本放置 Testry进行路由和定位，使用沿路缓存算法进行副本 位置时，调用随机选择函数chooseRandom,从n中随 放置：德克萨斯大学的MadhukarR等提出了一种协作 机选择一个数对应ArrayList中的节点就被选中为 的缓存放置算法[3)，即给定一组协作的缓存、缓存之 副本存储的节点.该函数是只有2个参数的重载函 间的网络距离以及从每个缓存到每个对象的访问频 数，第1个参数是选择节点的范围，它可以是某个机 率的预测，决定在哪里放置对象，从而使平均访问开 架，默认为整个集群：第2个参数是不能选择节点的 销最小化；Karg©r等4提出了能适应节点数量的动态 范围，默认为空，可以设置为某个机架 变化的一致性哈希算法，但它只适用于存储节点同构 4)Hds在进行副本选择过程中，有可能出现参 的情况，当节点的存储容量和处理能力有差异时，数 数不合格或内存异常等现象，一旦出现运行异常， 据将不能够均匀地分布到系统当中. chooseRandom函数就会把异常信息返回客户端该 云存储系统的典型代表是Hdfs[s),它需将每个 函数的调用者 存储数据块的副本放置在多个机架的多个节点上， 2Hdfs默认副本放置策略 存储数据块的副本放置策略将直接影响数据存储的 均衡性以及访问数据块的速度.Hdfs系统采用随机 如图1所示，Hds的副本放置策略是将每一个 选择节点的副本放置策略，该策略在系统运行一段 数据项的副本放置在多个节点上.在客户端运行的 时间后会造成数据分布不均衡的问题，降低数据的 节点上放置第1个副本，在客户端的远程机架上随 可靠性和读取性能.因此，本文提出了基于节点使用 机选择一个节点放置第2个副本，在第2个副本所 率选择存储节点的Hds副本放置策略的改进算法， 在机架上随机选择一个节点放置第3个副本 引入了客户端存储阈值，允许副本在放置过程中穿 越多个机架，以实现各节点数据存储的相对均衡，实 文件写入 验验证了改进策略的有效性 云存储 客户端客户端2…客户端 系统 1 副本放置策路的相关概念 写入 访问层 分布式文件系统 内容为研究Hdfs的副本放置策略，先介绍相关 文件文件2…文件 文件与数据 概念如下： 应用 接口层 分块 块关联表 I)获取集群信息：Hdf的NetworkTopolog罗类实 、分块存储 基础 现对其拓扑结构的操纵，该类中包含添加、删除和获 管理层 块 块2 块风 取节点信息等函数.比如，Hdfs通过调用NetworkTo- 数据块与节 存储：副本放置策略 点关联表 pology类的chooseRandom来随机获取一个节点的 存储层 存储介质 信息，通过调用getNumOfLeaves来获取所有节点的 pc2 pen 数目 图1副本放置策略 2)集群拓扑（机架与节点）：将Hdfs部署在多 Fig.1 The placement policy of duplication 台服务器上就形成了一个Hds的集群.如树状拓扑 结构的Hds集群，树根是一个大型交换机，交换机 分布式文件系统[6)的副本放置策略确定每一 之下可以是多个二级交换机，可以把每一个二级交 个数据块应该存放的位置，数据块与节点之间的关 换机设置为一个机架，每个机架之下连接多个节点 联被记录在数据块与节点关联表中，数据块最终会 Hds管理员可编写脚本文件来配置每个节点属 被存放在存储层的各个节点上。 于哪一个机架在进行机架配置时，应将相同交换机 2.1Hdfs默认副本放置策略的流程 下的节点设置为同一个机架就可实现合理的配置： Hds的分块存储文件在选择副本放置位置时， 一般把组成Hdfs集群的每一个服务器称为一 综合考虑了数据存储的可靠性、数据读写的带宽和负 个节点，对文件读写的客户端而言，其所在节点称为 载均衡等因素如将一个数据块所有副本都存储在一 本地节点，其他节点为远程节点就某一具体节点而 个节点上，则存储过程中所占用的带宽是最小的，因 言，称该节点所在的机架为本地机架，其他机架为远 为这可以减少数据块的网络传输，但该方案不提供有 程机架 效的冗余备份，一旦该节点发生故障，则该节点中存
发设计了一个动态、高效及可升级的内容分发网络 ＳＣＡＮ（ ｓｅａｌａｂｌｅ ｃｏｎｔｅｎｔ ａｅｅｅｓｓ ｎｅｔｗｏｒｋ）． ＳＣＡＮ 采 用 Ｔｅｓｔｒｙ 进行路由和定位，使用沿路缓存算法进行副本 放置；德克萨斯大学的 ＭａｄｈｕｋａｒＲ 等提出了一种协作 的缓存放置算法［３］ ，即给定一组协作的缓存、缓存之 间的网络距离以及从每个缓存到每个对象的访问频 率的预测，决定在哪里放置对象，从而使平均访问开 销最小化；Ｋａｒｇｅｒ 等［４］提出了能适应节点数量的动态 变化的一致性哈希算法，但它只适用于存储节点同构 的情况，当节点的存储容量和处理能力有差异时，数 据将不能够均匀地分布到系统当中． 云存储系统的典型代表是 Ｈｄｆｓ ［５］ ，它需将每个 存储数据块的副本放置在多个机架的多个节点上， 存储数据块的副本放置策略将直接影响数据存储的 均衡性以及访问数据块的速度．Ｈｄｆｓ 系统采用随机 选择节点的副本放置策略，该策略在系统运行一段 时间后会造成数据分布不均衡的问题，降低数据的 可靠性和读取性能．因此，本文提出了基于节点使用 率选择存储节点的 Ｈｄｆｓ 副本放置策略的改进算法， 引入了客户端存储阈值，允许副本在放置过程中穿 越多个机架，以实现各节点数据存储的相对均衡，实 验验证了改进策略的有效性． １ 副本放置策略的相关概念 内容为研究 Ｈｄｆｓ 的副本放置策略，先介绍相关 概念如下： １）获取集群信息：Ｈｄｆｓ 的 ＮｅｔｗｏｒｋＴｏｐｏｌｏｇｙ 类实 现对其拓扑结构的操纵，该类中包含添加、删除和获 取节点信息等函数．比如，Ｈｄｆｓ 通过调用 ＮｅｔｗｏｒｋＴｏ⁃ ｐｏｌｏｇｙ 类的 ｃｈｏｏｓｅＲａｎｄｏｍ 来随机获取一个节点的 信息，通过调用 ｇｅｔＮｕｍＯｆＬｅａｖｅｓ 来获取所有节点的 数目． ２）集群拓扑（机架与节点）：将 Ｈｄｆｓ 部署在多 台服务器上就形成了一个 Ｈｄｆｓ 的集群．如树状拓扑 结构的 Ｈｄｆｓ 集群，树根是一个大型交换机，交换机 之下可以是多个二级交换机，可以把每一个二级交 换机设置为一个机架，每个机架之下连接多个节点． Ｈｄｆｓ 管理员可编写脚本文件来配置每个节点属 于哪一个机架．在进行机架配置时，应将相同交换机 下的节点设置为同一个机架就可实现合理的配置． 一般把组成 Ｈｄｆｓ 集群的每一个服务器称为一 个节点，对文件读写的客户端而言，其所在节点称为 本地节点，其他节点为远程节点．就某一具体节点而 言，称该节点所在的机架为本地机架，其他机架为远 程机架． ３）随机函数：Ｈｄｆｓ 的 ＮｅｔｗｏｒｋＴｏｐｏｌｏｇｙ 类中有保 存所有节点信息的 ＡｒｒａｙＬｉｓｔ．Ｈｄｆｓ 在选择副本放置 位置时，调用随机选择函数 ｃｈｏｏｓｅＲａｎｄｏｍ，从 ｎ 中随 机选择一个数对应 ＡｒｒａｙＬｉｓｔ 中的节点就被选中为 副本存储的节点．该函数是只有 ２ 个参数的重载函 数，第 １ 个参数是选择节点的范围，它可以是某个机 架，默认为整个集群；第 ２ 个参数是不能选择节点的 范围，默认为空，可以设置为某个机架． ４）Ｈｄｆｓ 在进行副本选择过程中，有可能出现参 数不合格或内存异常等现象，一旦出现运行异常， ｃｈｏｏｓｅＲａｎｄｏｍ 函数就会把异常信息返回客户端该 函数的调用者． ２ Ｈｄｆｓ 默认副本放置策略 如图 １ 所示，Ｈｄｆｓ 的副本放置策略是将每一个 数据项的副本放置在多个节点上．在客户端运行的 节点上放置第 １ 个副本，在客户端的远程机架上随 机选择一个节点放置第 ２ 个副本，在第 ２ 个副本所 在机架上随机选择一个节点放置第 ３ 个副本． 图 １ 副本放置策略 Ｆｉｇ．１ Ｔｈｅ ｐｌａｃｅｍｅｎｔ ｐｏｌｉｃｙ ｏｆ ｄｕｐｌｉｃａｔｉｏｎ 分布式文件系统［６⁃７］ 的副本放置策略确定每一 个数据块应该存放的位置，数据块与节点之间的关 联被记录在数据块与节点关联表中，数据块最终会 被存放在存储层的各个节点上． ２．１ Ｈｄｆｓ 默认副本放置策略的流程 Ｈｄｆｓ 的分块存储文件在选择副本放置位置时， 综合考虑了数据存储的可靠性、数据读写的带宽和负 载均衡等因素．如将一个数据块所有副本都存储在一 个节点上，则存储过程中所占用的带宽是最小的，因 为这可以减少数据块的网络传输，但该方案不提供有 效的冗余备份，一旦该节点发生故障，则该节点中存 ·４９０· 智 能 系 统 学 报 第 ８ 卷
第6期 邵秀丽，等：Hadoop副本放置策略 ·491. 储的这一数据块及其所有副本都会丢失.因此，Hds 的副本放置策略流程，其中标注了本文所实现的对副 对任意一数据块不在同一个节点上放置多个副本，而 本放置策略的改进工作，Hfs默认的副本放置策略选 是将副本尽可能分散存放[s.图2给出了Hfs默认 择3个节点，可以选择多个节点放置副本 改进策略： 需要考虑客户端 的负载情况客户端负载过 ReplicationTargetChooser 大则不在客户端放置副本 类的chooseTarget函数来进 使用Replication TargetChooser 类的chooseLocalRack在本地 行节点的选择 Replication TargetChooser 机架上选择1个节点 类的chooseLocalNode函数 尝试选择客户端节点作为第 使用NetworkTopology类的 1个节点 contains函数判断客户端是 成功 否是集群中的1个DataNode 成功 Replication TargetChooser 改进策略： 类的chooseRandom函数在 成功 返给Replication TargetChooser 类的chooseTarget函数选择的 不进行随机选择，选则 集群中随机选择1个节点作为 节点 使用率最低的节点 结果 之前的掬作都成功 使用Replication TargetChooser ReplicationTargetChooser 之前的 类的chooseRandom函数在本 失败 类的chooseRemoteRack函数 开始选择第 在远程机架上随机选择1个节 2个节点 操作产 生异常 地机架上选择1个节点 点 成功 返回给Replication TargetChooser 之前的操作出现异常 返回客户端 类的chooseTarget函数选择的节 节点 结束 点 之前的操作都成功 之前的操作 HReplicationTargetChooserchoose 出现异常 开始选择第3个节点 类的choose RemoteRack在远程机 返回最终所选 架上选择1个节点 的所有节点 使用NetworkTopology类的 ReplicationTargetChooserchoose isOnSameRack判断前2个 类的chooseLocalRack在第2个节点 使用Replication Target 节点是否在同1个机架上 N 的本地机架上选择]个节点 Chooser类的choose 之前的操作 Random函数在集群中 都成功 随机选择剩余的节点 改进策路： 不限制具体机架， 改进策略： 不限制机架的个数 开始选择剩 不使用随机函数， 不使用随机函数， 余的节点 选择使用率最低的 节点 选择使用率最低的节点. 图2默认副本放置策略 Fig.2 The flowchart of default replica placement l)HdFs副本放置策略是调用ReplicationTarget-- getChooserchooser类的chooseLocalRack函数，在客户 Chooser类的chooseTargrt函数来实现的.开始使用 端节点所在机架随机选择一个节点作为第1个节点， NetworkTopology类的contains函数，contains函数通 然后将这个节点的信息传给ReplicationTargetChoos- 过判断客户端所在根节点与集群的根节点是否一致 erchooser类中的chooseTargrt函数，且将这个节点的 来判断客户端是否在集群中. 信息记录在ReplicationTargetChooserchooser类中的一 2)如果客户端是集群中的一个节点，则调用 个DatanodeDescriptor类型的数组results中. ReplicationTargetChooser类的chooseLocalNode函数 4)如果客户端不是集群中的节点，则使用Rep 来尝试选择客户端节点作为第1个节点： licationTargetChooser类的chooseRandom函数在集群 3)客户端存储尝试失败时则调用Replication Tar- 中随机选择一个节点作为第1个节点，且将这个选
储的这一数据块及其所有副本都会丢失．因此，Ｈｄｆｓ 对任意一数据块不在同一个节点上放置多个副本，而 是将副本尽可能分散存放［８⁃９］ ．图 ２ 给出了 Ｈｄｆｓ 默认 的副本放置策略流程，其中标注了本文所实现的对副 本放置策略的改进工作，Ｈｄｆｓ 默认的副本放置策略选 择 ３ 个节点，可以选择多个节点放置副本． 图 ２ 默认副本放置策略 Ｆｉｇ．２ Ｔｈｅ ｆｌｏｗｃｈａｒｔ ｏｆ ｄｅｆａｕｌｔ ｒｅｐｌｉｃａ ｐｌａｃｅｍｅｎｔ １）ＨｄＦｓ 副本放置策略是调用 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔ⁃ Ｃｈｏｏｓｅｒ 类的 ｃｈｏｏｓｅＴａｒｇｒｔ 函数来实现的．开始使用 ＮｅｔｗｏｒｋＴｏｐｏｌｏｇｙ 类的 ｃｏｎｔａｉｎｓ 函数，ｃｏｎｔａｉｎｓ 函数通 过判断客户端所在根节点与集群的根节点是否一致 来判断客户端是否在集群中． ２）如果客户端是集群中的一个节点，则调用 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 类的 ｃｈｏｏｓｅＬｏｃａｌＮｏｄｅ 函数 来尝试选择客户端节点作为第 １ 个节点． ３）客户端存储尝试失败时则调用 ＲｅｐｌｉｃａｔｉｏｎＴａｒ⁃ ｇｅｔＣｈｏｏｓｅｒｃｈｏｏｓｅｒ 类的 ｃｈｏｏｓｅＬｏｃａｌＲａｃｋ 函数，在客户 端节点所在机架随机选择一个节点作为第 １ 个节点， 然后将这个节点的信息传给 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓ⁃ ｅｒｃｈｏｏｓｅｒ 类中的 ｃｈｏｏｓｅＴａｒｇｒｔ 函数，且将这个节点的 信息记录在 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒｃｈｏｏｓｅｒ 类中的一 个 ＤａｔａｎｏｄｅＤｅｓｃｒｉｐｔｏｒ 类型的数组 ｒｅｓｕｌｔｓ 中． ４）如果客户端不是集群中的节点，则使用 Ｒｅｐ⁃ ｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 类的 ｃｈｏｏｓｅＲａｎｄｏｍ 函数在集群 中随机选择一个节点作为第 １ 个节点，且将这个选 第 ６ 期 邵秀丽，等：Ｈａｄｏｏｐ 副本放置策略 ·４９１·
·492 智能系统学报 第8卷 择的节点记录在数组results中. 空闲的节点，从而达到重新分配数据块的目的，最终 5)ReplicationTargetChooser chooseRemot- 达到整个集群的数据块分布均衡.在数据块重新分 eRack函数在第1个节点的远程机架上随机选择一 配的过程中，均衡器会尽量将一个数据块的复本分 个节点作为第2个节点.如果在远程机架上选择节 散到不同机架，以提高数据块的冗余，降低数据损坏 点失败，则使用ReplicationTargetChooser类的choos- 的可能性， eLocalRack函数在第1个节点的本地机架上随机选 Hdfs集群的管理员决定是否启动均衡器，启动 择一个节点作为第2个节点.将第2个节点记录在 后，会根据管理员设定的阀值来对集群进行均衡处 ReplicationTargetChooserchooser DatanodeDescriptor 理.阀值是每个节点的使用率（该节点上已经使用的 下的数组results中. 空间和节点的空间容量之间的比值)和集群的使用 6)选择第3个节点，如果前2个节点是在同一 率（集群中已使用的空间和集群的空间容量之间的 个机架上，则使用ReplicationTargetChooser类的 比值)之间的差值，默认的阀值是10%，管理员在启 chooseRemoteRack函数在前2个节点的远程机架上 动均衡器的时候，可以指定阀值的大小.在任何时 选择一个节点.如果所选择的前2个节点并不在同 刻，集群中只能运行一个均衡器 一个机架上面，则使用ReplicationTargetChooser类的 均衡器虽然可以解决数据块分布不均衡的问 chooseLocalRack函数在第2个节点的本地机架上随 题，但是存在着明显的问题： 机选择一个节点作为第3个节点，且存储第3个节 1)均衡器对于集群数据块均衡的调节具有滞 点信息在数组results中. 后性，它必须要在系统的不均衡状况超过阀值之后， 7)最终将results中的所有节点返回给副本选 才会进行调节 择函数的调用者 2)均衡器的运行和数据块的移动需要耗费一 2.2Hdfs副本放置策略的缺陷 定的资源，很可能一个数据块刚刚写入到集群中，就 Hfs默认副本放置策略综合考虑了多方面的 因为均衡性而被移动，这种情况下集群的资源使用 因素，在可靠性、读写效率，负载均衡方面都做了一 是很低效的， 定的权衡，是一个比较优秀的副本放置策略，但 3Hdfs副本放置策略的改进 Hdfs采用随机选择的副本放置策略.该策略没有考 虑到节点负载的情况，在数据均衡方面比较薄弱，这 Hds默认的副本放置策略存在的不足，以及 使数据损坏时需要恢复的数据块数量可能会很多， Hdfs提供的均衡器存在一些不尽人意的地方，本文 数据读取的速度会受到影响等问题 提出了对其改进的低使用率优先(low rate first)副 针对这一问题，Hdfs提供了解决方案一均衡 本放置策略， 器o.均衡器(balancer)是一个Hds的守护进程，启 3.1改进副本放置的流程 动之后，它会将数据块从负载较高的节点移到相对 图3是副本放置改进策略的流程. 判断本节点使用率 尝试选择本节点 与集群使用率的差 作为第1个节点 client是 是否高于阈值 datanode Y 开始选择 失败 成功 第1个节点 选择集群中使用率 选择本地节点为 client不是 最低的节点作为第 datanode 1个节点 第1个节点 尝试选择与第1个 选择该节点为第 节点不同机架并且 剩余节点选择在集 且使用率最低的节 成功 2个节点 群中使用率最低的 点作为第2个节点 在本机架选择使用 节点 远程机架无合适 率最低的节点作为 节点或者无远程机架 第2个节点 图3基于3副本放置策略的改进 Fig.3 The improved placement strategy based on three replicas 1)考虑到数据写入带宽问题，依然在客户端所 在的节点上写入第1个副本，但考虑了该节点的负载
择的节点记录在数组 ｒｅｓｕｌｔｓ 中． ５） ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 类 的 ｃｈｏｏｓｅＲｅｍｏｔ⁃ ｅＲａｃｋ 函数在第 １ 个节点的远程机架上随机选择一 个节点作为第 ２ 个节点．如果在远程机架上选择节 点失败，则使用 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 类的 ｃｈｏｏｓ⁃ ｅＬｏｃａｌＲａｃｋ 函数在第 １ 个节点的本地机架上随机选 择一个节点作为第 ２ 个节点．将第 ２ 个节点记录在 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒｃｈｏｏｓｅｒ 类中 ＤａｔａｎｏｄｅＤｅｓｃｒｉｐｔｏｒ 下的数组 ｒｅｓｕｌｔｓ 中． ６）选择第 ３ 个节点，如果前 ２ 个节点是在同一 个机 架 上， 则 使 用 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 类 的 ｃｈｏｏｓｅＲｅｍｏｔｅＲａｃｋ 函数在前 ２ 个节点的远程机架上 选择一个节点．如果所选择的前 ２ 个节点并不在同 一个机架上面，则使用 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 类的 ｃｈｏｏｓｅＬｏｃａｌＲａｃｋ 函数在第 ２ 个节点的本地机架上随 机选择一个节点作为第 ３ 个节点，且存储第 ３ 个节 点信息在数组 ｒｅｓｕｌｔｓ 中． ７）最终将 ｒｅｓｕｌｔｓ 中的所有节点返回给副本选 择函数的调用者． ２．２ Ｈｄｆｓ 副本放置策略的缺陷 Ｈｄｆｓ 默认副本放置策略综合考虑了多方面的 因素，在可靠性、读写效率，负载均衡方面都做了一 定的权衡， 是一个比较优秀的副本放置策略， 但 Ｈｄｆｓ 采用随机选择的副本放置策略．该策略没有考 虑到节点负载的情况，在数据均衡方面比较薄弱，这 使数据损坏时需要恢复的数据块数量可能会很多， 数据读取的速度会受到影响等问题． 针对这一问题，Ｈｄｆｓ 提供了解决方案———均衡 器［１０］ ．均衡器（ｂａｌａｎｃｅｒ）是一个 Ｈｄｆｓ 的守护进程，启 动之后，它会将数据块从负载较高的节点移到相对 空闲的节点，从而达到重新分配数据块的目的，最终 达到整个集群的数据块分布均衡．在数据块重新分 配的过程中，均衡器会尽量将一个数据块的复本分 散到不同机架，以提高数据块的冗余，降低数据损坏 的可能性． Ｈｄｆｓ 集群的管理员决定是否启动均衡器，启动 后，会根据管理员设定的阀值来对集群进行均衡处 理．阀值是每个节点的使用率（该节点上已经使用的 空间和节点的空间容量之间的比值）和集群的使用 率（集群中已使用的空间和集群的空间容量之间的 比值）之间的差值，默认的阀值是 １０％，管理员在启 动均衡器的时候，可以指定阀值的大小．在任何时 刻，集群中只能运行一个均衡器． 均衡器虽然可以解决数据块分布不均衡的问 题，但是存在着明显的问题： １）均衡器对于集群数据块均衡的调节具有滞 后性，它必须要在系统的不均衡状况超过阀值之后， 才会进行调节． ２）均衡器的运行和数据块的移动需要耗费一 定的资源，很可能一个数据块刚刚写入到集群中，就 因为均衡性而被移动，这种情况下集群的资源使用 是很低效的． ３ Ｈｄｆｓ 副本放置策略的改进 Ｈｄｆｓ 默认的副本放置策略存在的不足，以及 Ｈｄｆｓ 提供的均衡器存在一些不尽人意的地方，本文 提出了对其改进的低使用率优先（ ｌｏｗ ｒａｔｅ ｆｉｒｓｔ） 副 本放置策略． ３．１ 改进副本放置的流程 图 ３ 是副本放置改进策略的流程． 图 ３ 基于 ３ 副本放置策略的改进 Ｆｉｇ．３ Ｔｈｅ ｉｍｐｒｏｖｅｄ ｐｌａｃｅｍｅｎｔ ｓｔｒａｔｅｇｙ ｂａｓｅｄ ｏｎ ｔｈｒｅｅ ｒｅｐｌｉｃａｓ １）考虑到数据写入带宽问题，依然在客户端所 在的节点上写入第 １ 个副本，但考虑了该节点的负载 ·４９２· 智 能 系 统 学 报 第 ８ 卷
第6期 邵秀丽，等：Hadoop副本放置策略 ·493. 情况，即如果本地节点的负载超过了管理员指定的阀 尽管当发生故障时，此策略会影响恢复数据速 值，则选择集群中使用率较低的节点来放置副本」 度，而且每存储一个副本时都需要调用函数获取节点 2)除第1个副本在阀值满足的情况下放在本 信息，并判断该节点是否可以存储副本，这会降低运 地节点上之外，其余所有的副本放置位置的选择，都 行速度及安全性.但考虑到Hds默认放置策略的副本 是采用优先选择集群中比较空闲的节点的方式，以 放置的最终状态很难被控制，它在数据均衡方面的缺 避免在负载较高的节点上继续存储数据， 点比较明显，而这会带来一系列的问题，比如数据损 3)为提高数据块的冗余，尽可能地将数据存储 坏时需要恢复的数据块数量可能会有很多，数据读取 在至少2个机架上，本地机架上存储第1个副本，第 的速度可能会受到影响等因素，本文提出的对于Hfs 2个副本选择与第1个节点不同的机架进行存储因 默认副本放置策略的改进方法有相对优势. 为Hds是一次写入、多次读取的设计思想，在数据 3.2改进策略实现的核心类 写入的时候穿越多个机架，虽然写人带宽可能会有 副本放置改进策略会优先考虑在使用率比较低 所降低，但是提高了集群的数据块分布均衡，有利于 的节点上放置数据，这通过对Hs中负责副本放置 文件的读取和程序的运行 节点选择的类ReplicationTargetChooser的改进来完 4)为提高数据的冗余，保持每个节点只存储一 成：该类在Hdfs中的作用是当有新增数据块或数据 个副本的规则.Hfs的默认副本放置策略是一个节 块位置变动的时候，NameNode会调用该类来确定数 点最多放置一个副本，如果副本的数量超过节点的 据块放置的位置.ReplicationTargetChooser类使用 总数，则集群中最多只放置与节点同样数目的副本 chooseTarget函数来选择副本放置的节点，图4描述 低使用率优先的放置策略依然坚持这个原则，每个 了放置k个副本重写chooseTarget函数来实现的策 节点最多只放置一个副本 略改进。 初始化阶段 获取集群中所有的 根据数据DN 设置副本的数目不超过集群 DataNode节点信息 中的信息计算 规模 并将其存储在数组 Usage 设置本地节点阀值 DN中 定义存储所有节点的数组DN 判断客户端是否为集群中 定义存储选择的节点的数组 的DataNode Cdn y 定义集群整体使用率Usage 获取本地节点Ldn 判断其使用率与 是否只有 Y 选择DN中使用 选择Ldn作为第1个副本 Usage的差值是否 1个机架 率最低的k个节 放置节点 小于阀值标记 点加入Cdn中 Lowdn为Ldn N N 在DN中选择使用率 将dn,从DN中移除，加入到Cdn中 最小的DataNodef作 为第1个副本放置的 是否只有 节点，标记为dn, 1个机架 在DN中选择使用率最小的且与 N 选择DN中使 Y dn,不在同一个机架上的节点作 用率最低的 为第2个副本放置的节点将该几 选择DN中使用率 k-2个节点加 点从DN中移除，加入到Cdn中 最低的k-1个节点 入到Cdn中 加入到cdn中 返回Cdn中的 结果 图4基于K副本放置策略的改进 Fig.4 The improved placement strategy based on K replicas I)函数的初始化阶段：首先调用NetworkTopology 2)管理员可设置本地节点阀值，默认值为01， 类中的get NumOfLeaves函数来获取集群的大小，控制 改进后的Hfs在配置文件中为用户设置阀值提供 副本数目不超过集群的大小，如果设置的副本的数目 了接口，在Hdfs.xml文件中可以通过为dfs.replica- 超过集群的大小，则设置副本数目为集群大小 tion.threshold设置值来实现阀值的控制，阀值的范
情况，即如果本地节点的负载超过了管理员指定的阀 值，则选择集群中使用率较低的节点来放置副本． ２）除第 １ 个副本在阀值满足的情况下放在本 地节点上之外，其余所有的副本放置位置的选择，都 是采用优先选择集群中比较空闲的节点的方式，以 避免在负载较高的节点上继续存储数据． ３）为提高数据块的冗余，尽可能地将数据存储 在至少 ２ 个机架上，本地机架上存储第 １ 个副本，第 ２ 个副本选择与第 １ 个节点不同的机架进行存储．因 为 Ｈｄｆｓ 是一次写入、多次读取的设计思想，在数据 写入的时候穿越多个机架，虽然写入带宽可能会有 所降低，但是提高了集群的数据块分布均衡，有利于 文件的读取和程序的运行． ４）为提高数据的冗余，保持每个节点只存储一 个副本的规则．Ｈｄｆｓ 的默认副本放置策略是一个节 点最多放置一个副本，如果副本的数量超过节点的 总数，则集群中最多只放置与节点同样数目的副本． 低使用率优先的放置策略依然坚持这个原则，每个 节点最多只放置一个副本． 尽管当发生故障时，此策略会影响恢复数据速 度，而且每存储一个副本时都需要调用函数获取节点 信息，并判断该节点是否可以存储副本，这会降低运 行速度及安全性．但考虑到 Ｈｄｆｓ 默认放置策略的副本 放置的最终状态很难被控制，它在数据均衡方面的缺 点比较明显，而这会带来一系列的问题，比如数据损 坏时需要恢复的数据块数量可能会有很多，数据读取 的速度可能会受到影响等因素，本文提出的对于 Ｈｄｆｓ 默认副本放置策略的改进方法有相对优势． ３．２ 改进策略实现的核心类 副本放置改进策略会优先考虑在使用率比较低 的节点上放置数据，这通过对 Ｈｄｆｓ 中负责副本放置 节点选择的类 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 的改进来完 成；该类在 Ｈｄｆｓ 中的作用是当有新增数据块或数据 块位置变动的时候，ＮａｍｅＮｏｄｅ 会调用该类来确定数 据块放置的位 置． ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 类 使 用 ｃｈｏｏｓｅＴａｒｇｅｔ 函数来选择副本放置的节点，图 ４ 描述 了放置 ｋ 个副本重写 ｃｈｏｏｓｅＴａｒｇｅｔ 函数来实现的策 略改进． 图 ４ 基于 Ｋ 副本放置策略的改进 Ｆｉｇ．４ Ｔｈｅ ｉｍｐｒｏｖｅｄ ｐｌａｃｅｍｅｎｔ ｓｔｒａｔｅｇｙ ｂａｓｅｄ ｏｎ Ｋ ｒｅｐｌｉｃａｓ １）函数的初始化阶段：首先调用 ＮｅｔｗｏｒｋＴｏｐｏｌｏｇｙ 类中的 ｇｅｔＮｕｍＯｆＬｅａｖｅｓ 函数来获取集群的大小，控制 副本数目不超过集群的大小，如果设置的副本的数目 超过集群的大小，则设置副本数目为集群大小． ２）管理员可设置本地节点阀值，默认值为 ０．１， 改进后的 Ｈｄｆｓ 在配置文件中为用户设置阀值提供 了接口，在 Ｈｄｆｓ． ｘｍｌ 文件中可以通过为 ｄｆｓ．ｒｅｐｌｉｃａ⁃ ｔｉｏｎ．ｔｈｒｅｓｈｏｌｄ 设置值来实现阀值的控制，阀值的范 第 ６ 期 邵秀丽，等：Ｈａｄｏｏｐ 副本放置策略 ·４９３·
·494. 智能系统学报 第8卷 围在0~1,0表示本地节点的使用率必须小于等于 节点作为第1个副本放置的节点选择第1个节点 集群的使用率才会在本地节点上放置数据块的副 后，将其从DN中移除，加入到results数组中. 本：1表示不考虑使用率，一定要在本地节点上放置 9)在选择第2个节点的时候，在DN中选择使 数据块的副本」 用率最小的节点，然后使用Network Topology类的 3)使用Configuration类的getFloat函数配置文 isOnSameRack函数判断它与选取的第1个节点是 件中的阀值.但如果用户没有设置阀值或者设置的 否在相同的机架上.如果这2个节点不在一个机架 阀值不合理，chooseTarget函数依然使用默认阀值进 上，则选择这个节点作为第2个副本存放的节点，否 行副本的选择. 则，重新选择DN中其他节点中使用率最小的节点， 4)在重写的chooseTarget函数中需定义一个 直到找到这样的节点为止.选择第2个节点之后，将 DataNodeDescriptor类型的数组DN来存储全部节点 其从记录未被选择节点的数组DN中移除，加入到 的信息，DataNodeDescriptor是Hds中用于描述Da- 记录已选择节点的数组results中. taNode信息的类，chooseTarget函数可以通过操纵 10)继续上述步骤选择其他节点， DataNodeDescriptor的对象来获取一个节点的信息， 11)函数执行过程中，使用java中的ty来尝试 包括节点D、节点名称、节点全部存储空间和节点 运行，若chooseTarget函数的运行没有出现异常，则 已经使用的存储空间等.另外，还需定义DataNode- 最终将存储已选择节点的数组results返回给函数 Descriptor类型的数组results来存储已选择的节点， 的调用者若执行过程中出现不可处理的异常，则在 同时定义集群的存储空间使用率Usage。 catch语句中处理异常，返回客户端节点 5)使用NetworkTopology类中的getLeaf函数可 4 实验结果与分析 以获取集群中所有节点的信息，将返回的所有节点 信息存储在数组DN中，然后可以根据DN中的信 为了比较Hdfs默认的和本文改进的副本放置策 息计算集群的整体存储空间的使用率Usage.在获取 略，本文实现了由2部分组成的测试程序：1)负责模 所有节点信息之后，并不对数组DN进行任何处理， 拟一个节点运行的DataNode类，该类记录了模拟节 比如排序、建堆等.虽然考虑到后面的算法中需要多 点的惟一标识、容量、使用量、数据块数量以及机架标 次取得DN中使用率最小的节点，但考虑客户端和 识：2)模拟系统运行的NameNode类，包括对于Data- 不同机架，因此该问题又与经典TopK问题相似且 Node的初始化、设置阀值、设置副本放置策略和数据 稍有不同.一般副本个数K默认为3，如果在客户端 写入等内容的模拟.在模拟的过程中，并不进行真实 上放置一个副本，选择另外2个副本的计算复杂度 的数据的读写，只是对于数据读写后的结果进行模拟 为0(2N-3) 记录.在NameNode类中初始化所有的节点，每个节点 6)初始化后选择节点，先通过Hdfs调用choos 初始的容量是1T,used和block Num被设置为0.该程 eTarget函数，使用Network Topolog类中的contains 序模拟写入过程，设置写人数据块的大小和模拟数据 函数判断客户端节点是否在集群中，如果不在，则不 的分块对于每一个划分的数据块，程序运行相应的 在客户端上放置副本.否则还需进一步判断客户端 副本放置策略函数，选择3个节点用于放置划分的数 节点的使用率与集群使用率的差值，如果差值小于 据块.然后循环处理直到数据块的写人完成， 阀值，则在客户端上放置第1个副本，否则不在客户 写入所有数据后，可根据模拟节点的使用情况 端上放置副本.使用ReplicationTargetChooser类的is 计算不同的副本放置策略的数据存储均衡性.本文 GoodTarget判断客户端节点是否可用，才能确定是 使用标准差来衡量副本放置的均衡性，所使用的数 否在客户端节点上放置一个数据块。 据是所有DataNode的使用率，也就是每个节点的使 7)如果客户端不可用，则在DN中选择使用率 用容量used与总容量capacity之间的比值.设集群 最低的节点来尝试放置副本，如节点不可用，则将该 中一共有n个节点，所有节点的使用率分别为X1, 节点标记为暂时不可选择，然后继续在其他节点中 X2,Xn-1,X。.节点使用率的平均值X=（X,+ 选择一个使用率最低的节点，直到选择到合适的节 点为止 ++X从)/n,标准差c=,含(X-X0、 8)机架数目对副本放置节点的算法有一定的影 本文实验一测试了机架数目对于算法的影响， 响，使用NetworkTopology类的get NumOfRacks函数来 分别使用默认的策略和改进后的策略，模拟测试在 获取机架的数目，则在DN中选择一个使用率最小的 500个节点上写入大小不同的数据后，系统的存储
围在 ０～１，０ 表示本地节点的使用率必须小于等于 集群的使用率才会在本地节点上放置数据块的副 本；１ 表示不考虑使用率，一定要在本地节点上放置 数据块的副本． ３）使用 Ｃｏｎｆｉｇｕｒａｔｉｏｎ 类的 ｇｅｔＦｌｏａｔ 函数配置文 件中的阀值．但如果用户没有设置阀值或者设置的 阀值不合理，ｃｈｏｏｓｅＴａｒｇｅｔ 函数依然使用默认阀值进 行副本的选择． ４） 在重写的 ｃｈｏｏｓｅＴａｒｇｅｔ 函数中需定义一个 ＤａｔａＮｏｄｅＤｅｓｃｒｉｐｔｏｒ 类型的数组 ＤＮ 来存储全部节点 的信息，ＤａｔａＮｏｄｅＤｅｓｃｒｉｐｔｏｒ 是 Ｈｄｆｓ 中用于描述 Ｄａ⁃ ｔａＮｏｄｅ 信息的类， ｃｈｏｏｓｅＴａｒｇｅｔ 函数可以通过操纵 ＤａｔａＮｏｄｅＤｅｓｃｒｉｐｔｏｒ 的对象来获取一个节点的信息， 包括节点 ＩＤ、节点名称、节点全部存储空间和节点 已经使用的存储空间等．另外，还需定义 ＤａｔａＮｏｄｅ⁃ Ｄｅｓｃｒｉｐｔｏｒ 类型的数组 ｒｅｓｕｌｔｓ 来存储已选择的节点， 同时定义集群的存储空间使用率 Ｕｓａｇｅ． ５）使用 ＮｅｔｗｏｒｋＴｏｐｏｌｏｇｙ 类中的 ｇｅｔＬｅａｆ 函数可 以获取集群中所有节点的信息，将返回的所有节点 信息存储在数组 ＤＮ 中，然后可以根据 ＤＮ 中的信 息计算集群的整体存储空间的使用率 Ｕｓａｇｅ．在获取 所有节点信息之后，并不对数组 ＤＮ 进行任何处理， 比如排序、建堆等．虽然考虑到后面的算法中需要多 次取得 ＤＮ 中使用率最小的节点，但考虑客户端和 不同机架，因此该问题又与经典 ＴｏｐＫ 问题相似且 稍有不同．一般副本个数 Ｋ 默认为 ３，如果在客户端 上放置一个副本，选择另外 ２ 个副本的计算复杂度 为 Ｏ（２Ｎ －３）． ６）初始化后选择节点，先通过 Ｈｄｆｓ 调用 ｃｈｏｏｓ⁃ ｅＴａｒｇｅｔ 函数，使用 ＮｅｔｗｏｒｋＴｏｐｏｌｏｇｙ 类中的 ｃｏｎｔａｉｎｓ 函数判断客户端节点是否在集群中，如果不在，则不 在客户端上放置副本．否则还需进一步判断客户端 节点的使用率与集群使用率的差值，如果差值小于 阀值，则在客户端上放置第 １ 个副本，否则不在客户 端上放置副本．使用 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 类的 ｉｓ⁃ ＧｏｏｄＴａｒｇｅｔ 判断客户端节点是否可用，才能确定是 否在客户端节点上放置一个数据块． ７）如果客户端不可用，则在 ＤＮ 中选择使用率 最低的节点来尝试放置副本，如节点不可用，则将该 节点标记为暂时不可选择，然后继续在其他节点中 选择一个使用率最低的节点，直到选择到合适的节 点为止． ８）机架数目对副本放置节点的算法有一定的影 响，使用 ＮｅｔｗｏｒｋＴｏｐｏｌｏｇｙ 类的 ｇｅｔＮｕｍＯｆＲａｃｋｓ 函数来 获取机架的数目，则在 ＤＮ 中选择一个使用率最小的 节点作为第 １ 个副本放置的节点．选择第 １ 个节点 后，将其从 ＤＮ 中移除，加入到 ｒｅｓｕｌｔｓ 数组中． ９）在选择第 ２ 个节点的时候，在 ＤＮ 中选择使 用率最小的节点，然后使用 ＮｅｔｗｏｒｋＴｏｐｏｌｏｇｙ 类的 ｉｓＯｎＳａｍｅＲａｃｋ 函数判断它与选取的第 １ 个节点是 否在相同的机架上．如果这 ２ 个节点不在一个机架 上，则选择这个节点作为第 ２ 个副本存放的节点，否 则，重新选择 ＤＮ 中其他节点中使用率最小的节点， 直到找到这样的节点为止．选择第 ２ 个节点之后，将 其从记录未被选择节点的数组 ＤＮ 中移除，加入到 记录已选择节点的数组 ｒｅｓｕｌｔｓ 中． １０）继续上述步骤选择其他节点． １１）函数执行过程中，使用 ｊａｖａ 中的 ｔｒｙ 来尝试 运行，若 ｃｈｏｏｓｅＴａｒｇｅｔ 函数的运行没有出现异常，则 最终将存储已选择节点的数组 ｒｅｓｕｌｔｓ 返回给函数 的调用者．若执行过程中出现不可处理的异常，则在 ｃａｔｃｈ 语句中处理异常，返回客户端节点． ４ 实验结果与分析 为了比较 Ｈｄｆｓ 默认的和本文改进的副本放置策 略，本文实现了由 ２ 部分组成的测试程序：１）负责模 拟一个节点运行的 ＤａｔａＮｏｄｅ 类，该类记录了模拟节 点的惟一标识、容量、使用量、数据块数量以及机架标 识；２）模拟系统运行的 ＮａｍｅＮｏｄｅ 类，包括对于 Ｄａｔａ⁃ Ｎｏｄｅ 的初始化、设置阀值、设置副本放置策略和数据 写入等内容的模拟．在模拟的过程中，并不进行真实 的数据的读写，只是对于数据读写后的结果进行模拟 记录．在 ＮａｍｅＮｏｄｅ 类中初始化所有的节点，每个节点 初始的容量是 １ Ｔ，ｕｓｅｄ 和 ｂｌｏｃｋＮｕｍ 被设置为 ０．该程 序模拟写入过程，设置写入数据块的大小和模拟数据 的分块．对于每一个划分的数据块，程序运行相应的 副本放置策略函数，选择 ３ 个节点用于放置划分的数 据块．然后循环处理直到数据块的写入完成． 写入所有数据后，可根据模拟节点的使用情况 计算不同的副本放置策略的数据存储均衡性．本文 使用标准差来衡量副本放置的均衡性，所使用的数 据是所有 ＤａｔａＮｏｄｅ 的使用率，也就是每个节点的使 用容量 ｕｓｅｄ 与总容量 ｃａｐａｃｉｔｙ 之间的比值． 设集群 中一共有 ｎ 个节点，所有节点的使用率分别为 Ｘ１ ， Ｘ２ ，．．．，Ｘｎ －１ ， Ｘｎ ． 节 点 使 用 率 的 平 均 值 Ｘ － ＝ （ Ｘ１ ＋ Ｘ２ ＋…＋Ｘｎ－１ ＋Ｘｎ ） ／ ｎ，标准差 σ＝ １ ｎ ∑ ｎ ｉ ＝ １ （Ｘｉ －Ｘ － ） ２ ． 本文实验一测试了机架数目对于算法的影响， 分别使用默认的策略和改进后的策略，模拟测试在 ５００ 个节点上写入大小不同的数据后，系统的存储 ·４９４· 智 能 系 统 学 报 第 ８ 卷
第6期 邵秀丽，等：Hadoop副本放置策略 ·495. 均衡情况，写入文件大小为100G条件下的节点使 中，从而增加了时间和空间的开销.另外要计算集群 用率的标准差 的整体使用率与选择集群中使用率较小的节点，增 从图5中可以看出，对于默认的副本放置策略， 加了线性的开销. 机架数目在3个以内的时候，机架的个数对于系统 的均衡性会有一定的影响，但是差别在0.02%以内. 5结束语 当机架数目超过3个以后，机架数目对于系统均衡 本文基于节点存储率对Hs中负责副本放置 性的影响会在0.005%以内.而对于改进后的副本放 节点选择的类ReplicationTargetChooser进行了改进， 置策略，机架的数目对于集群的均衡性影响会变得 并部署了简单实际环境进行了实验，由于其实际环 更小，在0.002%以内.所以，机架的个数对于2种副 境受物理设备和其他异构条件等各种客观因素的影 本放置策略的影响都很小通过图5可以看出，改进 响不大，所以，本文所提方案提高了Hs的数据块 后的副本放置策略受到的影响更小，在不同机架个 放置的均衡性.但本文所提出的副本放置策略，关注 数情况下，都有更好的均衡性， 的主要是集群中数据块副本放置的均衡性，所考虑 的因素主要是节点的使用率，而没有考虑节点使用 s0.448 ·默认策略 的价格、安全性、处理速度等。 0.447 一改进策略 参考文献： 0.445 [1]KO B J.Scalable service differentiation in a shared storage 0.444 护 12345678910 cache[C]//Proc of the 23rd International Conference on 机架数目/个 Distributed Computing Systems.Washington,DC,USA, 图5机架数目对于算法的影响 2003:184-194. Fig.5 The impact of the algorithm based [2]CHEN Yan.SCAN:a dynamic,scalable,and efficient con- on the number of rack tent distribution network [C]//Proceedings of the Interna- 实验二测试随着写入数据的增加，不同副本放 tional Conference on Pervasive Computing.Zurich,Switzer- 置策略下集群存储的均衡性.实验选择在500个节 land,2002:282-286. 点、5个机架的条件下，分别使用默认的副本放置策 [3]KORUPOLU M R.Placement algorithms for hierarchical co- 略和改进后的副本放置策略，写入1G、10G、 operative caching[C//Proceedings of the Tenth Annual 100G、1T、10T和100T的数据，测试集群的副本 ACM-SIAM Symposium on Discrete Algorithms.PA,USA, 均衡情况. 1999:586-595. 根据图6显示，使用改进后的副本放置策略进 [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 Sym- 显好于使用默认的副本放置策略，在数据量比较小 posium on Theory of Computing.CA,USA,1997:654-663. 的时候这种优势还不太明显，但是在数据量比较大 [5]BORTHAKUR D.The hadoop distributed file system:archi- 的时候，改进后的策略的好处就会更加明显.可见， tecture and design EB/OL].[2012-11-08 ]http://ha- 改进后的副本放置策略，在数据块的均衡性方面有 doop.apache.org/core/docs. 更加良好的表现 [6]GUY L,LAURE E,STOCKINGER H,et al.Replica man- 学5r agement in data grids,GGF5[R].Global Grid Information Document,2002. ·默认策略 2 ·改进策咯 [7]STONEBRAKER M,ABADI D J,De WITT D J,et al.Ma- 王 pReduce and parallel DBMSs:friends or foes[J].Commu- 1 nication of the ACM,2010,53(1):64-71. 0 101021010310 [8]魏青松，卢显良，侯孟书.AdpReplica:自适应副本管理机 写入数据大小VG 制[J].计算机科学，2004,31(12)：34-36. 图6存储数据量对于算法的影响 WEI Qingsong,LU Xianliang,HOU Mengshu.AdpRePli- Fig.6 The impact of the algorithm based on ca:adaptive replica management mechanism J.Computer Science,2004,31(12):34-36. 本文提出的放置策略需获取集群中所有节点 [9]杨曙锋.分布式并行文件系统的副本管理策略[D].成 的信息，且将其存储在一个DataNodeDescriptor数组 都：电子科技大学，2003：23-31
均衡情况，写入文件大小为 １００ Ｇ 条件下的节点使 用率的标准差． 从图 ５ 中可以看出，对于默认的副本放置策略， 机架数目在 ３ 个以内的时候，机架的个数对于系统 的均衡性会有一定的影响，但是差别在 ０．０２％以内． 当机架数目超过 ３ 个以后，机架数目对于系统均衡 性的影响会在 ０．００５％以内．而对于改进后的副本放 置策略，机架的数目对于集群的均衡性影响会变得 更小，在 ０．００２％以内．所以，机架的个数对于 ２ 种副 本放置策略的影响都很小．通过图 ５ 可以看出，改进 后的副本放置策略受到的影响更小，在不同机架个 数情况下，都有更好的均衡性． 图 ５ 机架数目对于算法的影响 Ｆｉｇ．５ Ｔｈｅ ｉｍｐａｃｔ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｒａｃｋ 实验二测试随着写入数据的增加，不同副本放 置策略下集群存储的均衡性．实验选择在 ５００ 个节 点、５ 个机架的条件下，分别使用默认的副本放置策 略和改 进 后 的 副 本 放 置 策 略， 写 入 １ Ｇ、 １０ Ｇ、 １００ Ｇ、１ Ｔ、１０ Ｔ 和 １００ Ｔ 的数据，测试集群的副本 均衡情况． 根据图 ６ 显示，使用改进后的副本放置策略进 行副本放置位置的选择，集群中数据块的均衡性明 显好于使用默认的副本放置策略，在数据量比较小 的时候这种优势还不太明显，但是在数据量比较大 的时候，改进后的策略的好处就会更加明显．可见， 改进后的副本放置策略，在数据块的均衡性方面有 更加良好的表现． 图 ６ 存储数据量对于算法的影响 Ｆｉｇ．６ Ｔｈｅ ｉｍｐａｃｔ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ 本文提出的放置策略需获取集群中所有节点 的信息，且将其存储在一个 ＤａｔａＮｏｄｅＤｅｓｃｒｉｐｔｏｒ 数组 中，从而增加了时间和空间的开销．另外要计算集群 的整体使用率与选择集群中使用率较小的节点，增 加了线性的开销． ５ 结束语 本文基于节点存储率对 Ｈｄｆｓ 中负责副本放置 节点选择的类 ＲｅｐｌｉｃａｔｉｏｎＴａｒｇｅｔＣｈｏｏｓｅｒ 进行了改进， 并部署了简单实际环境进行了实验，由于其实际环 境受物理设备和其他异构条件等各种客观因素的影 响不大，所以，本文所提方案提高了 Ｈｄｆｓ 的数据块 放置的均衡性．但本文所提出的副本放置策略，关注 的主要是集群中数据块副本放置的均衡性，所考虑 的因素主要是节点的使用率，而没有考虑节点使用 的价格、安全性、处理速度等． 参考文献： ［１］ＫＯ Ｂ Ｊ． Ｓｃａｌａｂｌｅ ｓｅｒｖｉｃｅ ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ ｉｎ ａ ｓｈａｒｅｄ ｓｔｏｒａｇｅ ｃａｃｈｅ ［ Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ ｔｈｅ ２３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ． Ｗａｓｈｉｎｇｔｏｎ， ＤＣ， ＵＳＡ， ２００３： １８４⁃１９４． ［２］ＣＨＥＮ Ｙａｎ． ＳＣＡＮ： ａ ｄｙｎａｍｉｃ， ｓｃａｌａｂｌｅ， ａｎｄ ｅｆｆｉｃｉｅｎｔ ｃｏｎ⁃ ｔｅｎｔ ｄｉｓｔｒｉｂｕｔｉｏｎ ｎｅｔｗｏｒｋ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｅｒｖａｓｉｖｅ Ｃｏｍｐｕｔｉｎｇ． Ｚüｒｉｃｈ， Ｓｗｉｔｚｅｒ⁃ ｌａｎｄ， ２００２： ２８２⁃２８６． ［３］ＫＯＲＵＰＯＬＵ Ｍ Ｒ． Ｐｌａｃｅｍｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｈｉｅｒａｒｃｈｉｃａｌ ｃｏ⁃ ｏｐｅｒａｔｉｖｅ ｃａｃｈｉｎｇ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｔｅｎｔｈ Ａｎｎｕａｌ ＡＣＭ⁃ＳＩＡＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｄｉｓｃｒｅｔｅ Ａｌｇｏｒｉｔｈｍｓ． ＰＡ， ＵＳＡ， １９９９： ５８６⁃５９５． ［４］ＫＡＲＧＥＲ Ｄ， ＬＥＨＭＡＮ Ｅ， ＬＥＩＧＨＴＯＮ Ｔ， ｅｔ ａｌ． Ｃｏｎｓｉｓｔｅｎｔ ｈａｓｈｉｎｇ ａｎｄ ｒａｎｄｏｍ ｔｒｅｅｓ： ｄｉｓｔｒｉｂｕｔｅｄ ｃａｃｈｉｎｇ ｐｒｏｔｏｃｏｌｓ ｆｏｒ ｒｅｌｉｅｖｉｎｇ ｈｏｔ ｓｐｏｔｓ ｏｎ ｔｈｅ ｗｏｒｌｄ ｗｉｄｅ ｗｅｂ［Ｃ］ ／ ／ ＡＣＭ Ｓｙｍ⁃ ｐｏｓｉｕｍ ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ． ＣＡ， ＵＳＡ， １９９７： ６５４⁃６６３． ［５］ＢＯＲＴＨＡＫＵＲ Ｄ． Ｔｈｅ ｈａｄｏｏｐ ｄｉｓｔｒｉｂｕｔｅｄ ｆｉｌｅ ｓｙｓｔｅｍ： ａｒｃｈｉ⁃ ｔｅｃｔｕｒｅ ａｎｄ ｄｅｓｉｇｎ ［ ＥＢ／ ＯＬ］． ［ ２０１２⁃１１⁃０８］． ｈｔｔｐ： ／ ／ ｈａ⁃ ｄｏｏｐ．ａｐａｃｈｅ．ｏｒｇ ／ ｃｏｒｅ ／ ｄｏｃｓ． ［６］ＧＵＹ Ｌ， ＬＡＵＲＥ Ｅ， ＳＴＯＣＫＩＮＧＥＲ Ｈ，ｅｔ ａｌ． Ｒｅｐｌｉｃａ ｍａｎ⁃ ａｇｅｍｅｎｔ ｉｎ ｄａｔａ ｇｒｉｄｓ， ＧＧＦ５［Ｒ］． Ｇｌｏｂａｌ Ｇｒｉｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｄｏｃｕｍｅｎｔ， ２００２． ［７］ＳＴＯＮＥＢＲＡＫＥＲ Ｍ， ＡＢＡＤＩ Ｄ Ｊ， Ｄｅ ＷＩＴＴ Ｄ Ｊ，ｅｔ ａｌ． Ｍａ⁃ ｐＲｅｄｕｃｅ ａｎｄ ｐａｒａｌｌｅｌ ＤＢＭＳｓ： ｆｒｉｅｎｄｓ ｏｒ ｆｏｅｓ［ Ｊ］． Ｃｏｍｍｕ⁃ ｎｉｃａｔｉｏｎ ｏｆ ｔｈｅ ＡＣＭ， ２０１０， ５３（１）： ６４⁃７１． ［８］魏青松，卢显良，侯孟书． ＡｄｐＲｅｐｌｉｃａ：自适应副本管理机 制［Ｊ］． 计算机科学， ２００４， ３１（１２）： ３４⁃３６． ＷＥＩ Ｑｉｎｇｓｏｎｇ， ＬＵ Ｘｉａｎｌｉａｎｇ， ＨＯＵ Ｍｅｎｇｓｈｕ． ＡｄｐＲｅＰｌｉ⁃ ｃａ： ａｄａｐｔｉｖｅ ｒｅｐｌｉｃａ ｍａｎａｇｅｍｅｎｔ ｍｅｃｈａｎｉｓｍ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２００４， ３１（１２）： ３４⁃３６． ［９］杨曙锋． 分布式并行文件系统的副本管理策略［Ｄ］．成 都：电子科技大学， ２００３： ２３⁃３１． 第 ６ 期 邵秀丽，等：Ｈａｄｏｏｐ 副本放置策略 ·４９５·
·496· 智能系统学报 第8卷 YANG Shufeng.The Copies'management strategy of distrib- 王亚光，女，1988年生，硕士研究 uted parallel file system[D].Chengdu:University of Elec- 生，主要研究方向为网络安全与云计算 tronic Science and Technology of China,2003:23-31. 等发表学术论文2篇。 [10]BORDAWEKAR R,LANDHERR S,CAPPS D,et al.Ex- perimental evaluation of the Hewlett-Packard Exemplar file system C//ACM Sigmetric SPerformance Evaluation Re- view.[S.l.]1997. 李云龙，男，1985年生，硕士研究 作者简介： 生，主要研究方向为软件工程与云计 算发表学术论文3篇 邵秀丽，女，1963年生，教授，博土 生导师，天津市科委授予聘书专家，参 与或主持国家自然科学基金，天津市自 然科学基金、重点工程项目40余项。 获得天津市科学进步奖5项，在国内外 核心刊物上发表文章90余篇， 第11届全球智能控制与自动化大会(WCICA2014) The 11th World Congress on Intelligent Control and Automation(WCICA2014) The 11th World Congress on Intelligent Control and Automation (WCICA 2014)will be held in Shenyang,China, from June 27 to 30,2014.WCICA 2014 is technically sponsored by IEEE Robotics and Automation Society,IEEE Control Systems Society,National Natural Science Foundation of China,the Chinese Association of Automation,and the Chinese Association of Artificial Intelligence. WCICA 2014 features plenary keynotes and plenary panel discussion sessions by the world leading researchers as well as awards to honor outstanding papers presented at this Congress.The awards include Best Paper on Theory,Best Paper on Applications,Best Student Paper,Best Poster Paper,Best Paper on Biomedical Biosystem Related Areas,SUPCON Best Paper on Industrial Automation,and AlAG Best Paper on Supply Chain Related Topics. Moreover,we are in the process to arrange post-conference publication of a selected group of accepted papers at WCI- CA 2014 in more than ten leading international journals and top Chinese journals as special issues,among them are IEEE/ ASME Transactions on Mechatronics,IEEE Transactions on Robotics,IEEE Transactions on Control Systems Technology, IEEE Transactions on Industrial Electronics,IEEE Transactions on Systems,Man,and Cybernetics,Part B,and Acta Automation Sinica. It is our great pleasure to invite you to submit your original research papers to the Congress.WCICA 2014 also wel- comes proposals for organizing Focused Theme Sessions on the conference topics,Tutorials and Workshops on emerging topics.You are invited to submit focused theme session proposals to Prof.Simon X.Yang (syang@uoguelph.ca)before Dec.1,2013.Please refer to the Congress website for details. Website:http://2014.wcica.info/index.shtml. Tel:02483681047-8013. E-mail:weica2014@gmail.com
ＹＡＮＧ Ｓｈｕｆｅｎｇ． Ｔｈｅ Ｃｏｐｉｅｓ’ｍａｎａｇｅｍｅｎｔ ｓｔｒａｔｅｇｙ ｏｆ ｄｉｓｔｒｉｂ⁃ ｕｔｅｄ ｐａｒａｌｌｅｌ ｆｉｌｅ ｓｙｓｔｅｍ［Ｄ］． Ｃｈｅｎｇｄｕ： Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｅｌｅｃ⁃ ｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｃｈｉｎａ， ２００３： ２３⁃３１． ［１０］ＢＯＲＤＡＷＥＫＡＲ Ｒ， ＬＡＮＤＨＥＲＲ Ｓ， ＣＡＰＰＳ Ｄ， ｅｔ ａｌ． Ｅｘ⁃ ｐｅｒｉｍｅｎｔａｌ ｅｖａｌｕａｔｉｏｎ ｏｆ ｔｈｅ Ｈｅｗｌｅｔｔ⁃Ｐａｃｋａｒｄ Ｅｘｅｍｐｌａｒ ｆｉｌｅ ｓｙｓｔｅｍ［Ｃ］ ／ ／ ＡＣＭ Ｓｉｇｍｅｔｒｉｃ ＳＰｅｒｆｏｒｍａｎｃｅ Ｅｖａｌｕａｔｉｏｎ Ｒｅ⁃ ｖｉｅｗ． ［Ｓ．ｌ．］１９９７． 作者简介： 邵秀丽，女，１９６３ 年生，教授，博士 生导师，天津市科委授予聘书专家，参 与或主持国家自然科学基金，天津市自 然科学基金、重点工程项目 ４０ 余项。 获得天津市科学进步奖 ５ 项，在国内外 核心刊物上发表文章 ９０ 余篇． 王亚光，女，１９８８ 年生，硕士研究 生，主要研究方向为网络安全与云计算 等．发表学术论文 ２ 篇． 李云龙，男，１９８５ 年生，硕士研究 生，主要研究方向为软件工程与云计 算．发表学术论文 ３ 篇． 第 １１ 届全球智能控制与自动化大会（ＷＣＩＣＡ２０１４） Ｔｈｅ １１ｔｈ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ ａｎｄ Ａｕｔｏｍａｔｉｏｎ（ＷＣＩＣＡ２０１４） Ｔｈｅ １１ｔｈ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ ａｎｄ Ａｕｔｏｍａｔｉｏｎ （ＷＣＩＣＡ ２０１４） ｗｉｌｌ ｂｅ ｈｅｌｄ ｉｎ Ｓｈｅｎｙａｎｇ， Ｃｈｉｎａ， ｆｒｏｍ Ｊｕｎｅ ２７ ｔｏ ３０， ２０１４． ＷＣＩＣＡ ２０１４ ｉｓ ｔｅｃｈｎｉｃａｌｌｙ ｓｐｏｎｓｏｒｅｄ ｂｙ ＩＥＥＥ Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ Ｓｏｃｉｅｔｙ， ＩＥＥＥ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ Ｓｏｃｉｅｔｙ， Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ， ｔｈｅ Ｃｈｉｎｅｓｅ Ａｓｓｏｃｉａｔｉｏｎ ｏｆ Ａｕｔｏｍａｔｉｏｎ， ａｎｄ ｔｈｅ Ｃｈｉｎｅｓｅ Ａｓｓｏｃｉａｔｉｏｎ ｏｆ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ． ＷＣＩＣＡ ２０１４ ｆｅａｔｕｒｅｓ ｐｌｅｎａｒｙ ｋｅｙｎｏｔｅｓ ａｎｄ ｐｌｅｎａｒｙ ｐａｎｅｌ ｄｉｓｃｕｓｓｉｏｎ ｓｅｓｓｉｏｎｓ ｂｙ ｔｈｅ ｗｏｒｌｄ ｌｅａｄｉｎｇ ｒｅｓｅａｒｃｈｅｒｓ ａｓ ｗｅｌｌ ａｓ ａｗａｒｄｓ ｔｏ ｈｏｎｏｒ ｏｕｔｓｔａｎｄｉｎｇ ｐａｐｅｒｓ ｐｒｅｓｅｎｔｅｄ ａｔ ｔｈｉｓ Ｃｏｎｇｒｅｓｓ． Ｔｈｅ ａｗａｒｄｓ ｉｎｃｌｕｄｅ Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ｔｈｅｏｒｙ， Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ａｐｐｌｉｃａｔｉｏｎｓ， Ｂｅｓｔ Ｓｔｕｄｅｎｔ Ｐａｐｅｒ， Ｂｅｓｔ Ｐｏｓｔｅｒ Ｐａｐｅｒ， Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ｂｉｏｍｅｄｉｃａｌ ＆ Ｂｉｏｓｙｓｔｅｍ Ｒｅｌａｔｅｄ Ａｒｅａｓ， ＳＵＰＣＯＮ Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ｉｎｄｕｓｔｒｉａｌ Ａｕｔｏｍａｔｉｏｎ， ａｎｄ ＡＩＡＧ Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ｓｕｐｐｌｙ Ｃｈａｉｎ Ｒｅｌａｔｅｄ Ｔｏｐｉｃｓ． Ｍｏｒｅｏｖｅｒ， ｗｅ ａｒｅ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｔｏ ａｒｒａｎｇｅ ｐｏｓｔ⁃ｃｏｎｆｅｒｅｎｃｅ ｐｕｂｌｉｃａｔｉｏｎ ｏｆ ａ ｓｅｌｅｃｔｅｄ ｇｒｏｕｐ ｏｆ ａｃｃｅｐｔｅｄ ｐａｐｅｒｓ ａｔ ＷＣＩ⁃ ＣＡ ２０１４ ｉｎ ｍｏｒｅ ｔｈａｎ ｔｅｎ ｌｅａｄｉｎｇ ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌｓ ａｎｄ ｔｏｐ Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌｓ ａｓ ｓｐｅｃｉａｌ ｉｓｓｕｅｓ， ａｍｏｎｇ ｔｈｅｍ ａｒｅ ＩＥＥＥ／ ＡＳＭＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｅｃｈａｔｒｏｎｉｃｓ， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｒｏｂｏｔｉｃｓ， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ Ｔｅｃｈｎｏｌｏｇｙ， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｄｕｓｔｒｉａｌ Ｅｌｅｃｔｒｏｎｉｃｓ， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ， Ｍａｎ， ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ， Ｐａｒｔ Ｂ， ａｎｄ Ａｃｔａ Ａｕｔｏｍａｔｉｏｎ Ｓｉｎｉｃａ． Ｉｔ ｉｓ ｏｕｒ ｇｒｅａｔ ｐｌｅａｓｕｒｅ ｔｏ ｉｎｖｉｔｅ ｙｏｕ ｔｏ ｓｕｂｍｉｔ ｙｏｕｒ ｏｒｉｇｉｎａｌ ｒｅｓｅａｒｃｈ ｐａｐｅｒｓ ｔｏ ｔｈｅ Ｃｏｎｇｒｅｓｓ． ＷＣＩＣＡ ２０１４ ａｌｓｏ ｗｅｌ⁃ ｃｏｍｅｓ ｐｒｏｐｏｓａｌｓ ｆｏｒ ｏｒｇａｎｉｚｉｎｇ Ｆｏｃｕｓｅｄ Ｔｈｅｍｅ Ｓｅｓｓｉｏｎｓ ｏｎ ｔｈｅ ｃｏｎｆｅｒｅｎｃｅ ｔｏｐｉｃｓ， Ｔｕｔｏｒｉａｌｓ ａｎｄ Ｗｏｒｋｓｈｏｐｓ ｏｎ ｅｍｅｒｇｉｎｇ ｔｏｐｉｃｓ． Ｙｏｕ ａｒｅ ｉｎｖｉｔｅｄ ｔｏ ｓｕｂｍｉｔ ｆｏｃｕｓｅｄ ｔｈｅｍｅ ｓｅｓｓｉｏｎ ｐｒｏｐｏｓａｌｓ ｔｏ Ｐｒｏｆ． Ｓｉｍｏｎ Ｘ． Ｙａｎｇ （ ｓｙａｎｇ＠ ｕｏｇｕｅｌｐｈ．ｃａ） ｂｅｆｏｒｅ Ｄｅｃ． １， ２０１３． Ｐｌｅａｓｅ ｒｅｆｅｒ ｔｏ ｔｈｅ Ｃｏｎｇｒｅｓｓ ｗｅｂｓｉｔｅ ｆｏｒ ｄｅｔａｉｌｓ． Ｗｅｂｓｉｔｅ： ｈｔｔｐ： ／ ／ ２０１４．ｗｃｉｃａ．ｉｎｆｏ ／ ｉｎｄｅｘ．ｓｈｔｍｌ． Ｔｅｌ： ０２４８３６８１０４７⁃８０１３ ． Ｅ⁃ｍａｉｌ： ｗｃｉｃａ２０１４＠ ｇｍａｉｌ．ｃｏｍ． ·４９６· 智 能 系 统 学 报 第 ８ 卷