基于一致性哈希的Web动态负载均衡算法研究

李杰 聂云峰 金敏

摘要：随着Internet的迅猛发展，Web服务器集群中的负载均衡算法备受关注。为优化Web集群负载均衡能力，提出了基于一致性哈希的负载均衡算法（DCH）。首先定义了集群中服务器各项性能指标的量化值，根据量化值计算初始虚拟节点集合，优化了由服务器性能差异导致的负载分配不均；然后细化周期内负载定义，根据量化的服务器性能值与负载值动态计算虚拟节点集合，使集群负载更均衡。实验比较分析表明，该算法能有效降低集群系统的平均响应时间，提高系统吞吐量，从整体上提升集群系统性能。

关键词：一致性哈希；負载均衡；集群；虚拟节点；吞吐量

DOIDOI：10.11907/rjdk.173200

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）008-0121-04

英文摘要Abstract：With the rapid development of Internet，load balancing algorithms in Web server cluster have attracted more and more attention of researchers.In order to optimize the load balancing ability of Web cluster，this paper proposes a load balancing algorithm （DCH） based on consistent hash.The first quantitative performance index of each server in the cluster was defined，according to the quantitative calculated the initial virtual nodes，the load distribution inequality caused by server performance difference is optimized； then refinement cycle load is defined，according to the quantitative calculation of the virtual server performance node set and dynamic load value，the cluster load a more balanced.Through experimental comparison and analysis，the algorithm can effectively reduce the average response time of the cluster system and improve the system throughput and the performance of the cluster system as a whole.

英文关键词Key Words：consistency Hash； load balancing； cluster； virtual node； throughput

0 引言

随着Internet的迅猛发展，网络流量呈指数级增长，传统的单台Web服务器难以应付当前多网络环境下的高并发请求[1]。为给用户提供良好体验，保持服务器的高吞吐量，使用服务器集群成为当前最佳选择，集群中的负载均衡算法成为研究热点[2]。负载均衡算法决定了集群性能，算法性能不良会造成服务器资源浪费，导致集群中服务器之间负载不均衡，影响集群的吞吐量及响应时间。负载调度算法分为静态调度和动态调度算法。常用的静态调度算法包括：轮叫调度（Round Robin，RR）[3]，按顺序将请求依次分发到服务器；加权轮叫调度（Weighted Round Robin，WRR）[4]，对性能不同的服务器集群使用合适的权值代表服务器性能，按权值高低和轮叫方式将请求分发到服务器。常用的动态算法包括：最小连接调度（Least Connections，LC）[5]，获取集群下所有服务器的活跃连接数，将请求分发给连接数最小的服务器；加权最小连接（Weighted Least Connections，WLC） [6]，根据集群中服务器的性能差异为服务器指定权值，采用最小连接调度策略使服务器已建立的连接数和其权值成正比。

Genova等[7]提出了针对Pick-K的改进算法Pick-KX，在更新周期内，首先从集群S1，S2，S3，…，SN中选择K台服务器，获取它们的负载L1，L2，L3，…，LK，1≤K≤N，每当有请求到达时，将当前的请求以Pj=Xj/∑Ki=1Xj的概率分配选中的第j台服务器，其中Ltotal=∑Ki=1Li，Xj=（Ltotal-Lj）/Ltotal，j=1，2，3，…，K。

RR与WRR不考虑实时服务器实际负载状态，很容易造成服务器间负载倾斜、集群响应请求时间长等问题[8]。LC与WLC存在以下两个问题：①在实际应用中，用户的不同请求（如网页、图片、动态数据等）对RS造成的负载是不等量的，以服务器处理请求的连接数作为负载的衡量标准，缺乏一定的客观性；②这两种算法都是周期性获取服务器集群的连接数，每个周期内的请求都发给连接数最小的服务器，在局部时间内会导致接收请求的这台服务器过于繁忙而其它服务器空闲[9]。PICK-KX算法虽在理论上做到了概率上的负载均衡，但文献[10]通过实验证实了只有在周期较大且K=2时，才能得到较好效果，而且在周期较大的情况下，未被选中的服务器处于空闲状态，有可能出现局部时间内负载不均现象。

针对以上问题，本文对一致性哈希算法进行改进，提出一种新的算法—DCH（Dynamic Consistent Hashing），解决集群负载倾斜问题，以提高一致性算法在Web应用中的可用性及可靠性。

1 一致性哈希算法

一致性哈希算法（Consistent Hashing，CH）最早由Karger D等[11]提出，是当前主流的分布式哈希表协议之一，初衷是为了解决服务器集群中的热点（hot Pot）问题[12-13]，其基本流程为：设计哈希函数计算虚拟哈希环的哈希空间；对集群中服务器节点，通过哈希函数为其分配哈希值，分配到哈希环上；对用户请求通过哈希函数计算其键的哈希值，在哈希环中按顺时针方向查找第一个服务器，将请求分配给该服务器，如图1所示。该算法在服务器节点较少的情况下有可能造成哈希环上服务器节点分配不均衡，导致负载倾斜。为解决这一问题，亚马逊公司在其云存储平台Dynamo[14-15]中引入了虚拟节点概念。在服务器节点有限而需要很大哈希空间的情况下，将每台服务器虚拟成一组虚拟节点，设置恰当的虚拟节点数目分布到哈希环上。如图2所示，用户请求到达时，先通过哈希函数计算其键的哈希值分配到每个虚拟节点上，再查找该虚拟节点对应的物理服务器，将请求分配给物理服务器。

2 DCH算法

考虑到Web服务器与缓存服务器的差异，对一致性哈希作两点改进，提出DCH算法以适应Web应用环境。首先，集群初始化时，依据集群中各台服务器的性能差异，为每台节点设置不同的虚拟节点数目，不再依赖单预设值。其次，根据集群在运行过程中服务器负载的实时变化，每台服务器的虚拟节点个数也根据负载情况实时变化，以均衡各台服务器间的负载。

2.1 初始虚拟节点数目

服务器性能取决于CPU主频、内存大小及读取速率、系统I/O速率、网卡速率、网络带宽速率等因素，而负载的衡量也以这些因素的占用情况作为标准。本文探讨Web应用环境的情况，使用CPU主频、内存大小、网络带宽占用率作为服务器性能衡量标准，以三者的占用率作为负载的衡量标准。

2.3 DCH算法流程

DCH算法流程：①算法初始化，首个周期内收集各服务器性能，利用式（1）量化性能，进而利用式（2）计算初始虚拟节点数目，利用哈希函数h=H（x）将虚拟节点分配到哈希环上；②请求到达时，对请求进行IP地址哈希计算，按顺时针将其映射到离其最近的虚拟节点上，进而分配给RS；③m个周期T后，每个周期开始时，收集服务器负载指标，判断是否有指标超过临界阈值。超过阈值的服务器设置其负载权值为0，反之利用式（3）计算量化负载，利用式（4）计算负载权值，利用式（5）计算虚拟节点数目，重复步骤②分配请求；④当某台服务器的负载L（Ci）、L（Mi）、L（Bi）为0时，判定该服务器宕机，将该服务器的负载权值Pi设为0，不再发送请求到该服务器。当该服务器恢复正常时，计算该服务器虚拟节点数目并分配请求；⑤新的服务器节点加入时，按照步骤①、②、③计算该服务器的初始虚拟节点数目及动态虚拟节点数目，进而分配请求。

3 算法性能评估

验证改进算法的可行性，搭建基于LVS的集群系统，在集群中使用性能不一的服务器，分别使用WRR算法、WLC算法和DCH算法调度用户请求，测试在不同调度算法下的集群性能。集群性能在客户端体现为响应时间（RT）的长短，在集群服务器端体现为吞吐量（Throughput）上。在评估算法性能时，本文以这两个指标作为评估标准。RT的测试采用如表1所示固定RS数量的集群，集群中使用了1台LB，3台RS，1台客户机。throughput的测试与集群中服务器数量有关，测试时分别测量从1～8台服务器集群规模下的throughput值。实验中，设置向量[k1，k2，k3]为[0.6，0.2，0.2]，向量[w1，w2，w3]为[5，2.5，2.5]，周期T为10s，n为150，m为100，阈值α、β、γ分别为90%、85%、90%，采用JMeter工具模拟用户请求。

3.1 响应时间

请求响应时间实验结果如图3所示。图中横坐标QPS表示单位时间请求个数，纵坐标表示响应时间。从图中可以看出，在请求低于1 000时，3种调度算法的响应时间没有明显差别；当请求数量大于1 000时，DCH算法响应时间开始低于WRR和WLC算法；请求量达到1 300时，DCH算法响应时间低于WRR算法15%，低于WLC算法8%，且随着请求QPS的增大，差距越来越大。

3.2 集群吞吐量

集群吞吐量实验结果如图4所示。图中横坐标表示集群中服务器数量，纵坐标表示集群吞吐量。当RSN≤3时，三者吞吐量相差不大，当RS數量N>3时，使用DCH算法的集群吞吐量开始高于使用WLC和WRR集群的吞吐量，而且随着N值的增加，差距越来越明显。到N=8时，DCH算法吞吐量高于WRR算法13%，高于WLC算法10%。

3.3 实验结论

综上实验，使用改进算法的集群在请求响应时间和吞吐量上都好于使用WRR和WLC的集群，这表明在并发量高的环境下，改进算法在负载调度上更加合理，改进算法提高了集群应对高并发的极限能力。

4 结语

集群技术已成为互联网发展的主流趋势，运用负载均衡调度算法进行研究是十分必要的。本文基于一致性哈希算法提出一种用户Web服务器集群的动态负载均衡算法，考虑服务器性能及服务器负载情况，在固定的周期时间内评估服务器的接收负载能力，均衡地将负载分配到集群中，提高了集群吞吐量，缩短了响应时间，对Web服务器集群具有实用价值。

参考文献：

[1] 章文嵩，吴婷婷，金士尧，等.一个虚拟Internet服务器的设计与实现[J].软件学报，2000，11（1）：122-125.

[2] SONG B，YU G，WANG D，et al.An efficient user task handling mechanism based on dynamic load-balance for workflow systems[J].Lecture Notes in Computer Science，2003（2642）：483-494.

[3] 陈志刚，刘安丰，熊策，等.一种有效负载均衡的网格Web服务体系结构模型[J].计算机学报，2005，28（4）：458-466.

[4] 郭成城，晏蒲柳.一种异构Web服务器集群动态负载均衡算法[J].计算机学报，2005，28（2）：179-184.

[5] 陈一骄，卢锡城，时向泉，等.一种面向会话的自适应负载均衡算法[J].软件学报，2008，19（7）：1828-1836.

[6] SHARIFIAN S，MOTAMEDI S A，AKBARI M K.An approximation-based load-balancing algorithm with admission control for cluster Web servers with dynamic workloads[J].Journal of Supercomputing，2010，53（3）：440-463.

[7] GENOVA Z，CHRISTENSEN K J.Challenges in URL switching for implementing globally distributed Web sites[C].IEEE，International Workshops on Parallel Processing.2000：89-94.

[8] BUNT R B，EAGER D L，OSTER G M，et al.Achieving load balance and effective caching in clustered Web servers[C].Proceedings of International Web Caching Work，1999（6）：159-169.

[9] SOKLIC M E.Simulation of load balancing algorithms：a comparative study[J].ACM Sigcse Bulletin，2002，34（4）：138-141.

[10] ZHANG H，LIAO J，ZHU X.Advanced dynamic feedback and random dispatch load-balance algorithm[J].Journal of Electronics，2007，23（5）：641-644.

[11] 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].Twenty-Ninth ACM Symposium on Theory of Computing，1997：654-663.

[12] KARGER D，SHERMAN A，BERKHEIMER A，et al.Web caching with consistent hashing[J].Computer Networks，1999，31（1116）：1203–1213.

[13] LIN P，NIE H，DING G.Load balancing framework based on consistency hashing algorithm[C].International Conference on Mechatronics and Control.IEEE，2015：1504-1507.

[14] 聶世强，伍卫国，张兴军，等.一种基于跳跃hash的对象分布算法[J].软件学报，2017，28（8）：1929-1939.

[15] NEWCOMBE C，RATH T，ZHANG F，et al.How amazon Web services uses formal methods[J].Communications of the ACM，2015，58（4）：66-73.

（责任编辑：杜能钢）