redis 中的一致性 hash

一致性 hash 解决的问题？

有 N 台机器，为了让数据均匀的存放在 N 台机器上，我们可以通过 hash%N 的方式进行映射定位，当其中某台机器挂掉了，我们需要将它踢出集群，此时机器数量为 N-1，那么存放关系变为 hash%(N-1)，我们需要将大量数据进行移动，保证映射关系正确，这是灾难性的。一致性 hash 解决的问题当新增和减少机器时尽量少的影响已有 key 的存储关系。

一致性 hash 采用环形 hash 空间，将环形分成了 0-16383 个槽，一般会通过物理机的 ip 或者机器名将物理机 hash 到环上的某个槽位，如下图所示，有三台机器(每一个槽位都是主从模式，所以最少是 3 主 3 从)，分别对应槽位 0、槽位 5201、槽位 9900，假如张三通过 CRC16hash 计算出来的槽位值为 12556，则顺时针的以一个机器槽位是机器 A，所以张三会存储在机器 A 中，李四和王五类似原理。

当某些原因机器 B 故障被踢出集群了，则只需要将李四从机器 b 移到机器 c 即可，其他节点数据不需要变动。

redis 集群虚拟节点？

虚拟节点是为了是数据分配更均匀。例如当机器 ABC 的 hash 分布如下左图所示，则很明显机器 A 会分配更多的数据，为了解决这种不平均分配问题，可以采用下右图的虚拟节点方式，每个实际节点分配到对应的虚拟节点

为什么是 2 的 14 次方=16384 个槽位？

因为集群节点之间会通过 ping/pong 进行通信，通信的内容中包括一个 bitmap 类型的数组，数据大小与槽位个数相关，当槽位为 16384 的时候，数据大小为 2Kb(16384/8/1024=2Kb)，如果槽位个数为 65536，则通信的数据大小为 8Kb。而节点之间的通信 1s 中会执行 10 次，所以如果槽位较多的话会导致暂用过多的通信带宽。

redisCluster 使用的 hash 算法是什么？

RedisCluster 目前使用的计算 slot 槽位的算法为 CRC16 ，该算法本身会产生的 hash 值的大小为 16bit ，因此该算法可以产生 2^16=65536 个不同的值，取值范围为 0～65535 之间