韓信大招：一致性哈希
這是悟空的第 78 篇原創文章。
本文已收錄 Github：//github.com/Jackson0714/PassJava-Learning
韓信點兵的成語來源淮安民間傳說。常與多多益善搭配。寓意越多越好。我們來看下主公劉邦和韓信大將軍的對話。
劉邦：「你覺得我可以帶兵多少？」
韓信：「最多十萬。」
劉邦不解的問：「那你呢？」
韓信自豪地說：「越多越好，多多益善嘛！
假如劉邦現在給了韓信 1000 個士兵，需要大致均勻分成三組。士兵的編號是 6 位數，從 1-100000 隨機分配。比如第一個士兵的值是 245，第二個士兵的編號是82593，其他士兵類似。那麼如何對士兵進行分配呢？
劉邦：韓將軍，你看這些士兵怎麼分配好呢？
韓信：這還不簡單，我的一技能就能搞定。
一技能：哈希算法
分組
韓信的一技能哈希算法：將士兵的編號 num 值當做一個 hash 值，再和總做組數 N 做取余操作，得出的結果在 0 到 N – 1 之間，這個士兵就屬於那個組。
如下圖所示，每來一個士兵都有一個六位的 hash 值（也可以稱作編號），然後被韓信用除以 3 取餘數的方式分配到三個組。比如第一組中的編號為 123456 的士兵，除以 3 之後，整除，餘數為 0，所以分配到第一組。
查找士兵
現在已經分好組了，假如想找到編號為 666666 的士兵該怎麼找？首先將 666666 除以 3，得到餘數 0，說明在第一個組，然後去第一個組裏面找就可以了。
這裡有小夥伴可能會問，為什麼不是把所有士兵放到一個組？
因為一個組太大了，影響行軍速度。映射到互聯網架構中，就是通過增加節點從而減小單節點的負載壓力。
哈希分組弊端
劉邦看了這個一技能後，大呼：
韓將軍真是厲害。
哈希算法看起來很完美，那我再給你五百士兵，需要分成四個組怎麼辦？
這時，韓信的副將說話了：
這還不簡單，再用 4 取余不就好了嗎？
劉邦摸着下巴思索片刻後，對副將說：
這個方案可行，但很多士兵都被重新分組了，剛剛建立的團隊友情就被分解了。
我們來看下劉邦為什麼覺得方案不可行。
比如原來分配到一組的編號為 3 的士兵，當分成四組的時候，通過公式計算：3%4=3，所以會分配到到第四組。
依次類推，會發現很多士兵進行了重新分配，只有小部分不會變換分組，比如 1，2，12 等等。
韓信對着劉邦點點頭，對着主公說道：
主公，您說得沒錯，這就是我的一技能的
弱點所在。不過我還有一個技能：
一致性哈希。
二技能：一致性哈希
哈希環
一致性哈希算法也用了取模運算，但是它與哈希算法不同的地方：
- 哈希算法：對節點的數量進行取模運算。
- 一致性哈希算法：對 2^32 進行取模運算。
可以想像一下，一致性哈希算法，是將整個哈希值空間組成了一個虛擬的圓環，也就是哈希環。
如下圖，把 3 個組映射到固定大小為 2^32 的哈希環中。三個組一共將整個環分成了三個區域，C-A（第一組）、A-B（第二組）、B-C（第三組）。如下圖所示：
-
第一組負責存儲落在 C-A 區間內的數據。
-
第二組負責存儲落在 A-B 區間內的數據。
-
第三組負責存儲落在 B-C 區間內的數據。
士兵分配
假定編號為 9527 的士兵，進行哈希運算後，落到 C-A 區域。如下圖所示：
第二步，讓這個士兵順時針往前走，遇到的第一個節點 A 就是他所在的組了。如下圖所示:
增加分組
目前三個節點的時候，假定編號為 89757 的士兵經過哈希運算後，分配到了 B-C 區域（第三組），也就是屬於 C 節點管控。如下圖所示：
回到劉邦剛問的問題，如果分組變成四組，該怎麼進行士兵分配。
如下圖所示，增加一個節點 D，原來的區域 B-C 變成了區域 B-D（第三組） 和 D-C（第四組）。
那麼這名士兵屬於哪個節點管控呢？如下圖所示，士兵順時針往前走，先走到了 D 節點，所以屬於 D 節點管控。雖然還是屬於第三組，但是這名士兵的領導者已經變了：由 C 變成了 D。
從上面的變化來看，只有 B-C 區域中的部分數據會進行遷移：B-D 之間的數據會由 C 節點遷移到 D 節點。
而其他數據不受影響，也不用進行遷移。而且節點越多，需要遷移的數據就越少。這就是多多益善了~
劉邦看了後，大讚韓信：
不虧是大將軍，蕭何當時月下追你，值了！
哈希環缺陷
蕭何看了韓信畫的哈希環後，覺得有些不對勁，思索片刻後，對韓信說：
將軍，你這個哈希環上的節點分佈
不太均勻啊，你看第三組和第四組的的區域好小啊。
蕭何說得沒錯，確實存在這個問題，放到互聯網架構中，就存在如下問題：
節點分佈不均勻，導致業務對節點的訪問冷熱不均。
韓信眼中充滿着讚賞，知我者莫若蕭何。然後胸有成竹地說道：
你說得沒錯，不過我還有一個技能，
虛擬節點映射。
三技能：虛擬節點
一般虛擬節點比物理節點要多，並相對均勻地分佈在哈希環上。如下圖所示，12 個虛擬節點 N1~N12，相對均勻地分佈在虛擬節點上。如果有士兵屬於 N2/N3/N4 中的某一個，都會重新映射到 A 節點，依次類推，N5/N6/N7 屬於 B 節點的虛擬節點映射。
我們來看下蕭何的提出的問題，真實的 B-D 區域比較小，用虛擬節點後，N5/N6/N7 屬於 B 節點，N8/N9/N10 屬於 D 節點，他們分到的虛擬節點一樣多，而且區域大致相等。所以士兵的分配也比較均勻。
蕭何看了韓信的三技能後，直呼：妙哉妙哉！
總結
本篇通過韓信點兵的故事，然後從故事中衍生出劉邦、韓信、蕭何的對話，來講解士兵的分組的問題。現在對故事中的知識點做一個總結：
- 哈希算法會帶來增加或刪除節點時，數據遷移量太大的問題。
- 一致性哈希算法降低了數據遷移量。
- 節點較少，哈希環上每個節點實際佔據的區間大小不一，最終導致業務對節點的訪問冷熱不均。
- 引入虛擬節點映射解決了分佈不均問題。
- 節點越多時，使用哈希算法時，需要遷移的數據就越多，而使用一致性哈希算法，遷移的數據就越少。
- 一致性哈希算法本質上是一種路由尋址算法，適合簡單的路由尋址場景。
- 一致性哈希算法常用在負載均衡的架構設計中。
封面圖片來源王者榮耀。
往期推薦：
作者簡介：8 年互聯網經驗，擅長架構設計、分佈式、微服務。手寫了一套 SpringCloud 實戰教程，自主開發了 PMP 刷題小程序和 Java 刷題小程序。回復 pdf 領取。
