一致性哈希，原來(lái)這么多學(xué)問(wèn)！
面試中一致性哈希算法被問(wèn)到的概率非常大，本文將從如下三個(gè)方面探探一致性哈希算法，讓大家輕松應(yīng)對(duì)面試，并且說(shuō)出與眾不同的答案。
一致性哈希算法經(jīng)典使用場(chǎng)景
一致性哈希算法通常不適合用于服務(wù)類負(fù)載均衡
面試應(yīng)對(duì)之策
1、一致性哈希算法經(jīng)典使用場(chǎng)景
在數(shù)據(jù)庫(kù)存儲(chǔ)領(lǐng)域如果單表數(shù)據(jù)量很大，通常會(huì)采用分庫(kù)分表，在緩存領(lǐng)域同樣需要分庫(kù)，下面以一個(gè)非常常見(jiàn)的Redis分庫(kù)架構(gòu)為例進(jìn)行闡述。
將上述3個(gè)Redis節(jié)點(diǎn)稱之為分片，每一個(gè)節(jié)點(diǎn)存儲(chǔ)部分?jǐn)?shù)據(jù)，需要使用負(fù)載均衡算法，將數(shù)據(jù)盡量分?jǐn)偟礁鱾€(gè)節(jié)點(diǎn)，充分發(fā)揮分布式的優(yōu)勢(shì)，提升系統(tǒng)緩存訪問(wèn)的性能。
在分布緩存領(lǐng)域，對(duì)數(shù)據(jù)存在新增與查詢，即數(shù)據(jù)通過(guò)路由算法存儲(chǔ)在某一個(gè)節(jié)點(diǎn)后，查詢時(shí)需要盡量路由到同一個(gè)節(jié)點(diǎn)，否則會(huì)出現(xiàn)查詢未命中緩存的情況，這也是與分布式服務(wù)調(diào)用領(lǐng)域的負(fù)載算法一個(gè)不同點(diǎn)。
分布式緩存存儲(chǔ)類領(lǐng)域的負(fù)載均衡算法通常會(huì)使用某一個(gè)字段當(dāng)分片鍵，在進(jìn)行負(fù)載之前先求出分片字段對(duì)應(yīng)的 HashCode，然后與當(dāng)前的節(jié)點(diǎn)數(shù)取模。即 hashcode(分片鍵) % 節(jié)點(diǎn)總數(shù)(分片總數(shù))。
1.1 分布式緩存領(lǐng)域上述算法的弊端
先哈希再取模實(shí)現(xiàn)起來(lái)簡(jiǎn)單高效，但在分布式緩存領(lǐng)域存在一個(gè)致命的痛點(diǎn)，對(duì)擴(kuò)容、縮容不友好，會(huì)降低緩存的命中率。
因擴(kuò)容引起的數(shù)據(jù)命中率問(wèn)題示意圖如下：
例如當(dāng)前集群中由 3 個(gè)節(jié)點(diǎn)存儲(chǔ)，現(xiàn)在向集群中寫入 6 個(gè)數(shù)據(jù)，其分片鍵的 hashcode 為 1-6，數(shù)據(jù)的分布情況如上述所示。
根據(jù) hashcode 再取模的方式，由于數(shù)量從3臺(tái)到4臺(tái)，經(jīng)路由算法路由后，k4 會(huì)嘗試從 3.169 的機(jī)器去查找，但對(duì)應(yīng)的數(shù)據(jù)卻存儲(chǔ)在 3.166 上，以上面 6 個(gè)key的命中來(lái)看，只有 50% 的命中率，擴(kuò)容后帶來(lái)緩存穿透，大量數(shù)據(jù)進(jìn)入穿透到后臺(tái)數(shù)據(jù)庫(kù)。
面對(duì)上述問(wèn)題第一種解決方案：成倍擴(kuò)容。將原來(lái)的 3 個(gè)節(jié)點(diǎn)數(shù)量翻倍，新增加的第一臺(tái)數(shù)據(jù)來(lái)源于第一臺(tái)，以此類推，第 6 臺(tái)的數(shù)據(jù)來(lái)源于第 3 臺(tái)，這樣 k6 經(jīng)過(guò)新的負(fù)載均衡算法會(huì)落到第 6 臺(tái)，避免了緩存穿透。
成倍擴(kuò)容能有效解決擴(kuò)容后帶來(lái)的緩存穿透問(wèn)題，但這樣做會(huì)造成資源的浪費(fèi)，有沒(méi)有其他更好的方法呢？
一致性哈希算法閃亮登場(chǎng)。
1.2 一致性哈希算法
一致性哈希算法的設(shè)計(jì)理念如下圖所示：
首先將哈希值映射到 0 ~ 2 的 32 次方的一個(gè)圓中，然后將實(shí)際的物理節(jié)點(diǎn)的IP地址或取其可以表示一個(gè)節(jié)點(diǎn)的 hash 值，放入到 hash 環(huán)中。
然后對(duì)需要插入的數(shù)據(jù)先求哈希，再順時(shí)針沿著哈希環(huán)，找到第一個(gè)實(shí)際節(jié)點(diǎn)，數(shù)據(jù)將存儲(chǔ)到該實(shí)際節(jié)點(diǎn)上。
擴(kuò)容后的示例圖：
從中可以看到受影響的范圍能控制在兩個(gè)節(jié)點(diǎn)的 hashcode 之間的部分?jǐn)?shù)據(jù)，比起先哈希再取模，其未命中率將會(huì)得到極大的影響。
但一致性哈希算法要得到較好的效果，取決于各個(gè)實(shí)體節(jié)點(diǎn)在哈希環(huán)的分布情況，是否能分散，例如如下分布則會(huì)大打折扣：
這種情況會(huì)造成數(shù)據(jù)分布不均衡，為了解決數(shù)據(jù)很可能分布不均勻的情況，對(duì)一致性哈希算法，提出了改進(jìn)，引入了虛擬節(jié)點(diǎn)的，可以設(shè)置一個(gè)哈希環(huán)中存在多少個(gè)虛擬節(jié)點(diǎn)，然后將虛擬節(jié)點(diǎn)映射到實(shí)體節(jié)點(diǎn)，從而解決數(shù)據(jù)分布不均衡的問(wèn)題。
這樣通過(guò)為不同的的實(shí)際節(jié)點(diǎn)映射到多個(gè)虛擬節(jié)點(diǎn)，實(shí)現(xiàn)數(shù)據(jù)的均勻分布，并且擴(kuò)容或縮容時(shí)并不會(huì)出現(xiàn)大面積的緩存穿透。
溫馨提示：上述的映射只是一個(gè)理想狀態(tài)，其核心思路是為每一個(gè)實(shí)體節(jié)點(diǎn)創(chuàng)建多個(gè)虛擬節(jié)點(diǎn)，并且核心虛擬節(jié)點(diǎn)的Hash值越分散越好。
大家可以思考一下，如何用JAVA來(lái)實(shí)現(xiàn)一致性哈希算法？
一致性哈希算法的兩個(gè)關(guān)鍵：
順時(shí)針選擇節(jié)點(diǎn)
可以使用TreeMap，一來(lái)具備排序功能，天然提供了相應(yīng)的方法獲取順時(shí)針的一個(gè)元素。TreeMap 的 ceilingEntry()方法用于返回與大于或等于給定鍵元素(ele)的最小鍵元素鏈接的鍵值對(duì)。
虛擬節(jié)點(diǎn)如何生成分散的哈希值
生成分散的哈希值，通常可以基于md5來(lái)實(shí)現(xiàn)。
2、一致性哈希算法被 “濫用”
一致性哈希算法在面對(duì)分布式緩存有著得天獨(dú)厚的優(yōu)勢(shì)，因?yàn)樗漠a(chǎn)生就是為了解決分布式緩存擴(kuò)容、縮容帶來(lái)的緩存穿透問(wèn)題。但現(xiàn)在一致性在分布式服務(wù)調(diào)用的負(fù)載算法竟然也提供了一致性哈希算法的實(shí)現(xiàn)。
在Dubbo中為了實(shí)現(xiàn)客戶端在服務(wù)調(diào)用時(shí)對(duì)服務(wù)提供者進(jìn)行負(fù)載均衡，官方也提供了一致性哈希算法；
在RocketMQ集群消費(fèi)模式時(shí)消費(fèi)隊(duì)列的負(fù)載均衡機(jī)制竟然也實(shí)現(xiàn)了一致性哈希算法。
但我覺(jué)得一致性哈希算法在這些領(lǐng)域完全無(wú)法發(fā)揮其他優(yōu)勢(shì)，比輪循、加權(quán)輪循、隨機(jī)、加權(quán)隨機(jī)算法等負(fù)載均衡算法相比，實(shí)現(xiàn)復(fù)雜，性能低下，運(yùn)維管理復(fù)雜。
因?yàn)樵诜?wù)調(diào)用等負(fù)載均衡算法，多次服務(wù)調(diào)用之間關(guān)聯(lián)性不太強(qiáng)，在服務(wù)端擴(kuò)容、縮容后，對(duì)于客戶端來(lái)說(shuō)其實(shí)并不關(guān)心路由到哪臺(tái)服務(wù)器，其關(guān)心的是能否返回一臺(tái)服務(wù)器即可。
3、面試應(yīng)對(duì)之策
在面試過(guò)程中，遇到一致性哈希算的時(shí)候，盡量能從其使用場(chǎng)景：分布式緩存負(fù)載均衡，特別是突出擴(kuò)容、縮容能有效避免緩存穿透的問(wèn)題。同時(shí)需要闡述一致性哈希算法的缺陷以及其應(yīng)對(duì)策略(虛擬節(jié)點(diǎn))。
聊的差不多可以順便提一下閱讀過(guò)一致性哈希算法的源碼：強(qiáng)調(diào)TreeMap與虛擬節(jié)點(diǎn)哈希值的生成方法。
最后可以嘗試引導(dǎo)面試官聊聊現(xiàn)在一致性哈希算法有點(diǎn)被濫用的嫌疑，在輕松愉快的討論中與面試交流技術(shù)，面試官好評(píng)度蹭蹭往上漲。
本文就介紹到這里了，麻煩點(diǎn)亮在看，點(diǎn)贊、轉(zhuǎn)發(fā)、留言是對(duì)我最大的鼓勵(lì)。
精彩熱文TOP3
這篇文章出自好基友丁哥，他出版了《RocketMQ 技術(shù)內(nèi)幕》一書，榮獲 RocketMQ 官方社區(qū)優(yōu)秀布道師，在 MQ 領(lǐng)域有著較大的影響力，他將他日均千億級(jí)消息的 MQ 運(yùn)維經(jīng)驗(yàn)整理成了電子書，關(guān)注下方公眾號(hào)回復(fù) RMQPDF 即可免費(fèi)獲取。
下面是丁哥的個(gè)人微信號(hào)，有任何中間件有關(guān)的技術(shù)問(wèn)題，可以撩他討論。