1、http:/ 算法早在 1997 年就在論文 Consistenthashingandrandomtrees 中被提出，目前在 cache 系統中應用越來越廣泛；1 基本場景比如你有 N 個 cache 服務器(后面簡稱 cache),那么如何將一個對象 object 映射到 N 個 cache 上呢， 你很可能會采用類似下面的通用方法計算 object 的 hash 值，然后均勻的映射到到 N 個 cache;hash(object)%N一切都運行正常，再考慮如下的兩種情況；1一個 cache 服務器 mdown 掉了(在實際應用中必須要考慮這種情況)，這樣所有映射到 cachem 的對象都

2、會失效，怎么辦，需要把 cachem 從 cache 中移除，這時候 cache 是 N-1 臺，映射公式變成了hash(object)%(N-1)；2 由于訪問加重，需要添加 cache,這時候 cache 是 N+1 臺，映射公式變成了 hash(object)%(N+1)；1 和 2 意味著什么？這意味著突然之間幾乎所有的 cache 都失效了。對于服務器而言，這是一場災難，洪水般的訪問都會直接沖向后臺服務器；再來考慮第三個問題，由于硬件能力越來越強，你可能想讓后面添加的節點多做點活，顯然上面的 hash算法也做不到。有什么方法可以改變這個狀況呢，這就是 consistenthashin

3、g.2 hash 算法和單調性Hash 算法的一個衡量指標是單調性(Monotonicity),定義如下：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。容易看到，上面的簡單 hash 算法 hash(object)%N 難以滿足單調性要求。3 consistenthashing 算法的原理consistenthashing 是一種 hash 算法，簡單的說，在移除/添加一個 cache 時，它能夠盡可能小的改變已存在 key 映射關系，盡可能的滿足單調性

4、的要求。3.1環形 hash 空間考慮通常的 hash 算法都是將 value 映射到一個 32 為的 key 值，也即是 02A32-1 次方的數值空間；我們可以將這個空間想象成一個首（0）尾（2A32-1）相接的圓環，如下面圖 1 所示的那樣。把 cache 映射到 hash 空間Consistenthashing 的基本思想就是將對象和 cache 都映射到同一個 hash 數值空間中， 并且使用相同的hash 算法。假設當前有 A,B 和 C 共 3 臺 cache， 那么其映射結果將如圖 3 所示， 他們在 hash 空間中， 以對應的 hash值排列。hash(cacheA)=ke

5、yA;3.2 把對象映射到 hash 空間接下來考慮 4 個對象 object1object4布如圖 2 所示。hash（object1）=key1;,通過 hash 函數計算出的 hash 值 key 在環上的分hash(object4)=key4;圖 1 環形 hash 空間圖 24 個對象的 key 值分布hash(cacheC)=keyC;圖 3cache 和對象的 key 值分布說到這里，順便提一下 cache 的 hash 計算，一般的方法可以使用 cache 機器的 IP 地址或者機器名作為hash 輸入。把對象映射到 cache現在 cache 和對象都已經通過同一個 hash

6、 算法映射到 hash 數值空間中了， 接下來要考慮的就是如何將對象映射到 cache 上面了。在這個環形空間中， 如果沿著順時針方向從對象的 key 值出發， 直到遇見一個 cache,那么就將該對象存儲在這個 cache 上，因為對象和 cache 的 hash 值是固定的，因此這個 cache 必然是唯一和確定的。這樣不就找到了對象和 cache 的映射方法了嗎？！依然繼續上面的例子(參見圖 3),那么根據上面的方法，對象 objectl 將被存儲到 cacheA 上；object2 和 object3 對應到 cacheC;object4 對應到 cacheB;考察 cache 的變動

7、前面講過，通過 hash 然后求余的方法帶來的最大問題就在于不能滿足單調性，當 cache 有所變動時，cache 會失效，進而對后臺服務器造成巨大的沖擊，現在就來分析分析 consistenthashing 算法。移除 cache考慮假設 cacheB 掛掉了，根據上面講到的映射方法，這時受影響的將僅是那些沿 cacheB 逆時針遍歷直到下一個 cache(cacheC)之間的對象，也即是本來映射到 cacheB 上的那些對象。因此這里僅需要變動對象 object4,將其重新映射到 cacheC 上即可；參見圖 4。圖 5 添加 cacheD 后的映射關系4 虛擬節點考量 Hash 算法的另

8、一個指標是平衡性(Balance),定義如下:平衡性平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。3.5.2 添加 cache再考慮添加一臺新的象object2 和 object3 個cache(cacheB)cacheD 的情況，假設在這個環形之間。 這時受影響的將僅是那些沿之間的對象(它們是也本來映射到hash 空間中，cacheD 被映射在對cacheD 逆時針遍歷直到下一cacheC 上對象的一部分)，將這些對象重新映射到 cacheD 上即可。因此這里僅需要變動對象 object2,將其重新映射到cacheD 上；參見圖 5。圖 4Cach

9、eB 被移除后的 cache 映射hash 算法并不是保證絕對的平衡，如果 cache 較少的話，對象并不能被均勻的映射到 cache 上，比如在上面的例子中，僅部署 cacheA 和 cacheC 的情況下，在 4 個對象中，cacheA 僅存儲了 objectl,而 cacheC 則存儲了 object2、objects 和 object4；分布是很不均衡的。為了解決這種情況，consistenthashing 引入了“虛擬節點”的概念，它可以如下定義：“虛擬節點”(virtualnode)是實際節點在 hash 空間的復制品(replica),一實際個節點對應了若干個“虛擬節點”，這個對

10、應個數也成為“復制個數”，“虛擬節點”在 hash 空間中以 hash 值排列。仍以僅部署 cacheA 和 cacheC 的情況為例，在圖 4 中我們已經看到，cache 分布并不均勻。現在我們引入虛擬節點，并設置“復制個數”為 2,這就意味著一共會存在 4 個“虛擬節點”，cacheA1,cacheA2 代表了 cacheA；cacheC1,cacheC2 代表了 cacheC;假設一種比較理想的情況，參見圖 6。CacfieAloiiecdS圖 6 引入“虛擬節點”后的映射關系此時，對象到“虛擬節點”的映射關系為：objec1-cacheA2；objec2-cacheA1；objec3-

11、cacheC1;objec4-cacheC2；因此對象 object1 和 object2 都被映射到了 cacheA 上， 而 objects 和 object4 映射到了 cacheC 上； 平衡性有了很大提高。引入“虛擬節點”后，映射關系就從對象-節點轉換到了對象-虛擬節點。查詢物體所在 cache時的映射關系如圖 7 所示。hrtfih圖 7 查詢對象所在 cache“虛擬節點”的 hash 計算可以采用對應節點的 IP 地址加數字后綴的方式。例如假設 cacheA 的 IP 地址為 41。引入“虛擬節點”前，計算 cacheA 的 hash 值：Hash(“41);引入“虛擬節點”后，計算“虛擬節”點 cacheA1 和 cacheA2 的 hash 值：Hash(“41#1”);/cacheA1Hash(“41#2”);/cacheA2