面試官經(jīng)常問的一致性哈希算法，原來這么簡單
面試中一致性哈希算法被問到的概率非常大，本文將從如下三個方面探探一致性哈希算法，讓大家輕松應(yīng)對面試，并且說出與眾不同的答案。
一致性哈希算法經(jīng)典實用場景
一致性哈希算法通常不適合用于服務(wù)類負(fù)載均衡
面試應(yīng)對之策
1、一致性哈希算法經(jīng)典使用場景
在數(shù)據(jù)庫存儲領(lǐng)域如果單表數(shù)據(jù)量很大，通常會采用分庫分表，在緩存領(lǐng)域同樣需要分庫，下面以一個非常常見的Redis分庫架構(gòu)為例進行闡述。
在分布緩存領(lǐng)域，對數(shù)據(jù)存在新增與查詢，即數(shù)據(jù)通過路由算法存儲在某一個節(jié)點后，查詢時需要盡量路由到同一個節(jié)點，否則會出現(xiàn)查詢未命中緩存的情況，這也是與分布式服務(wù)調(diào)用領(lǐng)域的負(fù)載算法一個不同點。
分布式緩存存儲類領(lǐng)域的負(fù)載均衡算法通常會使用某一個字段當(dāng)分片鍵，在進行負(fù)載之前先求出分片字段對應(yīng)的HashCode，然后與當(dāng)前的節(jié)點數(shù)取模。即 hashcode(分片鍵) % 節(jié)點總數(shù)(分片總數(shù))。
1.1 在分布式緩存領(lǐng)域上述算法的弊端
先哈希再取模實現(xiàn)起來簡單高效，但在分布式緩存領(lǐng)域存在一個致命的痛點，對擴容、縮容不友好，會降低緩存的命中率。
因擴容引起的數(shù)據(jù)命中率問題示意圖如下：
例如當(dāng)前集群中由3個節(jié)點存儲，例如現(xiàn)在向集群中寫入6個數(shù)據(jù)，其分片鍵的hashcode為1-6，數(shù)據(jù)的分布情況如上述所示，但由于隨著業(yè)務(wù)的急劇增長，3臺redis已經(jīng)無法滿足業(yè)務(wù)的需求，項目組決定對其進行擴容，從原先的3臺擴容到4臺，這個時候項目組嘗試去緩存中查找 k1,k2,k3,k4,k5,k6時會出現(xiàn)什么問題？
根據(jù) hashcode 再取模的方式，由于數(shù)量從3臺到4臺，經(jīng)路由算法路由后，k4 會嘗試從3.169的機器去查找，但對應(yīng)的數(shù)據(jù)卻存儲在3.166上，以上面6個key的命中來看，只有50%的命中率，擴容后帶來緩存穿透，大量數(shù)據(jù)進入穿透到后臺數(shù)據(jù)庫。
面對上述問題第一種解決方案：成倍擴容。將原來的3個節(jié)點數(shù)量翻倍倍，新增加的第一臺數(shù)據(jù)來源于第一臺，以此類推，第6臺的數(shù)據(jù)來源于第3臺，這樣k6經(jīng)過新的負(fù)載均衡算法會落到第6臺，數(shù)據(jù)原本存在于第3臺，而第6臺的數(shù)據(jù)來源于第3臺，這樣避免了緩存穿透。
成倍擴容能有效解決擴容后帶來的緩存穿透問題，但這樣做會造成資源的浪費，有沒有其他更好的方法呢？
一致性哈希算法閃亮登場。
1.2 一致性哈希算法
一致性哈希算法的設(shè)計理念如下圖所示：
然后對需要插入的數(shù)據(jù)先求哈希，再順時針沿著哈希環(huán)，找到第一個實際節(jié)點，數(shù)據(jù)將存儲到該實際節(jié)點上。
擴容后的示例圖：
從中可以看到受影響的范圍能控制在兩個節(jié)點的hashcode之間的部分?jǐn)?shù)據(jù)，比起先哈希再取模，其未命中率將會得到極大的影響。
但一致性哈希算法要得到較好的效果，取決于各個實體節(jié)點在哈希環(huán)的分布情況，是否能分散，例如如下分布則會大打折扣：
這種情況會造成數(shù)據(jù)分布不均衡，為了解決數(shù)據(jù)很可能分布不均勻的情況，對一致性哈希算法，提出了改進，引入了虛擬節(jié)點的，可以設(shè)置一個哈希環(huán)中存在多少個虛擬節(jié)點，然后將虛擬節(jié)點映射到實體節(jié)點，從而解決數(shù)據(jù)分布不均衡的問題。
這樣通過為不同的的實際節(jié)點映射到多個虛擬節(jié)點，實現(xiàn)數(shù)據(jù)的均勻分布，并且擴容或縮容時并不會出現(xiàn)大面積的緩存穿透。
溫馨提示：上述的映射只是一個理想狀態(tài)，其核心思路是為每一個實體節(jié)點創(chuàng)建多個虛擬節(jié)點，并且核心虛擬節(jié)點的Hash值越分散越好。
大家可以思考一下，如何用JAVA來實現(xiàn)一致性哈希算法？
一致性哈希算法的兩個關(guān)鍵：
順時針選擇節(jié)點
可以使用TreeMap，一來具備排序功能，天然提供了相應(yīng)的方法獲取順時針的一個元素。
TreeMap 的 ceilingEntry()方法用于返回與大于或等于給定鍵元素(ele)的最小鍵元素鏈接的鍵值對。虛擬節(jié)點如何生成分散的哈希值
生成分散的哈希值，通?？梢曰趍d5來實現(xiàn)。
2、一致性哈希算法被“濫用”
一致性哈希算法在面對分布式緩存有著得天獨厚的優(yōu)勢，因為它的產(chǎn)生就是為了解決分布式緩存擴容、縮容帶來的緩存穿透問題。但現(xiàn)在一致性在分布式服務(wù)調(diào)用的負(fù)載算法竟然也提供了一致性哈希算法的實現(xiàn)。
在Dubbo中為了實現(xiàn)客戶端在服務(wù)調(diào)用時對服務(wù)提供者進行負(fù)載均衡，官方也提供了一致性哈希算法；在RocketMQ集群消費模式時消費隊列的負(fù)載均衡機制竟然也實現(xiàn)了一致性哈希算法，但我覺得一致性哈希算法在這些領(lǐng)域完全無法發(fā)揮其他優(yōu)勢，比輪循、加權(quán)輪循、隨機、加權(quán)隨機算法等負(fù)載均衡算法相比，實現(xiàn)復(fù)雜，性能低下，運維管理復(fù)雜。
因為在服務(wù)調(diào)用等負(fù)載均衡算法，多次服務(wù)調(diào)用之間關(guān)聯(lián)性不太強，在服務(wù)端擴容、縮容后，對于客戶端來說其實并不關(guān)心路由到哪臺服務(wù)器，其關(guān)心的是能否返回一臺服務(wù)器即可。
3、面試應(yīng)對之策
在面試過程中，遇到一致性哈希算的時候，盡量能從其使用場景：分布式緩存負(fù)載均衡，特別是突出擴容、縮容能有效避免緩存穿透的問題。同時需要闡述一致性哈希算法的缺陷以及其應(yīng)對策略(虛擬節(jié)點)。
聊的差不多可以順便提一下閱讀過一致性哈希算法的源碼：強調(diào)TreeMap與虛擬節(jié)點哈希值的生成方法。
最后可以嘗試引導(dǎo)面試官聊聊現(xiàn)在一致性哈希算法有點被濫用的嫌疑，在輕松愉快的討論中與面試交流技術(shù)，面試官好評度蹭蹭往上漲。