原始問題：假設(shè)我們需要對一堆圖片做緩存，緩存的圖片放在了2臺服務(wù)器上，當(dāng)?shù)絹硪粋€請求，應(yīng)該如何知道請求的圖片在哪臺上面呢？

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

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

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

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

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

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

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

所以出現(xiàn)進(jìn)階問題：當(dāng)緩存服務(wù)器數(shù)量發(fā)生變化時，如何盡可能避免大量緩存同時失效？

答案就是一致性Hash。

1、放置服務(wù)器

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

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

于是服務(wù)器被放置到了0~2^32-1某個數(shù)字對應(yīng)的位置上去：

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

為什么是2^32-1呢？因?yàn)榈谝淮翁岢鲆恢滦訦ash的論文是1997年發(fā)表的，那時候32位機(jī)器還是主流，2^32-1是大的Integer。而現(xiàn)在64位早就普及了，完全可以將這個值擴(kuò)大到2^64-1。

2、放置數(shù)據(jù)

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

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

3、把數(shù)據(jù)放到服務(wù)器上

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

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

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

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

很自然可以想到，增加多臺服務(wù)器就好了嘛。我們在Hash環(huán)上生成0、1、2三臺服務(wù)器的虛擬節(jié)點(diǎn)：

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

分享名稱：學(xué)習(xí)后端必須掌握的算法：一致性Hash
網(wǎng)站地址：http://jinyejixie.com/news/100085.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、網(wǎng)站設(shè)計(jì)公司、品牌網(wǎng)站建設(shè)、網(wǎng)站策劃、企業(yè)建站、服務(wù)器托管

廣告

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