面向多进程负载均衡的Hash算法比较与分析

张 莹,吴和生

(1.南京国电南自新能源科技有限公司,南京210032;2.南京大学软件学院,南京210093)

面向多进程负载均衡的Hash算法比较与分析

张 莹1,吴和生2

(1.南京国电南自新能源科技有限公司,南京210032;2.南京大学软件学院,南京210093)

Hash算法在高性能多进程负载均衡中起到关键作用,但目前面向多进程负载均衡的Hash算法研究主要集中在Hash算法设计和领域应用方面,较少有文献对现有的Hash算法性能进行分析比较。为此,总结面向多进程负载均衡的Hash算法应具有的特征,并据此筛选出5种适用于多进程负载均衡的主流Hash算法,从分配均衡性和耗时等方面进行理论分析和实验评估,为多进程负载均衡中Hash算法的选择与使用提供依据。分析结果表明, Toeplitz Hash算法较适合用于多进程的负载均衡。

多进程;负载均衡;Hash算法;分配均衡;时延;高性能

1 概述

负载均衡是云计算的基础成分,是服务器集群化的关键环节[1]。相较于传统的单进程负载均衡架构,在云计算中多进程架构可以充分利用处理器的并行处理能力以提高系统的整体性能。因此,多进程负载均衡成为现阶段云计算的研究热点[2-3]。

负载均衡的资源分配算法是负载均衡器的设计关键。在进行网络和服务器负载均衡时可供选择的负载均衡算法很多,主要有Hash算法、轮循算法、最少连接算法、响应速度算法、加权法等。其中,Hash算法是最常用的算法。特别在云计算环境中,Hash算法在高性能多进程负载均衡器中起着关键作用[4],其分配均衡性和时延直接影响到云计算负载均衡器的性能。

面向多进程负载均衡的Hash算法性能研究得到广泛关注。文献[5]研究了高速和大规模数据传输情况下,根据网络流量特性提高并行网络入侵检测系统(Network Intrusion Detection System,NIDS)节点性能的基于高效Hash算法的多进程负载均衡方案。文献[6]针对大量分布式会话启动协议(Session Initiation Protoco,SIP)请求研制的高性能多进程负载均衡器不仅提供了细粒度的控制,而且在吞吐量和响应时间方面有明显的提高。文献[7]探讨了多核服务器中基于Hash算法的多进程负载均衡调度技术。这些针对多进程负载均衡的Hash算法研究主要侧重于Hash算法设计和领域应用方面,尚未对现有的Hash算法的性能进行分析比较研究。鉴于Hash算法性能在多进程负载均衡中的关键作用,对其进行性能分析和比较研究无疑十分必要。

本文针对面向多进程负载均衡的Hash算法应具有的共性特征,从分配均衡性和时延等方面分析比较5种主要的适用于多进程负载均衡的Hash算法,并进行实验评估,为多进程负载均衡中Hash算法的选择与使用提供分析方法和依据。

2 用于多进程负载均衡的常用Hash算法

2.1 多进程负载均衡的特点

在负载均衡发展的初期,多数处理器是单核处理器。对负载均衡器而言,使用多进程架构并不能提升其整体性能,特别是在网卡、带宽、交换机性能不高的情况下,集群性能的瓶颈并不是负载均衡器的处理能力。所以,多数负载均衡器采用单进程架构。

近年来,多核处理器成为主流,操作系统多支持多核处理器,多个进程得以在物理上并行[8]。在这种情况下,使用多进程架构可以提升负载均衡器的整体性能。而且随着网卡、带宽等网络设施性能的不断提升,负载均衡器的性能逐渐成为瓶颈,尤其是在进行一些非常耗时的操作(如需要大量计算时间的SSL卸载)时。据此,现代负载均衡正逐渐向多进程架构转变。

相较于传统的单进程负载均衡架构,多进程架构具有如下特点:

(1)可以充分利用多核处理器的并行处理能力以提高系统的整体性能。

(2)需要保证当有多个用户进程尝试连接时,所有来自同一客户端IP的连接请求都被发往同一个用户进程,从而保证所有属于同一用户会话的数据包都被发往同一个负载均衡进程。

(3)需要保证大量用户进程尝试连接时,其自身各个进程分配的均衡性。

2.2 适用于多进程负载均衡的Hash算法特征

Hash算法的种类很多,根据多进程负载均衡不同于单进程架构的特点,适用于多进程负载均衡的Hash算法应该具有如下特征:

(1)对多种Hash输入类型都能产生较为均匀的Hash分布。这些 Hash输入类型主要包括 TCP/ IPV4,TCP/IPV6,IPV4和IPV6协议数据包。

(2)在进程数目较少(如2个)或较多(如64个)的情况下都能将输入均匀地散列到各个进程中。

(3)Hash函数的耗时要少。因为对每个新建连接都需要进行Hash运算,该Hash函数必须能计算得非常快,否则会成为系统性能的瓶颈。

2.3 多进程负载均衡常用Hash算法

根据上述特征分析表明,适用于多进程负载均衡的Hash算法主要有5种(见算法1～算法5)。文献[9-10]讨论了前4种Hash算法的性质,文献[11]讨论了第5种Hash算法的性质。

算法1 使用源IP地址进行Hash

这是最简单的Hash方法,直接用源IP地址模进程数N即可。该Hash函数表示如下:

当N=2k时,只需要取源IP地址的最后k比特,就是Hash函数的结果。

算法2 使用源IP的异或折叠(XOR Folding)

异或折叠技术被用于许多Hash函数的设计中,且在很多类似应用中被证明能够提供很好的效果。使用源IP地址的异或折叠Hash函数可以表示成:

其中,Di表示源IP地址的第i个字节。

算法3 使用源IP与目的IP的异或折叠

对算法2的简单改进,将目的IP地址也作为Hash函数的参数,即将源IP地址与目的IP地址一起做异或折叠。该Hash函数表示如下:

算法4 CRC16

16 bit循环冗余检查(Cyclic Redundancy Check, CRC)算法已经被证实可用于负载均衡中。虽然与之前的几种方法相比计算量较大,但是CRC16算法在高速系统中已经被成功运用。本文用网络数据包中的five-tuple(源IP、目标IP、源端口、目标端口、协议号)作为CRC16算法的输入,再对结果取模以构造Hash函数,该Hash函数描述如下:

H=CRC16(five-tuple)%N

算法5 Toeplitz Hash

文献[12]介绍了Toeplitz矩阵与Toeplitz hash。Toeplitz hash是一种使用Toeplitz矩阵计算Hash值的Hash方法,Toeplitz矩阵的特征是矩阵中处于同一对角线上的元素具有相同的值。更为精确地说,对n行m列的Toeplitz矩阵A,对任意1≤i,k≤n, i≤j,l≤m,如果 k-i=l-j,则 Ai,j=Ak,l。一个Toeplitz矩阵S=an-1…a1a0a-1…a-n+1如下:

任意长为(n+m-1)bit的序列S都对应一个n行m列的Toeplitz矩阵Ts。序列S定义了矩阵T的第1列和第1行,从而定义了整个Toeplitz矩阵。序列S的前n个元素被从下到上映射到矩阵的第一列上,序列S的后m个元素则被从左到右映射到矩阵的第一行上,上述矩阵对应序列为 an-1…a1a0a-1…a-n+1。一个n行m列的Toeplitz矩阵可以用来将长度为m的序列Hash到长度为n的另一个序列上。Free BSD内核源码中提供了一个用于实现Receive-Side Scaling功能的Toeplitz矩阵[13],本文使用该矩阵计算request_sock的Hash值。

3 理论分析及实验评估

3.1 5种Hash算法的比较分析

对于一个Hash算法,评价其优劣的重要标准应为分配均衡性和时间消耗。

Hash算法的分配均衡性,即对任意一组样本,进入Hash表每一个单元之概率的平均程度。因为这个概率越平均,数据在表中的分布就越平均,表的空间利用率就越高。

现有研究表明,比特之间异或运算和位移运算能够提高哈希值的随机特性[14]。这5种Hash算法本质上都是位移和异或操作的组合,因此,都具有较好的分配均衡性。

Hash算法的时间消耗也直接影响着系统的整体性能。不难计算,这5种Hash算法时间复杂度均为O(1)。本文将在3.2节中通过实验验证哪种Hash算法计算最快。

3.2 实验及评估

本文实验所使用数据集由麻省大学(Umass)网络中心收集[15],该数据集记录了麻省大学2007年6月9日-2007年6月22日期间每天上午9:30-10:30通过学校网关的数据包,共包括654 795条记录。本文实验使用上文提到的5种Hash算法计算这些包的Hash值,测试当存在2个、4个、8个、16个、32个、64个负载均衡进程的情况下Hash函数的分配均衡性,同时对这些过程计时,以考察Hash函数的时间消耗。

5种Hash法的实验结果如图1～图5所示,算法耗费时间分别为0.031 s,0.089 s,0.162 s,3.91 s,0.153 s。

从实验结果中可以看出,Hash算法1产生实验结果的不均衡性明显高于其他4种算法,这种不均衡性将导致多进程负载均衡系统整体性能的下降,所以,算法1明显不是一个最适合多进程负载均衡特性的算法。

对其余4种算法产生的实验结果求标准差,结果如图6所示。可以看出,当Hash的目标数量较多时,4种Hash算法方差都比较接近,这意味着这4种算法都能够较为均匀地将网络数据包分配到较大的集合中;但当Hash目标数量较小时(如2个或4个),算法2和算法3的均衡性严重降低。而算法4和算法5的均衡性几乎不受Hash目标数多少的影响,具有很好的稳定性,而且无论Hash目标的多少,这两种算法的实验结果都具有最小的标准差,提供最均衡的 Hash分配。但算法4的时间消耗(3.91 s)远大于算法 5 (0.153 s),在多进程负载均衡器中,Hash算法的时间消耗直接影响着系统的整体性能,从这个角度来看,算法5优于算法4。

综合考虑Hash算法的分配均衡性、时间消耗等各方面因素,可见Toeplitz hash是最适合应用于多进程负载均衡的Hash算法。值得注意的是,只有当Hash算法产生较为均衡的分配时,多进程负载均衡器才能获得最大的性能提升。

图1 源IP地址取模Hash结果

图2 源IP地址XOR Folding Hash结果

图3 目的IP地址与源IP地址XOR Folding Hash结果

图4 CRC16 Hash结果

图5 Toeplitz Hash结果

图6 算法2～算法5实验结果标准差

4 结束语

为对面向多进程负载均衡的Hash算法进行性能研究,本文在综述主流研究成果的基础上,分析了适用于多进程负载均衡的Hash算法特征,并以这些特征为原则,筛选出5种广泛应用于高性能负载均衡的Hash算法,从分配均衡性和时间消耗等方面进行算法分析和实验评估。实验结果表明,当Hash算法产生较为均衡的分配时,应用该算法的多进程负载均衡才能获得最大的性能提升,从而为多进程负载均衡中Hash算法的选择与使用提供了依据。鉴于Hash算法在高性能多进程负载均衡中起到关键作用,今后将在比较已有算法性能基础上,研究性能更优的Hash算法。

[1] Chiang M L,Yang Chenyu,Lien S L.Kernel Support for Fine-grained Load Balancing in a Web Cluster Providing Streaming Service[C]//Proc.of the 12th International Conference on Algorithms and Architectures for Parallel Processing.Fukuoka,Japan:Springer,2012:458-472.

[2] Yang Peijia.Load Balancing Mechanism for QoS-aware Cloud Computing Using Eucalyptus Platform[EB/OL]. [2013-03-10].http://140.118.33.1/ETD-db/ETD-search/view_etd?URN=etd-0612111-175517.

[3] Hu Jinhua,Gu Jianhua,Sun Guofei,et al.A Scheduling Strategy on Load Balancing of Virtual Machine Resources in Cloud Computing Environment[C]//Proc.of the 3rd International Symposium on Parallel Architectures,Algorithms and Programming.Dalian,China: [s.n.],2010:89-96.

[4] Randles M,Lamb D,Taleb-Bendiab A.A Comparative Study into Distributed Load Balancing Algorithms for Cloud Computing[C]//Proc.of the 24th IEEE International Conference on Advanced Information Networking and Applications Workshops.Perth,Australia:IEEE Computer Society,2010:551-556.

[5] Kim N U,Park M W,Park S H,et al.A Study on Effective Hash-based Load Balancing Scheme for Parallel NIDS[C]//Proc.of the 13th International Conference on Advanced Communication Technology.Phoenix Park,Korea:IEEE Press,2011:886-890.

[6] Jiang Hongbo,Iyengar A,Nahum E,et al.Design, Implementation,and Performance of a Load Balancer for SIP Server Clusters[J].IEEE/ACM Transactions on Networking,2012,20(4):1190-1202.

[7] Guo Danhua,Bhuyan L N,Liu Bin.An Efficient Parallelized L7-filter Design for Multicore Servers[J]. IEEE/ACM Transactions on Networking,2012,20(5): 1426-1439.

[8] Gepner P,Kowalik M F.Multi-core Processors:New Way to Achieve High System Performance[C]//Proc. of PARELEC'06.Washington D.C.,USA:[s.n.], 2006:9-13.

[9] Cao Zhiruo,WangZheng,ZeguraE.Performanceof Hashing-based Schemes for Internet Load Balancing[C]// Proc.of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies.Tel Aviv,Israel: IEEE Press,2000:332-341.

[10] Mansour Y,Nisan N,Tiwari P.The Computational Complexity of Universal Hashing[C]//Proc.of the 22nd Annual ACM Symposium on Theory of Computing. Baltimore,USA:ACM Press,1990:235-243.

[11] Microsoft Corporation.Receive-side Scaling Enhancements in Windows Server 2008[EB/OL].[2013-08-11]. http://www.microsoft.com/whdc/device/network/ndis_ rss.mspx.

[12] Krawczyk H.New Hash Functions for Message Authentication[C]//Proc.of Cryptology-Eurocrypt'95.Saint-Malo,France:[s.n.],1995:301-310.

[13] Ziehau S.FreeBSD/Linux Kernel Cross Reference:sys/ net/toeplitz.c[EB/OL].[2013-07-21].http://fxr. watson.org/fxr/source/net/toeplitz.c?v=DFBSD.

[14] 程 光,龚 俭,丁 伟,等.面向IP流测量的哈希算法研究[J].软件学报,2005,16(5):652-658.

[15] Umass.YouTube Traces from the Campus Network [EB/OL].[2013-06-15].http://traces.cs.umass.edu/ index.php/Network/Network.

编辑 金胡考

Comparison and Analysis of Hash Algorithm for Multi-process Load Balancing

ZHANG Ying1,WU He-sheng2
(1.Nanjing Guodian Nanzi New Energy Science&Technology Co.,Ltd.,Nanjing 210032,China;
2.Software Institute,Nanjing University,Nanjing 210093,China)

Hash algorithm plays a key role in high performance multi-process load balancing.The study of Hash algorithm for multi-process load balancing is mainly concentrated on the design and application of Hash algorithm,yet analysis and comparative study for the performance of the existing Hash algorithm are fewer.So this paper summarizes the common features that Hash algorithm for multi-process load balancing should have,and screens five major Hash algorithms applied in multi-process load balancing.Theoretical analysis and experimental evaluation about balanced allocation and time-consuming of Hash algorithm provides a foundation for selecting Hash algorithm for multi-process load balancing,and shows that Toeplitz Hash is the best one.

multi-process;load balancing;Hash algorithm;allocation balancing;time delay;high performance

1000-3428(2014)09-0071-06

A

TP393

10.3969/j.issn.1000-3428.2014.09.015

国家自然科学基金资助项目(60503021,60721002,60875038)。

张 莹(1975-),女,工程师,主研方向:Hash算法;吴和生,高级工程师、博士研究生。

2013-07-24

2013-11-05E-mail:zy429@163.com