Ref: https://pdai.tech/md/db/nosql-redis/db-redis-x-cluster.html

请求重定向

Redis cluster 采用去中心化的架构，集群的主节点各自负责一部分槽，客户端如何确定 key 到底会映射到哪个节点上呢？这就是我们要讲的请求重定向。
在 cluster 模式下，节点对请求的处理过程如下：

  • 检查当前 key 是否存在当前 NODE？
    • 通过 crc16（key）/16384 计算出 slot
    • 查询负责该 slot 负责的节点，得到节点指针
    • 该指针与自身节点比较
  • 若 slot 不是由自身负责，则返回 MOVED 重定向
  • 若 slot 由自身负责，且 key 在 slot 中，则返回该 key 对应结果
  • 若 key 不存在此 slot 中，检查该 slot 是否正在迁出（MIGRATING）？
  • 若 key 正在迁出，返回 ASK 错误重定向客户端到迁移的目的服务器上
  • 若 Slot 未迁出，检查 Slot 是否导入中？
  • 若 Slot 导入中且有 ASKING 标记，则直接操作
  • 否则返回 MOVED 重定向

这个过程中有两点需要具体理解下： MOVED 重定向 和 ASK 重定向。

Moved 重定向

image.png

  • 槽命中：直接返回结果
  • 槽不命中：即当前键命令所请求的键不在当前请求的节点中，则当前节点会向客户端发送一个 Moved 重定向，客户端根据 Moved 重定向所包含的内容找到目标节点，再一次发送命令。

从下面可以看出 php 的槽位 9244 不在当前节点中，所以会重定向到节点 192.168.2.23:7001 中。redis-cli 会帮你自动重定向（如果没有集群方式启动，即没加参数 -c，redis-cli 不会自动重定向），并且编写程序时，寻找目标节点的逻辑需要交予程序员手动完成。
cluster keyslot keyName # 得到keyName的槽

ASK 重定向

Ask 重定向发生于集群伸缩时，集群伸缩会导致槽迁移，当我们去源节点访问时，此时数据可能已经迁移到了目标节点，使用 Ask 重定向来解决此种情况。
image.png

smart 客户端

上述两种重定向的机制使得客户端的实现更加复杂，提供了 smart 客户端（JedisCluster）来减低复杂性，追求更好的性能。客户端内部负责计算 / 维护键 -> 槽 -> 节点映射，用于快速定位目标节点。
实现原理：

  • 从集群中选取一个可运行节点，使用 cluster slots 得到槽和节点的映射关系。

image.png

  • 将上述映射关系存到本地，通过映射关系就可以直接对目标节点进行操作（CRC16 (key) -> slot -> node），很好地避免了 Moved 重定向，并为每个节点创建 JedisPool.
  • 至此就可以用来进行命令操作

image.png

状态检测及维护

Redis Cluster 中节点状态如何维护呢？这里便涉及 有哪些状态，底层协议 Gossip，及 具体的通讯（心跳）机制。
Cluster 中的每个节点都维护一份在自己看来当前整个集群的状态，主要包括：

  • 当前集群状态
  • 集群中各节点所负责的 slots 信息，及其 migrate 状态
  • 集群中各节点的 master-slave 状态
  • 集群中各节点的存活状态及不可达投票

当集群状态变化时，如新节点加入、slot迁移、节点宕机、slave 提升为新 Master，我们希望这些变化尽快的被发现，传播到整个集群的所有节点并达成一致。节点之间相互的心跳（PING，PONG，MEET）及其携带的数据是集群状态传播最主要的途径。

Gossip 协议

Redis Cluster 通讯底层是 Gossip 协议，所以需要对 Gossip 协议有一定的了解。
gossip 协议（gossip protocol）又称 epidemic 协议（epidemic protocol），是基于流行病传播方式的节点或者进程之间信息交换的协议。 在分布式系统中被广泛使用，比如我们可以使用 gossip 协议来确保网络中所有节点的数据一样。
Gossip 协议已经是 P2P 网络中比较成熟的协议了。Gossip 协议的最大的好处是，即使集群节点的数量增加，每个节点的负载也不会增加很多，几乎是恒定的。这就允许 Consul 管理的集群规模能横向扩展到数千个节点。
Gossip 算法又被称为反熵（Anti-Entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了 Gossip 的特点：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻居节点，只要这些节可以通过网络连通，最终他们的状态都是一致的，当然这也是疫情传播的特点。https://www.backendcloud.cn/2017/11/12/raft-gossip/
上面的描述都比较学术，其实 Gossip 协议对于我们吃瓜群众来说一点也不陌生，Gossip 协议也成为流言协议，说白了就是八卦协议，这种传播规模和传播速度都是非常快的，你可以体会一下。所以计算机中的很多算法都是源自生活，而又高于生活的。

Gossip 协议的使用

Redis 集群是去中心化的，彼此之间状态同步靠 gossip 协议通信，集群的消息有以下几种类型：

  • Meet 通过「cluster meet ip port」命令，已有集群的节点会向新的节点发送邀请，加入现有集群。
  • Ping 节点每秒会向集群中其他节点发送 ping 消息，消息中带有自己已知的两个节点的地址、槽、状态信息、最后一次通信时间等。
  • Pong 节点收到 ping 消息后会回复 pong 消息，消息中同样带有自己已知的两个节点信息。

  • Fail 节点 ping 不通某节点后，会向集群所有节点广播该节点挂掉的消息。其他节点收到消息后标记已下线。

    基于 Gossip 协议的故障检测

    集群中的每个节点都会定期地向集群中的其他节点发送 PING 消息，以此交换各个节点状态信息，检测各个节点状态：在线状态、疑似下线状态 PFAIL、 已下线状态 FAIL。
    自己保存信息：当主节点 A 通过消息得知主节点 B 认为主节点 D 进入了疑似下线 (PFAIL) 状态时，主节点 A 会在自己的 clusterState.nodes 字典中找到主节点 D 所对应的 clusterNode 结构，并将主节点 B 的下线报告添加到 clusterNode 结构的 fail_reports 链表中，并后续关于结点 D 疑似下线的状态通过 Gossip 协议通知其他节点。
    一起裁定：如果集群里面，半数以上的主节点都将主节点 D 报告为疑似下线，那么主节点 D 将被标记为已下线 (FAIL) 状态，将主节点 D 标记为已下线的节点会向集群广播主节点 D 的 FAIL 消息，所有收到 FAIL 消息的节点都会立即更新 nodes 里面主节点 D 状态标记为已下线。
    最终裁定：将 node 标记为 FAIL 需要满足以下两个条件：

  • 有半数以上的主节点将 node 标记为 PFAIL 状态。

  • 当前节点也将 node 标记为 PFAIL 状态。

    通讯状态和维护

    我们理解了 Gossip 协议基础后，就可以进一步理解 Redis 节点之间相互的通讯心跳（PING，PONG，MEET）实现和维护了。我们通过几个问题来具体理解。

    什么时候进行心跳？

    Redis 节点会记录其向每一个节点上一次发出 ping 和收到 pong 的时间，心跳发送时机与这两个值有关。通过下面的方式既能保证及时更新集群状态，又不至于使心跳数过多：

  • 每次 Cron 向所有未建立链接的节点发送 ping 或 meet

  • 每 1 秒从所有已知节点中随机选取 5 个，向其中上次收到 pong 最久远的一个发送 ping
  • 每次 Cron 向收到 pong 超过 timeout/2 的节点发送 ping

  • 收到 ping 或 meet，立即回复 pong

    发送哪些心跳数据？

  • Header，发送者自己的信息

    • 所负责 slots 的信息
    • 主从信息
    • ip port 信息
    • 状态信息
  • Gossip，发送者所了解的部分其他节点的信息
    • ping_sent, pong_received
    • ip, port 信息
    • 状态信息，比如发送者认为该节点已经不可达，会在状态信息中标记其为 PFAIL 或 FAIL

      如何处理心跳？

  1. 新节点加入
  • 发送 meet 包加入集群
  • 从 pong 包中的 gossip 得到未知的其他节点
  • 循环上述过程，直到最终加入集群

image.png

  1. Slots 信息
  • 判断发送者声明的 slots 信息，跟本地记录的是否有不同
  • 如果不同，且发送者 epoch 较大，更新本地记录
  • 如果不同，且发送者 epoch 小，发送 Update 信息通知发送者
  1. Master slave 信息

发现发送者的 master、slave 信息变化，更新本地状态

  1. 节点 Fail 探测 (故障发现)
  • 超过超时时间仍然没有收到 pong 包的节点会被当前节点标记为 PFAIL
  • PFAIL 标记会随着 gossip 传播
  • 每次收到心跳包会检测其中对其他节点的 PFAIL 标记，当做对该节点 FAIL 的投票维护在本机
  • 对某个节点的 PFAIL 标记达到大多数时，将其变为 FAIL 标记并广播 FAIL 消息

注：Gossip 的存在使得集群状态的改变可以更快的达到整个集群。每个心跳包中会包含多个 Gossip 包，那么多少个才是合适的呢，redis 的选择是 N/10，其中 N 是节点数，这样可以保证在 PFAIL 投票的过期时间内，节点可以收到 80% 机器关于失败节点的 gossip，从而使其顺利进入 FAIL 状态。

将信息广播给其它节点？

当需要发布一些非常重要需要立即送达的信息时，上述心跳加 Gossip 的方式就显得捉襟见肘了，这时就需要向所有集群内机器的广播信息，使用广播发的场景：

  • 节点的 Fail 信息：当发现某一节点不可达时，探测节点会将其标记为 PFAIL 状态，并通过心跳传播出去。当某一节点发现这个节点的 PFAIL 超过半数时修改其为 FAIL 并发起广播。
  • Failover Request 信息：slave 尝试发起 FailOver 时广播其要求投票的信息

  • 新 Master 信息：Failover 成功的节点向整个集群广播自己的信息

    故障恢复（Failover）

    master 节点挂了之后，如何进行故障恢复呢？
    当 slave 发现自己的 master 变为 FAIL 状态时，便尝试进行 Failover，以期成为新的 master。由于挂掉的 master 可能会有多个 slave。Failover 的过程需要经过类 Raft 协议的过程在整个集群内达到一致， 其过程如下：

  • slave 发现自己的 master 变为 FAIL

  • 将自己记录的集群 currentEpoch 加 1，并广播 Failover Request 信息
  • 其他节点收到该信息，只有 master 响应，判断请求者的合法性，并发送 FAILOVER_AUTH_ACK，对每一个 epoch 只发送一次 ack
  • 尝试 failover 的 slave 收集 FAILOVER_AUTH_ACK
  • 超过半数后变成新 Master
  • 广播 Pong 通知其他集群节点

image.png

扩容 & 缩容

Redis Cluster 是如何进行扩容和缩容的呢？

扩容

当集群出现容量限制或者其他一些原因需要扩容时，redis cluster 提供了比较优雅的集群扩容方案。

  1. 首先将新节点加入到集群中，可以通过在集群中任何一个客户端执行 cluster meet 新节点 ip: 端口，或者通过 redis-trib add node 添加，新添加的节点默认在集群中都是主节点。
  2. 迁移数据的大致流程是，首先需要确定哪些槽需要被迁移到目标节点，然后获取槽中 key，将槽中的 key 全部迁移到目标节点，然后向集群所有主节点广播槽（数据）全部迁移到了目标节点。直接通过 redis-trib 工具做数据迁移很方便。 现在假设将节点 A 的槽 10 迁移到 B 节点，过程如下：
    1. B:cluster setslot 10 importing A.nodeId
    2. A:cluster setslot 10 migrating B.nodeId
    循环获取槽中 key，将 key 迁移到 B 节点
    A:cluster getkeysinslot 10 100
A:migrate B.ip B.port "" 0 5000 keys key1[ key2....]
    向集群广播槽已经迁移到 B 节点：cluster setslot 10 node B.nodeId

    缩容

    缩容的大致过程与扩容一致，需要判断下线的节点是否是主节点，以及主节点上是否有槽，若主节点上有槽，需要将槽迁移到集群中其他主节点，槽迁移完成之后，需要向其他节点广播该节点准备下线（cluster forget nodeId）。最后需要将该下线主节点的从节点指向其他主节点，当然最好是先将从节点下线。

    更深入理解

    通过几个例子，再深入理解 Redis Cluster

    为什么 Redis Cluster 的 Hash Slot 是 16384？

    我们知道一致性 hash 算法是 2 的 16 次方，为什么 hash slot 是 2 的 14 次方呢？作者原始回答(opens new window)
    在 redis 节点发送心跳包时需要把所有的槽放到这个心跳包里，以便让节点知道当前集群信息，16384=16k，在发送心跳包时使用 char 进行 bitmap 压缩后是 2k（2 8 (8 bit) 1024 (1k) = 16K），也就是说使用 2k 的空间创建了 16k 的槽数。
    虽然使用 CRC16 算法最多可以分配 65535（2^16-1）个槽位，65535=65k，压缩后就是 8k（8 8 (8 bit) 1024 (1k) =65K），也就是说需要需要 8k 的心跳包，作者认为这样做不太值得；并且一般情况下一个 redis 集群不会有超过 1000 个 master 节点，所以 16k 的槽位是个比较合适的选择。

    为什么 Redis Cluster 中不建议使用发布订阅呢？

    在集群模式下，所有的 publish 命令都会向所有节点（包括从节点）进行广播，造成每条 publish 数据都会在集群内所有节点传播一次，加重了带宽负担，对于在有大量节点的集群中频繁使用 pub，会严重消耗带宽，不建议使用。（虽然官网上讲有时候可以使用 Bloom 过滤器或其他算法进行优化的）

    其它常见方案

    还有一些方案出现在历史舞台上，我挑了几个经典的。简单了解下，增强下关联的知识体系。@pdai

    Redis Sentinel 集群 + Keepalived/Haproxy

    底层是 Redis Sentinel 集群，代理着 Redis 主从，Web 端通过 VIP 提供服务。当主节点发生故障，比如机器故障、Redis 节点故障或者网络不可达，Redis 之间的切换通过 Redis Sentinel 内部机制保障，VIP 切换通过 Keepalived 保障。
    image.png
    优点：
  • 秒级切换
  • 对应用透明

缺点：

  • 维护成本高
  • 存在脑裂

  • Sentinel 模式存在短时间的服务不可用

    Twemproxy

    多个同构 Twemproxy（配置相同）同时工作，接受客户端的请求，根据 hash 算法，转发给对应的 Redis。
    Twemproxy 方案比较成熟了，但是效果并不是很理想。一方面是定位问题比较困难，另一方面是它对自动剔除节点的支持不是很友好。
    image.png
    优点：

  • 开发简单，对应用几乎透明

  • 历史悠久，方案成熟

缺点：

  • 代理影响性能
  • LVS 和 Twemproxy 会有节点性能瓶颈
  • Redis 扩容非常麻烦

  • Twitter 内部已放弃使用该方案，新使用的架构未开源

    Codis

    Codis 是由豌豆荚开源的产品，涉及组件众多，其中 ZooKeeper 存放路由表和代理节点元数据、分发 Codis-Config 的命令；Codis-Config 是集成管理工具，有 Web 界面供使用；Codis-Proxy 是一个兼容 Redis 协议的无状态代理；Codis-Redis 基于 Redis 2.8 版本二次开发，加入 slot 支持，方便迁移数据。
    image.png
    优点：

  • 开发简单，对应用几乎透明

  • 性能比 Twemproxy 好
  • 有图形化界面，扩容容易，运维方便

缺点：

  • 代理依旧影响性能
  • 组件过多，需要很多机器资源
  • 修改了 Redis 代码，导致和官方无法同步，新特性跟进缓慢
  • 开发团队准备主推基于 Redis 改造的 reborndb