面试官 ： 你能说清楚 Redis 哈希槽和一致性哈希的要点吗？

一 . 前言

在 Redis 集群里面主要涉及到两种 Hash 算法 ：

• 一种是一致性哈希 ， 这种算法在 适用dis Cluster方案中并没有实现，主要在外部的代理模式 （Twemproxy）
• 一种是 Slot 哈希槽算法 ，这种算法就是 Cluster 的核心算法

所以谈到这个问题的时候，不能只讲一部分。在 Redis 3.0 之前，Redis 是没有集群方案的，在这个时期实现 Redis 的 分布式 主要由客户端自行实现。 一般的实现方式就是一致性 Hash。

而 Redis 3.0 之后 ，Redis 实现了 Cluster 集群，也就采用了相对而言更简洁的 Slot 槽方式。

下面来一步步的了解其中的变化 ，以及为什么要这样做 ：👉👉👉

第一步 ：单节点到多节点集群

之前也聊过，单节点的性能是有瓶颈的。当单节点达到瓶颈后，构建集群就是最合理，最经济的用法。

这就衍生出几个问题 ：

1. 单节点的时候，直接把数据往一个节点丢就行，查询也是一个节点去处理查询
2. 集群后，数据应该放在哪个节点？ 是全部存一份还是分开存？
3. 集群后, 查询应该查询哪个节点？ 不可能全量查询吧 ， 一个一个节点查，性能太差了

为了解决这些问题， Redis 提供了多种集群的构建方式 ：

• Sentinel 哨兵模式 ： 主节点支持读写，从节点支持读，哨兵节点负责维护高可用
  • 这个方案下，主节点和从节点都有全量数据，适合数据量相对少的场景
  • 主节点负责写操作，主节点数据写入后将数据按照流程同步到从节点
  • 当主节点异常后 ，从节点会被选举为主节点，从而完成后续的写和同步
• Redis Cluster ： 这个方案即为一致性Hash的方案，后面具体来讲
• Twemproxy ： 类似于代理模式，数据的分片和负责均衡由 Twemproxy 来实现
  • Twemproxy 本身不提供高可用，适用于轻量级的场景

可以看到， Redis 集群的方案很详细，Sentinel 流程里面对于上述问题的处理也很完善。但是数据量如果太大，用哨兵的方案就不够了。上十亿的数据每个节点复制一份，性能，容量都扛不住。

这个时候，就要考虑使用 Cluster 方案，那么一致性Hash在 Cluster 模式里面又起到什么作用呢？

第二阶段 ： 一致性哈希的种种变化

那么我们有了数据，也有了多个集群节点，怎么样让数据放在对应的节点上呢？

• 要求一 ： 数据量大，数据只能存在一个节点上
• 要求二 ： 要保证数据相对均匀分布到所有的节点上
• 要求三 ： 不能影响到查询的效率，所以查询应该只用查询一个集群节点
• 要求四 ： 要实现高可用，节点宕机后能快速恢复，支持缩容扩容

2.1 首先数据的分布方案

针对于要求一和要求二 ， 数据只能在一个节点，且所有数据应该均匀的分布在所有的节点上。

对于均匀而言 ，一般我们的方式就是 Hash + 取模 ，但是这样会有一些问题。

通过取模的方式我们虽然可以让数据均匀分布 ，但是一旦扩展或者缩容，就会导致全量数据的重新迁移和计算，这显然是不可行的。

于是就衍生出了一个方案 ：一致性哈希。具体的方案如下 ：

• S1 : 首先构建一个 Hash 环，例如一个Hash算法的范围是 0到2^32-1 ， 那么就会形成一个整数环
• S2 : 对 Redis 数据节点进行Hash ， 得到的值意味着它映射到了环上的一个点
• S3 : 插入时 ，当一个数据来的时候 ，对 Key 进行 Hash 函数计算，映射到环上的一个点
• S4 : 对该点进行顺时针查找，找到第一个 Redis子节点，就是该key应该操作的 Redis子节点
• S5 : 查询时同理 ， 先 Hash 再进行节点的查询

2.2 其次保证数据的均衡

上面的问题很明显，明显节点C和节点A之间空余空间更大，就会导致数据不均衡 ，大部分数据被指向了某一个节点。

为此 一致性Hash 做了更多的优化 ：虚拟节点。 当节点较少的时候，为每个物理节点创建多个虚拟节点，使所有的节点均匀的分布在 Hash 环上 ， 从而使数据相对均衡。

• S1 : 为每个物理节点生成多个虚拟节点，并且让所有的节点都均匀的分布在 Hash 环上面
• S2 : 当数据操作请求进来时 ， 如果指向了虚拟节点，就映射到实际的物理节点中

通过这样的方式，就可以保证数据的相对均衡。 当然，这种均衡还是相对的。

2.3 数据的查询和节点的扩容

数据查询的流程和数据插入的流程是一样的，当请求到来的时候，基于请求的 Key 计算出对应的数据节点，再到该节点中进行数据查询。

而节点变动就比较麻烦了，当一个节点需要下线的时候，需要将该节点里面的所有数据都会根据 Hash 环的轮动情况 ，迁移当前 Hash 范围内的数据到 Hash环 中对应的下一个节点中。

然后后续的查询都会走到下一个节点中进行查询

2.4 总结一下一致性哈希

上面说了，这种方案多见于外部代理组件，例如 Twitter 发布的 Twemproxy ，例如 Predis-Proxy。

一致性哈希能实现数据的定位，也能实现相对均匀的数据，但是它还是有一些问题 。

• 相对而言复杂度更高，节点发生变化的时候，需要迁移整个节点的数据。
• 数据只能相对均衡 ，无法对优势节点进行特殊定制，数据的分布完全基于 Hash 算法来实现
  • 这里如果把虚拟节点搞得更多，其实也能减少这种问题
• 一致性Hash抗风险能力相对弱一些，当节点挂了的时候，会导致数据出现大面积不均衡，从而导致单个节点压力高
  • 其实 Hash 槽也有，只不过一致性hash的特性会导致流量直接到下一个节点

这个时候就需要我们了解一下 Redis 的槽概念了。

第三阶段 ： Redis 集群分片的方案

3.1 Slot Partitioning 槽分区算法

Redis Cluster 定义了 16384 个槽位，将这些槽位分发给所有的物理节点

槽位的计算

• 通常 Cluster 默认基于 Key 进行 crc16 算法进行 Hash 计算，然后基于 16384 进行取模
• 但是 特殊情况下 ，Cluster 可以指定某个Key挂载到特定的槽位上（通过 Tag 实现 ， Tag 映射槽位）

指令的请求

与一致性Hash一样的是 ，Cluster 的槽位选择还是通过客户端来实现的。

当 Cluster 连接集群的时候，其本身会得到一份集群的槽位信息，从而直接定位到目标节点。

不过，每个集群节点同样会保存所有的槽位信息，目的在于后续槽位变动 或者 客户端向一个错误的节点发送指令时 ， 节点会基于这些信息将指令发送到正确的节点。

3.2 槽数据的迁移

当槽位进行迁移的时候，当前槽处于过渡状态。此时槽即存在于原节点A（migrating），又存在于新节点B （importing）。此时 Cluster 客户端中计算出来数据还在 A节点中（错误结果）。

• 当数据迁移时 ：
  • S1 : 一次性获取源节点槽位的所有 key 列表 , 逐个对 Key 进行迁移
  • S2 : 原节点A 此时充当客户端角色，指向 Dump 命令进行数据序列化
  • S3 : 原节点A 向 目标节点B 发起 restore 指令，携带序列化数据进行访问
  • S4 : 目标节点B 接收到数据，保存到目标节点 ，并且返回成功
  • S5 : 原节点A 把当前Key 在自己的节点中进行删除
• 当此时请求数据时 ：
  • S1 : 客户端首先去 A节点（错误节点） 请求数据 ，如果数据还在A节点中，直接返回
  • S2 : 如果数据已经迁移 ，A节点返回 ASK 指令，且告知 B节点的地址
  • S3 : 客户端向B节点发起 ASK 访问 , 此时仅为了避免死循环（因为可能迁移一半，槽位未创建好）
  • S4 : 执行之前的操作

3.3 槽思想的扩展

Redis Cluster 是 Redis 官方的方案，这其实也算是一种分片的思路。 而在外部工具里面 ，同样有类似的方案。

例如国产组件 Codis ， 其本质上是一个代理中间件，和 Twemproxy 有一些类似。

这个组件会将所有的 key 默认划分为 1024 个槽位(slot) 。 不同于客户端自己的处理，槽位的计算是在 Codis 中进行的 ，访问 Codis 和访问单节点Redis 没有区别。

3.4 后续待扩展的细节

• 槽位的计算方式
• 为什么定义这些数量的槽位
• 不同节点之间如何同步信息
• 。。。。。
• 时间有限，东西不少，后续迭代

总结

时间有限 ，Redis 槽位还有一些细节点这一篇没有说 ，后面会来探讨一下为什么槽位要那么定义，以及具体传输的细节。

内容可能会有一些不太准确的地方，学习的也不太深入 ，欢迎指教。

参考文档