分片阈值

基于分片一致性哈希负载均衡策略与应用

苏跃明;李晨;田丽华

【摘要】采用一致性哈希进行数据分区和负载均衡的分布式键值存储系统具有高

可扩展性的特点,但一致性哈希中哈希函数静态负载均衡的特性不能满足日益多样

化的应用场景需求.为了适应以上需求,从一致性哈希策略出发,结合动态负载均衡技

术,设计了一种基于一致性哈希的动态负载均衡策略.该策略使用与物理节点解耦的

分片代替传统的虚拟节点,并利用针对分片的监控信息,从分片级和节点级两个层面

对系统负载进行均衡调度,通过更细的调度粒度优化均衡效果.实验结果表明,该策略

保留了一致性哈希策略在系统扩展性上的优势,同时优化了一致性哈希策略负载均

衡的总体效果.利用基于分片的一致性哈希负载均衡策略,可以有效地均衡系统负载,

提高存储系统的效率.%Thedistributedkey-valuestoragesystem,whichus

consistenthashingfordatapartitioningandloadbalancing,hashighex-

r,thestaticloadbalancingstrategyinconsistent

r

toadapttoaboveneeds,adynamicloadbalancingstrategyisdesigned

badontheconsistenthashingandcombinedwithdynamicload

tsthefragmentdecoupledphysicalnodesinsteadof

traditionalvirtualnodesandusthemonitoringinformationoffragments

tomakedecisionsforloadbalancingschedulingfromtwoaspectsof

mentalresultsshowthatithas

retainedtheadvantageofconsistenthashingstrategyinsystem

scalability,whileoptimizingtheoverallperformanceofconsist-enthashing

temloadcanbeeffectivelybalancedandthe

utilizationofthesystemcanbeimproved.

【期刊名称】《计算机技术与发展》

【年(卷),期】2017(027)011

【总页数】5页(P62-65,70)

【关键词】一致性哈希;分片;动态负载均衡;分布式键值存储

【作者】苏跃明;李晨;田丽华

【作者单位】西安交通大学软件学院,陕西西安710000;百度(中国)有限公司,北京

100000;百度(中国)有限公司,北京100000;百度(中国)有限公司,北京100000

【正文语种】中文

【中图分类】TP39

为了满足社交和移动互联网时代，海量读写请求和数据爆发式的增长需求，分布式

存储系统被广泛应用。为了快速定位数据，同时提高集群的可扩展性，分布式存储

系统多采取一致性哈希算法对数据进行分区，但一致性哈希依赖哈希函数均衡系统

负载，属于静态均衡策略[1]。

随着键值存储应用领域发展的多样化，采用静态均衡的存储系统给企业造成了极大

的资源浪费。如何结合分布式存储系统的数据分区特点对其进行动态负载均衡成为

迫切需要解决的问题。

负载均衡策略主要分为动态负载均衡策略和静态负载均衡策略。静态负载均衡根据

对系统负载状态的先验分析[2]，预先制定系统负载策略，实现简单；而动态负载

均衡通过分析当前的系统负载情况，动态地分配和调度任务，适应场景多，均衡效

果好。一般分布式系统中，常用的负载均衡算法有随机算法、轮询、权重轮询、最

小连接数和动态反馈[3-5]，在利用这些策略进行负载均衡时，多要求分布式节点

之间具有一定的可替代性，即一个任务可由分布式系统中任意的节点进行处理[6]。

然而，对于分布式存储系统，单个节点并不能存储全量的数据，数据需要进行分区

分块存储，导致存储系统的读写任务只可以由特定节点处理。因此，分布式存储系

统的负载均衡与系统的数据分区方式紧密相关[7]。

目前主流的分区方式有范围分区、列表分区和哈希分区三种方式。分布式键值存储

系统只有一个列值，无法基于列表分区；范围分区是按照键的范围来进行数据分区，

典型的有MongoDB的Sharding分区方式。文献[8]通过对MongoDB的负载均

衡策略进行改进，优化了MongoDB的应用场景；而在分布式键值存储系统中，

应用最广泛的是哈希分区方式。相比于范围分区，哈希分区具有天然的静态负载均

衡特性，通过选择合适的哈希函数，就可以实现数据在哈希空间内的均衡分布。

常用的哈希函数有MD5和SHA。文献[9]给出的一致性哈希解决了哈希分区在集

群扩缩容时的数据重分布问题，在此基础上，Amazon的Dynamo在实现一致性

哈希策略时提出了虚拟节点的理论来解决集群内节点之间异构的问题[10]。

然而，这些方法都属于静态一致性哈希负载均衡策略，它们仅依赖于哈希函数进行

均衡负载，面对集群中部分数据的热点访问带来的负载不均，静态负载均衡算法将

无法调节[11]。

通过分析基于虚拟节点的一致性哈希策略，结合动态反馈的负载均衡技术，提出了

一种基于分片的一致性哈希动态负载均衡策略。使用与物理节点解耦的分片代替传

统的虚拟节点，并利用针对分片的监控信息对负载进行均衡调度。同时，调度策略

分为分片级和节点级两个层面，从而进一步优化负载均衡的效果。相比于传统基于

节点负载的动态反馈均衡策略，该策略具有更细的监控和调度粒度，从而实现了更

高效的均衡调度。

一致性哈希由MIT的Karger及其合作者提出，利用哈希函数将存储的key和服

务器哈希到同一个环形地址空间中，从而确定数据和服务器的映射关系。

相比于固定哈希系统扩容时需要对所有节点上的数据进行重新分布，当采用一致性

哈希的系统扩容时，只需要迁移相邻节点上的数据。为了合理分配集群内异构节点

的负载，Amazon在Dynamo中引入虚拟节点(VirtualNode)概念，一个物理节

点可配置成多个虚拟节点。

基于虚拟节点的一致性哈希仍然是通过哈希函数的平衡性，在概率上保证不同虚拟

节点上分配到的数据量一致[12]。然而，存储系统的负载不均还表现在系统访问压

力的分布不均，面对动态变化的访问负载，数据的平均分布并不足以保证访问压力

的均衡分布。面对复杂的负载场景，就需要对系统进行动态的负载均衡。改进策略

利用分片机制对一致性哈希策略进行了相应的改进，主要包括两点：

(1)将虚拟节点和物理节点彻底解耦，采用分片(Fragment)作为数据分区存储的逻

辑单元。

(2)基于分片负载监控，对系统负载进行动态的均衡调度。

基于虚拟节点的一致性哈希策略多采用静态配置文件维护虚拟节点与物理节点之间

的映射关系[13]。改进策略利用基于分片的一致性哈希，通过动态的分片管理物理

节点与数据之间的映射关系，分片可以进行分裂、合并、迁移操作。

3.1数据模型

在改进的一致性哈希策略中，数据与分片之间的位置关系使用哈希函数确定。一个

分片处理哈希值在当前分片ID与前驱分片ID之间的数据，数据与分片之间的映

射关系为：

Ft=(Fi-1≤Hash(Key)

其中，Ft为目标分片ID；Fi-1为目标分片的前驱分片ID；Hash为选用的哈希函

数，如MD5、SHA-1等。

利用哈希分区的静态负载均衡特性，使得数据在一致性哈希环地址空间内均匀分布

[14]。在获得目标分片ID后，需要查询目标分片所在的物理节点，分片与物理节

点的映射关系在负载均衡过程中会变化，通过有序的Map表管理。在取得物理节

点的地址后，客户端与物理节点直接进行数据操作。

物理节点上数据的读写操作都会被记录，存储系统的负载与单位时间内数据的读写

请求次数以及数据传输量和存储容量消耗成正比。因此，存储系统中服务器的负载

状况的主要影响因素有：单位时间读请求次数(记为QPS)、单位时间写请求次数

(记为UPS)、单位时间内平均传输的数据大小(记为DPS)和服务器消耗的存储空间

(记为S)。而每台服务器所能达到的最大负载阈值能够通过硬件指标进行计算，或

者通过性能压力测试来计算，因此，服务器的负载可以通过式(2)计算：

load=α+β+γ(2)

其中，QPSmax、UPSmax为指定配置的服务器在系统要求的读写延迟指标下，

单位时间内的最大读写次数；α,β,γ为权重因子。根据服务器压测数据设定，以分

片为单位统计UPS、QPS、DPS三项负载元数据。

基于上述数据模型可以实现对分布式存储系统的动态负载均衡，存储系统的负载均

衡涉及数据的跨节点迁移，均衡效果具有一定的滞后性。基于分片的一致性哈希动

态负载均衡策略采用时间窗口的方式，对一个时间窗内的平均负载进行分析，从而

决定当前节点或者分片是否过载。负载均衡的主要代价是数据跨节点迁移带来的网

络资源占用，通过分片级和节点级两个级别的负载均衡操作，降低负载均衡数据迁

移的粒度，从而优化负载均衡资源的消耗问题。

3.2分片级负载均衡

除了节点间的负载不均问题之外，分片间的负载不均问题也会导致系统资源的浪费。

同时，由于分片是跨节点数据迁移的最小单位，分片之间负载不均，提高了制定节

点之间负载均衡策略的复杂度。而基于分片的一致性哈希动态负载均衡，在负载统

计的粒度上可以由传统的节点级细化到分片级，利用分片的分裂、合并操作实现分

片级负载均衡。

分片级负载均衡以同一节点上分片的平均负载为目标，首先对时间窗内整个节点上

所有的分片计算出一个平均负载，记为loadavg。再以平均负载为基准设定阈值，

负载高出阈值的分片加入超载队列，低于阈值的加入低载队列。对超载队列中的分

片进行分裂操作，分裂为M个均载分片，若记待分裂分片负载为loadcur，则分

裂的分片个数与当前负载的关系为：

M=int()

记Fi为分裂的第i个分片的分片号，则该分片号可由式(4)给出：

Fi=int(Fi-1+×(Fi-Fi-1))

其中，F0为待分裂分片的前驱分片号。

分片的分裂和合并操作可以实现负载在分片之间的重分配。由于存储服务器同一个

节点上磁盘内和磁盘间的数据带宽要远高于机器之间的网络带宽，因此，节点内分

片之间的数据迁移效率要远高于节点之间的数据迁移效率。针对分片的负载均衡策

略的主要流程如图1所示。对低于轻载阈值的分片，加入轻载分片队列，对分片

进行合并操作，从而减少管理元信息的数量，降低系统管理开销。

3.3节点级负载均衡

分片级的负载均衡提高了对分片的管理和操作效率，但并不能改善不同节点之间的

负载不均问题，因此，还需要进行物理节点级别的负载均衡。物理节点级别的负载

均衡主要通过对分片进行跨节点的迁移来完成。事实上，就是在改变分片与物理节

点之间的映射关系，具体流程与分片级负载均衡相似。

节点间的负载均衡由于涉及到数据在网络中的传输，触发均衡的阈值一般设置的较

高。负载均衡的流程与分片级均衡流程相似，同样是确定重载节点后，选取合适的

分片向低载节点迁移。考虑到某些节点上分片平均负载较高，即便最小的分片迁移

到其他节点也会导致其他节点成为重载节点，当出现这种情况时，均衡策略会先对

当前节点中的部分分片进行分裂操作，然后再选取合适的分片迁移。

为了验证改进的一致性哈希动态负载均衡策略，通过一个负载均衡系统对其进行测

试实验。

测试环境中，核心路由连接了动态负载均衡系统的管理集群、数据集群、监控集群

以及客户端。管理集群是系统的中心节点；数据集群包含所有数据节点，部署了调

度和监控模块；监控集群负责收集系统监控信息；客户端是访问负载均衡系统的入

口。

系统采用接口化的设计，通过实现不同的元数据管理接口和均衡决策接口，就可以

实现不同的数据分区策略和负载均衡策略。利用这个特性，分别实现了基于分片和

基于虚拟节点的负载均衡系统，然后进行实验测试。

实验中，采用相同的元数据规模(3个物理节点，12个虚拟节点或分片)和测试数据，

均衡的目标值设置为系统平均负载的20%以内。初始状态分片和虚拟节点的分布

情况如表1所示。

通过施加一定规律的负载，对分片级别的负载均衡进行实验，当负载不均超过设定

阈值时，负载均衡系统进行负载均衡操作。从图2可以看出，通过对重载分片(85、

425、765)的分裂操作，降低了重载分片的负载；同时，通过对轻载分片(255、

595、935)的合并操作，平衡了分片之间差异过大的负载。

在分片级均衡的基础上，对节点级负载均衡进行实验，分别对基于虚拟节点和基于

分片的负载均衡系统施加负载压力。图3和图4分别是两个系统在负载均衡前的

负载分布图。

从图3可看出，基于虚拟节点的系统不仅出现了物理节点之间的负载不均衡，同

时在虚拟节点之间也出现了负载不均。从图4可看出，基于分片的系统，虽然出

现了节点之间的负载不均，但得益于节点内部分片间的负载均衡策略，分片之间负

载分布较为均衡。

经过一段时间的负载均衡调度，两个系统中各个物理节点的负载状况如图5所示。

从负载均衡的效果来看，基于虚拟节点的系统和基于分片的系统都能够通过一系列

的调度操作对负载不均衡的节点进行有效的负载均衡，达到将节点之间的负载控制

在平均负载的20%以内的目标。但基于分片的系统在数据迁移量和均衡效果上要

略优于基于虚拟节点的系统，迁移量上降低了约30%左右，且节点之间的负载也

更加均衡。

对以上实验结果进行分析，基于分片的系统，在负载均衡过程中采用了两级均衡策

略，其中分片级的负载均衡利用机器空闲资源在物理节点内部进行负载调度，使负

载分布均衡。相比之下，基于虚拟节点的系统，在采用相同的元数据复杂度(虚拟

节点数与分片数相同)的情况下，虚拟节点之间负载不均，导致在均衡决策时，迁

移负载的粒度较大，在多数场景下迁移的数据量要高于基于分片的系统。

从一致性哈希出发，结合动态负载均衡技术，设计了一个基于分片的一致性哈希动

态负载均衡策略。利用分片进一步解耦数据和节点的映射关系，并在对分片的监控

数据进行动态收集、分析的基础上，对分片间和节点间的负载进行均衡调度。实验

结果表明，该策略保留了一致性哈希在系统扩展性上的优势，同时优化了一致性哈

希策略负载均衡的总体效果。借助基于分片的一致性哈希负载均衡策略，可以有效

均衡系统负载，提高存储系统的效率。

【相关文献】

[1]黄秋兰，程耀东，陈刚.分布式存储系统的哈希算法研究[J].计算机工程与应用,2014,50(1)：1-

4.

[2]凌云,周华锋.面向异构集群系统的动态负载均衡技术研究[J].计算机工程与设计,2008,29(12)：

3068-3070.

[3]RaiI,mweightedroundrobinschedulingalgorithmsforinput

queuedswitches[C]//IEEEinternationalconferenceon

ki,Finland:IEEE,2001:2028-2032.

[4]KimJS,edroundrobinpacketschedulerusingrelativervice

share[C]//IEEEmilitarycommunicationsconference.[s.l.]:IEEE,2001:988-992.

[5]陈伟，张玉芳，熊忠阳.动态反馈的异构集群负载均衡算法的实现[J].重庆大学学报:自然科学

版,2010,33(2):73-78.

[6]朱虹宇，李挺，闫健恩，等.基于动态负载均衡的分布式任务调度算法研究[J].高技术通讯，

2014,24(12):1261-1269.

[7]尹向东,杨杰,屈长青.云计算环境下分布式文件系统的负载平衡研究[J].计算机科学，2014，

41(3):141-144.

[8]邓志飞，应良佳，王军威.基于IODA算法MongoDB负载均衡的改进[J].现代电信科技，

2013(7):9-13.

[9]KargerDR,LehmanE,LeightonFT,tenthashingandrandom

trees:distributedcachingprotocolsforrelievinghotspotsontheworldwide

web[C]//ACMsymposiumontheoryofcomputing.[s.l.]:ACM,1997:654-663.

[10]dynamoDB:aamlesslyscalablenon-relationaldataba

rvice[C]//ACMSIGMODinternationalconferenceonmanagementof

data.[s.l.]:[s.n.],2012:729-730.

[11]张聪萍,尹建伟.分布式文件系统的动态负载均衡算法[J].小型微型计算机系统，

2011,32(7):1424-1426.

[12]赵见.高性能高可用键值存储系统的设计与实现[D].成都：电子科技大学，2010.

[13]SchintkeF,ReinefeldA,HaridiS,edpaxoscommitfortransactionson

DHTs[C]//IEEE/ACMinternationalconferenceoncluster,cloudandgrid

computing.[s.l.]:IEEE,2010:448-454.

[14]田浪军，陈卫卫，陈卫东,等.云存储系统中动态负载均衡算法研究[J].计算机工

程,2013,39(10):19-23.