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

潘子浩

（廣東輕工職業(yè)技術(shù)學(xué)院，廣州510300）

0 引言

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

本論文針對一致性哈希算法進(jìn)行負(fù)載均衡算法研究，并探討以組的概念設(shè)計(jì)副本算法，在此基礎(chǔ)上以Redis搭建分布式存儲系統(tǒng)進(jìn)行驗(yàn)證。

1 負(fù)載均衡算法對比

1.1 常見的均衡算法

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

另一種常見的分布算法是對數(shù)據(jù)Key進(jìn)行哈希，根據(jù)哈希值對節(jié)點(diǎn)數(shù)M取模定位到服務(wù)器節(jié)點(diǎn)，此算法在均衡性方面有比較好的表現(xiàn)，但是集群擴(kuò)容或者縮容時(shí)，節(jié)點(diǎn)數(shù)M的變化，會造成集群內(nèi)大量數(shù)據(jù)的遷移，并不適合于持續(xù)寫入數(shù)據(jù)的分布式系統(tǒng)。在這種情況下，一致性哈希算法因?yàn)榱己玫木庑院蛦握{(diào)性，在分布式存儲中得到了廣泛的應(yīng)用。

1.2 帶虛擬節(jié)點(diǎn)的一致性哈希算法

基本的一致性哈希存在數(shù)據(jù)傾斜的問題，一般使用復(fù)制虛擬節(jié)點(diǎn)的方法進(jìn)行改進(jìn)［1］，其原理如圖1所示，算法過程如下：

（1）設(shè)置一個(gè)地址空間范圍為0～（232－1）的哈希環(huán)；

（2）使用存儲節(jié)點(diǎn)對應(yīng)虛擬節(jié)點(diǎn)的特征值（一般使用節(jié)點(diǎn)IP加虛擬節(jié)點(diǎn)編號組成字符串）計(jì)算哈希值，映射到哈希環(huán)上的一點(diǎn)。如圖1所示存儲節(jié)點(diǎn)Node2編號為3的虛擬節(jié)點(diǎn)Node2＃3，經(jīng)過哈希后落入哈希環(huán)上一點(diǎn)；

（3）對每個(gè)節(jié)點(diǎn)都設(shè)置一定數(shù)量的虛擬節(jié)點(diǎn)放置于哈希環(huán)上，圖1每個(gè)節(jié)點(diǎn)設(shè)置了3個(gè)虛擬節(jié)點(diǎn)；

（4）對存取數(shù)據(jù)的鍵Key使用相同的哈希函數(shù)計(jì)算哈希值映射到哈希環(huán)上，并以此位置順時(shí)針查找第一個(gè)落入到哈希環(huán)的虛擬節(jié)點(diǎn)，再進(jìn)而找到實(shí)際存儲節(jié)點(diǎn)。如圖1的Key2哈希后順時(shí)針找到虛擬節(jié)點(diǎn)為Node2＃3，從而找到實(shí)際存儲節(jié)點(diǎn)為Node2。

圖1 帶虛擬節(jié)點(diǎn)的一致性哈希環(huán)

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

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

表1 不同虛節(jié)點(diǎn)數(shù)下，集群節(jié)點(diǎn)理論最大負(fù)載與最小負(fù)載的比值

在集群節(jié)點(diǎn)數(shù)確定時(shí)，虛擬節(jié)點(diǎn)數(shù)的增加可以降低最大負(fù)載與最小負(fù)載的比值，提高節(jié)點(diǎn)間的負(fù)載均衡度；而在虛擬節(jié)點(diǎn)數(shù)確定時(shí)，集群增加實(shí)節(jié)點(diǎn)會造成均衡度會下降。一般而言考慮系統(tǒng)的復(fù)雜性，虛擬節(jié)點(diǎn)數(shù)并不能無限制的提高，實(shí)際應(yīng)用中，每個(gè)節(jié)點(diǎn)使用100個(gè)虛擬節(jié)點(diǎn)是一個(gè)常用的配置。

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

圖2 10000節(jié)點(diǎn)每節(jié)點(diǎn)100虛擬節(jié)點(diǎn)歸一化負(fù)載分布

1.4 改進(jìn)的一致性哈希算法

傳統(tǒng)帶虛節(jié)點(diǎn)一致性哈希算法并非完全均衡，非完全均衡造成了系統(tǒng)資源的浪費(fèi)。為解決均衡性問題，文獻(xiàn)［3］提出了動態(tài)調(diào)整虛擬節(jié)點(diǎn)的生成和分配的方法，文獻(xiàn)［4］則介紹了一種調(diào)整映射關(guān)系的一致性哈希算法，在保持單調(diào)性的同時(shí)實(shí)現(xiàn)了接近完美的負(fù)載均衡。算法的核心在于調(diào)整虛擬節(jié)點(diǎn)和實(shí)際節(jié)點(diǎn)的映射關(guān)系。具體如下：

（1）實(shí)節(jié)點(diǎn)數(shù)為M，設(shè)定一個(gè)初始的分區(qū)總數(shù)N，將哈希環(huán)空間均分為N個(gè)虛擬節(jié)點(diǎn)管理，N應(yīng)數(shù)倍大于實(shí)際節(jié)點(diǎn)數(shù)M。對M個(gè)實(shí)節(jié)點(diǎn)進(jìn)行編號，分別為S1，S2，S3...SM；對虛擬節(jié)點(diǎn)進(jìn)行編號，分別為V1，V2，V3...VN；

（2）按順序?qū)⑻摂M節(jié)點(diǎn)分組，逐組映射到實(shí)際節(jié)點(diǎn)：每M個(gè)虛擬節(jié)點(diǎn)為一組，組內(nèi)每個(gè)虛擬節(jié)點(diǎn)按順序映射到實(shí)際節(jié)點(diǎn)上，直到所有的虛擬節(jié)點(diǎn)映射完畢。最后一組虛擬節(jié)點(diǎn)數(shù)可能會小于M而無法映射所有的實(shí)節(jié)點(diǎn)。

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

表2 實(shí)節(jié)點(diǎn)和虛擬節(jié)點(diǎn)映射關(guān)系示例

先探討算法的均衡性。在表2中，M＝3時(shí)每個(gè)實(shí)節(jié)點(diǎn)都映射了6個(gè)虛擬節(jié)點(diǎn)，由于每個(gè)虛擬節(jié)點(diǎn)在哈希環(huán)中負(fù)責(zé)的地址空間相同，3個(gè)實(shí)節(jié)點(diǎn)理論上處于完全均衡狀態(tài)。當(dāng)M＝4時(shí)，最后一個(gè)虛擬節(jié)點(diǎn)組（包含了V17／V18）只映射到了2個(gè)實(shí)節(jié)點(diǎn)，其中S1、S2實(shí)節(jié)點(diǎn)映射了5個(gè)虛擬節(jié)點(diǎn)，另外S3、S4實(shí)節(jié)點(diǎn)對應(yīng)4個(gè)虛擬節(jié)點(diǎn)，集群并未處于完全均衡狀態(tài)，此時(shí)最大最小負(fù)載的比值為1.25（即5／4＝1.25）?？梢钥闯鰶]有達(dá)到完全均衡的原因與最后一組虛擬節(jié)點(diǎn)的分配有關(guān)，如果將初始的虛擬節(jié)點(diǎn)總數(shù)N設(shè)置為百倍于M甚至更大，那么最大最小負(fù)載之間的差值即可以控制在1%以內(nèi)，接近于完美負(fù)載均衡。

接下來探討算法的單調(diào)性。集群擴(kuò)容增加單個(gè)實(shí)節(jié)點(diǎn)Sx的虛擬節(jié)點(diǎn)再分配算法，如下所示：

（1）對每一個(gè)包含完整映射到所有舊實(shí)節(jié)點(diǎn)的虛擬節(jié)點(diǎn)組，在組內(nèi)按其映射的實(shí)節(jié)點(diǎn)編號從小到大重新排列；將虛擬節(jié)點(diǎn)組依次排列；

（2）順序進(jìn)行如下處理，從虛擬節(jié)點(diǎn)組的起始位置依次向后查找，直到出現(xiàn)第一個(gè)重復(fù)映射實(shí)節(jié)點(diǎn)的虛擬節(jié)點(diǎn)為止，將重復(fù)映射的虛擬節(jié)點(diǎn)（假設(shè)為Vi）重新映射到新節(jié)點(diǎn)Sx，此時(shí)形成新的虛擬節(jié)點(diǎn)組包含完整的實(shí)節(jié)點(diǎn)映射。下一虛擬節(jié)點(diǎn)組將從下一個(gè)虛擬節(jié)點(diǎn)Vi＋1開始；

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

表3展示了添加一個(gè)實(shí)節(jié)點(diǎn)時(shí)虛擬節(jié)點(diǎn)的再分配過程。

表3 初始M＝3添加節(jié)點(diǎn)S4時(shí)虛擬節(jié)點(diǎn)的再分配

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

節(jié)點(diǎn)的刪除操作，與添加的操作相似，按組進(jìn)行再分配映射，將映射到刪除節(jié)點(diǎn)的虛擬節(jié)點(diǎn)平均分配給剩余實(shí)節(jié)點(diǎn)，再分配映射時(shí)需要保證每組映射到虛擬節(jié)點(diǎn)的實(shí)節(jié)點(diǎn)不會重復(fù)。表4展示了刪除一個(gè)實(shí)節(jié)點(diǎn)時(shí)虛擬節(jié)點(diǎn)的再分配過程。

表4 初始M＝4時(shí)刪除S2實(shí)節(jié)點(diǎn)虛擬節(jié)點(diǎn)的再分配

表4展示刪除時(shí)再分配算法對應(yīng)的數(shù)據(jù)遷移比例為5／18約等于1／4，再分配之后遷移量接近于1／M，M為刪除節(jié)點(diǎn)前的實(shí)節(jié)點(diǎn)數(shù)。對于單次刪除K（K＞0）個(gè)實(shí)節(jié)點(diǎn)的操作，遷移比例為K／M，滿足單調(diào)性和均衡性要求。

綜上所述，改進(jìn)的一致性哈希算法接近于完美解決了均衡性和單調(diào)性的問題。

2 副本算法

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

基于改進(jìn)一致性哈希架構(gòu)下的分布式集群系統(tǒng)，論文對組內(nèi)數(shù)據(jù)分布設(shè)計(jì)了兩種新的副本算法，以進(jìn)一步提高集群服務(wù)器節(jié)點(diǎn)的性能和利用率，實(shí)現(xiàn)組內(nèi)機(jī)器的負(fù)載均衡。

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

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

表5 SA／SB／SC 三機(jī)主備關(guān)系

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

接下來從概率角度分析兩種副本方案的優(yōu)劣和系統(tǒng)風(fēng)險(xiǎn)。假設(shè)節(jié)點(diǎn)故障概率為p＝0.01，節(jié)點(diǎn)發(fā)生故障是獨(dú)立事件：

（1）組內(nèi)節(jié)點(diǎn)負(fù)載都低于滿載的1／2時(shí)，兩種方案，單個(gè)節(jié)點(diǎn)故障時(shí)都可以將流量切到正常節(jié)點(diǎn)，整組還可以繼續(xù)提供服務(wù)。

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

3 實(shí)驗(yàn)

3.1 一致性哈希算法均衡性驗(yàn)證

對改進(jìn)前的算法，每個(gè)實(shí)節(jié)點(diǎn)配置100個(gè)虛擬節(jié)點(diǎn)；對改進(jìn)后的一致性哈希算法，設(shè)置N為100000。隨機(jī)創(chuàng)建1000萬條由8位隨機(jī)字符組成的Key，統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的訪問次數(shù)作為節(jié)點(diǎn)負(fù)載，計(jì)算最大最小負(fù)載比值作為算法的均衡度。表6展示了兩種算法均衡度對比。

表6 改進(jìn)前后一致性哈希算法最大最小負(fù)載比值

從表6可以看到，改進(jìn)后的一致性哈希算法接近于完美均衡，節(jié)點(diǎn)間的負(fù)載差異非常低；對改進(jìn)前的算法，表6的實(shí)驗(yàn)結(jié)果也與表1高度吻合，改進(jìn)前算法存在節(jié)點(diǎn)負(fù)載不均衡的現(xiàn)象，此外也驗(yàn)證了使用節(jié)點(diǎn)負(fù)責(zé)哈希環(huán)地址空間作為節(jié)點(diǎn)負(fù)載是合理的。

3.2 副本算法驗(yàn)證

使用Redis搭建了主備、雙主兩組服務(wù)器，以相同的QPS請求下考察兩組服務(wù)器的CPU消耗、負(fù)載以及請求平均響應(yīng)時(shí)間。

從表7－表8看到，兩組服務(wù)器內(nèi)的總消耗基本相同，負(fù)載總和也接近。但雙主算法平均響應(yīng)時(shí)間上有明顯的優(yōu)勢，對用戶體驗(yàn)會更好。

表7 主備副本算法

表8 雙主副本算法

相比雙主方案，三主副本方案的優(yōu)勢是可以將單機(jī)負(fù)載從滿載的1／2提高到滿載的2／3。進(jìn)行如下的實(shí)驗(yàn)對比：三主機(jī)正常服務(wù)并且每個(gè)節(jié)點(diǎn)CPU消耗在50%～66%時(shí)，統(tǒng)計(jì)整組服務(wù)器的負(fù)載、平均響應(yīng)時(shí)間；然后停掉一臺機(jī)器，在整組流量不變的條件下，將流量切到剩余的兩臺主機(jī)，觀察整組服務(wù)器CPU消耗、負(fù)載、平均響應(yīng)時(shí)間的變化。

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

表9 三主機(jī)正常服務(wù)

表10 主機(jī)SC 故障

4 結(jié)語

本文對比了常見的靜態(tài)負(fù)載均衡算法，對帶虛擬節(jié)點(diǎn)的一致性哈希算法，通過實(shí)驗(yàn)分析得出算法并非完全均衡；引入了改進(jìn)的一致性哈希算法，在理論和實(shí)驗(yàn)驗(yàn)證中，此算法在保持單調(diào)性的同時(shí)達(dá)到了近乎完美的均衡。基于改進(jìn)的一致性哈希算法，使用組的概念替代傳統(tǒng)的節(jié)點(diǎn)，在解決副本的問題的同時(shí)實(shí)現(xiàn)組內(nèi)機(jī)器的負(fù)載均衡，并提出雙主副本和三主副本算法；經(jīng)過實(shí)驗(yàn)驗(yàn)證，雙主副本／三主副本方案對比主備方案，有著更好的性能和可靠性。