什么是一致性hash？

點擊上方藍色字體，選擇“標星公眾號”

優(yōu)質(zhì)文章，第一時間送達

  作者 |  barantt 

來源 |  urlify.cn/zINJNr

前言

說出來大家可能不相信，我昨天做夢夢到自己在面試，然后面試官問了我這個問題哈哈~然后我就打算按照自己的理解寫一寫。如果有寫的不對的歡迎大家指正！

直接開始

普通hash算法

普通hash算法就是把存儲的key取hash然后再對節(jié)點數(shù)取模之后判斷key所在節(jié)點的位置，

如上圖所示，假設(shè)現(xiàn)在有key1，key2，key3，key4四個key，通過上面說的方法均勻分布在了這4個節(jié)點上面?？瓷先シ浅ice~

但是如果現(xiàn)在我們集群需要擴容，增加一臺機器會發(fā)生啥？

可以看到，由于現(xiàn)在增加了一臺機器，所以現(xiàn)在我們?nèi)∧５膶ο笥?變成了4。

導(dǎo)致什么現(xiàn)象呢？假設(shè)我們的數(shù)據(jù)現(xiàn)在沒有遷移，那原來的key3和key4本來是分別在node0和node1上的，現(xiàn)在通過hash取模運算之后卻是在node0和node3上，所以在數(shù)據(jù)不做遷移的情況下會導(dǎo)致原有的緩存會大量失效。然后這種大面積的數(shù)據(jù)遷移是非常麻煩的！

這是擴容導(dǎo)致的問題，如果集群中的節(jié)點宕機呢？

現(xiàn)在node2掛了，集群節(jié)點數(shù)量變成了2，對應(yīng)的key通過hash取模之后所在的節(jié)點也會變化。導(dǎo)致node2上面原有的key查詢不到，會直接查庫。其余的key，除了key1能正常查詢外，其他key全都失效了。這時不僅涉及到數(shù)據(jù)遷移還會導(dǎo)致緩存穿透。

一致性hash

一致性hash其實是普通取模hash算法的改良版，其hash計算方法沒有變化，但是hash空間發(fā)生了變化，由原來的線性的變成了環(huán)。緩存節(jié)點通過hash計算之后得到在hash環(huán)中的位置；key通過hash計算之后得到所在環(huán)的位置，然后順時針方向找到第一個節(jié)點，這個節(jié)點就是存放key的節(jié)點。

來看看一致性hash是如何解決普通取模hash中擴容和宕機的問題的。

假設(shè)現(xiàn)在我們增加了一個節(jié)點node3，原來的key1現(xiàn)在順時針找到了新增加node3，對其余的節(jié)點沒有任何影響。只需要將node0到node3之間的key遷移到新的節(jié)點即可。

如果node2現(xiàn)在宕機了，那么原來的key2順時針找到的節(jié)點會變成node0，其余節(jié)點也沒有任何影響，只需要把node2上的key遷移到node0上即可。

那這個一致性hash難道就沒有啥毛病了嘛？

想一下，如果我們的節(jié)點數(shù)量很少，并且節(jié)點偏向一側(cè)會發(fā)生什么事情？

可以看到很大一部分的key都會落在node0上，從而導(dǎo)致node0的壓力過大掛掉，node0掛掉之后數(shù)據(jù)同時又會向node1上轉(zhuǎn)移，node1又會掛掉，最終導(dǎo)致整個集群不可用！這就是數(shù)據(jù)傾斜的問題，會引起節(jié)點雪崩?？上攵@個問題會很嚴重。

一致性hash優(yōu)化

數(shù)據(jù)傾斜的問題是通過虛擬節(jié)點來解決的。

就是在節(jié)點稀疏的hash環(huán)上對物理節(jié)點虛擬出一部分虛擬節(jié)點，key會打到虛擬節(jié)點上面，而虛擬節(jié)點上的key實際也是映射到物理節(jié)點上的，這樣就避免了數(shù)據(jù)傾斜導(dǎo)致單節(jié)點壓力過大導(dǎo)致節(jié)點雪崩的問題。

結(jié)語

做夢引起的一片博文。

介紹了普通取模hash的弊端，一致性hash如何解決，以及一致性hash優(yōu)化的問題。

鋒哥最新SpringCloud分布式電商秒殺課程發(fā)布

??????

??長按上方微信二維碼 2 秒

感謝點贊支持下哈