這是悟空的第 78 篇原創(chuàng)文章。
> 本文已收錄 Github：https://github.com/Jackson0714/PassJava-Learning
韓信點兵的成語來源淮安民間傳說么抗。常與多多益善搭配棵磷。寓意越多越好杂瘸。我們來看下主公劉邦和韓信大將軍的對話旁涤。
> **劉邦**：“你覺得我可以帶兵多少粱檀？”
>
> **韓信**：“最多十萬洲敢。”
>
> **劉邦**不解的問：“那你呢茄蚯？”
>
> **韓信**自豪地說：“越多越好压彭，多多益善嘛！
假如劉邦現(xiàn)在給了韓信 1000 個士兵渗常，需要大致均勻分成三組壮不。士兵的編號是 6 位數(shù)，從 1-100000 隨機分配皱碘。比如第一個士兵的值是 245询一，第二個士兵的編號是82593，其他士兵類似癌椿。那么如何對士兵進行分配呢健蕊？
> **劉邦**：韓將軍，你看這些士兵怎么分配好呢踢俄？
>
> **韓信**：這還不簡單绊诲，我的一技能就能搞定。
## 一技能：哈希算法
### 分組
韓信的一技能`哈希算法`：將士兵的編號 num 值當(dāng)做一個 hash 值褪贵，再和總做組數(shù) N 做取余操作掂之，得出的結(jié)果在 0 到 N - 1 之間，這個士兵就屬于那個組脆丁。
如下圖所示世舰，每來一個士兵都有一個六位的 hash 值（也可以稱作編號），然后被韓信用除以 3 取余數(shù)的方式分配到三個組槽卫。比如第一組中的編號為 123456 的士兵跟压，除以 3 之后，整除歼培，余數(shù)為 0震蒋，所以分配到第一組。
### 查找士兵
現(xiàn)在已經(jīng)分好組了躲庄，假如想找到編號為 666666 的士兵該怎么找查剖？首先將 666666 除以 3，得到余數(shù) 0噪窘，說明在第一個組笋庄，然后去第一個組里面找就可以了。
這里有小伙伴可能會問，為什么不是把所有士兵放到一個組直砂？
**因為一個組太大了菌仁，影響行軍速度**。映射到互聯(lián)網(wǎng)架構(gòu)中静暂，就是通過增加節(jié)點從而減小單節(jié)點的負載壓力济丘。
### 哈希分組弊端
劉邦看了這個一技能后，大呼：
> 韓將軍真是厲害洽蛀。
>
> 哈希算法看起來很完美闪盔，那我再給你五百士兵，需要分成四個組怎么辦辱士？
這時泪掀，韓信的副將說話了：
> 這還不簡單，再用 4 取余不就好了嗎颂碘？
劉邦摸著下巴思索片刻后异赫，對副將說：
> 這個方案可行，但很多士兵都被重新分組了头岔，剛剛建立的團隊友情就被分解了塔拳。
我們來看下劉邦為什么覺得方案不可行。
比如原來分配到一組的編號為 3 的士兵峡竣，當(dāng)分成四組的時候靠抑，通過公式計算：3%4=3，所以會分配到到第四組适掰。
依次類推颂碧，會發(fā)現(xiàn)很多士兵進行了重新分配，只有小部分不會變換分組类浪，比如 1载城，2，12 等等费就。
韓信對著劉邦點點頭诉瓦，對著主公說道：
> 主公，您說得沒錯力细，這就是我的一技能的`弱點`所在睬澡。
>
> 不過我還有一個技能：`一致性哈希`。
## 二技能：一致性哈希
### 哈希環(huán)
一致性哈希算法也用了取模運算眠蚂，但是它與哈希算法不同的地方：
- **哈希算法**：對節(jié)點的數(shù)量進行取模運算煞聪。
- **一致性哈希算法**：對 2^32 進行取模運算。
可以想象一下河狐，一致性哈希算法米绕，是將整個哈希值空間組成了一個虛擬的圓環(huán)瑟捣，也就是`哈希環(huán)`馋艺。
如下圖栅干，把 3 個組映射到固定大小為 `2^32` 的哈希環(huán)中。三個組一共將整個環(huán)分成了三個區(qū)域捐祠，C-A（第一組）碱鳞、A-B（第二組）、B-C（第三組）踱蛀。如下圖所示：
- 第一組負責(zé)存儲落在 C-A 區(qū)間內(nèi)的數(shù)據(jù)窿给。
- 第二組負責(zé)存儲落在 A-B 區(qū)間內(nèi)的數(shù)據(jù)。
- 第三組負責(zé)存儲落在 B-C 區(qū)間內(nèi)的數(shù)據(jù)率拒。
### 士兵分配
假定編號為 9527 的士兵崩泡，進行哈希運算后，落到 C-A 區(qū)域猬膨。如下圖所示：
第二步角撞，讓這個士兵順時針往前走，遇到的第一個節(jié)點 A 就是他所在的組了泰演。如下圖所示:
### 增加分組
目前三個節(jié)點的時候潮改，假定編號為 89757 的士兵經(jīng)過哈希運算后缨称，分配到了 B-C 區(qū)域（第三組），也就是屬于 C 節(jié)點管控劣领。如下圖所示：
回到劉邦剛問的問題，如果分組變成四組铁材，該怎么進行士兵分配尖淘。
如下圖所示，增加一個節(jié)點 D著觉，原來的區(qū)域 B-C 變成了區(qū)域 B-D（第三組） 和 D-C（第四組）德澈。
那么這名士兵屬于哪個節(jié)點管控呢？如下圖所示固惯，士兵順時針往前走梆造，先走到了 D 節(jié)點，所以屬于 D 節(jié)點管控葬毫。雖然還是屬于第三組镇辉，**但是這名士兵的領(lǐng)導(dǎo)者已經(jīng)變了：由 C 變成了 D**。
從上面的變化來看贴捡，只有 B-C 區(qū)域中的部分數(shù)據(jù)會進行遷移：B-D 之間的數(shù)據(jù)會由 C 節(jié)點`遷移`到 D 節(jié)點忽肛。
而**其他數(shù)據(jù)不受影響，也不用進行遷移**烂斋。而且節(jié)點越多屹逛，需要遷移的數(shù)據(jù)就越少础废。這就是多多益善了~
劉邦看了后，大贊韓信：
> 不虧是大將軍罕模，蕭何當(dāng)時月下追你评腺，值了！
### 哈希環(huán)缺陷
蕭何看了韓信畫的哈希環(huán)后淑掌，覺得有些不對勁蒿讥，思索片刻后，對韓信說：
> 將軍抛腕，你這個哈希環(huán)上的節(jié)點分布`不太均勻`啊芋绸，你看第三組和第四組的的區(qū)域好小啊。
蕭何說得沒錯担敌，確實存在這個問題摔敛，放到互聯(lián)網(wǎng)架構(gòu)中，就存在如下問題：
**節(jié)點分布不均勻全封，導(dǎo)致業(yè)務(wù)對節(jié)點的訪問冷熱不均**马昙。
韓信眼中充滿著贊賞，知我者莫若蕭何售貌。然后胸有成竹地說道：
> 你說得沒錯给猾，不過我還有一個技能，`虛擬節(jié)點映射`颂跨。
## 三技能：虛擬節(jié)點
一般虛擬節(jié)點比物理節(jié)點要多敢伸，并相對均勻地分布在哈希環(huán)上。如下圖所示恒削，12 個虛擬節(jié)點 N1~N12池颈，相對均勻地分布在虛擬節(jié)點上。如果有士兵屬于 N2/N3/N4 中的某一個钓丰，都會重新映射到 A 節(jié)點躯砰，依次類推，N5/N6/N7 屬于 B 節(jié)點的虛擬節(jié)點映射携丁。
我們來看下蕭何的提出的問題琢歇，真實的 B-D 區(qū)域比較小，用虛擬節(jié)點后梦鉴，N5/N6/N7 屬于 B 節(jié)點李茫，N8/N9/N10 屬于 D 節(jié)點，他們分到的虛擬節(jié)點一樣多肥橙，而且區(qū)域大致相等魄宏。所以士兵的分配也比較均勻。
> 蕭何看了韓信的三技能后存筏，直呼：妙哉妙哉宠互！
## 總結(jié)
本篇通過韓信點兵的故事味榛，然后從故事中衍生出劉邦、韓信予跌、蕭何的對話搏色，來講解士兵的分組的問題。現(xiàn)在對故事中的知識點做一個總結(jié)：
- 哈希算法會帶來增加或刪除節(jié)點時匕得，**數(shù)據(jù)遷移**量太大的問題继榆。
- 一致性哈希算法**降低**了數(shù)據(jù)遷移量巾表。
- 節(jié)點較少汁掠，哈希環(huán)上每個節(jié)點實際占據(jù)的區(qū)間大小不一，最終導(dǎo)致業(yè)務(wù)對節(jié)點的訪問**冷熱不均**集币。
- 引入**虛擬節(jié)點映射**解決了分布不均問題考阱。
- 節(jié)點**越多**時，使用哈希算法時鞠苟，需要遷移的數(shù)據(jù)就**越多**乞榨，而使用一致性哈希算法，遷移的數(shù)據(jù)就**越少**当娱。
- 一致性哈希算法本質(zhì)上是一種**路由尋址**算法吃既，適合簡單的路由尋址場景。
- 一致性哈希算法常用在負載均衡的架構(gòu)設(shè)計中跨细。
封面圖片來源王者榮耀鹦倚。
往期推薦：
[四：用動圖講解分布式 Raft](http://mp.weixin.qq.com/s?__biz=MzAwMjI0ODk0NA==&mid=2451950743&idx=1&sn=df1c600f636c8d9b119f534750c007eb&chksm=8d1c3508ba6bbc1e6e4def2ea4c25d9c5e69013d463af31f6bc78cacbc3735ccea455842303d&scene=21#wechat_redirect)
[三：諸葛亮 VS 龐統(tǒng)，拿下分布式 Paxos](http://mp.weixin.qq.com/s?__biz=MzAwMjI0ODk0NA==&mid=2451950571&idx=1&sn=04359a2a8db23a64da29cd03dafe0f9c&chksm=8d1c3274ba6bbb62b03a452f5598d355d0dc91ea955d810e5a8128c466b3b0d04f2e6469c49b&scene=21#wechat_redirect)
[二：用太極拳講分布式理論冀惭，真舒服震叙！](http://mp.weixin.qq.com/s?__biz=MzAwMjI0ODk0NA==&mid=2451950422&idx=1&sn=7f86457acedbd0853cbcb7dc4377dd54&chksm=8d1c32c9ba6bbbdfd3d8c698addfb13a02589409bdf6a03a777e9afc95249018293d9a9e0a3f&scene=21#wechat_redirect)
[一：用三國殺講分布式算法，舒適了吧散休？](http://mp.weixin.qq.com/s?__biz=MzAwMjI0ODk0NA==&mid=2451949807&idx=1&sn=d8fb211bc87275e004a8001e095ef402&chksm=8d1c3170ba6bb866ca19548e3922d64d194a0c798622aa954e0236b85cb0869c88ff40f3deed&scene=21#wechat_redirect)
> `作者簡介`：8 年互聯(lián)網(wǎng)經(jīng)驗媒楼，擅長架構(gòu)設(shè)計、分布式戚丸、微服務(wù)划址。手寫了一套 SpringCloud 實戰(zhàn)教程，自主開發(fā)了 PMP 刷題小程序和 Java 刷題小程序限府《岵回復(fù) pdf 領(lǐng)取。
