共计 2164 个字符，预计需要花费 6 分钟才能阅读完成。
比照几个类似算法，了解 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 中数据歪斜的问题
