现代电子技术
Modern Electronics Technique
Mar.  2024Vol. 47  No. 6
2024年3月15日第47卷第6期
0  引  言
随着大数据时代到来，人们的生活逐渐依附网络，使网络信息数据急剧猛增，给邮政业务带来了新的挑战。合理地存储邮政庞大数据才能使用户、快递企业和邮政管理者之间工作效率提高，降低企业投诉率。2022年全国快递业务量为1 105.81 亿件，同比增长2.1%，预计2023年全年邮政业业务的快递业务量将达
到1 300亿件。
在此背景下，使用分布式存储海量数据[1]成为数据存储的主要技术。其中HDFS 是分布式系统基础架构Hadoop 的核心功能模块，由于其具有数据传输速率高和容错性好的特性，可以有效解决邮政数据的存储问
题。如文献[2]提出在HDFS 分布式系统上层，使用Hbase 将邮政数据存放在数据库中，用以解决企业海量数据存储问题。文献[3]提出基于Hadoop 框架下的大数
DOI ：10.16652/j.issn.1004‐373x.2024.06.007
引用格式：李泽山.改进一致性哈希优化存储邮政数据算法的研究[J].现代电子技术，2024，47（6）：43‐48.
改进一致性哈希优化存储邮政数据算法的研究
李泽山
（国家林业和草原局信息中心， 北京  100714）
摘  要： 随着电子商务不断发展，邮政快递行业数据日益增多，传统方式对于邮政数据存储的理论与方法都已无法满足需求。基于此情况，使用一致性哈希算法来解决存储系统的横向弹性扩展，结合一致性哈希的虚拟节点与加权轮询算法优化Hadoop 平台下分布式文件系统（HDFS ）存储策略，实现集在同构与异构条件下的数据均衡效果。同时介绍集节点数据转移思想，设计负载因子与系统自检周期，实现了集动态权重的负载转移，并进行实验验证。实验结果表明，文章提出的改进算法与HDFS 、普通一致性哈希相比，在不同条件下集负载差值均有不同程度的提升，证明了该策略可以有效降低集
节点间负载差值。
关键词： 数据存储； 一致性哈希算法； 加权轮询算法； 分布式文件系统； 负载均衡； 异构集； 分配策略
中图分类号： TN919‐34； TP319.9                  文献标识码： A                    文章编号： 1004‐373X （2024）06‐0043‐06
Research on improved consistency hash optimization algorithm for storing postal data
LI Zeshan
字符串长度1是什么意思(The Information Center of National Forestry and Grassland Administration, Beijing 100714, China)
Abstract ： With the continuous development of e ‐commerce and the increasing number of data in the postal express industry, traditional methods are no longer meet the needs for the theories and methods of postal data storage. Based on this situation, the consistent hash algorithm is used to solve the horizontal elastic expansion of the storage system, and the storage strategy of distributed file system (HDFS) on Hadoop platform is optimized by combining consistent hashing with virtual nodes
and weighted polling algorithm to realize the data balance in clusters under homogeneous and heterogeneous conditions. The concept of cluster node data transfer is introduced, and the load factors and system self check cycles is designed, so as to realize the load transfer of dynamic cluster weights, and conduct the experimental verification. The experimental results show that the proposed improved algorithm has different degrees of improvement in cluster load difference compared with HDFS and regular consistency hashing under different conditions, proving that this strategy can effectively reduce the load difference between
cluster nodes.
Keywords ： data storage; consistent hashing algorithm; weighted polling algorithm; distributed file system; load balancing;
heterogeneous clusters; allocation strategy
收稿日期：2023‐08‐16          修回日期：2023‐09‐22
基金项目：内蒙古自然科学基金项目（2020MS06029）；内蒙古自然科学基金项目（2021LHMS06013）；内蒙古自然科学基金项目
（2020LH06009）；内蒙古自治区关键技术攻关计划项目（2020GG0165）
43
现代电子技术2024年第47卷
据分析功能对邮政快递的寄递系统进行设计。文献[4]在Hadoop框架基础上，结合内存数据库构建大数据模型，对存储在HDFS中的数据进行检测、监控与分析，设计一套反系统。但这些研究都在HDFS原有存储策略上进行，HDFS随机性放置数据的策略容易造成系统节点数据分布不均，直接影响系统性能，限制了存储效率。
1 相关工作
针对HDFS随机放置数据的问题，学者们提出如下解决方案：文献[5]存放数据的思想是计算所有节点当前的使用情况，选择使用空闲的节点存储数据；文献[6]把缓存问题转换为整数规划问题，设计了一种兼顾存储成本与带宽成本的对等方法；文献[7]提出根据集内节点存储性能和网络拓扑距离，到集的最优节点进行数据存放。这些方法在数据均衡方面取得了一定进展，但没有兼顾到可靠性与系统单调性的问题。
在此基础上，文献[8]提出一种单纯使用一致性哈希算法解决的方案，以实现系统单调的问题。文献[9]提
出在Hadoop下通过Datanode缓存部分小文件的策略，来解决Namenode在存储时负载失衡问题；文献[10]提出一种基于跳跃Hash的对象分布算法，凭借占用资源更少而优化存储数据效率。这些研究很大程度提升了数据可靠性，但未考虑到节点性能不同的异构集数据存储情况。
之后的研究中，文献[11]基于Eclipse的研发环境，设计一个任务调度器用以最大化利用分布式系统内的内存对集中的内存与缓存进行负载均衡，经实验证明，在部分场景下该方法比传统分布式系统具有更好的效率；文献[12]基于Nginx服务器研究了集负载均衡的场景，提出基于动态权重的连接算法，根据该算法得出数据的分配方法。
以上算法多数能与其他算法相兼容，说明使用算法仍然可以优化HDFS分布式系统的负载均衡。本文提出一种使用一致性哈希算法结合加权轮询的数据分配策略，在分布式系统中，集的动态扩展利用一致性哈希可以较好解决。但一致性哈希算法中没有对于负载均衡的描述，单一的一致性哈希容易导致系统的负载倾斜。因此，引入虚拟节点思想来均分数据，并结合加权轮询算法进行存储节点权值的数据分配，针对快递数据特点来改进HDFS分布式系统存储策略。将此方法与HDFS原存储策略以及基于虚拟节点的普通一致性哈希分配策略进行实验对比，证明文章研究的策略在不同条件下的数据存储负载均衡方面得到较大提升。
2 存储分配策略的研究
2.1 一致性哈希算法
一致性哈希是负载均衡领域里一种应用广泛的算法，最早于1997年，由麻省理工学院的David Karger提出，用于改进P2P网络中哈希表重映射的问题。算法中首先抽象整个存储系统形成一个封闭的232-1环形哈希空间，再使用哈希算法将存储节点与数据映射到哈希环内。
如图1所示，哈希环内有Node1、Node2、Node3三台机器，以及Data1、Data2、Data3、Data4四个存储对象。当Node2被删除，根据一致性哈希顺时针迁移原则，原本存储在Noede2的数据Data3会被存储到Node3中，系统内对象没有任何的改动，极大地减小了删除节点数据
分布时系统的压力。
图1  一致性哈希中删除节点
如图2所示，在集内进行节点（机器）添加操作时，在集中添加一个新的节点Node4，通过顺时针迁移原则，Data3会存储到Node4中。这种特殊的哈希算法实现了少量数据的迁移，避免了几乎全部数据的移动。因此，一致性哈希算法是对动态扩展能力进行优化的一种哈希算法[13]
。
图2  一致性哈希中添加节点
44
第6期
2.2  虚拟节点分配策略
虚拟节点是一种广泛应用于各种工程场景的概念，但当存储节点的数量太少，会导致其无法做到在哈希环上均匀分布，进而出现负载失衡。针对此问题，本文在物理节点与数据之间设计一个虚拟层，虚拟层由大量虚拟节点构成，如图3所示。虚拟节点被真实物理节点包含，多个虚拟节点对应一个物理节点，数据通过哈希函数映射到虚拟节点上，实际存储到对应的物理节点中，通过这种方法就有足够的虚拟节点来进行一致性哈希
操作。
图3  虚拟节点引入机制
如果系统内分配较少的虚拟节点，会造成一致性哈希无法满足系统负载均衡的效果；而虚拟节点过多又会导致存储系统需花费较长时间才能到对应的虚拟节点，拖慢系统效率。因此，设计虚拟节点的数量十分重要。
在集节点性能一致的同构条件下，根据邮政快递数据快递单号的唯一性，更改HDFS 中的块存储随机放置策略，将每一条数据中的单号作为key 值，映射到哈希环上，然后把节点的IP 地址再次映射到哈希环上，整个环内作1∶N  配比的虚拟节点映射。该哈希环便可分割为N +1个独立的区间，将key 分发到哈希环，由于key 的数量巨大，每个区间都能够分发到相对均匀的key 。可以推测，在一个1∶N  配比的虚拟节点映射的一致性哈希系统中，假设某个物理节点的初始哈希位置为P ，其所代表的所有映射节点的哈希位置应当表示为：    P ′=()
232-1N +1
k +P mod (232-1),  k =0,1,2,…,N （1）
在哈希环内为减少哈希映射的重复度，本文还为该系统采用一种完美哈希算法（Perfect Hashing ）作为计算哈希值的依据。其中，在性能和使用领域都比较有优势的是BKDR 哈希算法，以h 表示特征字符串的哈希结果，l 表示字符串长度，s 表示前后字符在哈希运算中的权重比（取值可以为31、131、1 313等），其计算公式表达为：
h =
∑n =0
l -1
x n
•s
n
（2）
由于在一致性哈希系统中，该计算结果需要对 232-1
的哈希环长度进行取模运算，因此最终的哈希结果表示为：
h =
()
∑n =0l -1
x n
•s
n
mod (232-1)（3）
异构服务器集中，由于各个节点性能不一，通常要配置数量巨大的虚拟节点来平衡异构状态。这种方法会造成为虚拟节点分配较多的额外资源，还降低了系统内查效率。若节点为i ，其计算能力设为a i ，每台节点的虚拟层引入的虚拟节点个数为k log ||N ，其中N 为设备总数，k 为常数。假设集内，算力最低的节点用a min 表示，那么在一致性哈希算法中，系统在异构条件下
分配虚拟节点个数为：∑i =0N
a i
a min k log ||N 。可以看出，当a i
a min
值很大时，则将引入大量的虚拟节点，降低了存储系统效率。
2.3  加权轮询算法分配策略
以上的分析说明在异构条件下仅凭虚拟节点的引
入无法保证数据均衡，需结合加权轮询算法继续优化数据分配策略。加权轮询算法是对轮询算法的改进，用权值来表示节点之间存在的差异，权值高的节点分配的存储任务多，权值低的节点分配的存储任务少。
在传统加权轮询算法中，一般人为设置算法内权值大小，这样无法动态表述节点间差异。本文提出的加权轮询实现负载均衡算法是在分配数据阶段通过获取节点的存储空间ROM 利用率，对比平均值进行数据的存储分配。其中，存储空间ROM 利用率即为算法中要收集的负载因子。
对于负载因子的收集，在Hadoop 中，通过API 接口编写相应依赖包可以采集磁盘的使用情况。通过命令hdfs dfsadmin‐report 获取磁盘的使用情况。
磁盘的利用率公式为：
η=
disctotal +discfree disctotal
（4）
式中：
η表示服务器磁盘的利用率；disctotal 表示磁盘空间；
discfree 表示磁盘剩余空间。Hadoop 中，主节点（namenode ）作为负载均衡服务
器，处理客户端发送的存储数据请求，之后发挥负载均衡服务器作用，对各个从节点实时反馈其负载状态，即
负载因子信息，然后把请求根据权值轮询分配到各节点，从节点根据实时负载情况分配数据，完成处理请求，将结果发送给主节点，之后主节点直接发送给客户端，完成分配。加权轮询分配的工作模型如图4所示。
李泽山：改进一致性哈希优化存储邮政数据算法的研究45
现代电子技术2024年第47
卷
图4  加权轮询分配数据模型
具体执行分配数据步骤如下：
1）系统收到数据存储请求后，开始收集当前各节点负载因子的值。
2）将各个负载因子的值与系统内负载平均值作比较，设系统平均负载为Lˉ，节点为i，若存在Lˉ≥L i，则将这台服务器的权值设置为0，此次存储不再对这台节点进行数据分配；若Lˉ<L i，则根据负载因子计算各个节点权重，根据权重进行节点的数据分配。
3）对分配的数据节点，根据负载因子按比分配数据，完成权值轮询分配任务。
2.4 节点间负载转移策略
在HDFS分布式系统中，为达到负载均衡更好的效果，需要满足节点间的数据迁移。此外，当某些节点中的读写频率较高，将造成此节点负载压力较大，严重时甚至导致系统崩溃。因此，需要结合虚拟节点与加权轮询算法进行节点间动态负载均衡转移策略设计。
实现系统动态负载均衡的过程是时刻获取每个节点当前负载信息。由于此操作需花费系统额外性能，因此文章设计抓取的节点负载信息以周期性的方式收集，用来降低这些额外开销。在时间周期上，兼顾算法的效率，本文收集的时间周期是30 s（T=30 s）。根据上文，设集内负载因子最轻节点负载为L min，负载因子最重节点负载为L max，负载因子居中节点为L mid，i为节点，调整负载均衡的上限为Threshold，若有节点i中L max-L mid>Threshold i，即对负载超重进行调整，策略为减少L max节点对应的虚拟层中节点。同时把计划存储到此节点的数据按照顺时针迁移原则转存环内顺时针下一个节点，并清空节点预警信息。
同理，若节点i中L mid-L min>Threshold i，即进行负载过轻调控，对应地增加L min虚拟层中虚拟节点数量，并对比环内逆时针下一节点中数据量，均衡两节点数据存储量，清空节点预警信息。
3 实验结果及分析
3.1 实验平台及部署
实验使用高性能计算机在VMware Workstation软件上进行。系统平台的参数如表1所示。默认已搭建完成Hadoop全分布式系统实验平台。
表1  系统平台的参数
平台设备
核心处理器（CPU）
内存
硬盘
操作服务器
虚拟机系统
服务器操作系统
规格
Intel core i7
8750H
16 GB DDR4
2 512 GB
Windows 10
professional
VMware
Workstation pro
Linux CentOS 7
描述
计算频率2.2~4.1 GHz
六核十二线程
I/O速度2 666 MHz硬盘
固态硬盘+机械式
64位操作系统
—
64位操作系统3.2 实验数据的选取
本文研究针对邮政行业快递数据的存储，快递公司的工作人员每扫描一份快递面单，系统会记录一条数据。实验的数据选取自内蒙古自治区邮政行业大数据信息统计系统内数据，由中通快递公司提供。此数据为扫描快递面单的部分信息，共有A~K等11个字段，如扫描时间、快递单号等。递面单信息的部分数据截图如图5
所示。
图5  快递面单信息的部分数据截图
3.3 集负载均衡实验
同构条件下，在VMware Workstation软件配置虚拟机阶段，对一台节点服务器配置完成后，再次复制此虚拟机，以达到从节点配置统一、负载因子一致的效果。使用3.2节中的实验数据，将快递单号作为唯一标识符，映射到哈希环上，真实服务器以IP地址同样映射到环上，使用IntelliJ IDEA开发软件编写Java代码，将改进的一致性哈希通过API连接到Hadoop的存储接口，覆盖其自带块存储策略。在同一大小数据下，进行多次数据存放实验取统计平均，可以得到不同存储节点的负载差值，结果如图6所示。
系统中，所有节点负载数据量最大和最小的差值与节点平均负载值的比率为负载率差值。理想的负载率差值应是根据系统节点数量的变化维持在稳定的水平上。
本文算法基于权值的虚拟节点一致性哈希在数据划分中，节点存储的数据量取决于负载因子大小。集配置相同时，从图6可以看到，本文算法与普通虚拟节点的一致性哈希存储数据策略相差不大，不同集规模
46
第6期
在划分数据时，节点中负载差值在5%~8%，相比HDFS 存储数据的分配策略有一定提升。可以推测到，随着测试实验数据量与集存储节点数量的增多，测试结果也
将稳定在这一区间内。
图6  同构集负载均衡对比
在虚拟机的配置阶段，将存储节点的磁盘空间设置为各不相同，以区分负载因子，设置集的异构条件。重复上一实验步骤，将数据分发给不同从节点，进行多次数据存放实验取统计平均，得到不同从节点的负载差值，如图7
所示。
图7  异构集负载均衡对比
可以看到，HDFS 与虚拟节点的一致性哈希两种数据存储策略在面对异构集时，负载差值波动较大，原因是两种策略并没有对集的节点间性能不同进行针对性的优化，导致在此情况下，负载差值相近；而本文算法根据设定好的负载因子，计算节点在分配数据时按结果进行比例划分，随着数据量与节点数量的增加，可以推测整个集的负载差值稳定在6%左右，集负载差值明显降低。
为验证集动态数据均衡情况，在图7基础上，对
存储节点的数据进行10 000次读写操作，进行数据节点间负载转移策略实验，结果如图8所示。可以看到相比HDFS 存储策略，使用虚拟节点的一致性哈希节点数据分布相对更均匀，负载差值稳定在23%左右；本文算法引入周期（T =30 s ）节点负载转移思想，实现集动态自适应调整数据，多次测试取平均，负载差值达到10%以下（约为8%），实用性得到显著提升，达到了设计的要求。同时，在实验中的系统负载变化平缓，节点数量发生变化而整个负载没有较大波动，说明存储系统中增删
节点的操作不会对系统造成过大的影响。
图8  读写任务后的集负载均衡对比
4  结  语
本文基于Hadoop 平台下HDFS 分布式系统，使用分布式思想来解决日益增多的邮政数据的存放问题。实验结果表明，文章提出的改进算法与HDFS 、普通一致性哈希相比，在不同条件下集负载差值均有不同程度的提升，证明了该策略可以有效降低集节点间负载差值。实验验证了加权轮询与虚拟节点的一致性哈希算法相融合的可行性，为邮政企业面对海量数据的存储提供新的解决思路。之后准备搭建真实的集环境，进一步进行实验，为项目的应用进行技术储备。
注：本文通讯作者为李泽山。
参
考
文
献
[1] 危华明，廖剑平.海量数据存储中云服务器性能加速方法仿真[J].计算机仿真，2023，40（5）：515‐519.
[2] 王卫锋，杨林.基于Hadoop 的邮政寄递大数据分析系统设计
与实现[J].中国科学院大学学报，2017，34（3）：395‐400.[3] 李朝晖.基于HADOOP 平台及内存数据库架构的反系统[Z].北京：中国邮政储蓄银行股份有限公司，2017‐11‐01.[4] 陈伟.一种改进的HDFS 副本放置策略[J].长春师范大学学报，
2018，37（4）：15‐20.
李泽山：改进一致性哈希优化存储邮政数据算法的研究47

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。