面試中一致性哈希演算法被問到的概率非常大，本文將從如下三個方面探探一致性哈希演算法，讓大家輕松應對面試，并且說出宇宙不同的答案，
- 一致性哈希演算法經典實用場景
- 一致性哈希演算法通常不適合用于服務類負載均衡
- 面試應對之策
1、一致性哈希演算法經典使用場景
在資料庫存盤領域如果單表資料量很大，通常會采用分庫分表，同樣在快取領域同樣需要分庫，下面以一個非常常見的Redis分庫架構為例進行闡述，
將上述3個Redis節點稱之為分片，每一個節點存盤部分資料，期間需要使用負載均衡演算法，將資料盡量分攤到各個節點，充分發揮分布式的優勢，提升系統快取訪問的性能，
在分布快取領域，對資料存在新增與查詢，即資料通過路由演算法存盤在某一個節點后，查詢時需要盡量路由到同一個節點，否則會出現查詢未命中快取的情況，這也是與分布式服務呼叫領域的負載演算法一個不同點，
分布式快取存盤類領域的負載均衡演算法通常會使用某一個欄位當分片鍵，在進行負載之前先求出分片欄位對應的HashCode，然后與當前的節點數取模，即 hashcode(分片鍵) % 節點總數(分片總數)，
1.1 在分布式快取領域上述演算法的弊端
先哈希再驅魔實作起來簡單高效，但在分布式快取領域存在一個致命的痛點，對擴容、縮容不友好，會降低快取的命中率，
因擴容引起的資料命中率問題示意圖如下：
例如當前集群中由3個節點存盤，例如現在向集群中寫入6個資料，其分片鍵的hashcode為1-6，資料的分布情況如上述所示，但由于隨著業務的急劇增長，3臺redis已經無法滿足業務的需求，專案組決定對其進行擴容，從原先的3臺擴容到4臺，這個時候專案組嘗試去快取中查找 k1,k2,k3,k4,k5,k6時會出現什么問題？
根據 hashcode 再取模的方式，由于數量從3臺到4臺，經路由演算法路由后，k4 會嘗試從3.169的機器去查找，但對應的資料卻存盤在3.166上，以上面6個key的命中來看，只有50%的命中率，擴容后帶來快取穿透，大量資料進入到后臺資料庫，
在資料存盤領域的第一種解決方案：成倍擴容，將原來的3個節點數量擴充倍，新增加的第一臺資料來源于第一臺，以此類推，第6臺的資料來源于第3臺，這樣k6經過新的負載均衡演算法會落到第6臺，資料原本存在于第3臺，而第6臺的資料來源于第3臺，這樣避免了快取穿透，
成倍擴容能有效解決擴容后帶來的快取穿透問題，但這樣做會造成資源的浪費，有沒有其他更好的方法呢？
一致性哈希演算法閃亮登場，
1.2 一致性哈希演算法
一致性哈希演算法
一致性哈希演算法的設計理念如下圖所示：
首先將哈希值映射到 0 ~ 2的32次方的一個圓中，然后將實際的物理節點的IP地址或取其hash值，放入到hash環中，
然后對需要插入的資料先求哈希，再順時針沿著哈希環，找到第一個實際節點，資料將存盤到該實際節點上，
擴容后的示例圖：
從中可以看到受影響的范圍能控制在兩個節點的hashcode之間的部分資料，比起先哈希再取模，其未命中率將會得到極大的影響，
但一致性哈希演算法要得到較好的效果，取決于各個物體節點在哈希環的分布情況，是否能分散，例如如下分布則會大打折扣：
這種情況會造成資料分布不均衡，為了解決資料很可能分布不均勻的情況，對一致性哈希演算法，提出了改進，引入了虛擬節點的，可以設定一個哈希環中存在多少個虛擬節點，然后將虛擬節點映射到物體節點，從而解決資料分布吧均衡的問題，
這樣通過為不同的的實際節點映射不同的虛擬節點，實作資料的均勻分布，并且擴容或縮容時并不會出現大面積的快取穿透，
溫馨提示：上述的映射只是一個理想狀態，其核心思路是為每一個物體節點創建多個虛擬節點，并且核心虛擬節點的Hash值越分散越好，
大家可以思考一下，如何用JAVA來實作一致性哈希演算法？
一致性哈希演算法的兩個關鍵：
-
順時針選擇節點
可以使用TreeMap，一來具備排序功能，天然提供了相應的方法獲取順時針的一個元素，
TreeMap 的 ceilingEntry()方法用于回傳與大于或等于給定鍵元素(ele)的最小鍵元素鏈接的鍵值對， -
虛擬節點如何生成分散的哈希值
生成分散的哈希值，通常可以基于md5加密演算法來實作，
2、一致性哈希演算法被“濫用”
一致性哈希演算法在面對分布式快取有著得天獨厚的優勢，因為它的產生就是為了解決分布式快取擴容、縮容帶來的快取穿透問題，但現在一致性在分布式服務呼叫的負載演算法竟然也引入了一致性哈希演算法，
在Dubbo中為了實作客戶端在服務呼叫時對服務提供者進行負載均衡，官方也提供了一致性哈希演算法；在RocketMQ集群消費模式時消費佇列的負載均衡機制竟然也實作了一致性哈希演算法，但我覺得一致性哈希演算法在這些領域完全無法發揮其他優勢，比輪循、加權輪循、隨機、加權隨機演算法等負載均衡演算法相比，實作復雜，性能低下，運維管理復雜，
因為在服務呼叫等負載均衡演算法，多次服務呼叫之間關聯性不太強，在服務端擴容、縮容后，對于客戶端來說其實并不關心路由到哪臺服務器，其關心的是能否回傳一臺服務器即可，
3、面試應對之策
在面試程序中，遇到一致性哈希算的時候，盡量能從其使用場景：分布式快取負載均衡，特別是突出擴容、縮容能有效避免快取穿透的問題，同時需要闡述一致性哈希演算法的缺陷以及其應對策略(虛擬節點)，
聊的差不多可以順便提一下閱讀過一致性哈希演算法的原始碼：強調TreeMap與虛擬節點哈希值的生成方法，
最后可以嘗試引導面試官聊聊現在一致性哈希演算法有點被濫用的嫌疑，在輕松愉快的討論中與面試交流技術，面試官好評度蹭蹭往上漲，
歡迎加筆者微信號(dingwpmz)，拉您如技術交流加群探討，關注『中間件興趣圈』回復**【PDF】**可獲取海量學習資料，
CSDN認證博客專家
RocketMQ
資深架構師
中間件興愛好者
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/256355.html
標籤：其他