什么是一致性hash？

點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”

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

  作者 |  barantt 

來(lái)源 |  urlify.cn/zINJNr

前言

說(shuō)出來(lái)大家可能不相信，我昨天做夢(mèng)夢(mèng)到自己在面試，然后面試官問(wèn)了我這個(gè)問(wèn)題哈哈~然后我就打算按照自己的理解寫(xiě)一寫(xiě)。如果有寫(xiě)的不對(duì)的歡迎大家指正！

直接開(kāi)始

普通hash算法

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

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

但是如果現(xiàn)在我們集群需要擴(kuò)容，增加一臺(tái)機(jī)器會(huì)發(fā)生啥？

可以看到，由于現(xiàn)在增加了一臺(tái)機(jī)器，所以現(xiàn)在我們?nèi)∧５膶?duì)象由3變成了4。

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

這是擴(kuò)容導(dǎo)致的問(wèn)題，如果集群中的節(jié)點(diǎn)宕機(jī)呢？

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

一致性hash

一致性hash其實(shí)是普通取模hash算法的改良版，其hash計(jì)算方法沒(méi)有變化，但是hash空間發(fā)生了變化，由原來(lái)的線性的變成了環(huán)。緩存節(jié)點(diǎn)通過(guò)hash計(jì)算之后得到在hash環(huán)中的位置；key通過(guò)hash計(jì)算之后得到所在環(huán)的位置，然后順時(shí)針?lè)较蛘业降谝粋€(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)就是存放key的節(jié)點(diǎn)。

來(lái)看看一致性hash是如何解決普通取模hash中擴(kuò)容和宕機(jī)的問(wèn)題的。

假設(shè)現(xiàn)在我們?cè)黾恿艘粋€(gè)節(jié)點(diǎn)node3，原來(lái)的key1現(xiàn)在順時(shí)針找到了新增加node3，對(duì)其余的節(jié)點(diǎn)沒(méi)有任何影響。只需要將node0到node3之間的key遷移到新的節(jié)點(diǎn)即可。

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

那這個(gè)一致性hash難道就沒(méi)有啥毛病了嘛？

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

可以看到很大一部分的key都會(huì)落在node0上，從而導(dǎo)致node0的壓力過(guò)大掛掉，node0掛掉之后數(shù)據(jù)同時(shí)又會(huì)向node1上轉(zhuǎn)移，node1又會(huì)掛掉，最終導(dǎo)致整個(gè)集群不可用！這就是數(shù)據(jù)傾斜的問(wèn)題，會(huì)引起節(jié)點(diǎn)雪崩。可想而知這個(gè)問(wèn)題會(huì)很?chē)?yán)重。

一致性hash優(yōu)化

數(shù)據(jù)傾斜的問(wèn)題是通過(guò)虛擬節(jié)點(diǎn)來(lái)解決的。

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

結(jié)語(yǔ)

做夢(mèng)引起的一片博文。

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

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

??????

??長(zhǎng)按上方微信二維碼 2 秒

感謝點(diǎn)贊支持下哈