學習后端必須掌握的算法：一致性Hash

原始問題：假設我們需要對一堆圖片做緩存，緩存的圖片放在了2臺服務器上，當到來一個請求，應該如何知道請求的圖片在哪臺上面呢？

暴力遍歷就不要去想了，否則緩存就沒有意義了。一個自然的想法就是根據圖片的名字做一個映射（Hash），將圖片名字映射到0，1兩個數字上面，例如有這樣的映射函數：

f(圖片名稱) = md5(圖片名稱) % 2

md5是一個典型的哈希函數，會產生128bit的值，模2后只可能是0或1，那么我們就根據這個值把圖片存入0、1兩臺服務器，當請求過來，根據圖片名稱計算出值，就可以知道圖片緩存放在第幾號服務器了：

但假設現在我們圖片太多了，需要再增加一臺服務器分擔壓力，哈希函數必須更改成0、1、2映射，我們改為：

f(圖片名稱) = md5(圖片名稱) % 3

理論上講，會有(N-1)/N的緩存會失效，其中N是服務器的數量，例如上述圖片緩存，除了0圖片、1圖片，其余圖片的存放位置都變了，失效的緩存有 2/3 * 6 = 4張圖片：

減少圖片服務器數量造成的后果亦是如此——在同一個時刻將會有大量緩存同時失效，稱為“緩存雪崩”。失效了就會直接去后端服務器取，大量的請求直接透過緩存打到后端服務器，后端服務器極有可能承受不住壓力而接連崩潰，最終造成整個系統癱瘓。

所以出現進階問題：當緩存服務器數量發生變化時，如何盡可能避免大量緩存同時失效？

答案就是一致性Hash。

1、放置服務器

我們將服務器像圖片一樣也進行哈希，服務器的“圖片名稱”一般就使用固定IP地址，Hash取模也不再是服務器數量，而是2^32，Hash的方法也不局限于md5，用一個抽象的函數表示：

f(服務器IP地址) = Hash(服務器IP地址) % 2^32

于是服務器被放置到了0~2^32-1某個數字對應的位置上去：

這里0~2^32-1是順時針放置還是逆時針放置，網上的說法不一，雖然不影響算法，但統一會更好。我在原論文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中沒有找到相應的描述，于是采用了網上的主流選擇：順時針放置0~2^32-1。

為什么是2^32-1呢？因為第一次提出一致性Hash的論文是1997年發表的，那時候32位機器還是主流，2^32-1是大的Integer。而現在64位早就普及了，完全可以將這個值擴大到2^64-1。

2、放置數據

我們將數據也按照相同的方式放到0~2^32-1的某個數字上去：

f(圖片名稱) = Hash(圖片名稱) % 2^32

3、把數據放到服務器上

對于每個數據，從映射的位置開始，順時針行走，放置到碰到的第一個服務器上。例如3、230將會放到0號圖片服務器，232將會放到1號圖片服務器，4175556547將會放到2號圖片服務器：

這樣一致性Hash就完成了。查找數據也是先映射、再順時針行走找到第一臺服務器。

而對于其他圖片來說，緩存位置并沒有發生變化，影響的數據量從（N-1）/ N 降為了 M，其中M是0號圖片服務器到1號圖片服務器之間的圖片數量。需要重新獲取的緩存數據量降低了，雪崩問題自然也就能夠得到緩解。

0、1、2三臺服務器并沒有均勻分布在環上，大量的圖片數據都被放到了0號服務器上，而很少數據放到1、2號等其他圖片服務器上，這種情況稱之為Hash環偏斜。如果存放的是緩存則0號服務器崩潰就會引起緩存雪崩，如果存放的是數據則0號服務器就可能單點故障。

很自然可以想到，增加多臺服務器就好了嘛。我們在Hash環上生成0、1、2三臺服務器的虛擬節點：

具體的做法是，在服務器IP后面增加編號，每一臺服務器產生多個Hash值，就能放置在0~2^32-1的多個位置上了。這樣一來，順時針行走能找到不同的服務器概率將會大大提高，避免了偏斜問題。虛擬的服務器節點數越多，偏斜出現的概率就越低。通常都需要設置32或以上的虛擬節點數目，我見過甚至有設置500的。

分享名稱：學習后端必須掌握的算法：一致性Hash
網站地址：http://m.kartarina.com/news/100085.html

成都網站建設公司_創新互聯，為您提供網站排名、網站設計公司、品牌網站建設、網站策劃、企業建站、服務器托管

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯