維基百科定義

一致哈希是一種特殊的哈希算法。在使用一致哈希算法后，哈希表槽位數(shù)（大?。┑母淖兤骄恍枰獙?duì) K/n個(gè)關(guān)鍵字重新映射，其中K是關(guān)鍵字的數(shù)量， n是槽位數(shù)量。然而在傳統(tǒng)的哈希表中，添加或刪除一個(gè)槽位的幾乎需要對(duì)所有關(guān)鍵字進(jìn)行重新映射。

引出

我們?cè)谏衔闹幸呀?jīng)介紹了一致性Hash算法的基本優(yōu)勢(shì)，我們看到了該算法主要解決的問(wèn)題是：當(dāng)slot數(shù)發(fā)生變化時(shí)，能夠盡量少的移動(dòng)數(shù)據(jù)。那么，我們思考一下，普通的Hash算法是如何實(shí)現(xiàn)？又存在什么問(wèn)題呢？ 那么我們引出一個(gè)問(wèn)題：

假設(shè)有1000w個(gè)數(shù)據(jù)項(xiàng)，100個(gè)存儲(chǔ)節(jié)點(diǎn)，請(qǐng)?jiān)O(shè)計(jì)一種算法合理地將他們存儲(chǔ)在這些節(jié)點(diǎn)上。

看一看普通Hash算法的原理：

1.png

算法的核心計(jì)算如下

for item in range(ITEMS):
    k = md5(str(item)).digest()
    h = unpack_from(">I", k)[0]
    # 通過(guò)取余的方式進(jìn)行映射
    n = h % NODES
    node_stat[n] += 1

從上述結(jié)果可以發(fā)現(xiàn)，普通的Hash算法均勻地將這些數(shù)據(jù)項(xiàng)打散到了這些節(jié)點(diǎn)上，并且分布最少和最多的存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)項(xiàng)數(shù)目小于1%。之所以分布均勻，主要是依賴Hash算法（實(shí)現(xiàn)使用的MD5算法）能夠比較隨機(jī)的分布。

然而，我們看看存在一個(gè)問(wèn)題，由于該算法使用節(jié)點(diǎn)數(shù)取余的方法，強(qiáng)依賴node的數(shù)目，因此，當(dāng)是node數(shù)發(fā)生變化的時(shí)候，item所對(duì)應(yīng)的node發(fā)生劇烈變化，而發(fā)生變化的成本就是我們需要在node數(shù)發(fā)生變化的時(shí)候，數(shù)據(jù)需要遷移，這對(duì)存儲(chǔ)產(chǎn)品來(lái)說(shuō)顯然是不能忍的，我們觀察一下增加node后，數(shù)據(jù)項(xiàng)移動(dòng)的情況：

如果有100個(gè)item，當(dāng)增加一個(gè)node，之前99%的數(shù)據(jù)都需要重新移動(dòng)。

這顯然是不能忍的，普通哈希算法的問(wèn)題我們已經(jīng)發(fā)現(xiàn)了，如何對(duì)其進(jìn)行改進(jìn)呢？沒(méi)錯(cuò)，我們的一致性哈希算法閃亮登場(chǎng)。

那么，一個(gè)亟待解決的問(wèn)題就變成了：當(dāng)node數(shù)發(fā)生變化時(shí)，如何保證盡量少引起遷移呢？即當(dāng)增加或者刪除節(jié)點(diǎn)時(shí)，對(duì)于大多數(shù)item，保證原來(lái)分配到的某個(gè)node，現(xiàn)在仍然應(yīng)該分配到那個(gè)node，將數(shù)據(jù)遷移量的降到最低。

一致性Hash算法的原理是這樣的：

2.png

雖然一致性Hash算法解決了節(jié)點(diǎn)變化導(dǎo)致的數(shù)據(jù)遷移問(wèn)題，但是，我們回過(guò)頭來(lái)再看看數(shù)據(jù)項(xiàng)分布的均勻性， 但是引入一致性哈希算法后，為什么就不均勻呢？數(shù)據(jù)項(xiàng)本身的哈希值并未發(fā)生變化，變化的是判斷數(shù)據(jù)項(xiàng)哈希應(yīng)該落到哪個(gè)節(jié)點(diǎn)的算法變了。

3.png

因此，主要是因?yàn)檫@100個(gè)節(jié)點(diǎn)Hash后，在環(huán)上分布不均勻，導(dǎo)致了每個(gè)節(jié)點(diǎn)實(shí)際占據(jù)環(huán)上的區(qū)間大小不一造成的。

改進(jìn)-虛節(jié)點(diǎn)

當(dāng)我們將node進(jìn)行哈希后，這些值并沒(méi)有均勻地落在環(huán)上，因此，最終會(huì)導(dǎo)致，這些節(jié)點(diǎn)所管轄的范圍并不均勻，最終導(dǎo)致了數(shù)據(jù)分布的不均勻。

consist_hash_virtual

因此，通過(guò)增加虛節(jié)點(diǎn)的方法，使得每個(gè)節(jié)點(diǎn)在環(huán)上所“管轄”更加均勻。這樣就既保證了在節(jié)點(diǎn)變化時(shí)，盡可能小的影響數(shù)據(jù)分布的變化，而同時(shí)又保證了數(shù)據(jù)分布的均勻。也就是靠增加“節(jié)點(diǎn)數(shù)量”加強(qiáng)管轄區(qū)間的均勻。

另一種改進(jìn)

然而，虛節(jié)點(diǎn)這種靠數(shù)量取勝的策略增加了存儲(chǔ)這些虛節(jié)點(diǎn)信息所需要的空間。在OpenStack的Swift組件中，使用了一種比較特殊的方法來(lái)解決分布不均的問(wèn)題，改進(jìn)了這些數(shù)據(jù)分布的算法，將環(huán)上的空間均勻的映射到一個(gè)線性空間，這樣，就保證分布的均勻性。

5.png