【redis】一致性hash算法和hash槽

普通hash取模

直接hash(key)%N , N为机器的数量，但不利于集器扩容或者缩容

一致性hash算法和hash槽

一致性hash算法是在redis 分片中使用，hash槽在redis cluster（集群）中使用

Redis一致性hash：Redis一致性hash是为了解决分布式环境下，数据分片的问题。在Redis集群中，数据是分布在不同的节点上的，这个过程就是数据分片。

Hash槽：在Redis中，数据是以hash槽的形式存储在不同的节点上的。Redis会根据key和节点的数量进行hash运算，然后将得到的结果对节点数量进行取模运算，最终得到的结果就是该key应该存储的hash槽。

一致性hash算法

应用场景：分布式缓存系统

Redis一致性hash是为了解决分布式环境下，数据分片的问题。在Redis集群中，数据是分布在不同的节点上的，这个过程就是数据分片

hash环

一致性hash是指将 “存储节点” 和 “数据” 都映射到一个首尾相连的hash环上。如果增删节点，仅影响该节点在hash环上顺时针相邻的后继节点，其他数据不会受到影响。

第一步：对存储节点进行哈希计算，也就是对存储节点做哈希映射，比如根据节点的 IP 地址进行哈希
假设有四个节点 Node A、B、C、D，经过 ip 地址的哈希计算，它们的位置如下：

第二步：当对数据进行存储或访问时，对数据进行哈希映射；
有4个存储对象 Object A、B、C、D，经过对 Key 的哈希计算后，它们的位置如下：

如何确定数据位于hash环上的位置？

对于各个 Object，它所真正的存储位置是按顺时针找到的第一个存储节点。例如 Object A 顺时针找到的第一个节点是 Node A，所以 Node A 负责存储 Object A，Object B 存储在 Node B。

一致性哈希算法大概如此，那么它的容错性和扩展性如何呢？

假设 Node C 节点挂掉了，Object C 的存储丢失，那么它顺时针找到的最新节点是 Node D。也就是说 Node C 挂掉了，受影响仅仅包括 Node B 到 Node C 区间的数据，并且这些数据会转移到 Node D 进行存储。

同理，假设现在数据量大了，需要增加一台节点 Node X。Node X 的位置在 Node B 到 Node C 直接，那么受到影响的仅仅是 Node B 到 Node X 间的数据，它们要重新落到 Node X 上。

一致性Hash算法使用 “取模法”，且是对 2^ 32次方取模，其可表示的范围为：0 ~ 2^32-1

与普通的hash算法有何不同？

普通的hash算法是对节点数进行hash，而一致性hash是对固定值 2^32 进行取模

易产生问题：数据倾斜

但是一致性哈希算法不能够均匀的分布节点，会出现大量请求都集中在一个节点的情况，在这种情况下进行容灾与扩容时，容易出现雪崩的连锁反应。

当在服务器节点数量太少的时候，容易出现分布不均而导致数据倾斜。

数据倾斜解决方法：虚拟节点映射

为了解决一致性哈希算法不能够均匀的分布节点的问题，就需要引入虚拟节点，对一个真实节点做多个副本。不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。

映射关系：缓存数据 ➜ 虚拟节点 ➜ 真实节点

虚拟节点映射物理节点，redis哈希槽的数量是16384个，redis cluster采用的是 CRC16(key) % 16384 算法

个人理解：其实也就是通过构造大量的虚拟节点映射，使得当向redis集群中存储k-v时，hash取模的值可以更大，这样对数据取模后的结果也就更加分散（所有数据穿插分散在不同真实节点上）！

在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

具体做法：可以在服务器IP或主机名的后面增加编号来实现，例如上面的情况，可以为每个服务节点增加三个虚拟节点，于是可以分为：RedisService1#1、 RedisService1#2、 RedisService1#3、 RedisService2#1、 RedisService2#2、 RedisService2#3

对于hash环来说，节点越多，数据分布越平稳。所以采用虚拟节点的方式，将一个节点虚拟成多个节点，保证环上有1000~2000个节点最佳。

一般10个Redis服务器的集群，每个节点可以虚拟100-200个节点，保证环上有1000-2000个节点

一般5个Redis集群，则每个节点虚拟200-400个节点，保证节点数是1000-2000之间，这样才能保证数据分布均衡

引入虚拟节点后，会提高节点的均衡度，还会提高系统的稳定性。

优点

一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

新增服务器节点/删除服务器节点： 在hash环中新增服务器，也是通过hash算法确认分布，只需要移动一小部分数据即可；移除也是同理

应用

在redis集群（主从、哨兵）、缓存中间件memcached中都有使用到它

hash槽

基本概念：槽可以理解为分区，数据都是存放在分区中的，然后分区与机器进行动态绑定。

redis-cluster把所有的“物理节点”映射到 [0-16383] 槽上（不一定是平均分配）,cluster 负责维护node ⇌ slot ⇌ value。

redis集群（cluster）并没有选用上面一致性哈希，而是采用了哈希槽（slot）的这种概念。主要的原因就是上面所说的，一致性哈希算法对于数据分布、节点位置的控制并不是很友好。

产生原因

如果Redis只用复制功能做主从，那么当数据量巨大的情况下，单机情况下可能已经承受不下一份数据，更不用说是主从都要各自保存一份完整数据。在这种情况下，数据分片是一个非常好的解决办法。因此可以借助hash槽自动对数据分片，并落到各个节点上分散存储。通过为每个节点指派不同数量的槽，可以控制不同节点负责的数据量和请求数。

hash方式：一个redis集群包含 16384 个哈希槽，数据库中的每个数据都属于这16384个哈希槽中的一个。集群使用公式 CRC16(key) % 16384 来计算键 key 属于哪个槽。一个redis节点包含N个槽，数据通过hash算法哈希到固定的槽里，所以槽只是决定了数据的存放位置，当多个数据hash出来的结果相同时，他们就被分配到相同的槽里，即也会映射到相同的服务节点上。

一致性hash算法和hash槽的本质区别

其实哈希槽的本质和一致性哈希算法非常相似，不同点就是对于哈希空间的定义。一致性哈希的空间是一个圆环，节点分布是基于圆环的，无法很好的控制数据分布。而 redis cluster 的槽位空间是自定义分配的，类似于 windows 盘分区的概念。这种分区是可以自定义大小，自定义位置的。

为什么redis集群不采用一致性哈希算法？

一致性哈希的节点分布基于圆环，无法很好的手动控制数据分布，比如有些节点的硬件差，希望少存一点数据，这种很难操作（还得通过虚拟节点映射，总之较繁琐）。
而redis集群的槽位空间是可以用户手动自定义分配的，类似于 windows 盘分区的概念，可以手动控制大小。例如机器硬盘小的，可以分配少一点槽位，硬盘大的可以分配多一点。
其实，无论是一致性哈希还是哈希槽的方式，在增减节点的时候，都会对一部分数据产生影响，都需要我们迁移数据，当然，redis集群也提供了相关手动迁移槽数据的命令。