在了解一致性哈希算法之前，最好先了解一下緩存中的一個應(yīng)用場景，了解了這個應(yīng)用場景之后，再來理解一致性哈希算法，就容易多了，也更能體現(xiàn)出一致性哈希算法的優(yōu)點，那么，我們先來描述一下這個經(jīng)典的分布式緩存的應(yīng)用場景。
一、場景描述
假設(shè)，我們有三臺緩存服務(wù)器，用于緩存圖片，分別為 0 號、1 號、2 號，現(xiàn)在，有 3 萬張圖片需要緩存，我們希望這些圖片被均勻的緩存到這3臺服務(wù)器上，以便它們能夠分?jǐn)偩彺娴膲毫?。也就是說，我們希望每臺服務(wù)器能夠緩存 1 萬張左右的圖片，那么，我們應(yīng)該怎樣做呢？
如果我們沒有任何規(guī)律的將 3 萬張圖片平均的緩存在 3 臺服務(wù)器上，可以滿足我們的要求嗎？可以！但是如果這樣做，當(dāng)我們需要訪問某個緩存項時，則需要遍歷3臺緩存服務(wù)器，從 3 萬個緩存項中找到我們需要訪問的緩存，遍歷的過程效率太低，時間太長，當(dāng)我們找到需要訪問的緩存項時，時長可能是不能被接受的，也就失去了緩存的意義，緩存的目的就是提高速度，改善用戶體驗，減輕后端服務(wù)器壓力，如果每次訪問一個緩存項都需要遍歷所有緩存服務(wù)器的所有緩存項，想想就覺得很累，那么，我們該怎么辦呢？
原始的做法是對緩存項的鍵進(jìn)行哈希，將 Hash 后的結(jié)果對緩存服務(wù)器的數(shù)量進(jìn)行取模操作，通過取模后的結(jié)果，決定緩存項將會緩存在哪一臺服務(wù)器上。
舉個例子，假設(shè)我們使用圖片名稱作為訪問圖片的 Key，假設(shè)圖片名稱是不重復(fù)的，那么，我們可以使用 hash(圖片名稱) % N，計算出圖片應(yīng)該存放在哪臺服務(wù)器上。
如果我們有 3 臺服務(wù)器，使用哈希后的結(jié)果對 3 求余，那么余數(shù)一定是 0、1、2，正好與我們之前的服務(wù)器編號相同，如果求余的結(jié)果為 0， 就把當(dāng)前名稱對應(yīng)的圖片緩存在 0 號服務(wù)器上，如果余數(shù)為 1，就緩存在 1 號服務(wù)器上，以此類推。
當(dāng)我們訪問任意一個圖片的時候，只要再次對圖片名稱進(jìn)行上述運(yùn)算，即可得出對應(yīng)的圖片應(yīng)該存放在哪一臺緩存服務(wù)器上。
但是，使用上述 Hash 算法進(jìn)行緩存時，會出現(xiàn)一些缺陷，試想一下，如果 3 臺緩存服務(wù)器已經(jīng)不能滿足我們的緩存需求，那么我們應(yīng)該怎么做呢？
很簡單，多增加兩臺緩存服務(wù)器不就行了，假設(shè)，我們增加了一臺緩存服務(wù)器，那么緩存服務(wù)器的數(shù)量就由 3 臺變成了 4 臺，此時，如果仍然使用上述方法對同一張圖片進(jìn)行緩存，那么這張圖片所在的服務(wù)器編號必定與原來 3 臺服務(wù)器時所在的服務(wù)器編號不同，因為除數(shù)由 3 變?yōu)榱?4，并且，之前緩存的圖片也需要全部調(diào)整，這種情況帶來的結(jié)果就是當(dāng)服務(wù)器數(shù)量變動時，全部緩存圖片的位置都要發(fā)生改變。
我們來回顧一下使用上述算法會出現(xiàn)的問題。
問題1：當(dāng)緩存服務(wù)器數(shù)量發(fā)生變化時，會引起緩存的雪崩，可能會引起整體系統(tǒng)壓力過大而崩潰（大量緩存同一時間失效）。
問題2：當(dāng)緩存服務(wù)器數(shù)量發(fā)生變化時，幾乎所有緩存的位置都會發(fā)生改變，怎樣才能盡量減少受影響的緩存呢？
為了解決這些問題，一致性哈希算法誕生了。
二、一致性哈希算法的基本概念
其實，一致性哈希算法也是使用取模的方法，只是，剛才描述的取模法是對服務(wù)器的數(shù)量進(jìn)行取模，而一致性哈希算法是對 2^32 取模，什么意思呢？我們慢慢聊。
首先，我們把 232 想象成一個圓，就像鐘表一樣，鐘表的圓可以理解成由 60 個點組成的圓，而此處我們把這個圓想象成由 232 個點組成的圓，示意圖如下：
圓環(huán)的正上方的點代表 0，0 點右側(cè)的第一個點代表 1，以此類推，2、3、4、5、6……直到 232-1，也就是說 0 點左側(cè)的第一個點代表 232-1，我們把這個由 232 個點組成的圓環(huán)稱為 Hash 環(huán)。
那么，一致性哈希算法與上圖中的圓環(huán)有什么關(guān)系呢？
假設(shè)我們有 3 臺緩存服務(wù)器，服務(wù)器 A、服務(wù)器 B、服務(wù)器 C，那么，這三臺服務(wù)器肯定有自己的 IP 地址，我們使用它們各自的 IP 地址進(jìn)行 Hash 計算，使用 Hash 后的結(jié)果對 232 取模，即：hash(A的IP地址) % 2^32。
通過上述公式算出的結(jié)果一定是一個 0 到 232-1 之間的一個整數(shù)，我們就用算出的這個整數(shù)，代表服務(wù)器 A，并且上圖中的 Hash 環(huán)上必定有一個點與這個整數(shù)對應(yīng)，那么，服務(wù)器 A 就可以映射到這個環(huán)上。
同理，服務(wù)器 B 與服務(wù)器 C 也可以通過相同的方法映射到上圖中的 Hash 環(huán)中：
hash(B的IP地址) % 2^32
hash(C的IP地址) % 2^32
示意圖如下，當(dāng)然，這是理想的情況：
到目前為止，我們已經(jīng)把服務(wù)器與 Hash 環(huán)聯(lián)系在了一起，那么使用同樣的方法，我們也可以將需要緩存的圖片映射到 Hash 環(huán)上。
假設(shè)，我們?nèi)匀皇褂脠D片的名稱作為找到圖片的 Key，那么我們使用
hash(圖片名稱Key) % 2^32 公式可以將圖片映射到上圖中的hash環(huán)上。
現(xiàn)在服務(wù)器與圖片都被映射到了 Hash 環(huán)上，那么這個圖片到底應(yīng)該被緩存到哪一臺服務(wù)器上呢？
圖片將會被緩存到服務(wù)器 A 上，為什么呢？因為從圖片的位置開始，沿順時針方向遇到的第一個服務(wù)器就是 A 服務(wù)器，所以，上圖中的圖片將會被緩存到服務(wù)器 A 上，如下圖所示，圖中橘黃色代表需緩存的圖片：
一致性哈希算法就是通過這種方法，判斷一個對象應(yīng)該被緩存到哪臺服務(wù)器上的，將緩存服務(wù)器與被緩存對象都映射到 Hash 環(huán)上以后，從被緩存對象的位置出發(fā)，沿順時針方向遇到的第一個服務(wù)器，就是當(dāng)前對象將要緩存于的服務(wù)器。
由于被緩存對象與服務(wù)器 Hash 后的值是固定的，所以，在服務(wù)器不變的情況下，一張圖片必定會被緩存到固定的服務(wù)器上，那么，當(dāng)下次想要訪問這張圖片時，只要再次使用相同的算法進(jìn)行計算，即可算出這個圖片被緩存在哪個服務(wù)器上，直接去對應(yīng)的服務(wù)器查找對應(yīng)的圖片即可。
剛才的示例只使用了一張圖片進(jìn)行演示，假設(shè)有四張圖片需要緩存，示意圖如下：
1 號、2 號圖片將會被緩存到服務(wù)器 A 上，3 號圖片將會被緩存到服務(wù)器 B 上，4 號圖片將會被緩存到服務(wù)器 C 上。
三、一致性哈希算法的優(yōu)點
經(jīng)過上述描述，應(yīng)該已經(jīng)明白了一致性哈希算法的原理了，但是話說回來，一致性哈希算法能夠解決之前出現(xiàn)的問題嗎？
之前說過，如果簡單的對服務(wù)器數(shù)量進(jìn)行取模，那么當(dāng)服務(wù)器數(shù)量發(fā)生變化時，所有數(shù)據(jù)全部需要調(diào)整。那么使用一致性哈希算法，能夠避免這個問題嗎？
在服務(wù)器 B 未移除時，圖片 3 應(yīng)該被緩存到服務(wù)器 B 中，假設(shè)，服務(wù)器 B 出現(xiàn)了故障，我們現(xiàn)在需要將服務(wù)器 B 移除，那么，我們將上圖中的服務(wù)器 B 從 Hash 環(huán)上移除。
可是當(dāng)服務(wù)器 B 移除以后，按照之前描述的一致性哈希算法的規(guī)則，圖片 3 應(yīng)該被緩存到服務(wù)器 C 中，因為從圖片 3 的位置出發(fā)，沿順時針方向遇到的第一個緩存服務(wù)器節(jié)點就是服務(wù)器 C，也就是說，如果服務(wù)器 B 出現(xiàn)故障被移除時，圖片 3 的緩存位置會發(fā)生改變：
但是，圖片 4 仍然會被緩存到服務(wù)器 C 中，圖片 1 與圖片 2 仍然會被緩存到服務(wù)器 A 中，這與服務(wù)器 B 移除之前并沒有任何區(qū)別，這就是一致性哈希算法的優(yōu)點。
如果使用之前的 Hash 算法，服務(wù)器數(shù)量發(fā)生改變時，所有服務(wù)器的所有緩存在同一時間失效了。而使用一致性哈希算法時，并不是所有緩存都會失效，而是只有部分緩存會失效。在這個例子中就只會影響服務(wù)器 B 至服務(wù)器 A 之間的數(shù)據(jù)，盡可能的提供有損的服務(wù)。
這就是一致性哈希算法所體現(xiàn)出的優(yōu)點。
四、Hash 環(huán)偏斜
在介紹一致性哈希的概念時，我們理想化的將 3 臺服務(wù)器均勻的映射到了 Hash 環(huán)上。但實際我們想象的與實際情況往往不一樣。在實際的映射中，服務(wù)器可能會被映射成如下模樣：
如果服務(wù)器被映射成上圖中的模樣，那么被緩存的對象很有可能大部分集中緩存在某一臺服務(wù)器上，如下圖所示：
圖中，1號、2號、3號、4號、6號圖片均被緩存在了服務(wù)器 A 上，只有 5 號圖片被緩存在了服務(wù)器 B 上，服務(wù)器 C 上甚至沒有緩存任何圖片，如果出現(xiàn)上圖中的情況，A、B、C 三臺服務(wù)器并沒有被合理的平均的充分利用，緩存分布的極度不均勻。并且，如果此時服務(wù)器 A 出現(xiàn)故障，那么失效緩存的數(shù)量也將達(dá)到最大值，在極端情況下，仍然有可能引起系統(tǒng)的崩潰，上圖中的情況則被稱之為 Hash 環(huán)的偏斜，那么，我們應(yīng)該怎樣防止 Hash 環(huán)的偏斜呢？
一致性 Hash 算法中使用"虛擬節(jié)點"解決了這個問題。
六、虛擬節(jié)點
由于我們只有 3 臺服務(wù)器，當(dāng)我們把服務(wù)器映射到 Hash 環(huán)上的時候，很有可能出現(xiàn) Hash 環(huán)偏斜的情況，當(dāng) Hash 環(huán)偏斜以后，緩存往往會極度不均衡的分布在各服務(wù)器上。如果想要均衡的將緩存分布到3臺服務(wù)器上，最好能讓這 3 臺服務(wù)器盡量多的、均勻的出現(xiàn)在 Hash 環(huán)上，但是，真實的服務(wù)器資源只有 3 臺，我們怎樣憑空的讓它們多起來呢，沒錯，就是憑空的讓服務(wù)器節(jié)點多起來。
既然沒有多余的真正的物理服務(wù)器節(jié)點，我們就只能將現(xiàn)有的物理節(jié)點通過虛擬的方法復(fù)制出來，這些由實際節(jié)點虛擬復(fù)制而來的節(jié)點被稱為“虛擬節(jié)點”。加入虛擬節(jié)點以后的hash環(huán)如下：
“虛擬節(jié)點”是實際節(jié)點在 Hash 環(huán)上的復(fù)制品,一個實際節(jié)點可以對應(yīng)多個虛擬節(jié)點。
從上圖可以看出，A、B、C 三臺服務(wù)器分別虛擬出了一個虛擬節(jié)點，當(dāng)然，如果你需要，也可以虛擬出更多的虛擬節(jié)點。引入虛擬節(jié)點的概念后，緩存的分布就均衡多了，如果你還不放心，可以虛擬出更多的虛擬節(jié)點，以便減小 hash 環(huán)偏斜所帶來的影響，虛擬節(jié)點越多，hash 環(huán)上的節(jié)點就越多，緩存被均勻分布的概率就越大。
以上內(nèi)容參考：http://www.zsythink.net/archives/1182
