分布式Redis（14）哈希槽

带着问题阅读

1. 一致性 Hash 的增删节点操作原理
2. 如何防止增删节点导致连接不平衡问题
3. 哈希槽和一致性 Hash 的不同之处以及优点
4. 哈希槽为什么使用 16384 个

一致性哈希算法

理论

一致性哈希算法是一种常用的分布式算法，其主要用途是在分布式系统中，将数据根据其键（key）进行散列（hash），然后将散列结果映射到环上，再根据数据节点的数量，将环划分为多个区间，每个节点负责处理环上一定区间范围内的数据。

普通哈希的问题

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

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

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

这个时候只能进行数据迁移，真是太麻烦了，而一致性哈希算法显然是一个更好选择！

一致性hash算法

一致性哈希同样使用了取模的方式，不同的是对 2^32 这个固定的值进行取模运算。
在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n 个关键字重新映射，其中K是关键字的数量， n是槽位数量，而不需要对所有的映射关系进行重新映射！

Hash环
我们可以把一致哈希算法是对 2^32 进行取模运算的结果值虚拟成一个圆环，环上的刻度对应一个 0~2^32 - 1 之间的数值，如下图：

节点入环

不平衡问题
我们通过新增节点和删除节点，知道了该方式会影响该节点的顺时针的后一个节点，其他节点不受影响。
但是因为生成哈希值的分布并不是均匀的，如下图新增k4、k5，如果节点B宕机了，k2和k4也迁移到节点C，导致那么大部分请求就落到节点C了，如果数量更多呢，此时会导致节点C压力陡增，这样就不均衡了！

那如何解决这个问题呢？那就是通过 虚拟节点
虚拟节点
虚拟节点 可以理解为是作为实际节点的一个copy，多个虚拟节点映射一个实际节点，因为在哈希环上节点越多就分布的越均匀，即使我们现实中不会有那么多真实节点。

上图中三个真实节点A、B、C，映射了9个虚拟节点，如果key值经过哈希落到临近A-1、A-2、A-3的虚拟节点，那么最终都将映射到真实节点A，你想如果虚拟节点再多点，是不是就会更均衡了！
假设真实节点A被移除，A对应虚拟节点也会移除，但是多虚拟节点方式可以映射更多真实节点，让剩余的节点更好得去承担节点变化的请求压力！
如下图：

这里简单讲解一下，图中真实节点A被移除，那么对应的虚拟节点移除，那么此时k1的重新映射到C-1、k3重新映射到B-3，也就是说被迁移到真实节点B和C，由此可见节点被移除会被更均衡的分散到其他节点上。图中只简单列举了几个虚拟节点，虚拟节点越多，相对会越均衡。

Redis 使用哈希槽

不知道朋友们记不记得Redis Cluster的实现，也是用了Hash的方式将键值按照一定算法分配到各个节点的，但是却没有使用一致性哈希算法，而是引入了哈希槽的概念!
这是为什么呢？我们先看下一致性哈希和哈希槽在计算上的区别

图中A、B、C表示的是三个节点，k1和k2表示的是key：一致性哈希是经过 hash() 函数计算后对 2^32 取模的值虚拟成一个圆环
哈希槽是将每个key通过CRC16计算得到一个16bit的值，然后16bit值再对16384取模来决定放置哪个槽
虽说在计算方式上有区别，好像都解决了数据均衡的问题，应该都是不错的选择。
OK，本文将先对Redis集群节点增减时如何进行哈希槽的分配进行分享，再回过头看为什么Redis 集群没有使用一致性hash，而是引入了哈希槽的概念的原因究竟是什么！

Redis Cluster集群

Redis集群是一种分布式数据库方案，通过服务器分片技术进行数据管理，我们来对它进行一个归纳总结。

哈希槽
集群将数据划分为 16384 （2^14）个槽位（哈希槽），每个Redis服务节点分配了一部分槽位，因为槽位的信息存储于每个节点中，客户端请求的key通过CRC16校验后对16384取模来决定放置哪个槽，这样也就定位到指定的节点中。

上图中 key 【小许】和【code】经过 CRC16 计算后再对哈希槽总个数 16384 取模，得到哈希槽位置分别是在888的节点A上和10924的节点C上面。
重点：每个节点都会记录哪些槽分配给了自己，哪些槽被分配给了其他节点

增加节点

新增一个节点D，redis cluster的这种做法是从各个节点的前面各拿取一部分slot(槽)到D上，会变成这样：

此时服务A、B、C、D通过分配各自有了对应的哈希槽，新增节点后集群会自动进行哈希槽的重新平均分配，比如上图中四个节点中每个节点的槽位数是：18384 / 4 = 4096。
当然这个你使用命令 【cluster addslots】为每个节点自定义分配槽的数量，这里有个特点，如果我们节点的机器性能有差异，那就可以为性能好的，配置更多槽位，更好的利用机器性能。

减少节点
如果减少一个节点C，redis cluster同样会自动进行槽数量的重新计算分配，然后后变成下面样子：

删除节点C之后，此时服务A、B节点中每个节点的槽位数是：18384 / 2 = 8192

客户端访问节点数据
Redis cluster的主节点各自负责一部分槽，我们来看下来自客户端的请求的key是如何定位到具体的节点，然后返回对应的数据的。

来自Redis-Cli客户端的请求连接到的是集群中的任何一个节点
● 首先检查当前key是否存在集群中的节点
● 通过CRC16（key）/ 16384计算出slot
● 查询负责该slot负责的节点是否存在
● 在该节点的话就直接就直接返回key对应的结果
● 不在该节点的话，那么会 MOVED重定向（包含槽位和目标地址）指引客户端转向至正确的节点，并再次发送之前执行的命令

为什么Redis是使用哈希槽而不是一致性哈希呢？

有人可能会说是当节点太少时，一致性哈希容易数据分布不均匀更容易导致雪崩。
但是看过我开头分享的一致性哈希文章，通过引入虚拟节点是基本可以避免这个问题的
如果非要说极限情况，那么Redis哈希槽，也有可能某些hash 区间的值特别多，然后导致该节点导访问过于集中的问题。
抛开这些极端情况，通过上面对哈希槽的总结，以下这些是更值得信服的回答：

• 当发生扩容时候，Redis可配置映射表的方式让哈希槽更灵活，可更方便组织映射到新增server上面的slot数，比一致性hash的算法更灵活方便。
• 在数据迁移时，一致性hash 需要重新计算key在新增节点的数据，然后迁移这部分数据，哈希槽则直接将一个slot对应的数据全部迁移，实现更简单
• 可以灵活的分配槽位，比如性能更好的节点分配更多槽位，性能相对较差的节点可以分配较少的槽位

为什么Redis Cluster哈希槽数量是16384？

我们知道一致性哈希算法是对2的32次方取模，而哈希槽是对2的14次方取模
Redis作者认为这样做不太值得；并且一般情况下一个redis集群不会有超过1000个master节点，所以16k的槽位是个比较合适的选择。
Redis作者的回答在这里：why redis-cluster use 16384 slots? · Issue #2576 · redis/redis

总结起来主要有以下因素

• Redis节点间通信时，心跳包会携带节点的所有槽信息，它能以幂等方式来更新配置。如果采用 16384 个插槽，占空间 2KB (16384/8);如果采用 65536 个插槽，占空间 8KB (65536/8)。
• Redis Cluster 不太可能扩展到超过 1000 个主节点，太多可能导致网络拥堵。
• 16384 个插槽范围比较合适，当集群扩展到1000个节点时，也能确保每个master节点有足够的插槽
  这也就是为什么哈希槽的数量是16384了！