这是悟空的第 78 篇原创文章。
> 本文已收录 Github：https://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 节点，他们分到的虚拟节点一样多，而且区域大致相等。所以士兵的分配也比较均匀。
> 萧何看了韩信的三技能后，直呼：妙哉妙哉！
## 总结
本篇通过韩信点兵的故事，然后从故事中衍生出刘邦、韩信、萧何的对话，来讲解士兵的分组的问题。现在对故事中的知识点做一个总结：
- 哈希算法会带来增加或删除节点时，**数据迁移**量太大的问题。
- 一致性哈希算法**降低**了数据迁移量。
- 节点较少，哈希环上每个节点实际占据的区间大小不一，最终导致业务对节点的访问**冷热不均**。
- 引入**虚拟节点映射**解决了分布不均问题。
- 节点**越多**时，使用哈希算法时，需要迁移的数据就**越多**，而使用一致性哈希算法，迁移的数据就**越少**。
- 一致性哈希算法本质上是一种**路由寻址**算法，适合简单的路由寻址场景。
- 一致性哈希算法常用在负载均衡的架构设计中。
封面图片来源王者荣耀。
往期推荐：
[四：用动图讲解分布式 Raft](http://mp.weixin.qq.com/s?__biz=MzAwMjI0ODk0NA==&mid=2451950743&idx=1&sn=df1c600f636c8d9b119f534750c007eb&chksm=8d1c3508ba6bbc1e6e4def2ea4c25d9c5e69013d463af31f6bc78cacbc3735ccea455842303d&scene=21#wechat_redirect)
[三：诸葛亮 VS 庞统，拿下分布式 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 年互联网经验，擅长架构设计、分布式、微服务。手写了一套 SpringCloud 实战教程，自主开发了 PMP 刷题小程序和 Java 刷题小程序。回复 pdf 领取。
