面向多進程負載均衡的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