一致性HASH是 分布式存儲(chǔ)中 經(jīng)典的散列算法

比如你有 N 個(gè) cache 服務(wù)器（后面簡(jiǎn)稱 cache ），那么如何將一個(gè)對(duì)象 object 映射到 N 個(gè) cache 上呢孩哑，你很可能會(huì)采用類似下面的通用方法計(jì)算 object 的 hash 值媒峡，然后均勻的映射到到 N 個(gè) cache ；

求余算法: hash(object)%N

一切都運(yùn)行正常，再考慮如下的兩種情況蜡豹；

1 一個(gè) cache 服務(wù)器 m down 掉了（在實(shí)際應(yīng)用中必須要考慮這種情況）麸粮，這樣所有映射到 cache m 的對(duì)象都會(huì)失效，怎么辦余素，需要把 cache m 從 cache 中移除豹休，這時(shí)候 cache 是 N-1 臺(tái)，映射公式變成了 hash(object)%(N-1) 桨吊；

2 由于訪問加重威根，需要添加 cache ，這時(shí)候 cache 是 N+1 臺(tái)视乐，映射公式變成了 hash(object)%(N+1) 洛搀；

1 和 2 意味著什么？這意味著突然之間幾乎所有的 cache 都失效了佑淀。對(duì)于服務(wù)器而言留美，這是一場(chǎng)災(zāi)難，洪水般的訪問都會(huì)直接沖向后臺(tái)服務(wù)器伸刃；

再來考慮第三個(gè)問題谎砾，由于硬件能力越來越強(qiáng)，你可能想讓后面添加的節(jié)點(diǎn)多做點(diǎn)活捧颅，顯然上面的 hash 算法也做不到景图。

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

hash 算法和單調(diào)性

Hash 算法的一個(gè)衡量指標(biāo)是單調(diào)性（ Monotonicity ）碉哑，定義如下：

單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中挚币，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去扣典，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)妆毕。

容易看到，上面的簡(jiǎn)單求余算法 hash(object)%N 難以滿足單調(diào)性要求贮尖。

Consistent Hashing 一致性hash的原理

consistent hashing 是一種 hash 算法笛粘，簡(jiǎn)單的說，在移除 / 添加一個(gè) cache 時(shí)湿硝，它能夠盡可能小的改變已存在key 映射關(guān)系薪前，盡可能的滿足單調(diào)性的要求。

1. 環(huán)形hash 空間

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

circle space

2. 把需要緩存的內(nèi)容(對(duì)象)映射到hash 空間

接下來考慮 4 個(gè)對(duì)象 object1~object4 例诀，通過 hash 函數(shù)計(jì)算出的 hash 值 key 在環(huán)上的分布如圖 2 所示随抠。

hash(object1) = key1;

… …

hash(object4) = key4;

object

3 .把服務(wù)器(節(jié)點(diǎn))映射到hash 空間

Consistent hashing 的基本思想就是將對(duì)象和 cache 都映射到同一個(gè) hash 數(shù)值空間中，并且使用相同的 hash算法繁涂。

假設(shè)當(dāng)前有 A,B 和 C 共 3 臺(tái)服務(wù)器(節(jié)點(diǎn))拱她，那么其映射結(jié)果將如圖 3 所示，他們?cè)?hash 空間中扔罪，以對(duì)應(yīng)的 hash 值排列秉沼。

一般的方法可以使用 服務(wù)器(節(jié)點(diǎn)) 機(jī)器的 IP 地址或者機(jī)器名作為 hash輸入。

hash(cache A) = key A;

… …

hash(cache C) = key C;

cache

4 .把對(duì)象映射到cache

現(xiàn)在cache和對(duì)象都已經(jīng)通過同一個(gè) hash 算法映射到 hash 數(shù)值空間中了矿酵，接下來要考慮的就是如何將對(duì)象映射到 cache 上面了唬复。

在這個(gè)環(huán)形空間中，如果沿著順時(shí)針方向從對(duì)象的 key 值出發(fā)全肮，直到遇見一個(gè) cache 敞咧，那么就將該對(duì)象存儲(chǔ)在這個(gè) cache 上，因?yàn)閷?duì)象和 cache 的 hash 值是固定的辜腺，因此這個(gè) cache 必然是唯一和確定的休建。這樣不就找到了對(duì)象和 cache 的映射方法了嗎？评疗！

依然繼續(xù)上面的例子测砂，那么根據(jù)上面的方法，對(duì)象 object1 將被存儲(chǔ)到 cache A 上百匆； object2 和object3 對(duì)應(yīng)到 cache C 砌些； object4 對(duì)應(yīng)到 cache B ；

5. 考察cache 的變動(dòng)

前面講過胧华，通過 hash 然后求余的方法帶來的最大問題就在于不能滿足單調(diào)性寄症，當(dāng) cache 有所變動(dòng)時(shí)宙彪， cache會(huì)失效矩动，進(jìn)而對(duì)后臺(tái)服務(wù)器造成巨大的沖擊，現(xiàn)在就來分析分析 consistent hashing 算法释漆。

5.1 移除 cache

考慮假設(shè) cache B 掛掉了悲没，根據(jù)上面講到的映射方法，這時(shí)受影響的將僅是那些沿 cache B 逆時(shí)針遍歷直到下一個(gè) cache （ cache C ）之間的對(duì)象男图，也即是本來映射到 cache B 上的那些對(duì)象示姿。

因此這里僅需要變動(dòng)對(duì)象 object4 ，將其重新映射到 cache C 上即可逊笆；參見圖 4 栈戳。

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

5.2 添加 cache

再考慮添加一臺(tái)新的 cache D 的情況，假設(shè)在這個(gè)環(huán)形 hash 空間中难裆， cache D 被映射在對(duì)象 object2 和object3 之間子檀。這時(shí)受影響的將僅是那些沿 cache D 逆時(shí)針遍歷直到下一個(gè) cache （ cache B ）之間的對(duì)象（它們是也本來映射到 cache C 上對(duì)象的一部分）镊掖，將這些對(duì)象重新映射到 cache D 上即可。

因此這里僅需要變動(dòng)對(duì)象 object2 褂痰，將其重新映射到 cache D 上亩进；參見圖 5 。

圖 5 添加 cache D 后的映射關(guān)系

6 .虛擬節(jié)點(diǎn)

考量 Hash 算法的另一個(gè)指標(biāo)是平衡性 (Balance) 缩歪，定義如下：

平衡性

　　平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去归薛，這樣可以使得所有的緩沖空間都得到利用。

hash 算法并不是保證絕對(duì)的平衡匪蝙，如果 cache 較少的話主籍，對(duì)象并不能被均勻的映射到 cache 上，比如在上面的例子中逛球，僅部署 cache A 和 cache C 的情況下崇猫，在 4 個(gè)對(duì)象中， cache A 僅存儲(chǔ)了 object1 需忿，而 cache C 則存儲(chǔ)了object2 诅炉、 object3 和 object4 ；分布是很不均衡的屋厘。

為了解決這種情況涕烧， consistent hashing 引入了“虛擬節(jié)點(diǎn)”的概念，它可以如下定義：

“虛擬節(jié)點(diǎn)”（ virtual node ）是實(shí)際節(jié)點(diǎn)在 hash 空間的復(fù)制品（ replica ）汗洒，一實(shí)際個(gè)節(jié)點(diǎn)對(duì)應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”议纯，這個(gè)對(duì)應(yīng)個(gè)數(shù)也成為“復(fù)制個(gè)數(shù)”，“虛擬節(jié)點(diǎn)”在 hash 空間中以 hash 值排列溢谤。

仍以僅部署 cache A 和 cache C 的情況為例瞻凤，在圖 4 中我們已經(jīng)看到， cache 分布并不均勻∈郎保現(xiàn)在我們引入虛擬節(jié)點(diǎn)阀参，并設(shè)置“復(fù)制個(gè)數(shù)”為 2 ，這就意味著一共會(huì)存在 4 個(gè)“虛擬節(jié)點(diǎn)”瞻坝， cache A1, cache A2 代表了 cache A蛛壳； cache C1, cache C2 代表了 cache C ；假設(shè)一種比較理想的情況所刀，參見圖 6 衙荐。

圖 6 引入“虛擬節(jié)點(diǎn)”后的映射關(guān)系

此時(shí)，對(duì)象到“虛擬節(jié)點(diǎn)”的映射關(guān)系為：

objec1->cache A2 浮创； objec2->cache A1 忧吟； objec3->cache C1 ； objec4->cache C2 斩披；

因此對(duì)象 object1 和 object2 都被映射到了 cache A 上溜族，而 object3 和 object4 映射到了 cache C 上胸嘴；平衡性有了很大提高。

引入“虛擬節(jié)點(diǎn)”后斩祭，映射關(guān)系就從 { 對(duì)象 -> 節(jié)點(diǎn) } 轉(zhuǎn)換到了 { 對(duì)象 -> 虛擬節(jié)點(diǎn) } 劣像。查詢物體所在 cache 時(shí)的映射關(guān)系如圖 7 所示。

圖 7 查詢對(duì)象所在 cache

“虛擬節(jié)點(diǎn)”的 hash 計(jì)算可以采用對(duì)應(yīng)節(jié)點(diǎn)的 IP 地址加數(shù)字后綴的方式摧玫。例如假設(shè) cache A 的 IP 地址為202.168.14.241 耳奕。

引入“虛擬節(jié)點(diǎn)”前，計(jì)算 cache A 的 hash 值：

Hash(“202.168.14.241”);

引入“虛擬節(jié)點(diǎn)”后诬像，計(jì)算“虛擬節(jié)”點(diǎn) cache A1 和 cache A2 的 hash 值：

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

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