韓信大招：一致性哈希！

韓信點(diǎn)兵的成語來源淮安民間傳說。常與多多益善搭配。寓意越多越好。我們來看下主公劉邦和韓信大將軍的對(duì)話。

劉邦：“你覺得我可以帶兵多少？”

韓信：“最多十萬。”

劉邦不解的問：“那你呢？”

韓信自豪地說：“越多越好，多多益善嘛！

假如劉邦現(xiàn)在給了韓信一千個(gè)士兵，需要大致均勻分成三組。士兵的編號(hào)是六位數(shù)，從 1-100000 隨機(jī)分配。比如第一個(gè)士兵的值是 245，第二個(gè)士兵的編號(hào)是 82593，其他士兵類似。那么如何對(duì)士兵進(jìn)行分配呢？

劉邦：韓將軍，你看這些士兵怎么分配好呢？

韓信：這還不簡單，我的一技能就能搞定。

一技能：哈希算法

分組

韓信的一技能哈希算法：將士兵的編號(hào) num 值當(dāng)做一個(gè)哈希值，再和總做小組數(shù) N 做取余操作，得出的結(jié)果在 0 到 N - 1 之間，這個(gè)士兵就屬于那個(gè)組。

如下圖所示，每來一個(gè)士兵都有一個(gè)六位的 hash 值（也可以稱作編號(hào)），然后被韓信用除以 3 取余數(shù)的方式分配到三個(gè)組。比如第一組中的編號(hào)為 123456 的士兵，除以 3 之后，整除，余數(shù)為 0，所以分配到第一組。

查找士兵

現(xiàn)在已經(jīng)分好組了，假如想找到編號(hào)為 666666 的士兵該怎么找？首先將 666666 除以 3，得到余數(shù) 0，說明在第一個(gè)組，然后去第一個(gè)組里面找就可以了。

這里有小伙伴可能會(huì)問，為什么不是把所有士兵放到一個(gè)組？

因?yàn)橐粋€(gè)組太大了，影響行軍速度。映射到互聯(lián)網(wǎng)架構(gòu)中，就是通過增加節(jié)點(diǎn)從而減小單節(jié)點(diǎn)的負(fù)載壓力。

哈希分組弊端

劉邦看了這個(gè)一技能后，大呼：

韓將軍真是厲害。

哈希算法看起來很完美，那我再給你五百士兵，需要分成四個(gè)組怎么辦？

這時(shí)，韓信的副將說話了：

這還不簡單，再用 4 取余不就好了嗎？

劉邦摸著下巴思索片刻后，對(duì)副將說：

這個(gè)方案可行，但很多士兵都被重新分組了，剛剛建立的團(tuán)隊(duì)友情就被分解了。

我們來看下劉邦為什么覺得方案不可行。

比如原來分配到一組的編號(hào)為 3 的士兵，當(dāng)分成四組的時(shí)候，通過公式計(jì)算：3%4=3，所以會(huì)分配到到第四組。

依次類推，會(huì)發(fā)現(xiàn)很多士兵進(jìn)行了重新分配，只有小部分不會(huì)變換分組，比如 1，2，12 不會(huì)被重新分組。

韓信對(duì)著劉邦點(diǎn)點(diǎn)頭，對(duì)著主公說道：

主公，您說得沒錯(cuò)，這就是我的一技能的弱點(diǎn)所在。

不過我還有一個(gè)技能：一致性哈希。

二技能：一致性哈希

哈希環(huán)

一致性哈希算法也用了取模運(yùn)算，但是它與哈希算法不同的地方：

• 哈希算法：對(duì)節(jié)點(diǎn)的數(shù)量進(jìn)行取模運(yùn)算。
• 一致性哈希算法：對(duì) 2^32 進(jìn)行取模運(yùn)算。

可以想象一下，一致性哈希算法，是將整個(gè)哈希值空間組成了一個(gè)虛擬的圓環(huán)，也就是哈希環(huán)。

如下圖，把 3 個(gè)組映射到固定大小為 2^32 的哈希環(huán)中。三個(gè)組一共將整個(gè)環(huán)分成了三個(gè)區(qū)域，C-A（第一組）、A-B（第二組）、B-C（第三組）。如下圖所示：

• 第一組負(fù)責(zé)存儲(chǔ)落在 C-A 區(qū)間內(nèi)的數(shù)據(jù)。

• 第二組負(fù)責(zé)存儲(chǔ)落在 A-B 區(qū)間內(nèi)的數(shù)據(jù)。

• 第三組負(fù)責(zé)存儲(chǔ)落在 B-C 區(qū)間內(nèi)的數(shù)據(jù)。

士兵分配

假定編號(hào)為 9527 的士兵，進(jìn)行哈希運(yùn)算后，落到 C-A 區(qū)域。如下圖所示：

第二步，讓這個(gè)士兵順時(shí)針往前走，遇到的第一個(gè)節(jié)點(diǎn) A 就是他所在的組了。如下圖所示:

增加分組

目前三個(gè)節(jié)點(diǎn)的時(shí)候，假定編號(hào)為 89757 的士兵經(jīng)過哈希運(yùn)算后，分配到了 B-C 區(qū)域（第三組），也就是屬于 C 節(jié)點(diǎn)管控。如下圖所示：

回到劉邦剛問的問題，如果分組變成四組，該怎么進(jìn)行士兵分配。

如下圖所示，增加一個(gè)節(jié)點(diǎn) D，原來的區(qū)域 B-C 變成了區(qū)域 B-D（第三組） 和 D-C（第四組）。

那么這名士兵屬于哪個(gè)節(jié)點(diǎn)管控呢？如下圖所示，士兵順時(shí)針往前走，先走到了 D 節(jié)點(diǎn)，所以屬于 D 節(jié)點(diǎn)管控。雖然還是屬于第三組，但是這名士兵的領(lǐng)導(dǎo)者已經(jīng)變了：由 C 變成了 D。

從上面的變化來看，只有 B-C 區(qū)域中的部分?jǐn)?shù)據(jù)會(huì)進(jìn)行遷移：B-D 之間的數(shù)據(jù)會(huì)由 C 節(jié)點(diǎn)遷移到 D 節(jié)點(diǎn)。

而其他數(shù)據(jù)不受影響，也不用進(jìn)行遷移。而且節(jié)點(diǎn)越多，需要遷移的數(shù)據(jù)就越少。這就是多多益善了~

劉邦看了后，大贊韓信：

不虧是大將軍，蕭何當(dāng)時(shí)月下追你，值了！

哈希環(huán)缺陷

蕭何看了韓信畫的哈希環(huán)后，覺得有些不對(duì)勁，思索片刻后，對(duì)韓信說：

將軍，你這個(gè)哈希環(huán)上的節(jié)點(diǎn)分布不太均勻啊，你看第三組和第四組的的區(qū)域好小啊。

蕭何說得沒錯(cuò)，確實(shí)存在這個(gè)問題，放到互聯(lián)網(wǎng)架構(gòu)中，就存在如下問題：

節(jié)點(diǎn)分布不均勻，導(dǎo)致業(yè)務(wù)對(duì)節(jié)點(diǎn)的訪問冷熱不均。

韓信眼中充滿著贊賞，知我者莫若蕭何。然后胸有成竹地說道：

你說得沒錯(cuò)，不過我還有一個(gè)技能，虛擬節(jié)點(diǎn)映射。

三技能：虛擬節(jié)點(diǎn)

一般虛擬節(jié)點(diǎn)比物理節(jié)點(diǎn)要多，并相對(duì)均勻地分布在哈希環(huán)上。如下圖所示，12 個(gè)虛擬節(jié)點(diǎn) N1~N12，相對(duì)均勻地分布在虛擬節(jié)點(diǎn)上。如果有士兵屬于 N2/N3/N4 中的某一個(gè)，都會(huì)重新映射到 A 節(jié)點(diǎn)，依次類推，N5/N6/N7 屬于 B 節(jié)點(diǎn)的虛擬節(jié)點(diǎn)映射。

我們來看下蕭何的提出的問題，真實(shí)的 B-D 區(qū)域比較小，用虛擬節(jié)點(diǎn)后，N5/N6/N7 屬于 B 節(jié)點(diǎn)，N8/N9/N10 屬于 D 節(jié)點(diǎn)，他們分到的虛擬節(jié)點(diǎn)一樣多，而且區(qū)域大致相等。所以士兵的分配也比較均勻。

蕭何看了韓信的三技能后，直呼：妙哉妙哉！

總結(jié)

本篇通過韓信點(diǎn)兵的故事，然后從故事中衍生出劉邦、韓信、蕭何的對(duì)話，來講解士兵的分組的問題。現(xiàn)在對(duì)故事中的知識(shí)點(diǎn)做一個(gè)總結(jié)：

• 哈希算法會(huì)帶來增加或刪除節(jié)點(diǎn)時(shí)，數(shù)據(jù)遷移量太大的問題。
• 一致性哈希算法降低了數(shù)據(jù)遷移量。
• 節(jié)點(diǎn)較少，哈希環(huán)上每個(gè)節(jié)點(diǎn)實(shí)際占據(jù)的區(qū)間大小不一，最終導(dǎo)致業(yè)務(wù)對(duì)節(jié)點(diǎn)的訪問冷熱不均。
• 引入虛擬節(jié)點(diǎn)映射解決了分布不均問題。
• 節(jié)點(diǎn)越多時(shí)，使用哈希算法時(shí)，需要遷移的數(shù)據(jù)就越多，而使用一致性哈希算法，遷移的數(shù)據(jù)就越少。
  
• 一致性哈希算法本質(zhì)上是一種路由尋址算法，適合簡單的路由尋址場景。
  
• 一致性哈希算法常用在負(fù)載均衡的架構(gòu)設(shè)計(jì)中。