以下内容轉載自：
朱雙印部落格| 白話解析：一緻性雜湊演算法 consistent hashing
原文位址：http://www.zsythink.net/archives/1182
在了解一緻性雜湊演算法之前，最好先了解一下緩存中的一個應用場景，了解了這個應用場景之後，再來了解一緻性雜湊演算法，就容易多了，也更能展現出一緻性雜湊演算法的優點，那麼，我們先來描述一下這個經典的分布式緩存的應用場景。
場景描述
假設，我們有三台緩存伺服器，用于緩存圖檔，我們為這三台緩存伺服器編号為0号、1号、2号，現在，有3萬張圖檔需要緩存，我們希望這些圖檔被均勻的緩存到這3台伺服器上，以便它們能夠分攤緩存的壓力。也就是說，我們希望每台伺服器能夠緩存1萬張左右的圖檔，那麼，我們應該怎樣做呢？如果我們沒有任何規律的将3萬張圖檔平均的緩存在3台伺服器上，可以滿足我們的要求嗎？可以！但是如果這樣做，當我們需要通路某個緩存項時，則需要周遊3台緩存伺服器，從3萬個緩存項中找到我們需要通路的緩存，周遊的過程效率太低，時間太長，當我們找到需要通路的緩存項時，時長可能是不能被接收的，也就失去了緩存的意義，緩存的目的就是提高速度，改善使用者體驗，減輕後端伺服器壓力，如果每次通路一個緩存項都需要周遊所有緩存伺服器的所有緩存項，想想就覺得很累，那麼，我們該怎麼辦呢？原始的做法是對緩存項的鍵進行哈希，将hash後的結果對緩存伺服器的數量進行取模操作，通過取模後的結果，決定緩存項将會緩存在哪一台伺服器上，這樣說可能不太容易了解，我們舉例說明，仍然以剛才描述的場景為例，假設我們使用圖檔名稱作為通路圖檔的key，假設圖檔名稱是不重複的，那麼，我們可以使用如下公式，計算出圖檔應該存放在哪台伺服器上。
hash（圖檔名稱）% N
因為圖檔的名稱是不重複的，是以，當我們對同一個圖檔名稱做相同的哈希計算時，得出的結果應該是不變的，如果我們有3台伺服器，使用哈希後的結果對3求餘，那麼餘數一定是0、1或者2，沒錯，正好與我們之前的伺服器編号相同，如果求餘的結果為0， 我們就把目前圖檔名稱對應的圖檔緩存在0号伺服器上，如果餘數為1，就把目前圖檔名對應的圖檔緩存在1号伺服器上，如果餘數為2，同理，那麼，當我們通路任意一個圖檔的時候，隻要再次對圖檔名稱進行上述運算，即可得出對應的圖檔應該存放在哪一台緩存伺服器上，我們隻要在這一台伺服器上查找圖檔即可，如果圖檔在對應的伺服器上不存在，則證明對應的圖檔沒有被緩存，也不用再去周遊其他緩存伺服器了，通過這樣的方法，即可将3萬張圖檔随機的分布到3台緩存伺服器上了，而且下次通路某張圖檔時，直接能夠判斷出該圖檔應該存在于哪台緩存伺服器上，這樣就能滿足我們的需求了，我們暫時稱上述算法為HASH算法或者取模算法，取模算法的過程可以用下圖表示。
但是，使用上述HASH算法進行緩存時，會出現一些缺陷，試想一下，如果3台緩存伺服器已經不能滿足我們的緩存需求，那麼我們應該怎麼做呢？沒錯，很簡單，多增加兩台緩存伺服器不就行了，假設，我們增加了一台緩存伺服器，那麼緩存伺服器的數量就由3台變成了4台，此時，如果仍然使用上述方法對同一張圖檔進行緩存，那麼這張圖檔所在的伺服器編号必定與原來3台伺服器時所在的伺服器編号不同，因為除數由3變為了4，被除數不變的情況下，餘數肯定不同，這種情況帶來的結果就是當伺服器數量變動時，所有緩存的位置都要發生改變，換句話說，當伺服器數量發生改變時，所有緩存在一定時間内是失效的，當應用無法從緩存中擷取資料時，則會向後端伺服器請求資料，同理，假設3台緩存中突然有一台緩存伺服器出現了故障，無法進行緩存，那麼我們則需要将故障機器移除，但是如果移除了一台緩存伺服器，那麼緩存伺服器數量從3台變為2台，如果想要通路一張圖檔，這張圖檔的緩存位置必定會發生改變，以前緩存的圖檔也會失去緩存的作用與意義，由于大量緩存在同一時間失效，造成了緩存的雪崩，此時前端緩存已經無法起到承擔部分壓力的作用，後端伺服器将會承受巨大的壓力，整個系統很有可能被壓垮，是以，我們應該想辦法不讓這種情況發生，但是由于上述HASH算法本身的緣故，使用取模法進行緩存時，這種情況是無法避免的，為了解決這些問題，一緻性雜湊演算法誕生了。
我們來回顧一下使用上述算法會出現的問題。
問題1：當緩存伺服器數量發生變化時，會引起緩存的雪崩，可能會引起整體系統壓力過大而崩潰（大量緩存同一時間失效）。
問題2：當緩存伺服器數量發生變化時，幾乎所有緩存的位置都會發生改變，怎樣才能盡量減少受影響的緩存呢？
其實，上面兩個問題是一個問題，那麼，一緻性雜湊演算法能夠解決上述問題嗎？
我們現在就來了解一下一緻性雜湊演算法。
一緻性雜湊演算法的基本概念
其實，一緻性雜湊演算法也是使用取模的方法，隻是，剛才描述的取模法是對伺服器的數量進行取模，而一緻性雜湊演算法是對2^32取模，什麼意思呢？我們慢慢聊。
首先，我們把二的三十二次方想象成一個圓，就像鐘表一樣，鐘表的圓可以了解成由60個點組成的圓，而此處我們把這個圓想象成由2^32個點組成的圓，示意圖如下：
圓環的正上方的點代表0，0點右側的第一個點代表1，以此類推，2、3、4、5、6……直到2^32-1,也就是說0點左側的第一個點代表2^32-1
我們把這個由2的32次方個點組成的圓環稱為hash環。
那麼，一緻性雜湊演算法與上圖中的圓環有什麼關系呢？我們繼續聊，仍然以之前描述的場景為例，假設我們有3台緩存伺服器，伺服器A、伺服器B、伺服器C，那麼，在生産環境中，這三台伺服器肯定有自己的IP位址，我們使用它們各自的IP位址進行哈希計算，使用哈希後的結果對2^32取模，可以使用如下公式示意。
hash（伺服器A的IP位址） % 2^32
通過上述公式算出的結果一定是一個0到2^32-1之間的一個整數，我們就用算出的這個整數，代表伺服器A，既然這個整數肯定處于0到2^32-1之間，那麼，上圖中的hash環上必定有一個點與這個整數對應，而我們剛才已經說明，使用這個整數代表伺服器A，那麼，伺服器A就可以映射到這個環上，用下圖示意
同理，伺服器B與伺服器C也可以通過相同的方法映射到上圖中的hash環中
hash（伺服器B的IP位址） % 2^32
hash（伺服器C的IP位址） % 2^32
通過上述方法，可以将伺服器B與伺服器C映射到上圖中的hash環上，示意圖如下
假設3台伺服器映射到hash環上以後如上圖所示（當然，這是理想的情況，我們慢慢聊）。
好了，到目前為止，我們已經把緩存伺服器與hash環聯系在了一起，我們通過上述方法，把緩存伺服器映射到了hash環上，那麼使用同樣的方法，我們也可以将需要緩存的對象映射到hash環上。
假設，我們需要使用緩存伺服器緩存圖檔，而且我們仍然使用圖檔的名稱作為找到圖檔的key，那麼我們使用如下公式可以将圖檔映射到上圖中的hash環上。
hash（圖檔名稱） % 2^32
映射後的示意圖如下，下圖中的橘黃色圓形表示圖檔
好了，現在伺服器與圖檔都被映射到了hash環上，那麼上圖中的這個圖檔到底應該被緩存到哪一台伺服器上呢？上圖中的圖檔将會被緩存到伺服器A上，為什麼呢？因為從圖檔的位置開始，沿順時針方向遇到的第一個伺服器就是A伺服器，是以，上圖中的圖檔将會被緩存到伺服器A上，如下圖所示。
沒錯，一緻性雜湊演算法就是通過這種方法，判斷一個對象應該被緩存到哪台伺服器上的，将緩存伺服器與被緩存對象都映射到hash環上以後，從被緩存對象的位置出發，沿順時針方向遇到的第一個伺服器，就是目前對象将要緩存于的伺服器，由于被緩存對象與伺服器hash後的值是固定的，是以，在伺服器不變的情況下，一張圖檔必定會被緩存到固定的伺服器上，那麼，當下次想要通路這張圖檔時，隻要再次使用相同的算法進行計算，即可算出這個圖檔被緩存在哪個伺服器上，直接去對應的伺服器查找對應的圖檔即可。
剛才的示例隻使用了一張圖檔進行示範，假設有四張圖檔需要緩存，示意圖如下
1号、2号圖檔将會被緩存到伺服器A上，3号圖檔将會被緩存到伺服器B上，4号圖檔将會被緩存到伺服器C上。
一緻性雜湊演算法的優點
經過上述描述，我想兄弟你應該已經明白了一緻性雜湊演算法的原理了，但是話說回來，一緻性雜湊演算法能夠解決之前出現的問題嗎，我們說過，如果簡單的對伺服器數量進行取模，那麼當伺服器數量發生變化時，會産生緩存的雪崩，進而很有可能導緻系統崩潰，那麼使用一緻性雜湊演算法，能夠避免這個問題嗎？我們來模拟一遍，即可得到答案。
假設，伺服器B出現了故障，我們現在需要将伺服器B移除，那麼，我們将上圖中的伺服器B從hash環上移除即可，移除伺服器B以後示意圖如下。
在伺服器B未移除時，圖檔3應該被緩存到伺服器B中，可是當伺服器B移除以後，按照之前描述的一緻性雜湊演算法的規則，圖檔3應該被緩存到伺服器C中，因為從圖檔3的位置出發，沿順時針方向遇到的第一個緩存伺服器節點就是伺服器C，也就是說，如果伺服器B出現故障被移除時，圖檔3的緩存位置會發生改變
但是，圖檔4仍然會被緩存到伺服器C中，圖檔1與圖檔2仍然會被緩存到伺服器A中，這與伺服器B移除之前并沒有任何差別，這就是一緻性雜湊演算法的優點，如果使用之前的hash算法，伺服器數量發生改變時，所有伺服器的所有緩存在同一時間失效了，而使用一緻性雜湊演算法時，伺服器的數量如果發生改變，并不是所有緩存都會失效，而是隻有部分緩存會失效，前端的緩存仍然能分擔整個系統的壓力，而不至于所有壓力都在同一時間集中到後端伺服器上。
這就是一緻性雜湊演算法所展現出的優點。
hash環的偏斜
在介紹一緻性哈希的概念時，我們理想化的将3台伺服器均勻的映射到了hash環上，如下圖所示
但是，理想很豐滿，現實很骨感，我們想象的與實際情況往往不一樣。
在實際的映射中，伺服器可能會被映射成如下模樣。
聰明如你一定想到了，如果伺服器被映射成上圖中的模樣，那麼被緩存的對象很有可能大部分集中緩存在某一台伺服器上，如下圖所示。
上圖中，1号、2号、3号、4号、6号圖檔均被緩存在了伺服器A上，隻有5号圖檔被緩存在了伺服器B上，伺服器C上甚至沒有緩存任何圖檔，如果出現上圖中的情況，A、B、C三台伺服器并沒有被合理的平均的充分利用，緩存分布的極度不均勻，而且，如果此時伺服器A出現故障，那麼失效緩存的數量也将達到最大值，在極端情況下，仍然有可能引起系統的崩潰，上圖中的情況則被稱之為hash環的偏斜，那麼，我們應該怎樣防止hash環的偏斜呢？一緻性hash算法中使用"虛拟節點"解決了這個問題，我們繼續聊。
虛拟節點
話接上文，由于我們隻有3台伺服器，當我們把伺服器映射到hash環上的時候，很有可能出現hash環偏斜的情況，當hash環偏斜以後，緩存往往會極度不均衡的分布在各伺服器上，聰明如你一定已經想到了，如果想要均衡的将緩存分布到3台伺服器上，最好能讓這3台伺服器盡量多的、均勻的出現在hash環上，但是，真實的伺服器資源隻有3台，我們怎樣憑空的讓它們多起來呢，沒錯，就是憑空的讓伺服器節點多起來，既然沒有多餘的真正的實體伺服器節點，我們就隻能将現有的實體節點通過虛拟的方法複制出來，這些由實際節點虛拟複制而來的節點被稱為"虛拟節點"。加入虛拟節點以後的hash環如下。
"虛拟節點"是"實際節點"（實際的實體伺服器）在hash環上的複制品,一個實際節點可以對應多個虛拟節點。
從上圖可以看出，A、B、C三台伺服器分别虛拟出了一個虛拟節點，當然，如果你需要，也可以虛拟出更多的虛拟節點。引入虛拟節點的概念後，緩存的分布就均衡多了，上圖中，1号、3号圖檔被緩存在伺服器A中，5号、4号圖檔被緩存在伺服器B中，6号、2号圖檔被緩存在伺服器C中，如果你還不放心，可以虛拟出更多的虛拟節點，以便減小hash環偏斜所帶來的影響，虛拟節點越多，hash環上的節點就越多，緩存被均勻分布的機率就越大。
好了，一緻性雜湊演算法的原理就總結到這裡，如有錯誤，歡迎賜教，如需轉載，請聯系作者。
原文連結：白話解析：一緻性雜湊演算法 consistent hashing