Redis：分片（Redis Cluster）

Redis 集群（Redis Cluster）是 Redis 官方提供的分布式数据库方案，通过划分 hash 槽来分区，进行数据分享，每个主节点只保存部分信息。。在前文中我们介绍了主从复制与哨兵，这两个机制保障了redis的高可用，但实际使用中会发现虽然slave节点扩展了整个系统的的读并发能力，但是写能力和存储能力是无法进行扩展，就只能是master节点能够承载的上限。如果。...

jchen104

3016人浏览 · 2022-08-27 14:11:20

jchen104 · 2022-08-27 14:11:20 发布

参考资料：

《RedisCluster集群架构原理与通信原理》

《深入分析Cluster 集群模式》

《redis cluster模式》

《深入剖析Redis系列(三) - Redis集群模式搭建与原理详解》

前文：

写在开头：本文为学习后的总结，可能有不到位的地方，错误的地方，欢迎各位指正。

configEpoch与currentEpoch

一、Redis Cluster 基本原理

1、集群简介

Redis 集群（Redis Cluster）是 Redis 官方提供的分布式数据库方案，通过划分 hash 槽来分区，进行数据分享，每个主节点只保存部分信息。。

在前文中我们介绍了主从复制与哨兵，这两个机制保障了redis的高可用，但实际使用中会发现虽然slave节点扩展了整个系统的的读并发能力，但是写能力和存储能力是无法进行扩展，就只能是master节点能够承载的上限。
如果面对海量数据那么必然需要构建master（主节点分片，每个分片只保存一部分数据)之间的集群，同时必然需要吸收高可用（主从复制和哨兵机制）能力，即每个master分片节点还需要有slave节点，所以在Redis 3.0版本中对应的设计就是Redis Cluster。

2、集群节点

        Redis 集群由多个节点组成，节点刚启动时，彼此是相互独立的。节点通过握手（ CLUSTER MEET 命令）来将其他节点添加到自己所处的集群中。
        向一个节点发送 CLUSTER MEET 命令，可以让当前节点与指定 IP、PORT 的节点进行握手，握手成功时，当前节点会将指定节点加入所在集群。
        Redis 集群节点分为主节点（master）和从节点（slave），其中主节点用于处理槽，而从节点则用于复制某个主节点，并在被复制的主节点下线时，代替下线主节点继续处理命令请求。

这里需要注意的是：

集群中主节点保存键值对以及过期时间的方式与单机 Redis 服务完全相同。
故障转移是所进行的主从切换是由从节点自发完成的。（哨兵机制中是由哨兵节点来完成的）

3、分配 Hash 槽

分布式存储需要解决的首要问题是把整个数据集按照分区规则映射到多个节点的问题，即把数据集划分到多个节点上，每个节点负责整体数据的一个子集。

Redis 集群通过划分 hash 槽（slot）来将数据分区。Redis 集群通过分区的方式来保存数据库的键值对：集群的整个数据库被分为 16384 个哈希槽，数据库中的每个键都属于这 16384 个槽的其中一个，集群中的每个节点可以处理 0 个或最多 16384 个槽。

通过向节点发送 CLUSTER ADDSLOTS (官方文档)命令，可以将一个或多个槽指派给节点负责。

> CLUSTER ADDSLOTS 1 2 3
OK

集群中的每个节点负责一部分哈希槽，比如集群中有３个节点，则：

节点Ａ存储的哈希槽范围是：0 – 5500
节点Ｂ存储的哈希槽范围是：5501 – 11000
节点Ｃ存储的哈希槽范围是：11001 – 16384

4、寻址

当客户端向节点发送与数据库键有关的命令时，接受命令的节点会计算出命令要处理的数据库属于哪个槽，并检查这个槽是否指派给了自己：

如果键所在的槽正好指派给了当前节点，那么当前节点直接执行命令。
如果键所在的槽没有指派给当前节点，那么节点会向客户端返回一个 MOVED（正常工作时使用）或ASK（槽迁移时使用）重定向，指引客户端重定向至正确的节点。

4.1、计算键属于哪个槽

决定一个 key 应该分配到那个槽的算法是：计算该 key 的 CRC16 结果再模 16834。

HASH_SLOT = CRC16(KEY) mod 16384

当节点计算出 key 所属的槽为 i 之后，节点会根据以下条件判断槽是否由自己负责：

clusterState.slots[i] == clusterState.myself

4.2、MOVED 重定向

当节点发现键所在的槽并非自己负责处理的时候，节点就会向客户端返回一个 MOVED 重定向，指引客户端转向正在负责槽的节点。

MOVED 重定向的格式为：

MOVED <slot> <ip>:<port>

流程如下：

客户端连接任一实例，获取到slots与实例节点的映射关系，并将该映射关系的信息缓存在本地。
将需要访问的redis信息的key，经过CRC16计算后，再对16384 取模得到对应的 Slot 索引。
通过slot的位置进一步定位到具体所在的实例，再将请求发送到对应的实例上。

5、重新分区

Redis 集群的重新分区操作可以将任意数量的已经指派给某个节点（源节点）的槽改为指派给另一个节点（目标节点），并且相关槽所属的键值对也会从源节点被移动到目标节点。

重新分区操作可以在线进行，在重新分区的过程中，集群不需要下线，并且源节点和目标节点都可以继续处理命令请求。

Redis 集群的重新分区操作由 Redis 集群管理软件 redis-trib 负责执行的，redis-trib 通过向源节点和目标节点发送命令来进行重新分区操作。

重新分区的实现原理如下图所示：

首先将源节点中要迁移的槽中的键值对都迁移至目标节点。
待所有键值对迁移完毕后将槽指定给目标节点。

那么问题来了，当源节点中的键值对没有完全迁移完时，由于部分数据已经转移进了目标节点但还未重新指派槽，于是寻址还是定位到了源节点，这时为了能让客户端找到新的节点，便产生了ASK重定向。

ASK 重定向

在客户端收到关于槽 X 的 ASK 重定向之后，客户端会在接下来的一次命令请求中将关于槽 X 的命令请求发送至 ASK 重定向所指示的节点，但这种转向不会对客户端今后发送关于槽 X 的命令请求产生任何影响，客户端仍然会将关于槽 X 的命令请求发送至目前负责处理槽 X 的节点（这是因为前后2次的访问并无关联，无法确定后续访问的节点是否已迁移）。

判断 ASK 错误的过程如下图所示：

二、源码分析

上一节我们介绍了集群的基本功能，这一节我们从源码的角度来展开分析下。

clusterState

集群中的每一个节点都保存了一个clusterState，用来记录集群中所有节点的状态信息，这其中每个节点的状态使用clusterNode结构来保存。

clusterState结构记录了在当前节点的集群目前所处的状态还有所有槽的指派信息：

typedef struct clusterState {
	....
    clusterNode *myself;  // 指针指向自己的clusterNode 
	uint64_t currentEpoch;	// 集群当前的配置纪元，这是一个集群状态相关的概念，可以当做记录集群状态变更的递增版本号
	dict *nodes;          // 当前节点记录的所有节点的字典，为clusterNode指针数组
	clusterNode *slots[CLUSTER_SLOTS]; // slot与clusterNode指针映射关系
	....
} clusterState;

下面两张图为我们展示了clusterState中nodes和slots的作用，分别是指向集群中的所有节点，与槽的分配。

clusterNode

每个节点的属性使用clusterNode来表示：

typedef struct clusterNode {
    mstime_t ctime; // 创建节点的时间 
    char name[CLUSTER_NAMELEN]; // 节点的名字 
    int flags;      // 节点标识，标记节点角色或者状态，比如主节点从节点或者在线和下线 
    uint64_t configEpoch; // 节点当前的配置纪元，这是一个集群节点配置相关的概念，每个集群节点都有自己独一无二的 configepoch
    unsigned char slots[CLUSTER_SLOTS/8]; // slots位图，由当前clusterNode负责的slot为1
    int numslots;   // 负责多少槽
    int numslaves;  // 有多少从节点
    struct clusterNode **slaves; // 指向所有的从节点
    struct clusterNode *slaveof; // 指向主节点（如果该节点为从节点的话）
    mstime_t ping_sent;      // 当前节点最后一次向该节点发送 PING 消息的时间 
    mstime_t pong_received;  // 当前节点最后一次收到该节点 PONG 消息的时间 
    mstime_t fail_time;      // FAIL 标志位被设置的时间 
	...
    char ip[NET_IP_STR_LEN];  / 节点的IP 地址 
    int port;                   / 端口 
	...
    list *fail_reports;         / 下线记录列表 
} clusterNode;

slots与numslot

槽信息会被保存在redisnode节点结构的slots和numslot属性中，其中slots是一个二进制数组大小为16383，该数组的索引正好对应16384个槽，值为0或1，1就表示该索引对应槽由当前redis节点负责；numslot记录当前redis节点负责的槽总数。

在一个集群的中redis节点会相互网络连接发送信息，并告知对方自己在负责哪些槽。其他redis节点收到信息后，会更新自己的clusterState结构信息，主要是包含全部槽信息的clusterState.slots属性和clusterState.nodes中对应节点的clusterNode.slots和numslot信息。因此每一个redis节点中都保存在完整的槽节点指派信息。

configEpoch与currentEpoch

currentEpoch

currentEpoch是集群当前的配置纪元，这是一个集群状态相关的概念，可以当做记录集群状态变更的递增版本号。

        currentEpoch 作用在于，当集群的状态发生改变，某个节点为了执行一些动作需要寻求其他节点的同意时，就会增加 currentEpoch 的值，例如故障转移流程：
        当从节点 A 发现其所属的主节点下线时，就会试图发起故障转移流程。首先就是增加 currentEpoch 的值，这个增加后的 currentEpoch 是所有集群节点中最大的。然后从节点A向所有节点发包用于拉票，请求其他主节点投票给自己，使自己能成为新的主节点。
        其他节点收到包后，发现发送者的 currentEpoch 比自己的 currentEpoch 大，就会更新自己的 currentEpoch，并在尚未投票的情况下，投票给从节点 A，表示同意使其成为新的主节点。

configEpoch

configEpoch是节点当前的配置纪元，这是一个集群节点配置相关的概念，每个集群节点都有自己独一无二的 configepoch。

        每一个 master 在向其他节点发送消息时，都会附带其 configEpoch 信息，以及一份表示它所负责的 slots 信息。节点收到消息之后，就会根据消息中的 configEpoch 和负责的 slots 信息，记录到相应节点属性中。这边有两种情况：
（1）如果该消息中的 slots 在当前节点中被记录为还未有节点负责，那可以直接指定为发送消息的节点。
（2）如果消息中的 slots 在当前节点已经被记录为有节点负责，这种情况相当于有多个节点都宣称他负责了某个 slot，那怎么处理了？
        这时候就要用到 configEpoch，configEpoch 更大的说明是更新的配置，当前节点会使用 configEpoch 更大的配置。多个节点宣称负责同一个 slot 最常见的场景就是故障转移之后。当故障的主节点重新连接时，他会向集群其他节点发送消息，会带上自己故障前负责的 slots 信息，当其他节点收到后判断该节点的 configEpoch 更小，知道是旧的配置信息，则不会进行更新。
        节点的 configEpoch 会在自己当选为新的主节点的时候，更新为集群当前选举的纪元，其实也就是 currentEpoch 的值。
        因为每一次选举只会有一个从节点当选为新的主节点，所以该从节点的 configEpoch 会是当前所有集群节点 configEpoch 中的最大值。这样，该从节点成为主节点后，就会向所有节点发送广播包，强制其他节点更新相关槽位的负责节点为自己。

CLUSTER MEET命令实现

节点node1会为节点node2创建一个 clusterNode 结构，并将该结构添加到自己的 clusterState.nodes 字典里面。
节点node1根据CLUSTER MEET命令给定的IP地址和端口号，向节点node2发送一条MEET消息。
节点node2接收到节点node1发送的MEET消息，节点node2同样会为节点A创建一个clusterNode结构，并将该结构添加到自己的clusterState.nodes字典里面。
节点node2向节点node1返回一条PONG消息。
节点node1将受到节点node2返回的PONG消息，通过这条PONG消息节点node1可以知道节点node2已经成功的接收了自己发送的MEET消息。
节点1将向节点node2返回一条PING消息。
节点node2将接收到的节点node1返回的PING消息，通过这条PING消息节点node2可以知道节点node1已经成功的接收到了自己返回的PONG消息，握手完成。
节点node1会将节点node2的信息通过Gossip协议传播给集群中的其他节点，让其他节点也与节点node2进行握手，最终，经过一段时间后，节点node2会被集群中的所有节点认识。

三、故障发现与恢复

1、Redis Cluster 通信

1.1、通信指令

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

MEET - 请求接收方加入发送方所在的集群。
PING - 集群中每个节点每隔一段时间（默认为一秒）从已知节点列表中随机选出五个节点，然后对这五个节点中最久没联系的节点发送 PING 消息，以此检测被选中的节点是否在线。
PONG - 当接收方收到发送方发来的 MEET 消息或 PING 消息时，会返回一条 PONG 消息作为应答。
FAIL - 当一个主节点 A 判断另一个主节点 B 已经进入 FAIL 状态时，节点 A 会向集群广播一条关于节点 B 的 FAIL 消息，所有收到这条消息的节点都会立即将节点 B 标记为已下线。

1.2、状态检测及维护

集群中每个节点都维护一份在自己看来当前整个集群的状态，主要包括：

当前集群状态集群中各节点所负责的slots信息（用于重定向）
集群中各节点的master-slave状态
集群中各节点的存活状态及不可达投票（用于节点的下线判断）

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

2、故障发现

2.1、心跳检测

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

每1秒从所有已知节点中随机选取5个，向其中上次收到pong最久远的一个发送ping
收到ping或meet，立即回复pong

心跳检测每次发送的数据包括：

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

当接收者收到消息时，便会根据这些发送过来的消息更新自己保存的clusterState与clusterNode节点信息。

2.2、故障发现

将某个节点标记为 FAIL 需要满足以下两个条件：

有半数以上的主节点将该节点标记为 PFAIL 状态。
当前节点也将该节点标记为 PFAIL 状态。

假设此时有A、B、C三个主节点

当主节点 A 通过 Gossip 消息得知主节点 B 认为主节点 C 进入了 PFAIL 或 FAIL 状态时，主节点 A 会在自己的 clusterState.nodes 字典中找到主节点 C 对应的 clusterNode 结构，并将主节点 C 的故障报告（failure report）添加到 clusterNode 结构的 fail_reports 链表中。

这样，主节点 A 就可以通过主节点 C 的 clusterNode->fail_reports 链表快速计算出有多少个节点将主节点 C 标记为 PFAIL 状态。

当主节点 A 为主节点 C 新增故障报告的时候，会顺带检查是否需要将主节点 C 标记为 FAIL，如果通过 fail_reports 链表发现主节点 C 被半数以上负责处理槽的主节点标记为疑似下线（PFAIL），则会进一步将主节点 C 标记为已下线（FAIL），同时向集群广播 “主节点 C 已经 FAIL 的消息”，所有收到消息的节点都会立即将主节点 C 标记为已下线。

3、故障恢复（Failover）

当一个从节点发现自己正在复制的主节点进入了已下线，则开始对下线主节点进行故障转移，如果只有一个slave节点，则从节点会执行SLAVEOF no one命令，成为新的主节点。如果有多个slave节点，则需要先竞选出新的master：

集群中设立一个自增计数器，初始值为 0 ，每次执行故障转移选举，计数就会+1。
检测到主节点下线的从节点向集群所有master广播一条CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST消息，所有收到消息、并具备投票权的主节点都向这个从节点投票。
如果收到消息、并具备投票权的主节点未投票给其他从节点（只能投一票哦，所以投过了不行），则返回一条CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息，表示支持。
参与选举的从节点都会接收CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息，如果收集到的选票大于等于 (n/2) + 1 支持，n代表所有具备选举权的master，那么这个从节点就被选举为新主节点。
如果这一轮从节点都没能争取到足够多的票数，则发起再一轮选举（自增计数器+1），直至选出新的master。

其他节点收到消息后，会判断是否要给发送消息的节点投票，判断流程如下：

当前节点是 slave，或者当前节点是 master，但是不负责处理槽，则当前节点没有投票权，直接返回。
请求节点的 currentEpoch 小于当前节点的 currentEpoch，校验失败返回。因为发送者的状态与当前集群状态不一致，可能是长时间下线的节点刚刚上线，这种情况下，直接返回即可。
当前节点在该 currentEpoch 已经投过票，校验失败返回。
请求节点是 master，校验失败返回。
请求节点的 master 为空，校验失败返回。
请求节点的 master 没有故障，并且不是手动故障转移，校验失败返回。因为手动故障转移是可以在 master 正常的情况下直接发起的。
上一次为该master的投票时间，在cluster_node_timeout的2倍范围内，校验失败返回。这个用于使获胜从节点有时间将其成为新主节点的消息通知给其他从节点，从而避免另一个从节点发起新一轮选举又进行一次没必要的故障转移
请求节点宣称要负责的槽位，是否比之前负责这些槽位的节点，具有相等或更大的 configEpoch，如果不是，校验失败返回。

新的主节点会撤销所有对已下线主节点的slots指派，并将这些slots全部指派给自己。并向集群广播一条PONG消息，这条PONG消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点已经接管了原本由已下线节点负责处理的槽。

然后新的主节点开始接收和自己负责处理的槽有关的命令请求，故障转移完成。

这个选举新主节点的方法和选举领头 Sentinel 的方法非常相似，因为两者都是基于 Raft 算法的领头选举（leader election）方法来实现的。

四、补充

1、集群功能限制

Redis 集群相对单机，存在一些功能限制：

key 批量操作支持有限：类似 mset、mget 操作，目前只支持对具有相同 slot 值的 key 执行批量操作。对于映射为不同 slot 值的 key 由于执行 mget、mget 等操作可能存在于多个节点上，因此不被支持。
key 事务操作支持有限：只支持多 key 在同一节点上的事务操作，当多个 key 分布在不同的节点上时无法使用事务功能。
key 作为数据分区的最小粒度，不能将一个大的键值对象如 hash、list 等映射到不同的节点。
不支持多数据库空间：单机下的 Redis 可以支持 16 个数据库（db0 ~ db15），集群模式下只能使用一个数据库空间，即 db0。
复制结构只支持一层：从节点只能复制主节点，不支持主从复制链