每天进步一点点，坚持下去，你总是会不一样的。加油！
最近在整理java常用的一些基础、ZooKeeper、Spring全家桶、源码、Dubbo、Elasticsearch、Redis、MySql、RabbitMQ、Kafka、Linux 、微服务等技术栈。
今天主要分享的是一致性hash是什么？解决了什么问题？
二、简单哈希
三、一致性哈希
四、一致性哈希的数据倾斜问题
五、 Redis 集群分槽的实现
一、前言
假设我们的网站有个用户表，建站初期，人流很少，系统平稳运行。随着慢慢发展，运营力度的提高，我们的网站爆发式增长。用户从几十万到千万级的提升。单表难以正常抗压，我们急需要进行表的拆分，分到不同的机器上。
上面这个例子，其实就是把我们的数据按照一定的规则进行分散存储，然后取的时候直接按这个规则去取。其实这种规则就是我们的一致性哈希算法，就是为了解决了这里面的
存取规则
的问题，有了这个规则，我们就知道数据存在哪，需要从哪里去取。
二、简单哈希
我们很容易想到的 HashMap 的哈希code，计算 key 的哈希值，然后拿这个哈希值对底层数组取模就得到了一个哈希桶，如果数据存在的话，就一定在这个哈希桶里，否则就不存在。
比如我们的用户表，我们可以按照用户id去分库分表，假设此时存在水平的三个库表，如下，我们分别称之为 节点D1，节点D2，节点D0
| 机器 ip |
数据库 |
数据表 |
| 127.0.0.1 |
member
|
user_info |
| 127.0.0.2 |
member |
user_info |
| 127.0.0.3 |
member |
user_info |
假设用户 A 的记录落在了 D1 机器，用户 B 的记录落在了 D2 机器，用户 C 的机器落在了 D0 机器上，用户 A 要存在哪条数据库上的计算过程是用户 A 的用户 id 的哈希值对 3 取模，因为现在只有 3 台机器，伪代码:
A_id.hash() % / 3，
用户 B 和用户 C 依次类推。
假设我们的系统用户量又激增了，我们又需要扩容，此时我们再计算哈希值的时候，取模不再是对 3 取模了，而是对 4 进行取模了，之前
A_id.hash() % / 3 = 1
而现在
A_id.hash() % / 4 = ?
这个值很大概率不会是 1，所以这就会出现用户明明存在记录但是却查不到的情况，这个问题就很严重了，如果要解决这个问题只能在机器节点数量变化的时候对数据重新哈希，这样的话代价是很大的。
所以，我们需要想办法让这种情况不发生，这种情况发生的根本是哈希算法本身的特性导致的，直接使用取模的话这是无法避免的。所以就有了一致性哈希。
三、一致性哈希
我们已经通过数据库的例子介绍了哈希算法，然后也分析了它的劣势，当机器数量变动的时候，全部数据都要重新处理，这个显然不可取。
好的，那么到这里，我们需要解决的问题就是：当增加或者删除节点时，对于大多数记录，保证原来分配到的某个节点，现在仍然应该分配到那个节点，将数据迁移量的降到最低，这就是我们的一致性哈希要做的事情。
1、一致性哈希
一致性 Hash 算法也是使用取模的思想，只是，刚才描述的取模法是对节点数量进行取模，而一致性Hash算法是对
2^32
取模，什么意思呢？简单来说，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为
0-2^32-1
（即哈希值是一个32位无符号整形），整个哈希环如下，从
0 ~ 2^32-1
代表的分别是一个个的节点,这个环也叫哈希环。
我们将节点进行一次哈希，按照一定的规则，比如我们按照 ip 地址的哈希值，让节点落在哈希环上。比如此时我们可能得到了如下图的环
这样我们就可以根据 key 找到对应的服务器然后存储了，我们这样规定，通过数据 key 的哈希值落在哈希环上的节点，如果命中了机器节点就落在这个机器上，否则落在顺时针直到碰到第一个机器。
如下图所示 : A 的哈希值落在了 D2 节点的前面，往下找落在了 D2 机器上，D的哈希值 在 D1 节点的前面，往下找到了 D1 机器，B的哈希值刚好落在了D1 节点上。
2、一致性哈希的分析
一致性哈希主要就是解决当机器减少或增加的时候，大面积的数据重新哈希的问题。
当某个节点宕机时，数据记录会被定位到下一个节点上；
当新增节点的时候 ，相关区间内的数据记录就需要重新哈希。
2.1、某节点宕机
我们假设上图中的节点 D2 因为一些其他原因宕机了，我们可以看到，只有数据 A 的记录需要重新进行定位存储到节点 D1 上，因为 D1 是 D2 的下一个节点，其它的数据都没有被影响到，被影响的仅仅是 图中的 D0-D2 这段区间的记录，之前落在 D2 上的数据现在都要落到 D1 上面了，具体如下图。
2.2、新增节点
同理，如果我们需要增加一台机器，也就是增加一个节点D4，如下图所示，这个节点落在 D1-D2 之间，按照我们上面说的规则，那么此时之前落在 D2 到 D4 之间的数据需要重新按照规则落到新节点上，其它位置的数据不用改变。
四、一致性哈希的数据倾斜问题
一致性Hash算法在服务节点太少的时候，会因为节点分布不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题。
如下图所示，假如我们只有两台机器，这两台机器离的很近，那么顺时针第一个机器节点上将存在大量的数据，第二个机器节点上数据会很少。如下图所示，D0 机器承载了绝大多数的数据
虚拟节点解决数据倾斜问题
为了避免出现数据倾斜问题，一致性 Hash 算法引入了虚拟节点的机制，也就是我们的每个机器节都点会进行多次哈希，最终在我们的哈希环上会有多个虚拟节点存在，这种方式就能削弱甚至避免数据倾斜问题。
通常将虚拟节点数设置为32甚至更大，这样一来，即使服务节点数很少也能做到相对均匀的数据分布。这也是 Dubbo 一致性哈希负载均衡的实现思想。
五、 Redis 集群分槽的实现
Redis 集群并没有直接使用一致性哈希，而是使用了
哈希槽 （slot）
的概念，Redis 没有直接使用哈希算法 hash()，而是使用了
crc16
校验算法
。槽位其实就是一个个的空间的单位。
Redis 集群包含了
16384
个哈希槽，每个 Key 经过计算后会落在一个具体的槽位上，而槽位具体在哪个机器上是用户自己根据自己机器的情况配置的，机器硬盘小的可以分配少一点槽位，硬盘大的可以分配多一点。如果节点硬盘都差不多则可以平均分配。所以哈希槽这种概念很好地解决了一致性哈希的弊端。
- END -
好了，以上就是今天的内容。有错误的地方欢迎指正。快分享给你的朋友，一起学习吧！
