韩信的指兵成语来自淮安民间传说。通常搭配越多越好。意思越多越好。我们来看看主人公刘邦与韩信将军的对话。刘邦：“你看我能带多少兵马？”韩信：“最多十万。””刘邦不解地问道：“那你呢？韩信得意道：“越多越好，越多越好！韩信的一千名士兵，需要大致分为三组。士兵的数量是六位数，从1到100000之间随机分配。比如，第一个士兵的数值是245，第二个士兵的数量是82593，其他士兵的数量类似。那怎么分配士兵？刘邦：韩将军，你如何分配这些士兵？韩信：这不是easy，我一个技能就搞定一技能：哈希算法分组韩信的一技能哈希算法：取士兵的编号num值作为哈希值，然后对分组总数N进行取余运算。如果结果在0到N-1之间，则该士兵属于该组。如下图所示，每个士兵都有一个六位的哈希值（也叫序号），然后除以Hanxin除以3求余数，分配到三组。例如，数字12345第一组6名士兵，除以3后余数为0，所以分配到第一组。士兵已通过哈希算法分组。如果你想找到编号为666666的士兵，应该怎么找呢？先把666666除以3，余数为0，说明在第一组，然后去第一组找。这里有朋友可能会问，为什么不把所有的士兵都放在一个团里呢？因为一组太大，会影响行军速度。映射到互联网架构上，就是通过增加节点来降低单个节点的负载压力。哈希分组的缺点。刘邦见此身手，大呼：韩将军真厉害。哈希算法看起来很完美。那我再给你500个兵，需要分成四组怎么办？这时候，韩信的副将说道：这也不容易，用4个来取余还不行吗？刘邦摸着下巴想了想，对副将说：这个计划是可行的，但许多士兵已经重新集结，刚刚建立的团队友谊已经破裂。且看刘邦为何认为方案不可行。例如，编号为3的士兵原本被分配到一个组，当它被分成四组时，按公式计算：3%4=3，所以它会被分配到第四组。以此类推，会发现很多士兵被重新编组，只有一小部分不会换组，比如1、2、12不会重新编组。韩信对刘邦点了点头，对主公说：“主公您说得对，这是我第一功夫的弱点。”但我还有一项技能：一致性哈希。二技能：Consistenthash哈希环consistenthash算法也是使用取模运算，但它与hash算法不同的是：Hash算法：对节点数进行取模运算。一致性哈希算法：对2^32进行取模运算。可以想象，一致性哈希算法通过形成整个哈希值空间，形成了一个虚拟环，也就是哈希环。如下图所示，三个组映射到一个固定大小为2^32的哈希环。三组将整个环划分为三个区域，C-A（第一组）、A-B（第二组）、B-C（第三组）。如下图所示：分为三组第一组负责存储C-A范围内的数据。第二组负责存储A-B范围内的数据。第三组负责存储B-C范围内的数据。士兵分配假设士兵编号9527，经过哈希处理后，属于区域C-A。如下图：士兵站立的第二步，让士兵顺时针前行，遇到的第一个节点A就是他的组。如下图所示：当遇到顺时针第一个节点增加当前三个节点的分组时，假设编号为89757的士兵经过哈希运算后分配到B-C区（第三组），即属于C节点的控制。如下图：属于C的节点回到了刘邦刚提出的问题，如果分组变成四组，士兵应该怎么分配。如下图，增加一个节点D，原来的区域B-C变成区域B-D（第三组）和D-C（第四组）。添加D节点，那么这个士兵属于哪个节点呢？如下图，小兵顺时针走，最先到达D节点，所以属于D节点控制。虽然还是属于第三组，但是这个小兵的leader发生了变化：从C变成了D。leader发生了变化从上面的变化来看，只会迁移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节点。它们被分配了尽可能多的虚拟节点。,面积大致相等。因此，士兵的分布比较均匀。看到韩信的三技能后，萧何叫道：喵仔喵仔！通过韩信点兵的故事来概括本文，然后从故事中推导出刘邦与韩信、萧何的对话来说明编兵问题。现在对故事中的知识点做一个总结：哈希算法会带来节点增删时数据迁移过多的问题。一致性哈希算法减少了数据迁移量。节点较少，哈希环上每个节点实际占用的区间不同，最终导致业务访问节点不均。虚拟节点映射的引入解决了分布不均的问题。节点越多，使用哈希算法时需要迁移的数据越多，使用一致性哈希算法时需要迁移的数据越少。一致性哈希算法本质上是一种路由寻址算法，适用于简单的路由寻址场景。一致性哈希算法常用于负载均衡的架构设计中。本文转载自微信公众号“悟空聊天结构”，可通过以下二维码关注。转载本文请联系悟空聊天架构公众号。
