轉(zhuǎn)載自： http://hi.baidu.com/fdwm_lx/blog/item/fe46344e11517705b3de054c.html

在大型web應(yīng)用中，緩存可算是當今的一個標準開發(fā)配置了。在大 規(guī)模的緩存應(yīng)用中，應(yīng)運而生了分布式緩存系統(tǒng)。分布式緩存系統(tǒng)的基本原理，大家也有所耳聞。key-value如何均勻的分散到集群中？說到此，最常規(guī)的 方式莫過于hash取模的方式。比如集群中可用機器適量為N，那么key值為K的的數(shù)據(jù)請求很簡單的應(yīng)該路由到hash(K) mod N對應(yīng)的機器。的確，這種結(jié)構(gòu)是簡單的，也是實用的。但是在一些高速發(fā)展的web系統(tǒng)中，這樣的解決方案仍有些缺陷。隨著系統(tǒng)訪問壓力的增長，緩存系統(tǒng)不 得不通過增加機器節(jié)點的方式提高集群的相應(yīng)速度和數(shù)據(jù)承載量。增加機器意味著按照hash取模的方式，在增加機器節(jié)點的這一時刻，大量的緩存命不中，緩存 數(shù)據(jù)需要重新建立，甚至是進行整體的緩存數(shù)據(jù)遷移，瞬間會給DB帶來極高的系統(tǒng)負載，設(shè)置導(dǎo)致DB服務(wù)器宕機。 那么就沒有辦法解決hash取模的方式帶來的詬病嗎？看下文。

一致性哈希（Consistent Hashing）：

????? 選擇具體的機器節(jié)點不在只依賴需要緩存數(shù)據(jù)的key的hash本身了，而是機器節(jié)點本身也進行了hash運算。

（1） hash機器節(jié)點

首先求出 機器節(jié)點的hash值（怎么算機器節(jié)點的hash？ip可以作為hash的參數(shù)吧。。當然還有其他的方法了），然后將其分布到0～2^32的一個圓環(huán)上 （順時針分布）。如下圖所示：

集群中有 機器：A , B, C, D, E五臺機器，通過一定的hash算法我們將其分布到如上圖所示的環(huán)上。

（2）訪問方式

如果有一 個寫入緩存的請求，其中Key值為K，計算器hash值Hash(K)， Hash(K) 對應(yīng)于圖 – 1環(huán)中的某一個點，如果該點對應(yīng)沒有映射到具體的某一個機器節(jié)點，那么順時針查找，直到第一次找到有映射機器的節(jié)點，該節(jié)點就是確定的目標節(jié)點，如果超過 了2^32仍然找不到節(jié)點，則命中第一個機器節(jié)點。比如 Hash(K) 的值介于A~B之間，那么命中的機器節(jié)點應(yīng)該是B節(jié)點（如上圖 ）。

（3）增加節(jié)點的處理

如上圖 – 1，在原有集群的基礎(chǔ)上欲增加一臺機器F，增加過程如下：

計算機器 節(jié)點的Hash值，將機器映射到環(huán)中的一個節(jié)點，如下圖：

增加機器 節(jié)點F之后，訪問策略不改變，依然按照（2）中的方式訪問，此時緩存命不中的情況依然不可避免，不能命中的數(shù)據(jù)是hash(K)在增加節(jié)點以前落在C～F 之間的數(shù)據(jù)。盡管依然存在節(jié)點增加帶來的命中問題，但是比較傳統(tǒng)的 hash取模的方式，一致性hash已經(jīng)將不命中的數(shù)據(jù)降到了最低。

?

Consistent Hashing最大限度地抑制了hash鍵的重新分布。另外要取得比較好的負載均衡的效果，往往在服務(wù)器數(shù)量比較少的時候需要增加虛擬節(jié)點來保證服務(wù)器能 均勻的分布在圓環(huán)上。因為使用一般的hash方法，服務(wù)器的映射地點的分布非常不均勻。使用虛擬節(jié)點的思想，為每個物理節(jié)點（服務(wù)器）在圓上分配 100～200個點。這樣就能抑制分布不均勻，最大限度地減小服務(wù)器增減時的緩存重新分布。用戶數(shù)據(jù)映射在虛擬節(jié)點上，就表示用戶數(shù)據(jù)真正存儲位置是在該 虛擬節(jié)點代表的實際物理服務(wù)器上。
下面有一個圖描述了需要為每臺物理服務(wù)器增加的虛擬節(jié)點。

?

x軸表示的是需要為每臺物理服務(wù)器擴展的虛擬節(jié)點倍數(shù)(scale)，y軸是實際物理服務(wù)器數(shù)，可以看出，當物理服務(wù)器的數(shù)量很小時，需要更大的虛 擬節(jié)點，反之則需要更少的節(jié)點，從圖上可以看出，在物理服務(wù)器有10臺時，差不多需要為每臺服務(wù)器增加100~200個虛擬節(jié)點才能達到真正的負載均衡。

-----------------

一致性hash，假設(shè)本來應(yīng)該落在B點的數(shù)據(jù)，在A，B之間加一臺機器，平均有一半的數(shù)據(jù)會無效。并且A到加的機器點上的數(shù)據(jù)在B上已經(jīng)沒有用，怎么去清 理。隨著機器的越來越多，不命中的概率也會越來越多。
雖然說最常用的hash取模不可避免的需要做數(shù)據(jù)遷移，但是可以選擇時間點，比如半夜兩點。這個時候訪問肯定會很少。?

--

如果是C、A之間加入節(jié)點B，那原來落在CB之間的數(shù)據(jù)不再找A，而是找B了，這部分數(shù)據(jù)在A確實是失效。但你說的這個是純理論。實際中加入B節(jié)點之 后，CB間的數(shù)據(jù)（原來命中A上）會逐漸保存到B上（而不是不命中的時候什么都不做），同時A上的數(shù)據(jù)隨著新到數(shù)據(jù)增加，原來那部分失效數(shù)據(jù)通過LRU算 法將逐漸淘汰掉。所以我覺隨著機器增加，不命中的概率不會大幅波動。

事實上，一致性hash就是用來解決存儲節(jié)點增加導(dǎo)致的命中降低問題的。
實際例子：日本mixi也是逐漸增加到200臺以上的memcached服務(wù)器集群，用的就是這種方法，并沒有你說的問題。

一致性哈希(Consistent Hashing)