一致性哈希
[TOC]
前言
伴随着系统流量的增大,出现了应用集群。在 Redis 中为了保证 Redis 的高可用也为 Redis 搭建了集群对数据进行分槽存放。在 Mysql数据库要存储的量达到一个很高的地步的时候,我们会对数据库进行分库分表操作。OK，到这儿先假设我们不知道什么是集群、什么是分库分表,我们先来看一个数据库水平切分演变的例子:
假设我们的系统中有一张会员表
customer_info, 我们的系统刚开始无人问津,我们在一个单个的数据库中放这张表，所有的会员记录都插入到这个数据库的这张表中，这没什么问题，是一个很正常且合理的操作。某段时间，我们的系统突然火爆了起来，注册会员激增，达到了千万级别并且还在快速增长，这时候所有的用户请求数据都会请求这张表，毫无疑问数据库的压力很大，于是可能会经常发生宕机事件，给系统造成了很大影响。为了解决这件事情，我们将单张表的数据切分到多个服务器上去，每个服务器具有相应的库与表，只是表中数据不同。 这样做能够有效的缓解单机数据库的压力和系统的性能瓶颈。
看完了这个例子,我们对水平拆分数据库有了一个大致的印象，其实就是把很多的数据按照一定的规则存放在不同的服务器上，然后查找的时候能够根据存放的时候的规则去找到前面存放的数据。那么我们要说的一致性哈希算法，其实就是解决了这里面的 存取规则 的问题，有了这个一致性哈希算法，我们能够准确的知道我们要取的数据落在哪个机器的哪个数据库中。
1. 简单哈希
还是上面水平拆分数据库的例子,假设我们现在不知道什么一致性哈希什么集群分槽，就让我们自己想的话，我们可以很容器的想到 java 中的 HashMap 的原理，它通过计算了一个 key 的哈希值，然后拿这个哈希值对底层数组取模就得到了一个哈希桶，如果数据存在的话，就一定在这个哈希桶里，否则就不存在。类似的可以想到，假设我们的 customer_info 我们可以按照用户id去分库分表，假设此时存在水平的三个库表,如下,我们分别称之为 节点D1,节点D2,节点D0
| 机器 ip | 数据库 | 数据表 |
|---|---|---|
| 127.0.0.1 | customer | customer_info |
| 127.0.0.2 | customer | customer_info |
| 127.0.0.3 | customer | customer_info |
分库分表的时候,用户 A 的记录落在了 D1 机器，用户 B 的记录落在了 D2 机器，用户 C 的机器落在了 D0 机器上，用户 A 要存在哪条数据库上的计算过程是用户 A 的会员 id 的哈希值对 3 取模，因为现在只有 3 台机器，伪代码: A_id.hash() % / 3，用户 B 和用户 C 依次类推。如下图所示
image.png
这好像很方便的解决了存取规则的问题，我们来分析一波:
假设我们的系统用户量又激增了，我们就需要再加一些机器,此时我们再计算哈希值的时候，取模不再是对 3 取模了，而是对 4 进行取模了，之前 A_id.hash() % / 3 = 1,而现在 A_id.hash() % / 4 = ? 这个值很大概率不会是 1，所以这就会出现用户明明存在记录但是却查不到的情况，这就问题很大了，如果要解决这个问题只能在机器节点数量变化的时候对数据重新哈希，这代价就有点大了。所以，我们需要想办法让这种情况不发生，这种情况发生的根本是哈希算法本身的特性导致的，直接使用取模的话这是无法避免的。所以就有了一致性哈希
2. 一致性哈希
上面通过数据库的例子介绍了哈希算法，然后也分析了它的劣势,当机器数量发生变动的时候，几乎所有的数据都会移动(不移动的应该是运气比较好吧前后取模都是同一个值)，这个代价很大。此时的问题从水平如何拆分变成了，当增加或者删除节点时，对于大多数记录，保证原来分配到的某个节点，现在仍然应该分配到那个节点，将数据迁移量的降到最低，这就是一致性哈希要做的事情。在这里我们不指定是数据库还是什么，反正都是分布式存储节点。
2.1 一致性哈希
一致性 Hash 算法也是使用取模的思想，只是，刚才描述的取模法是对节点数量进行取模，而一致性Hash算法是对 2^32 取模，什么意思呢？简单来说，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希环如下，从 0 ~ 2^32-1 代表的分别是一个个的节点,这个环也叫哈希环
image.png
然后我们将我们的节点进行一次哈希，按照一定的规则，比如按照 ip 地址的哈希值，让节点落在哈希环上。比如此时我们可能得到了如下图的环:
image.png
然后就是需要通过数据 key 找到对应的服务器然后存储了，我们约定,通过数据 key 的哈希值落在哈希环上的节点，如果命中了机器节点就落在这个机器上，否则落在顺时针直到碰到第一个机器。如下图所示 : A 的哈希值落在了 D2 节点的前面，往下找落在了 D2 机器上，D的哈希值 在 D1 节点的前面，往下找到了 D1 机器，B的哈希值刚好落在了D1 节点上，依次~~~
image.png
2.2 一致性哈希的分析
一致性哈希主要就是解决当机器减少或增加的时候，大面积的数据重新哈希的问题，主要从下面 2 个方向去考虑的，当节点宕机时，数据记录会被定位到下一个节点上，当新增节点的时候 ，相关区间内的数据记录就需要重新哈希。
2.2.1 某节点宕机
我们假设上图中的 节点 D2 因为一些原因宕机了,可以看到，只有数据 A 的记录需要重新重新定位存储到节点 D1 上，因为 D1 是 D2 的下一个节点，其它的数据都没有被影响到，此时被影响的仅仅是 图中的 D0-D2 这段区间的记录，也就是之前落在 D2 上的数据现在都要落到 D1 上面了。如下图
节点宕机
2.2.2 新增节点
我们假设我们需要增加一台机器，也就是增加一个节点D4，如下图所示，这个节点落在 D2-D1 之间，按照上述的哈希环上的哈希值落在节点的规则，那么此时之前落在 D2 到 D4 之间的数据都需要重新定位到新的节点上面了，而其它位置的数据是不需要有改变的。
新增节点
2.3 一致性哈希的数据倾斜问题
一致性Hash算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题。比如只有 2 台机器，这 2 台机器离的很近，那么顺时针第一个机器节点上将存在大量的数据，第二个机器节点上数据会很少。如下图所示，D0 机器承载了绝大多数的数据
数据倾斜
2.4 虚拟节点解决数据倾斜问题
为了避免出现数据倾斜问题，一致性 Hash 算法引入了虚拟节点的机制，也就是每个机器节点会进行多次哈希，最终每个机器节点在哈希环上会有多个虚拟节点存在，使用这种方式来大大削弱甚至避免数据倾斜问题。同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“D1#1”、“D1#2”、“D1#3”三个虚拟节点的数据均定位到 D1 上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。这也是 Dubbo 负载均衡中有一种一致性哈希负载均衡的实现思想。
虚拟节点
2.5 一致性哈希的应用案例
一致性哈希用到的地方很多，特别是中间件里面，比如 Dubbo 的负载均衡也有一种策略是一致性哈希策略，使用的就是虚拟节点实现的。Redis 集群中也用到了相关思想但是没有用它而是根据实际情况改进了一下。而对于存储数据的节点水平切分的时候它的作用就更不可代替了。and so on···
3. Redis 集群分槽的实现
Redis 集群并没有直接使用一致性哈希，而是使用了哈希槽 （slot） 的概念，Redis 没有直接使用哈希算法 hash()，而是使用了crc16校验算法。槽位其实就是一个个的空间的单位。其实哈希槽的本质和一致性哈希算法非常相似，不同点就是对于哈希空间的定义。一致性哈希的空间是一个圆环，节点分布是基于圆环的，无法很好的控制数据分布，可能会产生数据倾斜问题。而 Redis 的槽位空间是自定义分配的，类似于Windows盘分区的概念。这种分区是可以自定义大小，自定义位置的。Redis 集群包含了 16384 个哈希槽，每个 Key 经过计算后会落在一个具体的槽位上，而槽位具体在哪个机器上是用户自己根据自己机器的情况配置的，机器硬盘小的可以分配少一点槽位，硬盘大的可以分配多一点。如果节点硬盘都差不多则可以平均分配。所以哈希槽这种概念很好地解决了一致性哈希的弊端。
另外在容错性和扩展性上与一致性哈希一样，都是对受影响的数据进行转移而不影响其它的数据。而哈希槽本质上是对槽位的转移，把故障节点负责的槽位转移到其他正常的节点上。扩展节点也是一样，把其他节点上的槽位转移到新的节点上。
需要注意的是，对于槽位的转移和分派，Redis集群是不会自动进行的，而是需要人工配置的。所以Redis集群的高可用是依赖于节点的主从复制与主从间的自动故障转移。
Redis 分槽
