基于一致性哈希的負載均衡算法研究

潘子浩

（廣東輕工職業技術學院，廣州510300）

0 引言

隨著互聯網在世界范圍的應用與發展，海量的數據不斷被創造處理，人類處理的數據從PB到TB到ZB發展。面對眾多數據，分布式存儲應運而生，將存儲設備以特定的技術連接起來，跨越設備的差異，地理的限制，向外提供統一快速安全的服務接口。但分布式存儲也面臨著多種技術上的挑戰，其一是在同構設備構成的系統，設備間如何保持數據分布以及訪問方面均衡，而對異構系統，如何保證設備匹配到與其性能相當的負載，這個是負載均衡算法需要考慮的問題；另外隨著應用的發展，設備的添加和刪除是常見的操作，在設備變動后如何繼續保持負載均衡也是算法需要研究的問題；此外由于設備眾多，設備出現故障是常見的，所以副本的放置算法關系到存儲集群的可用性。

本論文針對一致性哈希算法進行負載均衡算法研究，并探討以組的概念設計副本算法，在此基礎上以Redis搭建分布式存儲系統進行驗證。

1 負載均衡算法對比

1.1 常見的均衡算法

在分布式存儲中，數據如何分布放置是及其重要的算法，關系著集群的負載均衡。相比于有中心節點的分布式存儲如HDFS，去中心化的算法因為相對簡單，且無中心節點瓶頸問題，應用也非常廣泛。去中心的數據分布算法常見的有節點空間法，針對數據Key的范圍，劃分為多個分區，每個分區由一個或者一組服務器節點負責，這個算法實現簡單，但是也存在一些問題：空間劃分是依據人的經驗，隨著數據的不斷寫入，數據會逐漸傾斜造成節點間負載不均衡；此外集群需要擴容縮容時，重新劃分節點一般采用分裂或者合并相鄰節點的方式，并不是基于全局考慮，在集群變動后，負載均衡問題依然突出。

另一種常見的分布算法是對數據Key進行哈希，根據哈希值對節點數M取模定位到服務器節點，此算法在均衡性方面有比較好的表現，但是集群擴容或者縮容時，節點數M的變化，會造成集群內大量數據的遷移，并不適合于持續寫入數據的分布式系統。在這種情況下，一致性哈希算法因為良好的均衡性和單調性，在分布式存儲中得到了廣泛的應用。

1.2 帶虛擬節點的一致性哈希算法

基本的一致性哈希存在數據傾斜的問題，一般使用復制虛擬節點的方法進行改進［1］，其原理如圖1所示，算法過程如下：

（1）設置一個地址空間范圍為0～（232－1）的哈希環；

（2）使用存儲節點對應虛擬節點的特征值（一般使用節點IP加虛擬節點編號組成字符串）計算哈希值，映射到哈希環上的一點。如圖1所示存儲節點Node2編號為3的虛擬節點Node2＃3，經過哈希后落入哈希環上一點；

（3）對每個節點都設置一定數量的虛擬節點放置于哈希環上，圖1每個節點設置了3個虛擬節點；

（4）對存取數據的鍵Key使用相同的哈希函數計算哈希值映射到哈希環上，并以此位置順時針查找第一個落入到哈希環的虛擬節點，再進而找到實際存儲節點。如圖1的Key2哈希后順時針找到虛擬節點為Node2＃3，從而找到實際存儲節點為Node2。

圖1 帶虛擬節點的一致性哈希環

1.3 一致性哈希算法的均衡性

根據聶曉文等人的研究，一致性哈希并非完全均衡，即使增加虛擬節點也不能完全消除非均衡性［2］。一致性哈希算法負載傾斜的情況可以通過實驗進行探討。從圖1可見，落入每個節點數據Key的數量，與節點在哈希環中負責的地址空間（zone）成正比例關系，不考慮熱點數據情況下，節點的負載與其對應的地址空間密切相關，因而節點間負載的均衡度可以由節點在哈希環負責的地址空間的差異來度量。定義每個節點所負責的地址空間作為節點的理論負載，節點間負載的均衡性，用兩個指標來衡量，集群中節點最大負載與最小負載的比值，以及節點間負載的離散程度，這兩個指標也是實際工程應用中比較關注的指標。表1展示了不同虛擬節點配置，集群節點間最大負載與最小負載的比值。

表1 不同虛節點數下，集群節點理論最大負載與最小負載的比值

在集群節點數確定時，虛擬節點數的增加可以降低最大負載與最小負載的比值，提高節點間的負載均衡度；而在虛擬節點數確定時，集群增加實節點會造成均衡度會下降。一般而言考慮系統的復雜性，虛擬節點數并不能無限制的提高，實際應用中，每個節點使用100個虛擬節點是一個常用的配置。

圖2展示了10000個實節點每個節點100個虛擬節點的集群系統，對負載進行歸一化后，集群節點負載的離散情況。其中超過30%的節點理論負載偏離了平均負載10%以上（負載小于0.9或者大于1.1），結合表1，此集群系統最大最小負載的比值達到了2.23。根據木桶原理，當理論負載最大的節點達到其機器滿載時，集群即達到了最大處理能力，繼續增大流量將造成集群的故障，在此臨界狀態下理論最低負載的節點只有滿載的45%（即100%／2.23），存在較大的資源浪費，如再考慮系統安全需要對負載做一定的冗余，集群整理利用率更低。

圖2 10000節點每節點100虛擬節點歸一化負載分布

1.4 改進的一致性哈希算法

傳統帶虛節點一致性哈希算法并非完全均衡，非完全均衡造成了系統資源的浪費。為解決均衡性問題，文獻［3］提出了動態調整虛擬節點的生成和分配的方法，文獻［4］則介紹了一種調整映射關系的一致性哈希算法，在保持單調性的同時實現了接近完美的負載均衡。算法的核心在于調整虛擬節點和實際節點的映射關系。具體如下：

（1）實節點數為M，設定一個初始的分區總數N，將哈希環空間均分為N個虛擬節點管理，N應數倍大于實際節點數M。對M個實節點進行編號，分別為S1，S2，S3...SM；對虛擬節點進行編號，分別為V1，V2，V3...VN；

（2）按順序將虛擬節點分組，逐組映射到實際節點：每M個虛擬節點為一組，組內每個虛擬節點按順序映射到實際節點上，直到所有的虛擬節點映射完畢。最后一組虛擬節點數可能會小于M而無法映射所有的實節點。

表2展示了設置了N＝18下，M＝3和M＝4兩種情況下的映射關系，例如M＝3時S1映射到了V1／V4／V7／V10／V13／V16。

表2 實節點和虛擬節點映射關系示例

先探討算法的均衡性。在表2中，M＝3時每個實節點都映射了6個虛擬節點，由于每個虛擬節點在哈希環中負責的地址空間相同，3個實節點理論上處于完全均衡狀態。當M＝4時，最后一個虛擬節點組（包含了V17／V18）只映射到了2個實節點，其中S1、S2實節點映射了5個虛擬節點，另外S3、S4實節點對應4個虛擬節點，集群并未處于完全均衡狀態，此時最大最小負載的比值為1.25（即5／4＝1.25）。可以看出沒有達到完全均衡的原因與最后一組虛擬節點的分配有關，如果將初始的虛擬節點總數N設置為百倍于M甚至更大，那么最大最小負載之間的差值即可以控制在1%以內，接近于完美負載均衡。

接下來探討算法的單調性。集群擴容增加單個實節點Sx的虛擬節點再分配算法，如下所示：

（1）對每一個包含完整映射到所有舊實節點的虛擬節點組，在組內按其映射的實節點編號從小到大重新排列；將虛擬節點組依次排列；

（2）順序進行如下處理，從虛擬節點組的起始位置依次向后查找，直到出現第一個重復映射實節點的虛擬節點為止，將重復映射的虛擬節點（假設為Vi）重新映射到新節點Sx，此時形成新的虛擬節點組包含完整的實節點映射。下一虛擬節點組將從下一個虛擬節點Vi＋1開始；

（3）重復執行步驟（2）直到最后一組無法再分配為止。

表3展示了添加一個實節點時虛擬節點的再分配過程。

表3 初始M＝3添加節點S4時虛擬節點的再分配

表3中深色區域的虛擬節點被重分配到新實節點S4，對應的數據需要遷移，除此以外其他部分不需要遷移，對應遷移的比例為4／18約等于1／4，容易證明新加一個實節點需要進行的遷移量接近于1／M′，M′為變動后實節點總數，滿足了單調性的要求。均衡性的問題如前述討論，當N為數百倍于M′時，節點間的負載差異可以控制在1%以內。同樣，對于單次添加K（K＞1）個實節點的虛擬節點再分配算法與此類似，再分配完之后遷移的量接近于K／M′，滿足單調性和均衡性要求。

節點的刪除操作，與添加的操作相似，按組進行再分配映射，將映射到刪除節點的虛擬節點平均分配給剩余實節點，再分配映射時需要保證每組映射到虛擬節點的實節點不會重復。表4展示了刪除一個實節點時虛擬節點的再分配過程。

表4 初始M＝4時刪除S2實節點虛擬節點的再分配

表4展示刪除時再分配算法對應的數據遷移比例為5／18約等于1／4，再分配之后遷移量接近于1／M，M為刪除節點前的實節點數。對于單次刪除K（K＞0）個實節點的操作，遷移比例為K／M，滿足單調性和均衡性要求。

綜上所述，改進的一致性哈希算法接近于完美解決了均衡性和單調性的問題。

2 副本算法

分布式存儲中常用副本技術提高系統的可靠性、容錯性和運行性能［5］。一致性哈希算法下的副本策略，文獻［4］使用的副本策略是將副本放置于哈希環中，而文獻［6］采用了另外一種方法，將實節點邏輯上劃分為不同的組，以組替換哈希環中的節點，在邏輯組內采用主備的方式提高分布式系統的可靠性，訪問一個數據Key是先經過哈希在哈希環中找到對應的邏輯組，在組內再查找數據Key對應的主機實現數據的讀寫操作。此方案提高了系統的可靠性與安全性，但也還存在一個問題，組內不管是采用一主一備，還是一主多備的方式，備份與主節點之間負載的均衡，并沒有得到很好的解決。在大部分讀多寫少的應用場景，以一主一備或者一主多備的架構模式，主節點承擔了大部分來自訪問端的讀寫請求，備節點只做數據同步寫入，主備之間負載并不均衡，備機基本處于空閑的狀態，集群的性能沒有得到最大的利用。

基于改進一致性哈希架構下的分布式集群系統，論文對組內數據分布設計了兩種新的副本算法，以進一步提高集群服務器節點的性能和利用率，實現組內機器的負載均衡。

方案一：在組內設置兩臺服務器節點，但將兩個節點同時利用起來作為主機使用（雙主方案），兩主機互備。組內兩節點分別記為SA、SB。對落入到這組的數據Key進行分組，哈希值為奇數的數據Key以SA作為主機，SB為備機；哈希值為偶數的Key以SB作為主機，SA為備機。此設置下，兩臺服務器都將被利用起來，共同承擔進入本邏輯組的請求，組內節點達到了負載均衡的效果?？紤]到節點內的緩存，網絡帶寬，進程切換等因素，整體性能將比主備方案更加高效。不過考慮到機器可能會出現故障，一般會限制組內SA、SB節點的負載低于機器滿載的50%，否則任意一個節點出現故障時，故障節點的請求轉向剩余的節點將造成過載最終壓垮整組服務器。

方案二：將組內節點數從兩臺提高到多臺。這里以組內三節點情況進行說明（三主方案），更多節點的情況與此相似。三個實節點分別記為SA、SB、SC，調整備份邏輯，對落入此邏輯組的數據Key，按照哈希值模6，對余數不同的6份數據執行不同的主備邏輯，如表5所示。

表5 SA／SB／SC 三機主備關系

哈希值模6等于0和1的數據以SA為主機，其中一半的Key備份到SB（哈希值模6等于0），另外一半的Key備份到SC（哈希值模6等于1）；對以SB和SC為主機的Key也采用同樣的備份邏輯，即本主機數據的備份由另外兩臺承擔。對進入此組的所有數據Key，每個節點都只處理其中的2／6，三個節點的負載處于均衡的狀態。考慮單機故障的情況，當組內任何一個節點出現故障時，其請求平攤到備機。如當SA節點故障時，哈希值模6為0和1的數據Key將分別由SB和SC節點提供服務；此刻對于SB和SC兩節點來說，請求量將增加50%，負載也將提高50%。為了不讓節點因升高50%的負載造成過載而壓垮服務器，設計時一般會限定單個節點的負載低于其滿載的2／3。與雙主方案相比，單機負載的上限被提高，可以進一步提高系統利用率。兩機和三機同時故障的情況，會造成部分甚至全部數據Key不可讀寫，不在此方案探討范圍。

接下來從概率角度分析兩種副本方案的優劣和系統風險。假設節點故障概率為p＝0.01，節點發生故障是獨立事件：

（1）組內節點負載都低于滿載的1／2時，兩種方案，單個節點故障時都可以將流量切到正常節點，整組還可以繼續提供服務。

（2）組內節點負載超過滿載1／2但低于2／3時，對方案一，如果發生單個節點的故障，將流量轉到正常節點會造成節點的過載，進而造成整組的故障，因而組可用的概率等于（1－p）*（1－p）＝0.9801。對方案二，單個節點故障，流量切到另外兩個正常節點并不會造成節點的過載。只有兩個及以上節點發生故障時，整組才不可用，組可用的概率為（1－p）＾3＋p*（1－p）*（1－p）*3＝0.999702，抗風險能力高于方案一。同時方案二有更積極的意義，節點負載可提高到滿載的2／3，系統利用率更高，集群可以承載更多的流量。

3 實驗

3.1 一致性哈希算法均衡性驗證

對改進前的算法，每個實節點配置100個虛擬節點；對改進后的一致性哈希算法，設置N為100000。隨機創建1000萬條由8位隨機字符組成的Key，統計每個節點的訪問次數作為節點負載，計算最大最小負載比值作為算法的均衡度。表6展示了兩種算法均衡度對比。

表6 改進前后一致性哈希算法最大最小負載比值

從表6可以看到，改進后的一致性哈希算法接近于完美均衡，節點間的負載差異非常低；對改進前的算法，表6的實驗結果也與表1高度吻合，改進前算法存在節點負載不均衡的現象，此外也驗證了使用節點負責哈希環地址空間作為節點負載是合理的。

3.2 副本算法驗證

使用Redis搭建了主備、雙主兩組服務器，以相同的QPS請求下考察兩組服務器的CPU消耗、負載以及請求平均響應時間。

從表7－表8看到，兩組服務器內的總消耗基本相同，負載總和也接近。但雙主算法平均響應時間上有明顯的優勢，對用戶體驗會更好。

表7 主備副本算法

表8 雙主副本算法

相比雙主方案，三主副本方案的優勢是可以將單機負載從滿載的1／2提高到滿載的2／3。進行如下的實驗對比：三主機正常服務并且每個節點CPU消耗在50%～66%時，統計整組服務器的負載、平均響應時間；然后停掉一臺機器，在整組流量不變的條件下，將流量切到剩余的兩臺主機，觀察整組服務器CPU消耗、負載、平均響應時間的變化。

從表9－表10可以看到，正常服務時，三節點的CPU占用和負載基本一致，符合預期。在單機故障下請求轉發到正常主機時，雖然正常節點的單機流量的增加造成了CPU和負載的上升，以及平均響應時間升高，但節點尚未處于過載，整組服務器仍保持正常服務狀態。從而驗證了三主副本策略與雙主策略相比，可以在不降低系統可靠性下提高系統的利用率。

表9 三主機正常服務

表10 主機SC 故障

4 結語

本文對比了常見的靜態負載均衡算法，對帶虛擬節點的一致性哈希算法，通過實驗分析得出算法并非完全均衡；引入了改進的一致性哈希算法，在理論和實驗驗證中，此算法在保持單調性的同時達到了近乎完美的均衡?；诟倪M的一致性哈希算法，使用組的概念替代傳統的節點，在解決副本的問題的同時實現組內機器的負載均衡，并提出雙主副本和三主副本算法；經過實驗驗證，雙主副本／三主副本方案對比主備方案，有著更好的性能和可靠性。