學(xué)習(xí)后端必須掌握的算法：一致性Hash

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

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

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

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

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

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

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

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

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

答案就是一致性Hash。

1、放置服務(wù)器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

分享名稱：學(xué)習(xí)后端必須掌握的算法：一致性Hash
網(wǎng)站地址：http://www.muchs.cn/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)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)