求模，也就是 key % 节点数 N, 当节点数量变化时（如服务器扩容 / 下线），几乎所有数据的映射关系都会失效，导致大量数据需要重新迁移，引发 “哈希雪崩”。
| key的hash值 | 节点数 | 求模 |
|---|---|---|
| 10 | 3 | 10 % 3 = 1 |
| 11 | 3 | 11 % 3 = 2 |
| 12 | 3 | 12 % 3 = 0 |
| 10 | 4 | 10 % 4 = 2 |
| 11 | 4 | 11 % 4 = 3 |
| 12 | 4 | 12 % 4 = 0 |
此时可以看到之前分配到1，2，0节点的key，需要被重新移动到2，3，0。也就是75%的数据需要移动。
如果这个总数是20亿呢？这会是一场灾难
那如何解决这个问题呢？
正所谓头痛医头，脚痛医脚。既然是因为分母发生变化导致，那我想个办法让分母不变不就解决这个问题了？
聪明的小伙伴已经想到了，把分母设为int最大值2³²-1即可。
这时候新的问题又来了，2³²-1=4294967295 这么大的一个分母(节点数)，任何数求模余数都是他自己，这就失去了求模的意义，求模的本质是为了对hash瘦身，你倒好又绕回来了，因此这条路走不通，但也提供了灵感。
因此，在1997年，consistent hash算法被提出，它结合了环形数组与上述的灵感。将hash算法的输出范围抽象成一个圆环，并hash值限定为0-2³²-1。
把每一个节点(Node)算出一个hash值，放在hash ring对应的位置上
假设有3个节点
将要存储的数据(key)也通过相同的算法计算出hash值，放在hash ring对应的位置上
假设有1000个key，数据映射到环后，
顺时针方向寻找第一个遇到的节点，该节点就是存储key的节点
当要动态增删节点时，一致性hash只会影响hash ring上相邻节点的部份数据，而不是迁移所有数据，这极大减少了数据迁移量
删除结节也同理，就是一个在hash ring上此消彼长的过程。
让我们再回到此图，在最初的3个节点中，我们会发现一丝丝不和谐的因素，蓝色节点中keys的数量为103，绿色节点keys的数量为572，红色节点的keys数量为325，他们之间的分配并不均衡。
当节点较少时，keys可能集中分布在某一个特定节点，导致旱的旱死，涝的涝死，这便是数据倾斜。
那如何优化呢？在计算机中，没有什么是不能通过增加一层中间层能解决的。
为每个物理节点创建多个"虚拟节点"，由虚拟节点代替物理节点，映射到hash ring上
有了理论支撑，在具体落地的过程中，发生了细微变化。但核心目标依旧不变：当节点变化时，数据最小化迁移。
| Consistend Hash | Hash Slot | |
|---|---|---|
| 空间初始化 | 构建 0~2³²-1 的hash ring。 | 划分固定数量的Hash Slot，比如Redis的16384个槽。 |
| 数据映射 | 通过hash(key)映射到ring上的某个点，顺时针找到最近节点 | 通过hash(key)得到hash，再通过hash%槽总数得到槽编号，最后通过槽编号与节点的映射关系得到所属节点。 |
| 节点映射 | 计算节点的hash值，比如(IP+端口)，直接映射到环上 | 节点不直接映射，而是通过维护与槽位的映射关系，如节点 A 负责槽 0~5460，节点 B 负责槽 5461~10922 |
| Consisten hash痛点 | Hash Slot方案 |
|---|---|
| 数据倾斜 | 槽的数量足够大，且槽数量在节点之间均匀分配，比如Redis有16384个槽，假设3个节点，每个节点分配5461个槽，因为槽的数量很大，所以天然避免数据倾斜 |
| 数据迁移颗粒度大 | 迁移粒度从 “节点级” 缩小到 “槽级”—— 节点扩容 / 缩容时，仅需迁移 “待分配 / 释放的槽”（而非整个节点的数据） |
事实上，Hash Slot与Consistend Hash在思想上没有本质上的差别。你也可以创建16384个虚拟节点来对标Hash Slot，只是工程化难度不同的选择而已
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。
