1 基本場景

比如你有 N 個 cache 服務器（后面簡稱 cache ），那么如何將一個對象 object 映射到 N 個 cache 上呢，你很可能會采用類似下面的通用方法計算 object 的 hash 值，然后均勻的映射到到 N 個 cache ；

hash(object)%N

一切都運行正常，再考慮如下的兩種情況；

1 一個 cache 服務器 m down 掉了（在實際應用中必須要考慮這種情況），這樣所有映射到 cache m 的對象都會失效，怎么辦，需要把 cache m 從 cache 中移除，這時候 cache 是 N-1 臺，映射公式變成了 hash(object)%(N-1) ；

2 由于訪問加重，需要添加 cache ，這時候 cache 是 N+1 臺，映射公式變成了 hash(object)%(N+1) ；

1 和 2 意味著什么？這意味著突然之間幾乎所有的 cache 都失效了。對于服務器而言，這是一場災難，洪水般的訪問都會直接沖向后臺服務器；

再來考慮第三個問題，由于硬件能力越來越強，你可能想讓后面添加的節點多做點活，顯然上面的 hash 算法也做不到。

有什么方法可以改變這個狀況呢，這就是 consistent hashing...

2 hash 算法和單調性

Hash 算法的一個衡量指標是單調性（ Monotonicity ），定義如下：

單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。

容易看到，上面的簡單 hash 算法 hash(object)%N 難以滿足單調性要求。

3 consistent hashing 算法的原理

consistent hashing 是一種 hash 算法，簡單的說，在移除 / 添加一個 cache 時，它能夠盡可能小的改變已存在 key 映射關系，盡可能的滿足單調性的要求。

下面就來按照 5 個步驟簡單講講 consistent hashing 算法的基本原理。

3.1 環形hash 空間

考慮通常的 hash 算法都是將 value 映射到一個 32 為的 key 值，也即是 0~2^32-1 次方的數值空間；我們可以將這個空間想象成一個首（ 0 ）尾（ 2^32-1 ）相接的圓環，如下面圖 1 所示的那樣。

圖 2 4 個對象的 key 值分布

3.3 把cache 映射到hash 空間

Consistent hashing 的基本思想就是將對象和 cache 都映射到同一個 hash 數值空間中，并且使用相同的 hash 算法。

假設當前有 A,B 和 C 共 3 臺 cache ，那么其映射結果將如圖 3 所示，他們在 hash 空間中，以對應的 hash 值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

圖 4 Cache B 被移除后的 cache 映射

3.5.2 添加 cache

再考慮添加一臺新的 cache D 的情況，假設在這個環形 hash 空間中， cache D 被映射在對象 object2 和 object3 之間。這時受影響的將僅是那些沿 cache D 逆時針遍歷直到下一個 cache （ cache B ）之間的對象（它們是也本來映射到 cache C 上對象的一部分），將這些對象重新映射到 cache D 上即可。

因此這里僅需要變動對象 object2 ，將其重新映射到 cache D 上；參見圖 5 。

圖 6 引入“虛擬節點”后的映射關系

此時，對象到“虛擬節點”的映射關系為：

objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；

因此對象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。

引入“虛擬節點”后，映射關系就從 { 對象 -> 節點 } 轉換到了 { 對象 -> 虛擬節點 } 。查詢物體所在 cache 時的映射關系如圖 7 所示。

圖 7 查詢對象所在 cache

“虛擬節點”的 hash 計算可以采用對應節點的 IP 地址加數字后綴的方式。例如假設 cache A 的 IP 地址為 202.168.14.241 。

引入“虛擬節點”前，計算 cache A 的 hash 值：

Hash(“202.168.14.241”);

引入“虛擬節點”后，計算“虛擬節”點 cache A1 和 cache A2 的 hash 值：

Hash(“202.168.14.241#1”); // cache A1

Hash(“202.168.14.241#2”); // cache A2