比照几个类似算法，了解Redis Cluster集群所应用算法的起因。首先介绍一下枯燥性：

枯燥性是指如果曾经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲退出到零碎中。哈希的后果应可能保障原有已调配的内容能够被映射到新的缓冲中去，而不会被映射到旧的缓冲汇合中的其余缓冲区。

一、HASH取余算法

简略公式:

hash(object)%N

利用场景:

比方你有 N 个 cache 服务器（前面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采纳相似上面的通用办法计算 object 的 hash 值，而后平均的映射到到 N 个 cache ；

所有都运行失常，再思考如下的两种状况；

1 一个 cache 服务器 m down 掉了（在理论利用中必须要思考这种状况），这样所有映射到 cache m 的对象都会生效，怎么办，须要把 cache m 从 cache 中移除，这时候 cache 是 N-1 台，映射公式变成了 hash(object)%(N-1) ；

2 因为拜访减轻，须要增加 cache ，这时候 cache 是 N+1 台，映射公式变成了 hash(object)%(N+1) ；

1 和 2 意味着什么？这意味着忽然之间简直所有的 cache 都生效了。对于服务器而言，这是一场劫难，洪水般的拜访都会间接冲向后盾服务器；

再来思考第三个问题，因为硬件能力越来越强，你可能想让前面增加的节点多做点活，显然下面的 hash 算法也做不到。

hash取余不满足枯燥性准则。

有什么办法能够扭转这个情况呢，这就是 一致性hash。

二、一致性hash算法

consistent hashing 是一种 hash 算法，简略的说，在移除 / 增加一个 cache 时，它可能尽可能小的扭转已存在key 映射关系，尽可能的满足枯燥性的要求。

在一致性hash算法中，将0到2^32-1区间的数字按顺时针造成一个圆环，如下图所示(图没有截全，请自行脑补)：

在redis集群中，将集群服务器的ip或者服务器名称进行hash函数，而后对2^32取模，失去的数字在上述圆环中定位，失去服务器在圆环中的地位。

当在redis集群中存入key时，对key进行hash函数，而后进行2^32取模，失去的数值就是该key在hash环上的地位。而后从该地位起，顺时针沿着圆环走，走到第一个服务器的地位，就是该key寄存的地位。如下图所示:

ObjectA通过hash()函数计算并进行2^32取模后，失去在hash环上的地位，而后顺时针找到第一个服务器地位，就是ObjectA寄存的地位。ObjectB也是同样的情理。

这么设计有何益处呢？咱们看下图:

在上图中，假如C服务器宕机了，那么此时，C服务器中寄存的key，会瞬移到D服务器中。同时，新退出的数据，通过计算失去在hash环上的地位后，顺时针查找服务器也会间接跳过C，寄存到D中。如此一来，服务器宕机不会影响到全副服务器中数据寄存。而是只影响了D服务器中数据的寄存内容。这就防止了在hash取余中宕机一台服务器，分母就会变动而导致所有服务器中数据都要变动的状况呈现。

同样的，当退出一台服务器时，也是在hash环中查找退出的地位，新的数据顺时针找到新加服务器后，会存入新加的服务器上，而不影响其余服务器的数据。可见，hash一致性算法满足了枯燥性准则。

那么hash一致性算法有何毛病呢？

如果当初有三台服务器A、B和C，通过计算，A和B在hash环上地位比拟近，B和C,C和A间隔比拟远。那么此时，顺时针落在C服务器和A服务器的数据概率就会变大。落在B服务器上的概率就小。这就呈现了 数据歪斜 的问题。不能平均调配数据。下图也是数据歪斜问题的一个体现:

三、hash槽位算法

针对一致性hash算法数据歪斜的问题，Reids Cluster进行了优化，衍生出了hash槽位算法。上面看是如何实现的。

redis集群中，有固定的槽位数:16384。redis会依据集群master数量，平均分配给每个master节点肯定数量的槽位。redis会依据key进行hash计算，并对16384进行取模，失去的后果就是槽位数。这个槽位调配给了哪个服务器，那么这条数据就寄存到哪个服务器上。

当产生redis集群扩容时，集群退出新节点后，须要执行reshard命令，进行从新hash调配。此时，redis会让用户输出调配新节点个数。个别就是16384个槽位/主节点数失去的值，对数据进行平分。抉择平分后，是之前的节点的每个节点，分一些key进去，给到新节点，来凑够新节点的个数。因为redis的槽位总数是固定16384个，新加一个节点，rehash一次后，槽位数和节点的对应关系必定会发生变化。就是原有节点拿出一部分槽位来，分给新退出节点。

因为新退出节点槽位是其余节点匀过去的，所以，其槽位数不是间断的，而是一段一段的。为何是其余节点匀过去，而不是全副重新分配一遍槽位呢，因为之前的节点曾经存入数据了，如果全副重新分配，那么曾经存入的key还须要重新整理，所以优先调配没有存入key值的槽位到新节点。

redis集群缩容就是将删除的槽位，平均分配给其余master节点来接收数据。

在redis cluster集群中，相当于是节点上放的是槽位，槽位里放的是数据。通过平均分配节点上的槽位，来防止一致性hash中数据歪斜的问题