基于一致性哈希的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.

（責任編輯：杜能鋼）