一篇文章搞懂「一致性哈希」

• 2019 年 10 月 6 日
• 筆記

在解決分散式系統中負載均衡的問題時候可以使用Hash演算法讓固定的一部分請求落到同一台伺服器上，這樣每台伺服器固定處理一部分請求，起到負載均衡的作用。我們常想到的就是「哈希」，另外一個名詞「一致性哈希」也經常被提起，甚至再面試中也會被經常被問。

其實，一致性哈希的演算法思想在日常編程中也極其重要，本文就帶領大家一起學習一致性哈希。

哈希hash

首先了解一下什麼是哈希，hash的意思是散列，目的將一組輸入的數據均勻的分開、打散，往往用來配合路由演算法做負載均衡，多用在分散式系統中。比如memcached它只提供了KV的存儲、讀取，如果使用了多台memcache做一個「邏輯集群」，就需要客戶端做「路由演算法」，來保證進去後，能「原路」拿出來。

Hash演算法的最經典應用就是HashMap了，HashMap的數據結構簡單如下圖所示：

在HashMap中，當元素超過默認大小的時候，就涉及到一個擴容的操作，這樣之前的數據分布會不會改變呢？

所以，普通Hash演算法有一個明顯的劣勢：即當node數發生變化（增加、移除）後，數據項會被重新「打散」，導致大部分數據項不能落到原來的節點上，從而導致大量數據需要遷移。

那麼就有了這樣一個很重的問題：當node數發生變化時，如何保證盡量少引起遷移呢？即當增加或者刪除節點時，對於大多數item，保證原來分配到的某個node，現在仍然應該分配到那個node，將數據遷移量的降到最低。

一致性Hash演算法

關於一致性Hash演算法，首先介紹這個演算法的具體原理：

先構造一個長度為2^32的整數環（這個環被稱為一致性Hash環），根據節點名稱的Hash值（其分布為[0, 2^32-1]）將伺服器節點放置在這個Hash環上（例如下圖的abcd），然後根據數據的Key值計算得到其Hash值（其分布也為[0, 2^32-1]），接著在Hash環上順時針查找距離這個Key值的Hash值最近的伺服器節點，完成Key到伺服器的映射查找。

這種演算法解決了普通餘數Hash演算法伸縮性差的問題，可以保證在上線、下線伺服器的情況下盡量有多的請求命中原來路由到的伺服器。

當然，萬事不可能十全十美，一致性Hash演算法比普通的餘數Hash演算法更具有伸縮性，但是同時其演算法實現也更為複雜。

帶虛擬節點的一致性Hash演算法

使用一致性Hash演算法，儘管增強了系統的伸縮性，但是也有可能導致負載分布不均勻，解決辦法就是使用虛擬節點代替真實節點。

比如說有Hash環上有A、B、C三個伺服器節點，分別有100個請求會被路由到相應伺服器上。現在在A與B之間增加了一個節點D，這導致了原來會路由到B上的部分節點被路由到了D上，這樣A、C上被路由到的請求明顯多於B、D上的，原來三個伺服器節點上均衡的負載被打破了。某種程度上來說，這失去了負載均衡的意義，因為負載均衡的目的本身就是為了使得目標伺服器均分所有的請求。

解決這個問題的辦法是引入虛擬節點，其工作原理是：將一個物理節點拆分為多個虛擬節點，並且同一個物理節點的虛擬節點盡量均勻分布在Hash環上。採取這樣的方式，就可以有效地解決增加或減少節點時候的負載不均衡的問題。

總結

在分散式系統中一致性hash起著不可忽略的地位，無論是分散式快取，還是分散式Rpc框架的負載均衡策略都有所使用。歡迎大家和小強一起討論分散式相關的知識。