一致性哈希

   一、什么是一致性哈希
    一致性哈希是一种用于分布式系统中数据分片和负载均衡的算法。它的核心思想是将数据和节点通过哈希函数映射到一个固定范围的环形空间中，每个节点在环上占据一个位置，而数据则根据哈希函数计算出的值映射到环上的某个位置上。目前主要应用于分布式缓存当中。

    可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。

   二、普通哈希的问题

    1.  负载均衡

    分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是集群管理最基本的功能。如果采用常用的hash(object)%N 取模的方式，在节点进行添加或者删除后，需要重新进行迁移改变映射关系，否则可能导致原有的数据无法找到。

    比如：随着业务和流量的增加，假如我们的Redis查询服务节点扩展到了3个，为了将查询请求进行均衡，每次请求都在相同的Redis中，使用hv = hash(key) % 3的方式计算，对每次查询请求都通过hash值计算，得出来0、1 、2的值分别对应服务节点的编号，计算得到的hv的值就去对应的节点处理。

    但是这里有个问题，服务增减是需要对此时的key进行重新计算，比如减少一个服务的时候，此时需要按 hv = hash(key) % 2计算，而增加一个服务节点的时候需要按 hv = hash(key) % 4计算，而这种取模基数的变化会改变大部分原来的映射关系，导致数据查询不到。

    也就是说在对系统做扩容或者缩容时，必须迁移改变了映射关系的数据，否则会出现查询不到数据的问题。

    我们应该要重新想一个新的算法，来避免分布式系统在扩容或者缩容时，发生过多的数据迁移。而一致性哈希算法显然是一个更好选择！

    三、一致性哈希算法

    一致性哈希算法就很好地解决了分布式系统在扩容或者缩容时，发生过多的数据迁移的问题。一致性哈希同样使用了取模的方式，不同的是对 2^32 这个固定的值进行取模运算。

   1. 哈希环

   首先，我们把全量的缓存空间当做一个环形存储结构。环形空间总共分成2^32个缓存区。通过对 2^32 进行取模运算的结果值虚拟成一个圆环，环上的刻度对应一个 0~2^32 - 1 之间的数值。如下图：

   1） 节点入环

   一致性哈希要进行两步哈希：

   第一步：对存储节点进行哈希计算，也就是对存储节点做哈希映射，比如根据节点的 IP 地址进行哈希；

   第二步：当对数据进行存储或访问时，对数据进行哈希映射；

   所以，一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上。

   2） 新增节点

   当缓存集群的节点有所增加的时候，普通哈希算法会导致原有哈希映射大面积失效。而一致性哈希整个环形空间的映射仍然会保持顺时针规则，只有一小部分key的归属会受到影响。

3） 删除节点

2. 对「数据」进行哈希映射得到的结果要怎么找到存储该数据的「节点」呢？

映射的结果值往顺时针的方向的找到第一个节点，就是存储该数据的节点。

因此，在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。

3. 不平衡
我们通过新增节点和删除节点，知道了该方式会影响该节点的顺时针的后一个节点，其他节点不受影响。

但是因为生成哈希值的分布并不是均匀的，如下图新增k4、k5，如果节点B宕机了，k2和k4也迁移到节点C，导致那么大部分请求就落到节点C了，如果数量更多呢，此时会导致节点C压力陡增，这样就不均衡了！

4. 如何通过虚拟节点提高均衡度？

要想解决节点在哈希环上分配不均匀的问题，就是要有大量的节点，节点数越多，哈希环上的节点分布的就越均匀。

但问题是，实际中我们没有那么多节点。为了优化这种节点太少而产生的不均衡情况，一致性哈希算法引入了[虚拟节点]的概念。也就是对一个真实节点做多个副本。

具体做法是，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。

比如对每个节点分别设置 3 个虚拟节点：

对节点 A 加上编号来作为虚拟节点：A-01、A-02、A-03
对节点 B 加上编号来作为虚拟节点：B-01、B-02、B-03
对节点 C 加上编号来作为虚拟节点：C-01、C-02、C-03

五、为什么一致性哈希算法更多地应用在分布式缓存

由于分布式缓存系统的节点部署变化更频繁，而传统关系型数据库的分库分表相对稳定。不过说到mysq1，在水平分库分表的过程中， 仍然可以采用一致性哈希的思想。虽然这样的处理逻辑会复杂一些，却可以避免动态水平扩展时候的问题。