2. 吉林大学计算机科学与技术学院, 吉林 长春 130022
2. College of Computer Science and Technology, Jilin University, Changchun 130022, China
1 引言
分布式集群存储是一种大数据存储管理的关键技术，其中HDFS(Hadoop distributed file system)因其高传输率和高容错性成为解决大数据高效存储应用的有效方法[1-2].考虑到HDFS数据放置策略的随机性方式容易造成数据分布不均衡，进而会影响系统整体性能的问题，目前已经从多种角度提出了解决此问题的研究方案[3].王宁等提出了一种满足用户需求的存储数据块的最小服务成本策略，能够实现副本数和副本位置的动态调整，能节省存储空间，提高系统的可靠性和稳定性[4]； 翟海滨等提出一种权衡存储成本和带宽成本的P2P缓存容量设计方法，将最优缓存容量设计问题描述为整数规划问题[5]； 文[6-8]推断出最优数据放置策略，降低使用的冗余，然后降低相关联的开销.但这些研究中，在选择数据可靠性提升的同时，没有兼顾到数据均衡问题和系统执行性能等问题.
针对上述问题，李建敦、 葛雄资等提出了一种基于布局的虚拟磁盘节能调度方法，动态划分为工作区与就绪区，以工作区为主向用户分发资源，能够有效地缓解响应时间延长的问题[9-10]； 江柳、 刘通等提出了一种通过
Datanode缓存部分小文件的策略来解决Namenode在存储时的性能瓶颈问题，以降低访问时延，提高访问效率[11-12]； 王意洁、 谭一鸣、 何丽等实现了HDFS中文件读写过程中的并行传输策略，改进了副本自动复制策略，提高了读写效率，缩短延迟时间，为云存储用户提供高效并稳定的服务[13-15].在此基础上，本文提出了使用一致性哈希算法对数据副本进行分散存储原则的方法，结合一致性哈希改进算法[16]，引入虚拟数据节点与等分存储区域[17-20]，能够在考虑数据均衡分布的同时，自适应地完成存储数据的快速定位，提升系统性能.
2 一致性哈希数据存储算法 2.1 基本原理针对评价一致性哈希算法平衡性、 单调性、 分散性、 负载问题这4个方面的要素，设计一致性哈希层次模型： 将所有由存储集群组成的存储空间抽象成闭合的环形哈希空间，使用与对象存储一样的Hash算法把所有分布式集群中的机器以唯一识别名映射到环中(通常情况下采用机器的IP或者机器别名作为唯一识别名)，将机架中所有的数据节点以唯一标识映射到环形空间中，最终通过Hash函数映射找到要存储的机架号，映射确定数据模块要存储数据节点的具体位置，如图 1所示.
|
| 图 1 一致性哈希映射过程 Figure 1 Consistent Hash mapping process |
在分布式集群存储中，基于哈希的组织形式能很好地将数据尽可能平均地分布到各个数据节点中.直接将机架和数据节点映射到哈希环，由于映射情况的分散性和降低负载的需求，会存在数据存储分布不均衡的问题.充分考虑系统预期的规模，为机架和数据节点引入虚拟节点，通过一致性哈希映射，数据对象能够均匀地分配到各虚拟节点，减少数据直接映射到节点后由于扩展带来的数据迁移，如图 2所示.
|
| 图 2 引入虚拟节点后的映射过程 Figure 2 Virtual node mapping process |
通过这种设计方式，能够使存储环中的每个机架及数据节点对应多个虚拟数据节点，由于所有的虚拟数据节点都能够映射到存储环状空间，因此在一致性哈希计算过程中，可以使得数据查询转变为对存储数据的机架和数据节点进行操作，完成查询到虚拟节点的任务，虚拟节点的数量可以依据设备硬件性能进行划分和添加，保证能在均衡分布存储数据的同时兼顾各数据节点的性能因素，提高系统整体性能.
3 优化策略 3.1 数据存储空间优化调整HDFS通常的设计方案都是用于支持大文件的数据存储的，HDFS中典型的数据块大小默认是64 MB.HDFS文件访问存储空间的时间主要包含3个因素： 寻址时间、 响应时间和数据传输时间，访问性能经常通过文件传送效率ηeff衡量，如式(1)所示：
|
(1) |
式中，tadr为文件系统寻址时间，trep为响应时间，ttrans为数据传输时间，sblock数据存储空间，ν数据传输速度.由式(1)可以看出，在设备硬件性能和数据布局确定的情况下，寻址时间、 响应时间也是能够确定的，因此数据存储空间的设定就会对文件传送效率影响显著.当数据存储空间设定过大时，能够提高文件传送效率，但会造成负载分布不均衡的问题； 当数据存储空间设定过小时，能够较好地完成降低负载的需求，但会降低文件传送效率.因此需要综合考虑负载均衡问题和文件传送效率，调整数据存储空间.
本文使用对存储空间进行均分的方法，将存储空间的环形区域进行均分操作，此时存储空间中的所有虚拟节点都包含多个均分存储区域，即每一个虚拟节点负责的存储空间都由多个均分区域组成.当数据节点通过哈希计算映射到存储空间后，定址找到数据节点所处位置的第1个均分区域为此节点的映射位置，若位置冲突则使用线性探测再散列的方法顺时针方向继续查找下一个均分区域，直到每个数据节点负责的存储空间都由多个等分区域构成.存储时，数据按照划分好的存储空间可以完成分组存储，当集群中有机器添加或者删除时，通过按顺时针迁移的一致性哈希算法规则，在保持单调性的同时，减少了数据的迁移量和服务器的压力.等分存储空间后，数据节点映射存储位置如图 3所示.
|
| 图 3 等分存储空间映射示意 Figure 3 Illustrate for an aliquot storage space mapping |
副本数量和副本放置位置是副本放置策略的2个主要研究方面： 副本数量越多，数据可用性和系统性能越高，但存储与通信消耗系统的成本也越大，影响用户服务质量.数据可用性、 系统的扩展和负载均衡(包括系统数据节点的存储平衡和数据读写的负载均衡)等问题受到副本放置位置的影响，HDFS的副本放置策略为两个副本放置在相同机架上的不同数据节点上，第3个副本放置在不同于此机架的数据节点上，使用这种方法能够提高数据写性能，减少读操作的网络聚合带宽，对于多副本问题(m个副本)，沿用此方式，通过Hash算法函数映射存储到n个机架，设定顺时针方向依次在k个机架中的每个机架内选取两个不同数据节点存储两个副本，若机架或者数据节点存在异常，继续按照顺时针方向查找相邻机架或者数据节点进行搜索，检验存储空间满足条件后完成存储工作； 在n-k个机架中按上述方法每个机架内顺次选取一个合适的数据节点用来存储剩余的副本.通过两次嵌套Hash计算映射方式在环状存储空间寻找机架的数据节点，具体流程如图 4所示.
|
| 图 4 数据调整策略流程 Figure 4 Data adjustment strategy |
机架进入环状存储空间时，变化机架前后几个与备份数据相关机架的迁移状况如图 5所示，针对数据节点的添加和删除问题，可以依照顺时针迁移规则使用一致性哈希算法映射得到环状空间上新的映射数据节点，此时数据在单个机架中的等分区域内发生映射变化，存储数据可能保持原有存储位置或者产生小范围迁移； 针对机架的添加和删除问题，存储数据多份备份依照一致性哈希算法映射被连续的存储在环状空间毗邻的几个机架上，当集群添加机架或者遇到故障退出机架时，与之相邻的前后几个机架的数据都需要进行迁移.机架出现变化后，数据节点的映射方式可根据图 4所示流程确定.可以看出，使用此种算法处理分布式集群数据存储问题能够继承一致性哈希算法在保持单调性的同时，可以避免大量数据迁移而加大服务器压力的优点.
|
| 图 5 数据迁移示例(2备份数) Figure 5 Data migration examples |
对存储数据进行优化时，数据文件都按照给定的等分区域的空间大小进行备份操作，并按照一致性哈希完成分布存储.而根据上述数据调整策略，在分析数据的过程中，使用的数据是分布在不同的数据节点和不同的机架上使用MapReduce框架处理数据并行计算时，节点通信是需要考虑的主要问题.
下面对数据调整策略中的网络通信性能进行分析，假设集群存储中处理数据多副本问题，数据副本数量为m，使用集群中的机架数量为n，等分存储区域大小为q.在进行数据的任务调度时应尽量保证数据的通信效率，同一机架内的数据通信最为通畅.集群存储将数据的多个副本放在不同的数据节点下，以此来保证负载均衡，根据上述数据调整策略，有k个机架上分布两个副本的几率可以表示为
|
(2) |
那么数据任务执行过程中通信量的计算可以表示为
|
(3) |
由不同的数据节点抽取数据时，要考虑网络带宽的因素，这里设定在数据通信过程中，从同一机架的数据节点抽取数据网络带宽(价值度量)为v1，数据块与任务节点处在同一机架内几率设为p1，不同机架的数据节点抽取数据的网络带宽为v2，数据块与任务节点处在不同机架的概率为p2.则数据节点抽取数据的网络带宽可以表示为
|
(4) |
综上所述，通信时间可以表示为
|
(5) |
由式(5)可以看出，影响一致性哈希算法性能的因素有存储集群规模、 备份副本数量、 使用机架数量、 通信带宽等.数据集群分布情况下，集群规模越大，数据聚类关联性越差，网络宽带通信增长，算法执行性能越差.一致性哈希算法通过增加数据获取概率改良算法性能，考虑存储数据开销和数据的协调一致性因素，副本数量应适当选取，一般情况下应结合文件传送效率，负载均衡等要素综合考虑.所以在集群规模、 数据存储空间以及通信带宽变动较小的情况下，使用一致性哈希算法可以有效地提高数据处理效率.
4 实验与结果分析在局域网中搭建HDFS存储集群，操作系统使用Ubuntu14.04，安装Hadoop云平台计算，英特尔至强4核CPU，8 G内存，1 TB SATA硬盘，千兆网卡配置用于存储集群数据节点的连接，模拟6个机架(每个机架分别有6、 8、 12、 9、 8、 10个数据节点).
整个集群中，最低配置为3个节点，可以实现高可用，当某一节点出现故障时，其它节点可以对外提供服务.同时，任何数据块、 多副本会优先选择不同节点存放，确保了节点故障，数据不会丢失； 当增加一个节点时，集群会自动把原节点存放副本的数据分发一份到新增节点，而有一个节点故障时，在设定的节点老化时间之后，集群会自动分发出3份副本，确保数据副本的一致性和安全性； 当节点数超过3个时，3份副本的存放会在多个节点中根据负载均衡来选择存放.通过这样的多副本冗余存储、 集群负载均衡、 服务高可用、 元数据备份及历史版本，能够压缩可用空间，实际可用空间=物理空间/3，通过标准化硬件来提升可用性的同时，降低总体应用成本.实验使用作者课题组主持的“基于大数据智能库存管理关键技术及系统研发”项目中存储的真实数据集，数据集的具体情况见表 1，数据节点的性能是相同的，数据节点需要依据实际的存储集群情况进行配置，使用网卡物理地址与局域网IP联合作为唯一标识位置，映射函数使用一致性哈希的Chord算法，等分存储空间大小设定为64 MB，上传数据规模为50 GB，存储约1 200个存储区域.
| 文件 | 副本数 | 文件大小 | 占用空间 | 记录条数 |
| 用户信息 | 3 | 1 MB | 3 MB | 2 130 |
| 发布消息 | 6 | 16 GB | 48 GB | 512 k |
| 环境数据 | 4 | 640 MB | 1 900 MB | 9 680 |
使用上述设置完成多机架连接测试并行性能变化趋势实验，验证多机架并行连接与备份分配比重关系.这里认为各个数据节点均衡分布且个体性能差异不大，理论上各机架中数据节点按照一致性哈希算法被分配数据备份的机会均等.从图 6中可以看出，按照数据的负载均衡理论实际情况中机架的数据节点备份应与理论情况相近，能够保证机架之间数据的平衡性存储.图 7所示为运行时间对比情况，使用一致性哈希优化算法与标准Hadoop平台下的约减端连接查询处理算法对数据进行连接查询，对比可知，映射任务在本地完成数据连接明显比从映射端到约减端的数据传输花费时间缩短且缩减了数据传输的启动开销.
|
| 图 6 机架备份分布情况 Figure 6 The backup distribution of rack |
|
| 图 7 数据连接查询运行时间对比 Figure 7 Comparison of data connection query run-time |
使用数据上传实验将数据集从本地文件系统上传至HDFS，验证优化存储策略与数据上传速度的关系，通过考虑机架数据节点中的备份数分配情况，了解数据节点之间的数据均衡性能.理论上认为数据节点分布在均匀区域内且性能差异不大，因此数据节点会有均等的机会被分配机架获取备份.由图 8可以看出，随着数据规模的增长，数据传输的最终通信时间能够基本保持稳定(51.5 s左右且浮动振幅不大)，机架中各个数据节点获取备份的概率均能保持在理论值(10％)上下浮动，表明机架中的数据节点在被分配备份时能够保证负载均衡.
|
| 图 8 实际备份分布情况及运行时间对比 Figure 8 The backup distribution and run-time comparison |
根据数据迁移与备份数比例变化趋势验证一致性哈希算法单调性和负载均衡的特性，完成对集群数据节点添加与删除的操作，图 9为机架经过映射调整后的实际值获取备份情况，可以看出新添加的数据节点获取备份概率较高，出现这种情况的原因是数据在完成映射的过程中需要重新规划数据节点获取备份的概率，但振荡幅值较小在合理范围内(1.8％)，并没有影响机架内的整体负载均衡； 出现这种情况是因为需要花费另外的时间来选择数据节点.图中给出了采用一致性哈希算法与随机分布的Hadoop平台策略进行数据调整的运行时间对比，可以看出随着新进节点的数据规模增长运行时间增长幅度较小，数据处理效率较高，说明这种设计算法能够满足较大规模数据的处理.
|
| 图 9 数据节点调整后备份分布情况 Figure 9 The distribution of the data after the node adjustment |
本文介绍了作为分布式集群存储的HDFS大数据存储优化问题，提出了基于一致性哈希原理的多副本数据一致性哈希优化存储位置放置策略，使用创建虚拟节点技术和等分存储区域保证了数据存储的均衡性分布，加快了数据处理的速度，能够针对集群的实际要求完成扩展，并按照扩展情况制定使数据存储完成自适应优化调整.
基于一致性哈希Chord算法使用MapReduce并行处理，实现多机架并行连接处理.实验表明，存储优化后，算例的执行速度得到有效提升，针对GB级规模数据，能够保证负载均衡问题； 多机架连接实验中优化处理的算例执行时间明显低于常规约减处理算法； 针对实际情况中可能出现的扩展与删减问题的测试表明，使用优化存储策略处理此类问题时，振荡幅值能够在合理范围内变化，对整体负载均衡影响不大，且执行时间与负载占比变化趋势一致.
由于实验数据和实验硬件条件限制问题，使用数据规模仅能达到GB级，而已经能够对优化策略根据数据规模变化的执行时间、 效率等变化趋势开展研究与分析，接下来的工作计划搭建针对TB级以上数据完成存储的集群环境，进一步进行实验分析，为项目的研究开发工作进行技术储备.
| [1] | Kim K, Kim J, Min C, et al. Content-based chunk placement scheme for decentralized deduplication on distributed file systems[M]//Computational Science and Its Applications-ICCSA 2013. Berlin, Germany:Springer, 2013:173-183. |
| [2] | Josef S, Johannes M, Alexander S. Creating optimal cloud storage systems[J]. Future Generation Computer Systems, 2013, 29 (4): 1062–1072. DOI:10.1016/j.future.2012.06.004 |
| [3] | 刘晨光. 面向Hadoop存储系统的节能优化技术研究[D]. 武汉:华中科技大学, 2012. Liu C G. Research on optimizing energy efficiency for Hadoop storage system[D]. Wuhan:Huazhong University of Science & Technology, 2012. |
| [4] | 王宁, 杨扬, 孟坤, 等. 云计算环境下基于用户体验的成本最优存储策略研究[J]. 电子学报, 2014, 42 (1): 20–27. Wang N, Yang Y, Meng K, et al. A customer experience-based cost minimization strategy of storing data in cloud computing[J]. Acta Electronica Sinica, 2014, 42 (1): 20–27. |
| [5] | 翟海滨, 张鸿, 刘欣然, 等. 最小化出口流量花费的接入级P2P缓存容量设计方法[J]. 电子学报, 2015, 43 (5): 879–887. Zhai H B, Zhang H, Liu X R, et al. A P2P cache capacity design method to minimize the total traffic cost of access ISPs[J]. Acta Electronica Sinica, 2015, 43 (5): 879–887. |
| [6] | Kamiyama N, Mori T, Kawahara R, et al. Analyzing influence of network topology on designing ISP[J]. Telecommunication Systems, 2013, 52 (2): 969–977. |
| [7] | Pamies-Juarez L, García-López P, Sánchez-Artigas M, et al. Towards the design of optimal data redundancy schemes for heterogeneous cloud storage infrastructures[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2011, 55 (5): 1100–1113. |
| [8] | Hefeeda M, Noorizadeh B. On the benefits of cooperative proxy caching for peer-to-peer traffic[J]. IEEE Transactions on Parallel & Distributed Systems, 2010, 21 (7): 998–1010. |
| [9] | 李建敦, 彭俊杰, 张武. 云存储中一种基于布局的虚拟磁盘节能调度方法[J]. 电子学报, 2012, 40 (11): 2247–2254. Li J D, Peng J J, Zhang W. A layout-based energy-aware approach for virtual disk scheduling in cloud storage[J]. Acta Electronica Sinica, 2012, 40 (11): 2247–2254. |
| [10] | 葛雄资. 基于预取的磁盘存储系统节能技术研究[D]. 武汉:华中科技大学, 2012. Ge X Z. Study on energy-aware prefetching techniques for disk storage systems[D]. Wuhan:Huazhong University of Science & Technology, 2012. |
| [11] | 江柳. HDFS下小文件存储优化相关技术研究[D]. 北京:北京邮电大学, 2014. Jiang L. The research of increase the IO speed of small files in HDFS[D]. Beijing:Beijing University of Posts and Telecommunication, 2014. |
| [12] | 刘通. 基于HDFS的小文件处理与副本策略优化研究[D]. 青岛:中国海洋大学, 2014. Liu T. Research on the optimization of small files processing and replication strategy based on HDFS[D]. Qingdao:Ocean University of China, 2014. |
| [13] | 王意洁, 孙伟东, 周松, 等. 云计算环境下的分布存储关键技术[J]. 软件学报, 2013, 23 (4): 962–986. Wang Y J, Sun W D, Zhou S, et al. Key technologies of distributed storage for cloud computing[J]. Journal of Software, 2013, 23 (4): 962–986. |
| [14] | 谭一鸣, 曾国荪, 王伟. 随机任务在云计算平台中能耗的优化管理方法[J]. 软件学报, 2012, 23 (2): 266–278. Tan Y M, Zeng G S, Wang W. Policy of energy optimal management for cloud computing platform with stochastic tasks[J]. Journal of Software, 2012, 23 (2): 266–278. DOI:10.3724/SP.J.1001.2012.04143 |
| [15] | 何丽, 饶俊, 赵富强. 一种基于能耗优化的云计算系统任务调度方法[J]. 计算机工程与应用, 2013, 49 (20): 19–22. He L, Rao J, Zhao F Q. Task scheduling method based on energy optimization in cloud computing system[J]. Computer Engineering and Applications, 2013, 49 (20): 19–22. |
| [16] | Tena F L, Knauth T, Fetzer C. PowerCass:Energy efficient, consistent hashing based storage for micro clouds based infrastructure[C]//2014 IEEE 7th International Conference on Cloud Computing (CLOUD). Piscataway, NJ, USA:IEEE, 2014:48-55. |
| [17] | 席屏, 薛峰. 多层一致性哈希的HDFS副本放置策略[J]. 计算机系统应用, 2015, 24 (2): 127–133. Xi P, Xue F. Replica placement strategy based on multi-layer consistent Hashing in HDFS[J]. Computer Systems & Applications, 2015, 24 (2): 127–133. |
| [18] | Bowers K D, Juels A, Oprea A. HAIL:A high availability and integrity layer for cloud storage[C]//Proceedings of the 16th ACM Conference on Computer and Communications Security. New York, NJ, USA:ACM, 2012:187-198. |
| [19] | 邵秀丽, 王亚光, 李云龙, 等. Hadoop副本放置策略[J]. 智能系统学报, 2013 (6): 489–496. Shao X L, Wang Y G, Li Y L, et al. Research on the replica placement strategy of Hadoop[J]. CAAI Transactions on Intelligent Systems, 2013 (6): 489–496. |
| [20] | Berl A, Gelenbe E, Girolamo M D, et al. Energy-efficient cloud computing[J]. The Computer Journal, 2013, 53 (7): 1045–1051. |