基于一致性哈希的Web動態(tài)負載均衡算法研究

李杰 聶云峰 金敏

摘要：隨著Internet的迅猛發(fā)展，Web服務器集群中的負載均衡算法備受關(guān)注。為優(yōu)化Web集群負載均衡能力，提出了基于一致性哈希的負載均衡算法（DCH）。首先定義了集群中服務器各項性能指標的量化值，根據(jù)量化值計算初始虛擬節(jié)點集合，優(yōu)化了由服務器性能差異導致的負載分配不均；然后細化周期內(nèi)負載定義，根據(jù)量化的服務器性能值與負載值動態(tài)計算虛擬節(jié)點集合，使集群負載更均衡。實驗比較分析表明，該算法能有效降低集群系統(tǒng)的平均響應時間，提高系統(tǒng)吞吐量，從整體上提升集群系統(tǒng)性能。

關(guān)鍵詞：一致性哈希；負載均衡；集群；虛擬節(jié)點；吞吐量

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.

英文關(guān)鍵詞Key Words：consistency Hash； load balancing； cluster； virtual node； throughput

0 引言

隨著Internet的迅猛發(fā)展，網(wǎng)絡流量呈指數(shù)級增長，傳統(tǒng)的單臺Web服務器難以應付當前多網(wǎng)絡環(huán)境下的高并發(fā)請求[1]。為給用戶提供良好體驗，保持服務器的高吞吐量，使用服務器集群成為當前最佳選擇，集群中的負載均衡算法成為研究熱點[2]。負載均衡算法決定了集群性能，算法性能不良會造成服務器資源浪費，導致集群中服務器之間負載不均衡，影響集群的吞吐量及響應時間。負載調(diào)度算法分為靜態(tài)調(diào)度和動態(tài)調(diào)度算法。常用的靜態(tài)調(diào)度算法包括：輪叫調(diào)度（Round Robin，RR）[3]，按順序?qū)⒄埱笠来畏职l(fā)到服務器；加權(quán)輪叫調(diào)度（Weighted Round Robin，WRR）[4]，對性能不同的服務器集群使用合適的權(quán)值代表服務器性能，按權(quán)值高低和輪叫方式將請求分發(fā)到服務器。常用的動態(tài)算法包括：最小連接調(diào)度（Least Connections，LC）[5]，獲取集群下所有服務器的活躍連接數(shù)，將請求分發(fā)給連接數(shù)最小的服務器；加權(quán)最小連接（Weighted Least Connections，WLC） [6]，根據(jù)集群中服務器的性能差異為服務器指定權(quán)值，采用最小連接調(diào)度策略使服務器已建立的連接數(shù)和其權(quán)值成正比。

Genova等[7]提出了針對Pick-K的改進算法Pick-KX，在更新周期內(nèi)，首先從集群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不考慮實時服務器實際負載狀態(tài)，很容易造成服務器間負載傾斜、集群響應請求時間長等問題[8]。LC與WLC存在以下兩個問題：①在實際應用中，用戶的不同請求（如網(wǎng)頁、圖片、動態(tài)數(shù)據(jù)等）對RS造成的負載是不等量的，以服務器處理請求的連接數(shù)作為負載的衡量標準，缺乏一定的客觀性；②這兩種算法都是周期性獲取服務器集群的連接數(shù)，每個周期內(nèi)的請求都發(fā)給連接數(shù)最小的服務器，在局部時間內(nèi)會導致接收請求的這臺服務器過于繁忙而其它服務器空閑[9]。PICK-KX算法雖在理論上做到了概率上的負載均衡，但文獻[10]通過實驗證實了只有在周期較大且K=2時，才能得到較好效果，而且在周期較大的情況下，未被選中的服務器處于空閑狀態(tài)，有可能出現(xiàn)局部時間內(nèi)負載不均現(xiàn)象。

針對以上問題，本文對一致性哈希算法進行改進，提出一種新的算法—DCH（Dynamic Consistent Hashing），解決集群負載傾斜問題，以提高一致性算法在Web應用中的可用性及可靠性。

1 一致性哈希算法

一致性哈希算法（Consistent Hashing，CH）最早由Karger D等[11]提出，是當前主流的分布式哈希表協(xié)議之一，初衷是為了解決服務器集群中的熱點（hot Pot）問題[12-13]，其基本流程為：設計哈希函數(shù)計算虛擬哈希環(huán)的哈?？臻g；對集群中服務器節(jié)點，通過哈希函數(shù)為其分配哈希值，分配到哈希環(huán)上；對用戶請求通過哈希函數(shù)計算其鍵的哈希值，在哈希環(huán)中按順時針方向查找第一個服務器，將請求分配給該服務器，如圖1所示。該算法在服務器節(jié)點較少的情況下有可能造成哈希環(huán)上服務器節(jié)點分配不均衡，導致負載傾斜。為解決這一問題，亞馬遜公司在其云存儲平臺Dynamo[14-15]中引入了虛擬節(jié)點概念。在服務器節(jié)點有限而需要很大哈?？臻g的情況下，將每臺服務器虛擬成一組虛擬節(jié)點，設置恰當?shù)奶摂M節(jié)點數(shù)目分布到哈希環(huán)上。如圖2所示，用戶請求到達時，先通過哈希函數(shù)計算其鍵的哈希值分配到每個虛擬節(jié)點上，再查找該虛擬節(jié)點對應的物理服務器，將請求分配給物理服務器。

2 DCH算法

考慮到Web服務器與緩存服務器的差異，對一致性哈希作兩點改進，提出DCH算法以適應Web應用環(huán)境。首先，集群初始化時，依據(jù)集群中各臺服務器的性能差異，為每臺節(jié)點設置不同的虛擬節(jié)點數(shù)目，不再依賴單預設值。其次，根據(jù)集群在運行過程中服務器負載的實時變化，每臺服務器的虛擬節(jié)點個數(shù)也根據(jù)負載情況實時變化，以均衡各臺服務器間的負載。

2.1 初始虛擬節(jié)點數(shù)目

服務器性能取決于CPU主頻、內(nèi)存大小及讀取速率、系統(tǒng)I/O速率、網(wǎng)卡速率、網(wǎng)絡帶寬速率等因素，而負載的衡量也以這些因素的占用情況作為標準。本文探討Web應用環(huán)境的情況，使用CPU主頻、內(nèi)存大小、網(wǎng)絡帶寬占用率作為服務器性能衡量標準，以三者的占用率作為負載的衡量標準。

2.3 DCH算法流程

DCH算法流程：①算法初始化，首個周期內(nèi)收集各服務器性能，利用式（1）量化性能，進而利用式（2）計算初始虛擬節(jié)點數(shù)目，利用哈希函數(shù)h=H（x）將虛擬節(jié)點分配到哈希環(huán)上；②請求到達時，對請求進行IP地址哈希計算，按順時針將其映射到離其最近的虛擬節(jié)點上，進而分配給RS；③m個周期T后，每個周期開始時，收集服務器負載指標，判斷是否有指標超過臨界閾值。超過閾值的服務器設置其負載權(quán)值為0，反之利用式（3）計算量化負載，利用式（4）計算負載權(quán)值，利用式（5）計算虛擬節(jié)點數(shù)目，重復步驟②分配請求；④當某臺服務器的負載L（Ci）、L（Mi）、L（Bi）為0時，判定該服務器宕機，將該服務器的負載權(quán)值Pi設為0，不再發(fā)送請求到該服務器。當該服務器恢復正常時，計算該服務器虛擬節(jié)點數(shù)目并分配請求；⑤新的服務器節(jié)點加入時，按照步驟①、②、③計算該服務器的初始虛擬節(jié)點數(shù)目及動態(tài)虛擬節(jié)點數(shù)目，進而分配請求。

3 算法性能評估

驗證改進算法的可行性，搭建基于LVS的集群系統(tǒng)，在集群中使用性能不一的服務器，分別使用WRR算法、WLC算法和DCH算法調(diào)度用戶請求，測試在不同調(diào)度算法下的集群性能。集群性能在客戶端體現(xiàn)為響應時間（RT）的長短，在集群服務器端體現(xiàn)為吞吐量（Throughput）上。在評估算法性能時，本文以這兩個指標作為評估標準。RT的測試采用如表1所示固定RS數(shù)量的集群，集群中使用了1臺LB，3臺RS，1臺客戶機。throughput的測試與集群中服務器數(shù)量有關(guān)，測試時分別測量從1～8臺服務器集群規(guī)模下的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 響應時間

請求響應時間實驗結(jié)果如圖3所示。圖中橫坐標QPS表示單位時間請求個數(shù)，縱坐標表示響應時間。從圖中可以看出，在請求低于1 000時，3種調(diào)度算法的響應時間沒有明顯差別；當請求數(shù)量大于1 000時，DCH算法響應時間開始低于WRR和WLC算法；請求量達到1 300時，DCH算法響應時間低于WRR算法15%，低于WLC算法8%，且隨著請求QPS的增大，差距越來越大。

3.2 集群吞吐量

集群吞吐量實驗結(jié)果如圖4所示。圖中橫坐標表示集群中服務器數(shù)量，縱坐標表示集群吞吐量。當RSN≤3時，三者吞吐量相差不大，當RS數(shù)量N>3時，使用DCH算法的集群吞吐量開始高于使用WLC和WRR集群的吞吐量，而且隨著N值的增加，差距越來越明顯。到N=8時，DCH算法吞吐量高于WRR算法13%，高于WLC算法10%。

3.3 實驗結(jié)論

綜上實驗，使用改進算法的集群在請求響應時間和吞吐量上都好于使用WRR和WLC的集群，這表明在并發(fā)量高的環(huán)境下，改進算法在負載調(diào)度上更加合理，改進算法提高了集群應對高并發(fā)的極限能力。

4 結(jié)語

集群技術(shù)已成為互聯(lián)網(wǎng)發(fā)展的主流趨勢，運用負載均衡調(diào)度算法進行研究是十分必要的。本文基于一致性哈希算法提出一種用戶Web服務器集群的動態(tài)負載均衡算法，考慮服務器性能及服務器負載情況，在固定的周期時間內(nèi)評估服務器的接收負載能力，均衡地將負載分配到集群中，提高了集群吞吐量，縮短了響應時間，對Web服務器集群具有實用價值。

參考文獻：

[1] 章文嵩，吳婷婷，金士堯，等.一個虛擬Internet服務器的設計與實現(xiàn)[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] 陳志剛，劉安豐，熊策，等.一種有效負載均衡的網(wǎng)格Web服務體系結(jié)構(gòu)模型[J].計算機學報，2005，28（4）：458-466.

[4] 郭成城，晏蒲柳.一種異構(gòu)Web服務器集群動態(tài)負載均衡算法[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] 聶世強，伍衛(wèi)國，張興軍，等.一種基于跳躍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.

（責任編輯：杜能鋼）