分布式系統(tǒng)中一致性哈希

問題場景

近年來B2C眼坏、O2O等商業(yè)概念的提出和移動端的發(fā)展型豁，使得分布式系統(tǒng)流行了起來酬凳。分布式系統(tǒng)相對于單系統(tǒng)谋竖，解決了流量大红柱、系統(tǒng)高可用和高容錯等問題。功能強大也意味著實現(xiàn)起來需要更多技術(shù)的支持蓖乘。例如系統(tǒng)訪問層的負載均衡锤悄，緩存層的多實例主從復(fù)制備份，數(shù)據(jù)層的分庫分表等嘉抒。

我們以負載均衡為例零聚，常見的負載均衡方法有很多，但是它們的優(yōu)缺點也都很明顯：

隨機訪問策略。 系統(tǒng)隨機訪問隶症，缺點：可能造成服務(wù)器負載壓力不均衡政模，俗話講就是撐的撐死，餓的餓死蚂会。

輪詢策略淋样。 請求均勻分配，如果服務(wù)器有性能差異胁住，則無法實現(xiàn)性能好的服務(wù)器能夠多承擔(dān)一部分习蓬。

權(quán)重輪詢策略。 權(quán)值需要靜態(tài)配置措嵌，無法自動調(diào)節(jié)躲叼，不適合對長連接和命中率有要求的場景。

Hash取模策略企巢。 不穩(wěn)定枫慷，如果列表中某臺服務(wù)器宕機，則會導(dǎo)致路由算法產(chǎn)生變化浪规，由此導(dǎo)致命中率的急劇下降或听。

一致性哈希策略。

以上幾個策略笋婿，排除本篇介紹的一致性哈希誉裆，可能使用最多的就是 Hash取模策略了。Hash取模策略的缺點也是很明顯的缸濒，這種缺點也許在負載均衡的時候不是很明顯足丢，但是在涉及數(shù)據(jù)訪問的主從備份和分庫分表中就體現(xiàn)明顯了。

使用Hash取模的問題

負載均衡

負載均衡時庇配，假設(shè)現(xiàn)有3臺服務(wù)器(編號分別為0斩跌、1瀑踢、2)称勋，使用哈希取模的計算方式則是：對訪問者的IP，通過固定算式hash(IP) % N（N為服務(wù)器的個數(shù)）顷扩，使得每個IP都可以定位到特定的服務(wù)器啸澡。

例如現(xiàn)有IP地址 10.58.34.31袖订，對IP哈希取模策時，計算結(jié)果為2嗅虏，即訪問編號為2的服務(wù)器：

String ip ="10.58.34.31";intv1 = hash(ip) %3;System.out.println("訪問服務(wù)器："+ v1);// 訪問服務(wù)器：2

如果此時服務(wù)器2宕機了洛姑，則會導(dǎo)致所有計算結(jié)果為2的 IP 對應(yīng)的用戶都訪問異常（包括上例中的IP）⌒眨或者你新增了一臺服務(wù)器3吏口，這時不修改N值的話那么服務(wù)器3永遠不會被訪問到奄容。

image.png

當(dāng)然如果你能動態(tài)獲取到當(dāng)前可用服務(wù)器的個數(shù)，亦即N值是根據(jù)當(dāng)前可用服務(wù)器個數(shù)動態(tài)來變化的产徊，則可解決此問題昂勒。但是對于特定地區(qū)或特定IP訪問特定服務(wù)器類的需求會造成訪問偏差。

分庫分表

負載均衡中有這種問題舟铜，那么分庫分表中同樣也有這樣的問題戈盈。例如隨著業(yè)務(wù)的飛速增長，我們的注冊用戶也越來越多谆刨，單個用戶表數(shù)量已經(jīng)達到千萬級甚至更大塘娶。由于Mysql的單表建議百萬級數(shù)據(jù)存儲，所以這時為了保證系統(tǒng)查詢和運行效率痊夭，肯定會考慮到分庫分表刁岸。

對于分庫分表，數(shù)據(jù)的分配是個重要的問題她我，你需要保證數(shù)據(jù)分配在這個服務(wù)器虹曙，那么在查詢時也需要到該服務(wù)器上來查詢，否則會造成數(shù)據(jù)查詢丟失的問題番舆。

通常是根據(jù)用戶的 ID 哈希取模得到的值然后路由到對應(yīng)的存儲位置酝碳，計算公式為：hash(userId) % N，其中N為分庫或分表的個數(shù)恨狈。

例如分庫數(shù)為2時疏哗，計算結(jié)果為1，則ID為1010的用戶存儲在編號為1對應(yīng)的庫中：

String userId ="1010";intv1 = hash(userId) %2;System.out.println("存儲："+ v1);// 存儲：1

image.png

之后業(yè)務(wù)數(shù)量持續(xù)增長禾怠，又新增一臺用戶服務(wù)庫返奉，當(dāng)我們根據(jù)ID=1010去查詢數(shù)據(jù)時，路由計算方式為：

intv2 = hash(userId) %3;System.out.println("存儲："+ v2);// 存儲：0

我們得到的路由值是0刃宵，最后的結(jié)果就不用說了衡瓶，存在編號1上的數(shù)據(jù)我們?nèi)ゾ幪枮?的庫上去查詢肯定是得不到查詢結(jié)果的徘公。

image.png

為了數(shù)據(jù)可用牲证，你需要做數(shù)據(jù)遷移，按照新的路由規(guī)則對所有用戶重新分配存儲地址关面。每次的庫或表的數(shù)量改變你都需要做一次全部用戶信息數(shù)據(jù)的遷移坦袍。不用想這其中的工作量是有多費時費力了。

是否有某種方法等太，有效解決這種分布式存儲結(jié)構(gòu)下動態(tài)增加或刪除節(jié)點所帶來的問題捂齐，能保證這種不受實例數(shù)量變化影響而準確路由到正確的實例上的算法或?qū)崿F(xiàn)機制呢？解決這些問題缩抡，一致性哈希算法誕生了奠宜。

基本原理

一致性哈希算法在1997年由麻省理工學(xué)院的Karger等人在解決分布式Cache中提出的，--設(shè)計目標是為了解決因特網(wǎng)中的熱點(Hot spot)問題，初衷和CARP十分類似压真。一致性哈希修正了CARP使用的簡單哈希算法帶來的問題娩嚼，使得DHT可以在P2P環(huán)境中真正得到應(yīng)用。

上面說的哈希取模方法滴肿，它是針對一個點的岳悟，業(yè)務(wù)布局嚴重依賴于這個計算的點值結(jié)果。你結(jié)算的結(jié)果是2泼差，那么就對應(yīng)到編號為2的服務(wù)器上贵少。這樣的映射就造成了業(yè)務(wù)容錯性和可擴展性極低。

我們思考下堆缘，是否可以將這個計算結(jié)果的點值賦予范圍的意義滔灶？我們知道Hash取模之后得到的是一個 int 型的整值。

//Objects 類中默認的 hash 方法publicstaticinthash(Object... values){returnArrays.hashCode(values);}

既然 hash的計算結(jié)果是 int 類型吼肥，而 java 中 int 的最小值是-2

31宽气，最大值是2

31-1。意味著任何通過哈希取模之后的無符號值都會在 0 ~ 2

31-1范圍之間潜沦，共2

32個數(shù)萄涯。那我們是否可以不對服務(wù)器的數(shù)量進行取模而是直接對2^32取模。這就形成了一致性哈希的基本算法思想唆鸡，什么意思呢涝影？

這里需要注意一點：

默認的 hash 方法結(jié)果是有負值的情況，因此需要我們重寫hash方法争占，保證哈希值的非負性燃逻。

簡單來說，一致性Hash算法將整個哈希值空間組織成一個虛擬的圓環(huán)臂痕，如假設(shè)某哈希函數(shù) H 的值空間為 0 ~ 2^32-1（即哈希值是一個32位無符號整形）伯襟，整個哈希環(huán)如下：

image.png

整個空間圓按順時針方向布局，圓環(huán)的正上方的點代表0握童，0點右側(cè)的第一個點代表1姆怪。以此類推2、3澡绩、4稽揭、5、6……直到2

32-1肥卡，也就是說0點左側(cè)的第一個點代表2

32-1溪掀， 0和2

32-1在零點中方向重合，我們把這個由2

32個點組成的圓環(huán)稱為 Hash環(huán)步鉴。

那么揪胃，一致性哈希算法與上圖中的圓環(huán)有什么關(guān)系呢璃哟？仍然以之前描述的場景為例，假設(shè)我們有4臺服務(wù)器喊递，服務(wù)器0沮稚、服務(wù)器1、服務(wù)器2册舞，服務(wù)器3蕴掏，那么，在生產(chǎn)環(huán)境中调鲸，這4臺服務(wù)器肯定有自己的 IP 地址或主機名盛杰，我們使用它們各自的 IP 地址或主機名作為關(guān)鍵字進行哈希計算，使用哈希后的結(jié)果對2^32取模藐石，可以使用如下公式示意：

hash（服務(wù)器的IP地址） %? 2^32

最后會得到一個 [0, 2^32-1]之間的一個無符號整形數(shù)即供，這個整數(shù)就代表服務(wù)器的編號。同時這個整數(shù)肯定處于[0, 2^32-1]之間于微，那么逗嫡，上圖中的 hash 環(huán)上必定有一個點與這個整數(shù)對應(yīng)。那么這個服務(wù)器就可以映射到這個環(huán)上株依。

多個服務(wù)器都通過這種方式進行計算驱证，最后都會各自映射到圓環(huán)上的某個點，這樣每臺機器就能確定其在哈希環(huán)上的位置恋腕，如下圖所示抹锄。

image.png

容錯性和可擴展性

那么用戶訪問，如何分配訪問的服務(wù)器呢荠藤？我們根據(jù)用戶的 IP 使用上面相同的函數(shù) Hash 計算出哈希值伙单，并確定此數(shù)據(jù)在環(huán)上的位置，從此位置沿環(huán) 順時針行走哈肖，遇到的第一臺服務(wù)器就是其應(yīng)該定位到的服務(wù)器吻育。

image.png

從上圖可以看出 用戶1 順時針遇到的第一臺服務(wù)器是 服務(wù)器3 ，所以該用戶被分配給服務(wù)器3來提供服務(wù)淤井。同理可以看出用戶2被分配給了服務(wù)器2布疼。

1. 新增服務(wù)器節(jié)點

如果這時需要新增一臺服務(wù)器節(jié)點，一致性哈希策略是如何應(yīng)對的呢庄吼？如下圖所示缎除，我們新增了一臺服務(wù)器4，通過上述一致性哈希算法計算后得出它在哈希環(huán)的位置总寻。

image.png

可以發(fā)現(xiàn)，原來訪問服務(wù)器3的用戶1現(xiàn)在訪問的對象是服務(wù)器4梢为，用戶能正常訪問且服務(wù)不需要停機就可以自動切換渐行。

2. 刪除服務(wù)器節(jié)點

如果這時某臺服務(wù)器異常宕機或者運維撤銷了一臺服務(wù)器轰坊，那么這時會發(fā)生什么情況呢？如下圖所示祟印，假設(shè)我們撤銷了服務(wù)器2肴沫。

image.png

可以看出，我們服務(wù)仍然能正常提供服務(wù)蕴忆，只不過這時用戶2會被分配到服務(wù)1上了而已颤芬。

通過一致性哈希的方式，我們提高了我們系統(tǒng)的容錯性和可擴展性套鹅，分布式節(jié)點的變動不會影響整個系統(tǒng)的運行且不需要我們做一些人為的調(diào)整策略站蝠。

Hash環(huán)的數(shù)據(jù)傾斜問題

一致性哈希雖然為我們提供了穩(wěn)定的切換策略，但是它也有一些小缺陷卓鹿。因為 hash取模算法得到的結(jié)果是隨機的菱魔，我們并不能保證各個服務(wù)節(jié)點能均勻的分配到哈希環(huán)上。

例如當(dāng)有4個服務(wù)節(jié)點時吟孙，我們把哈希環(huán)認為是一個圓盤時鐘澜倦，我們并不能保證4個服務(wù)節(jié)點剛好均勻的落在時鐘的 12、3杰妓、6藻治、9點上。

分布不均勻就會產(chǎn)生一個問題巷挥，用戶的請求訪問就會不均勻栋艳，同時4個服務(wù)承受的壓力就會不均勻。這種問題現(xiàn)象我們稱之為句各，Hash環(huán)的數(shù)據(jù)傾斜問題吸占。

image.png

如上圖所示，服務(wù)器0 到 服務(wù)器1 之間的哈希點值占據(jù)比例最大凿宾，大量請求會集中到 服務(wù)器1 上矾屯，而只有極少量會定位到 服務(wù)器0 或其他幾個節(jié)點上，從而出現(xiàn) hash環(huán)偏斜的情況初厚。

如果想要均衡的將緩存分布到每臺服務(wù)器上件蚕，最好能讓這每臺服務(wù)器盡量多的、均勻的出現(xiàn)在hash環(huán)上产禾，但是如上圖中所示排作，真實的服務(wù)器資源只有4臺，我們怎樣憑空的讓它們多起來呢亚情？

既然沒有多余的真正的物理服務(wù)器節(jié)點妄痪，我們就只能將現(xiàn)有的物理節(jié)點通過虛擬的方法復(fù)制出來。

這些由實際節(jié)點虛擬復(fù)制而來的節(jié)點被稱為 "虛擬節(jié)點"楞件，即對每一個服務(wù)節(jié)點計算多個哈希衫生，每個計算結(jié)果位置都放置一個此服務(wù)節(jié)點裳瘪，稱為虛擬節(jié)點。具體做法可以在服務(wù)器IP或主機名的后面增加編號來實現(xiàn)罪针。

如上圖所示彭羹，假如 服務(wù)器1 的 IP 是 192.168.32.132，那么原 服務(wù)器1 節(jié)點在環(huán)形空間的位置就是hash("192.168.32.132") % 2^32泪酱。

我們基于 服務(wù)器1 構(gòu)建兩個虛擬節(jié)點派殷，Server1-A 和 Server1-B，虛擬節(jié)點在環(huán)形空間的位置可以利用（IP+后綴）計算墓阀，例如：

hash("192.168.32.132#A") % 2^32hash("192.168.32.132#B") % 2^32

此時毡惜，環(huán)形空間中不再有物理節(jié)點 服務(wù)器1，服務(wù)器2岂津，……虱黄，替代的是只有虛擬節(jié)點 Server1-A，Server1-B吮成，Server2-A橱乱，Server2-B，……粱甫。

image.png

同時數(shù)據(jù)定位算法不變泳叠，只是多了一步虛擬節(jié)點到實際節(jié)點的映射，例如定位到 “Server1-A”茶宵、“Server1-B” 兩個虛擬節(jié)點的數(shù)據(jù)均定位到 服務(wù)器1上危纫。這樣就解決了服務(wù)節(jié)點少時數(shù)據(jù)傾斜的問題。

在實際應(yīng)用中乌庶，通常將虛擬節(jié)點數(shù)設(shè)置為32甚至更大种蝶，因此即使很少的服務(wù)節(jié)點也能做到相對均勻的數(shù)據(jù)分布。由于虛擬節(jié)點數(shù)量較多瞒大，與虛擬節(jié)點的映射關(guān)系也變得相對均衡了螃征。

總結(jié)

一致性哈希一般在分布式緩存中使用的也比較多，本篇只介紹了服務(wù)的負載均衡和分布式存儲透敌，對于分布式緩存其實原理是類似的盯滚，讀者可以自己舉一反三來思考下。

其實酗电，在分布式存儲和分布式緩存中魄藕，當(dāng)服務(wù)節(jié)點發(fā)生變化時（新增或減少），一致性哈希算法并不能杜絕數(shù)據(jù)遷移的問題撵术，但是可以避免數(shù)據(jù)的全量遷移背率，需要遷移的只是更改的節(jié)點和它的上游節(jié)點它們兩個節(jié)點之間的那部分數(shù)據(jù)。

另外，我們都知道 hash算法 有一個避免不了的問題退渗，就是哈希沖突移稳。對于用戶請求IP的哈希沖突蕴纳，其實只是不同用戶被分配到了同一臺服務(wù)器上会油，這個沒什么影響。但是如果是服務(wù)節(jié)點有哈希沖突呢古毛？這會導(dǎo)致兩個服務(wù)節(jié)點在哈希環(huán)上對應(yīng)同一個點翻翩，其實我感覺這個問題也不大，因為一方面哈希沖突的概率比較低稻薇，另一方面我們可以通過虛擬節(jié)點也可減少這種情況嫂冻。