李杰 聶云峰 金敏

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

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

DOIDOI：10.11907/rjdk.173200

中圖分類號：TP312

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

Genova等[7]提出了針對Pick-K的改進算法Pick-KX，在更新周期內(nèi)，首先從集群S1，S2，S3，…，SN中選擇K臺服務(wù)器，獲取它們的負載L1，L2，L3，…，LK，1≤K≤N，每當(dāng)有請求到達時，將當(dāng)前的請求以Pj=Xj/∑Ki=1Xj的概率分配選中的第j臺服務(wù)器，其中Ltotal=∑Ki=1Li，Xj=（Ltotal-Lj）/Ltotal，j=1，2，3，…，K。

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

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

1 一致性哈希算法

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

2 DCH算法

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

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

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

2.3 DCH算法流程

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

3 算法性能評估

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

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

3.2 集群吞吐量

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

3.3 實驗結(jié)論

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

4 結(jié)語

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

參考文獻：

[1] 章文嵩，吳婷婷，金士堯，等.一個虛擬Internet服務(wù)器的設(shè)計與實現(xiàn)[J].軟件學(xué)報，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服務(wù)體系結(jié)構(gòu)模型[J].計算機學(xué)報，2005，28（4）：458-466.

[4] 郭成城，晏蒲柳.一種異構(gòu)Web服務(wù)器集群動態(tài)負載均衡算法[J].計算機學(xué)報，2005，28（2）：179-184.

[5] 陳一驕，盧錫城，時向泉，等.一種面向會話的自適應(yīng)負載均衡算法[J].軟件學(xué)報，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].軟件學(xué)報，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.

（責(zé)任編輯：杜能鋼）