導讀
今天在看Redis時看到其擴容，縮容機制用的是一緻性Hash算法，今天就來談論下一緻性Hash，本文借鑒了小林coding公衆号的部分了解與解讀。大家如果想要深入了解，關注其公衆号。
一緻性Hash解決的問題
大多數網站背後肯定不是隻有一台伺服器提供服務，因為單機的并發量和資料量都是有限的，是以都會用多台伺服器構成叢集來對外提供服務。但是問題來了，現在有那麼多個節點，要如何配置設定用戶端的請求呢？
考慮到每個節點的硬體配置有所差別，我們可以引入權重值，将硬體配置更好的節點的權重值設高，然後根據各個節點的權重值，按照一定比重配置設定在不同的節點上，讓硬體配置更好的節點承擔更多的請求，這種算法叫做權重輪詢。
權重輪詢算法使用場景是建立在每個節點存儲的資料都是相同的前提。是以，每次讀資料的請求，通路任意一個節點都能得到結果。
但是，權重輪詢算法是無法應對「分布式系統」的，因為分布式系統中，每個節點存儲的資料是不同的。
當我們想提高系統的容量，就會将資料水準切分到不同的節點來存儲，也就是将資料分布到了不同的節點。比如一個分布式 KV（key-valu） 緩存系統，某個 key 應該到哪個或者哪些節點上獲得，應該是确定的，不是說任意通路一個節點都可以得到緩存結果的。
可能大家很快就想到了：雜湊演算法。因為對同一個關鍵字進行哈希計算，每次計算都是相同的值，這樣就可以将某個 key 确定到一個節點了，可以滿足分布式系統的負載均衡需求。
雜湊演算法最簡單的做法就是進行取模運算，比如分布式系統中有 3 個節點，基于 hash(key) % 3 公式對資料進行了映射。
但是有一個很緻命的問題，如果節點數量發生了變化，也就是在對系統做擴容或者縮容時，必須遷移改變了映射關系的資料，否則會出現查詢不到資料的問題。
這時一緻性雜湊演算法來了。一緻性雜湊演算法就很好地解決了分布式系統在擴容或者縮容時，發生過多的資料遷移的問題。
一緻性Hash
一緻雜湊演算法也用了取模運算，但與雜湊演算法不同的是，雜湊演算法是對節點的數量進行取模運算，而一緻雜湊演算法是對 2^32 進行取模運算，是一個固定的值。
我們可以把一緻雜湊演算法是對 2^32 進行取模運算的結果值組織成一個圓環，就像鐘表一樣，鐘表的圓可以了解成由 60 個點組成的圓，而此處我們把這個圓想象成由 2^32 個點組成的圓，這個圓環被稱為哈希環，如下圖：
一緻性哈希要進行兩步哈希：
- 第一步：對存儲節點進行哈希計算，也就是對存儲節點做哈希映射，比如根據節點的 IP 位址進行哈希；
- 第二步：當對資料進行存儲或通路時，對資料進行哈希映射；
是以，一緻性哈希是指将「存儲節點」和「資料」都映射到一個首尾相連的哈希環上。
問題來了，對「資料」進行哈希映射得到一個結果要怎麼找到存儲該資料的節點呢？
答案是，映射的結果值往順時針的方向的找到第一個節點，就是存儲該資料的節點。
舉個例子，有 3 個節點經過哈希計算，映射到了如下圖的位置：
接着，對要查詢的 key-01 進行哈希計算，确定此 key-01 映射在哈希環的位置，然後從這個位置往順時針的方向找到第一個節點，就是存儲該 key-01 資料的節點。
比如，下圖中的 key-01 映射的位置，往順時針的方向找到第一個節點就是節點 A。
是以，當需要對指定 key 的值進行讀寫的時候，要通過下面 2 步進行尋址：
- 首先，對 key 進行哈希計算，确定此 key 在環上的位置；
- 然後，從這個位置沿着順時針方向走，遇到的第一節點就是存儲 key 的節點。
知道了一緻哈希尋址的方式，我們來看看，如果增加一個節點或者減少一個節點會發生大量的資料遷移嗎？
假設節點數量從 3 增加到了 4，新的節點 D 經過哈希計算後映射到了下圖中的位置：
你可以看到，key-01、key-03 都不受影響，隻有 key-02 需要被遷移節點 D。
假設節點數量從 3 減少到了 2，比如将節點 A 移除：
你可以看到，key-02 和 key-03 不會受到影響，隻有 key-01 需要被遷移節點 B。
是以，在一緻雜湊演算法中，如果增加或者移除一個節點，僅影響該節點在哈希環上順時針相鄰的後繼節點，其它資料也不會受到影響。
上面這些圖中 3 個節點映射在哈希環還是比較分散的，是以看起來請求都會「均衡」到每個節點。
但是一緻性雜湊演算法并不保證節點能夠在哈希環上分布均勻，這樣就會帶來一個問題，會有大量的請求集中在一個節點上。
比如，下圖中 3 個節點的映射位置都在哈希環的右半邊：
這時候有一半以上的資料的尋址都會找節點 A，也就是通路請求主要集中的節點 A 上，這肯定不行的呀，說好的負載均衡呢，這種情況一點都不均衡。
另外，在這種節點分布不均勻的情況下，進行容災與擴容時，哈希環上的相鄰節點容易受到過大影響，容易發生雪崩式的連鎖反應。
比如，上圖中如果節點 A 被移除了，當節點 A 當機後，根據一緻性雜湊演算法的規則，其上資料應該全部遷移到相鄰的節點 B 上，這樣，節點 B 的資料量、通路量都會迅速增加很多倍，一旦新增的壓力超過了節點 B 的處理能力上限，就會導緻節點 B 崩潰，進而形成雪崩式的連鎖反應。
是以，一緻性雜湊演算法雖然減少了資料遷移量，但是存在節點分布不均勻的問題。
通過虛拟節點提高均衡度
要想解決節點能在哈希環上配置設定不均勻的問題，就是要有大量的節點，節點數越多，哈希環上的節點分布的就越均勻。
但問題是，實際中我們沒有那麼多節點。是以這個時候我們就加入虛拟節點，也就是對一個真實節點做多個副本。
具體做法是，不再将真實節點映射到哈希環上，而是将虛拟節點映射到哈希環上，并将虛拟節點映射到實際節點，是以這裡有「兩層」映射關系。
比如對每個節點分别設定 3 個虛拟節點：
- 對節點 A 加上編号來作為虛拟節點：A-01、A-02、A-03
- 對節點 B 加上編号來作為虛拟節點：B-01、B-02、B-03
- 對節點 C 加上編号來作為虛拟節點：C-01、C-02、C-03
引入虛拟節點後，原本哈希環上隻有 3 個節點的情況，就會變成有 9 個虛拟節點映射到哈希環上，哈希環上的節點數量多了 3 倍
你可以看到，節點數量多了後，節點在哈希環上的分布就相對均勻了。這時候，如果有通路請求尋址到「A-01」這個虛拟節點，接着再通過「A-01」虛拟節點找到真實節點 A，這樣請求就能通路到真實節點 A 了。
上面為了友善了解，每個真實節點僅包含 3 個虛拟節點，這樣能起到的均衡效果其實很有限。而在實際的工程中，虛拟節點的數量會大很多，比如 Nginx 的一緻性雜湊演算法，每個權重為 1 的真實節點就含有160 個虛拟節點。
另外，虛拟節點除了會提高節點的均衡度，還會提高系統的穩定性。當節點變化時，會有不同的節點共同分擔系統的變化，是以穩定性更高。
比如，當某個節點被移除時，對應該節點的多個虛拟節點均會移除，而這些虛拟節點按順時針方向的下一個虛拟節點，可能會對應不同的真實節點，即這些不同的真實節點共同分擔了節點變化導緻的壓力。
而且，有了虛拟節點後，還可以為硬體配置更好的節點增權重重，比如對權重更高的節點增加更多的虛拟機節點即可。
是以，帶虛拟節點的一緻性哈希方法不僅适合硬體配置不同的節點的場景，而且适合節點規模會發生變化的場景。
總結
不同的負載均衡算法适用的業務場景也不同的。
輪訓這類的政策隻能适用與每個節點的資料都是相同的場景，通路任意節點都能請求到資料。但是不适用分布式系統，因為分布式系統意味着資料水準切分到了不同的節點上，通路資料的時候，一定要尋址存儲該資料的節點。
雜湊演算法雖然能建立資料和節點的映射關系，但是每次在節點數量發生變化的時候，最壞情況下所有資料都需要遷移，這樣太麻煩了，是以不适用節點數量變化的場景。
為了減少遷移的資料量，就出現了一緻性雜湊演算法。
一緻性哈希是指将**「存儲節點」和「資料」都映射到一個首尾相連的哈希環上**，如果增加或者移除一個節點，僅影響該節點在哈希環上順時針相鄰的後繼節點，其它資料也不會受到影響。
但是一緻性雜湊演算法不能夠均勻的分布節點，會出現大量請求都集中在一個節點的情況，在這種情況下進行容災與擴容時，容易出現雪崩的連鎖反應。
為了解決一緻性雜湊演算法不能夠均勻的分布節點的問題，就需要引入虛拟節點，對一個真實節點做多個副本。不再将真實節點映射到哈希環上，而是将虛拟節點映射到哈希環上，并将虛拟節點映射到實際節點，是以這裡有「兩層」映射關系。
引入虛拟節點後，可以會提高節點的均衡度，還會提高系統的穩定性。是以，帶虛拟節點的一緻性哈希方法不僅适合硬體配置不同的節點的場景，而且适合節點規模會發生變化的場景。