基于動態(tài)權重的一致性哈希微服務負載均衡優(yōu)化*

張開琦，劉曉燕，王 信，吉春山，嚴 馨

(1.昆明理工大學信息工程與自動化學院,云南 昆明 650500；2.金川鎳鉆研究設計院,甘肅 金昌 737100)

1 引言

隨著信息時代的發(fā)展，人們對系統(tǒng)網(wǎng)站的使用量越來越多，這對系統(tǒng)服務器的負載能力提出了考驗。解決負載問題一般是采用2種方法，一種是使用具有強大硬件配置的后臺服務網(wǎng)絡，但因為各種原因這種方法很難實現(xiàn)；而另一種便是采用負載均衡方法來解決服務負載過大的問題。負載均衡廣泛地應用于分布式環(huán)境，由于當今大數(shù)據(jù)與云計算的廣泛使用，分布式服務系統(tǒng)也被開發(fā)人員頻繁使用。其中微服務架構(gòu)作為分布式架構(gòu)的代表，因為其按功能來劃分服務的特點，會導致各個服務的負載均衡難以控制，出現(xiàn)有的服務訪問量過高，而有的服務基本無人訪問的問題。

目前解決負載均衡的方法有很多，但是針對微服務架構(gòu)的負載均衡方法還在不斷地研究之中。很多企業(yè)都在構(gòu)建自己的微服務服務集群，開發(fā)自己的云計算平臺，因此解決微服務負載均衡問題被各大公司提上了日程。

針對微服務的負載均衡問題，本文提出一種基于動態(tài)權重的一致性哈希負載均衡優(yōu)化方法。一致性哈希是一種具有良好橫向擴展性的集群動態(tài)擴展技術。 但是，一致性哈希自身并沒有負載均衡的措施，很容易導致負載的傾斜。本文針對電商系統(tǒng)，將系統(tǒng)按功能劃分微服務架構(gòu)，部署在Docker容器中，提出一種基于虛擬機節(jié)點的一致性哈希服務劃分方式，使用動態(tài)權重實現(xiàn)服務訪問量過大時，自動增加服務和服務負載傳遞。通過與輪詢和傳統(tǒng)一致性哈希算法的實驗對比，表明此方法相比傳統(tǒng)一致性哈希算法在負載均衡方面有很大的性能提升。

2 相關工作

針對微服務集群的負載均衡問題，當使用微服務時，首先要考慮一些設計上的均衡問題，例如平衡微服務的大小和數(shù)量，平衡單個微服務和整個系統(tǒng)之間的非功能性需求。文獻[1]介紹了一種用Hash算法解決這些平衡問題的方案。文獻[2]介紹了一種用于構(gòu)建云應用程序的軟件框架Orleans，它運用貪婪策略處理負載平衡。它將請求隨機分配給服務器，如果請求被分配給過載的服務器，服務器將拒絕請求，然后其被重新分配給另一臺服務器；如果服務器未過載，但服務器上的請求激活空間過載，則到達的請求將被發(fā)送到此服務器上新創(chuàng)建的激活空間中，閑置足夠長時間的激活空間將被關閉，此方法類似于本文的微服務方法。但是，本文添加了權重屬性以更準確地測量負載。Microsoft Azure Service Fabric的平衡管理器根據(jù)網(wǎng)絡流量來計算哈希函數(shù)。哈希函數(shù)需要源IP、源端口、目標IP、目標端口和協(xié)議類型等信息，管理器確保來自同一鏈接的所有包都被相同的服務器接收并且平均分配。文獻[3]提出了一種運用一致性哈希加強緩存來減小大型Web應用程序中故障的負面影響。Ringpop是一個Uber開發(fā)的使用一致性哈希進行負載均衡的開源庫，它為每個節(jié)點添加統(tǒng)一數(shù)量的副本點，這與本文的方法類似。但是，由于節(jié)點分布不均，無法保證這些點的均勻分布。文獻[4]介紹了一種針對哈希環(huán)節(jié)點的遍歷次數(shù)進行優(yōu)化的多重查詢方法；文獻[5]提出了EFAH Hashing算法；文獻[6]提出了一種更快捷、占用資源更少的一致性哈希算法，叫做跳躍性一致性哈希算法；文獻[7]提出了一種基于跳躍 Hash 的對象分布算法。文獻[7]研究了基于Nginx服務器的Web服務集群的負載均衡場景，提出了一種基于動態(tài)權重最小連接算法DWLC(Dynamic Weighted Least-Connection)，根據(jù)每臺從機的性能來決定權重設置，并根據(jù)Least-Connection算法來決定最后分配結(jié)果。

容器技術近些年被廣泛應用到分布式系統(tǒng)開發(fā)中。在所有的容器平臺中，Docker絕對是最受開發(fā)者歡迎的。2013年，Docker的推出開啟了應用程序開發(fā)的一場革命，有大量的論文使用Doc- ker作為環(huán)境的解決方案。文獻[8]測試了本地Docker環(huán)境與傳統(tǒng)Red Hat環(huán)境之間的性能差異。該測試表明，在性能之間只有0.4%的可忽略的差異。這意味著Docker容器可以在生產(chǎn)環(huán)境中發(fā)揮更大的作用。文獻[9]提出了一種基于Docker和Agave的網(wǎng)關，在Docker的幫助下將網(wǎng)關更加輕量級化。

3 動態(tài)權重一致性哈希劃分方法

3.1 基本概念

實現(xiàn)微服務架構(gòu)的負載均衡是非常重要的，因為不知道將會有多少用戶進行訪問。假設一個服務同時處理用戶請求的上限為1 000，分配20個服務為10 000名用戶來提供服務。當有20 000名用戶發(fā)出請求時，將必須開啟新的服務來處理新增加的請求，這些服務中有的服務是過載的而有的服務卻是相對空閑的。

本文選擇一致性哈希作為哈希函數(shù)。然而一致性哈希函數(shù)存在一些缺陷。一致性哈希在超過1 000個虛擬節(jié)點的環(huán)境中效果最好，而通常很多應用程序的切片鍵太少，所以無法使用一致性哈希來解決負載均衡問題，因此需要改進以彌補這種缺陷。

3.2 虛擬節(jié)點劃分

虛擬節(jié)點是一種被廣泛應用于工程場景的概念，通過網(wǎng)路映射的方式，在一臺物理主機上搭建多個網(wǎng)絡連接。本文運用虛擬節(jié)點，旨在縮短用戶的請求映射到哈希環(huán)上后尋找目標節(jié)點所需要遍歷的哈希長度，從而提升分配的效率。

一致性哈希方法的基本原理是將存儲空間抽象成一個232節(jié)點的圓，將存儲節(jié)點分配到這個圓上，環(huán)上的節(jié)點都有一個哈希值。采用同樣的方法求出存儲數(shù)據(jù)的鍵的哈希值，并同樣映射到圓上。然后從數(shù)據(jù)映射到的位置順時針查找，將數(shù)據(jù)存儲在第1個找到的服務器上。

在本文微服務架構(gòu)場景下，一致性哈希的關鍵步驟是將每個服務映射到圓邊緣上的點，但如果服務的數(shù)量不夠，會導致分布不均勻，這就會造成負載不均的問題。本文用于解決該問題的方法是在用戶與服務之間增加一個虛擬層，其哈希環(huán)如圖1所示，虛擬層由大量虛擬節(jié)點組成。使用一致性哈希創(chuàng)建用戶與虛擬節(jié)點之間的映射，虛擬節(jié)點與服務之間通過簡單取模操作創(chuàng)建映射，通過這種方法就有足夠的虛擬節(jié)點來進行一致性哈希操作。虛擬節(jié)點的數(shù)量也很重要，如果虛擬節(jié)點的數(shù)量過少，將會導致原有的一致性哈希方法負載均衡效果不明顯；反之，則會導致找到一個對應用戶的虛擬節(jié)點所需時間過長。

Figure 1 User mapping to virtual machine node圖1 用戶映射到虛擬機節(jié)點

本文根據(jù)用戶請求的IP地址來計算用戶的key，服務的key通過服務的IP地址與端口來計算。我們使用FNV(Fowler-Noll-Vo)算法[10]來Hash這些信息。FNV算法分為FNV-1，F(xiàn)NV-1a和FNV-0 3種，目前FNV-0算法已經(jīng)被放棄使用了，而FNV-1a算法只是在FNV-1的基礎上將相乘和異或運算進行了順序調(diào)換，其它過程和參數(shù)與FNV-1相同，F(xiàn)NV-1a算法在進行小數(shù)據(jù)哈希時有更好的性能(小于4個字節(jié))，故本文采用FNV-1算法。FNV-1算法能在保持較小沖突率的情況下Hash大量的數(shù)據(jù)，因為它高度分散的特性，使其適用于Hash一些非常相近的字符串。通過求出的數(shù)據(jù)Hash值，可以盡量保證相同的用戶Hash到相同的服務上去。使用FNV-1算法來Hash信息如圖2所示。

Figure 2 Using hash function and FNV-1圖2 使用哈希函數(shù)和FNV-1

3.3 動態(tài)權重均衡

因為一致性哈希算法本身并沒有相應的負載均衡策略，所以本文通過一種基于動態(tài)權值分配的方法對微服務的負載進行均衡優(yōu)化。分布式系統(tǒng)的負載均衡是復雜的，其系統(tǒng)資源占用因用戶而異，一些活躍的用戶需要更多的資源，因此需要為其開辟更多的微服務；相反，一些相對不活躍的用戶很少訪問服務，不需要給他們分配很多微服務。

我們根據(jù)用戶的訪問情況計算用戶的權重，將用戶權重屬性定義到用戶的數(shù)據(jù)表中，權重定義為：

W=(Nu+Ns)/t

其中，W是用戶的權重值，Nu是用戶發(fā)起請求的次數(shù)，Ns是請求調(diào)用微服務的數(shù)量，t是用戶訪問的時間。Nu,Ns和t由服務收集和更新，通過自動平衡服務進行更改。因為權重短時間內(nèi)不會顯著變化，所以可以間隔一段時間后進行更改。

自動平衡服務計算并保存每個服務組中用戶的總權重。如果一個用戶想要登錄，并且給用戶分配的權重超過了給他分配的服務權重的上限，自動平衡服務就會撤銷之前的分配，并且將其分配給一個新的服務。如果所有的服務都達到了上限，自動平衡服務就會開辟一個新的服務，并將用戶分配給這個服務。這樣，負載過高的服務只能接收那些不活躍的用戶，而活躍的用戶會分配給負載相對較低的服務。

動態(tài)權重均衡算法如算法1所示。

算法1動態(tài)權重均衡算法

Input:Li-Load of this service,Lmin-Load of the service with the lowest weight,T-Threshold of the service,Nc-Number of the services,W-Weight of the coming user。

1.Lmin=L0;

2.Fori=0toNc{

3.IfLi+W

4.Lmin=Li; Assign users to this service;}

5.}

6.IfLmin=L0andL0+W>TThen{

7. Start new service;

Assign users to new service;}

如果用戶超過1小時沒有任何操作，自動平衡服務將從服務器組中減去此用戶的權重。如果用戶之后又進行操作，自動平衡服務將重復上述操作。

3.4 服務間的負載轉(zhuǎn)移

在分布式架構(gòu)系統(tǒng)中，用戶的遷移量對系統(tǒng)的負載均衡尤為重要，當某些服務中的用戶訪問量增多時，會導致服務的壓力過大，影響系統(tǒng)執(zhí)行效率，嚴重時會導致服務宕機崩潰，因此，需要將負載壓力過大的服務中的用戶轉(zhuǎn)移到其他壓力相對較小的服務中去。

當用戶登錄或注銷時，服務的總權重將變得不平衡。可以關閉那些空閑的服務，但是有些服務還是負載過大。故需要將一些負載壓力過大服務中的服務請求轉(zhuǎn)移到負載相對小的服務中。因此，本文設計了一種基于動態(tài)權重的服務之間負載轉(zhuǎn)移的算法。

負載轉(zhuǎn)移算法如算法2所示。

算法2負載轉(zhuǎn)移算法

Input:Li-Load of this service,Wj-Weight of this user,S-Safety line for balance,WList-List of the users to be transferred to idle services,LList-List of idle services to receive users。

1.ForeachLdo{

2.IfLi

3. AddLitoLList}

4.Else{

WhileLi>Sdo{

5. AddWjtoWList;

6.Li=Li-Wj;}}

7.WhileWListis not empty{

8. SelectLlfromLList;}

9.IfWl+Ll

10. TransferWltoLl}

11.Else{

12. RemoveLlfromLList}

13.IfLListis emptythen{

14. Create new service and add it toLList}}

通過遍歷所有的服務和用戶，檢查哪些用戶請求需要被轉(zhuǎn)移，哪些服務可以用來接受這些請求。當遍歷所有的服務，沒有服務滿足接收用戶請求的條件時，系統(tǒng)將自動開啟一個新的服務，用來接收轉(zhuǎn)移的用戶請求。

在該算法中，通過概率搜索來選擇接收用戶轉(zhuǎn)移的服務，而不是通過隨機選擇和在符合條件的服務列表中順序選擇。這種方法是由Menon等人[11]首次提出的，該方法按固定順序從多個處理器中選擇一個處理器。本文將目標換為系統(tǒng)中無順序的微服務，自動平衡服務為空閑服務列表中的每個服務分配一個概率。服務被選擇的概率如下所示：

Pi=(Lmax-Li/Lavg-Lmin)/Z

其中，Pi是分配給服務i的概率，Lmax是系統(tǒng)中服務的負載最大值，Lmin是系統(tǒng)中服務的負載最小值，Lavg是系統(tǒng)中服務的負載平均值。Z是一個與負載最大值、最小值和平均值相關的常數(shù)。然后自動平衡服務根據(jù)概率Pi來選擇接收用戶轉(zhuǎn)移的服務，負載越大的服務被選擇的概率越小。在應用上，其實不需要選擇負載最小的服務來接收轉(zhuǎn)移的負載，只需要保證相關用戶負載被轉(zhuǎn)移到負載較少的服務中去。結(jié)合前面舉一個例子，假設一組服務的負載為{40,25,30,20,40},得出Z為4.1，概率為{0，0.32，0.24,0.44,0}。這意味著負載為最大負載值40的服務，不被自動平衡服務識別為可以接收轉(zhuǎn)移負載的服務，剩下3個服務根據(jù)概率值來被選擇為接收負載的服務。

假如上述的服務組中增加了一個用戶，其負載變?yōu)閧40,26,30,20,40}，那么它的概率變?yōu)閧0,0.32,0.23,0.45,0}。這些服務的概率與之前的沒有顯著差異，所以不需要在每次增加新用戶時都對服務的概率進行重新計算，只需要在服務組的Lmax和Lmin顯著變化時對概率進行重新計算。

4 實驗結(jié)果及分析

4.1 實驗平臺及部署

本實驗在VMware workstation上進行，在VM上安裝并運行Docker虛擬機。使用雙核CPU和8 GB內(nèi)存，虛擬機的系統(tǒng)為Ubuntu 16.04.2。將服務部署在Docker容器中，使用apt-get命令來安裝實驗中需要的軟件。

4.2 實驗方案

為了觀察本文算法的負載均衡效果，標準差是衡量負載均衡的一個流行度量，但是在有些情況下，2組負載數(shù)據(jù)的標準差σ是相同的，為了解決這一問題，將最大負載與平均負載的差除以平均負載作為衡量負載均衡的另一指標U，負載不平衡的概率為:

U=(Lmax-Lavg)/Lavg

加入不平衡參數(shù)U后的負載如表1所示。

Table 1 Load example after adding parameter U表1 加入U后的負載例子

這個標準由負載最大的服務來主導。假設有2個服務組，它們的平均負載都為10，并且它們的標準差也相等。很明顯，負載最大值為20的服務組負載不平衡的概率大于負載最大值為15的服務組。前一個的負載不平衡率為1.0，而后一個為0.5。

使用Apache JMeter作為本文的基準測試工具。Apache JMeter是Apache為基準HTTP服務器提供的壓力測試工具。它可以模擬多線程并發(fā)請求和測試服務器負載壓力。使用Docker容器部署20個服務組來進行負載均衡測試。本文設計的實驗將會通過同等時間長度內(nèi)，發(fā)送1×103，5×103,10×103,50×103,100×1035個數(shù)量級的數(shù)據(jù)請求來觀察在不同的負載情況下，本文算法的實際計算效率和負載均衡狀況。

4.3 運行效率測試

首先需要比較本文算法與傳統(tǒng)一致性哈希算法和輪詢算法的運行效率差異，輪詢算法是一種常見的負載均衡算法，主要是將請求按順序輪流分配到服務器上，其對比圖如圖3所示。

Figure 3 Comparison of efficiency圖3 運行效率對比

從實驗的結(jié)果來看，本文基于動態(tài)權重的一致性哈希算法在各個并發(fā)量的情況下效果相對穩(wěn)定，有較好的表現(xiàn)。因為傳統(tǒng)一致性哈希算法沒有添加虛擬節(jié)點進行優(yōu)化，導致每次分配都需要遍歷很長的距離，從而導致額外的開銷增多，隨著訪問量的增加，處理的效率隨之降低。而另外一組輪詢算法因為是在整個微服務集群中按順序選擇服務，其在并發(fā)請求數(shù)量增加的情況下處理效果相對穩(wěn)定，但如果集群中服務節(jié)點數(shù)量增加，會產(chǎn)生一些分配性能上的損失。

4.4 節(jié)點劃分方法測試

通過比較3種不同的算法來評估本文算法的切分服務。表2顯示了3種算法的負載不平衡概率結(jié)果。

Table 2 Load test results表2 負載測試結(jié)果

由表3所示，改進后的一致性哈希算法負載不平衡概率較低，是原有一致性哈希算法的31%。基于虛擬節(jié)點的一致性哈希算法的標準差和不平衡概率較低，明顯小于傳統(tǒng)一致性哈希算法和輪詢算法的。這是因為傳統(tǒng)一致性哈希算法中沒有足夠的服務來作為節(jié)點，用戶的請求很可能集中訪問某一節(jié)點導致負載傾斜，所以當節(jié)點數(shù)量不足時，只使用一致性哈希算法來進行節(jié)點劃分，其結(jié)果是不理想的。而輪詢算法是通過在服務集群的服務列表中按順序分配請求，而微服務集群中的服務器存在性能上的差異，導致高性能的服務器負載低，而低性能的服務器負載過高。

4.5 動態(tài)權重方法測試

由于動態(tài)加權的方法是在劃分方法的基礎上改進的，所以測試的方法與之前大致相同。區(qū)別是本文創(chuàng)建了10個虛擬用戶，并設置了他們的訪問時間和訪問次數(shù)。使用Apache JMeter對用戶進行了多次重復實驗，結(jié)果見表3，其中Wavg為權重的平均值，σw為權重的標準差。

Table 3 Dynamic weight test results表3 動態(tài)權重測試結(jié)果

表3結(jié)果表明，該方法具有良好的負載均衡性能，其不僅可以均衡用戶的訪問數(shù)量，還可以使用戶的負載水平達到一個相對的平衡。

4.6 負載傳遞方法測試

首先重復上述步驟，然后通過自動平衡服務發(fā)送一個信號，使其對服務集群中的服務進行負載均衡，其結(jié)果如表4所示，其中Before為集群中服務進行負載傳遞前的各項數(shù)值，After為進行負載傳遞后的各項數(shù)值。表4的結(jié)果表明，經(jīng)過負載傳遞之后，服務集群中權重和用戶數(shù)基本分配均等。此方法很大程度上解決了負載均衡問題。

Table 4 Test results of transmission method表4 傳遞方法測試結(jié)果

5 結(jié)束語

隨著大數(shù)據(jù)時代的到來，處理負載均衡問題已經(jīng)成為服務集群的重要問題，一種有效的負載均衡方法決定著系統(tǒng)所能發(fā)揮的性能。本文針對分布式系統(tǒng)的負載均衡問題，對一致性哈希算法進行優(yōu)化，提出一種基于動態(tài)權重的一致性哈希處理負載問題的策略。通過增加一層虛擬節(jié)點的哈希環(huán)來解決傳統(tǒng)一致性哈希算法因為節(jié)點不足導致負載傾斜的問題；并提出了基于權重分配負載以及實現(xiàn)服務負載傳遞的方法。從實驗結(jié)果來看，該方法有效地提高了系統(tǒng)的性能，降低了負載不平衡的概率，實現(xiàn)了服務集群中各服務的負載和用戶訪問的均衡。與傳統(tǒng)的方法相比，負載均衡的效果得到了有效的提高。