Redis Cluster 是 Redis 提供的分布式数据库方案，集群通过分片（sharding）来进行数据共享，并提供复制和故障转移功能。当遇到单机内存、并发、流量等瓶颈时，可以采用 Cluster 架构达到负载均衡的目的。

集群节点

一个 Redis 集群通常由多个节点（node）组成，在刚开始的时候，每个节点都是相互独立的，它们都处于一个只包含自己的集群当中，要组建一个真正可工作的集群，我们必领将各个独立的节点连接起来，构成一个包含多个节点的集群。节点需要开启 cluster-enabled 配置项使服务器运行在集群模式下。

处于集群状态下的节点会继续使用 redisServer 结构来保存服务器状态，使用 redisClient 结构来保存客户端状态，至于那些只有在集群模式下才会用到的数据，节点会将它们保存到 clusterNode、clusterLink 以及 clusterState 结构里面。

1. clusterNode

clusterNode 结构保存了节点的当前状态，比如节点的创建时间、节点名称、IP 地址和端口号等等。每个节点都会使用一个 clusterNode 结构来记录自己的状态，并为集群中的所有其他节点（包括主节点和从节点）都创建一个相应的 clusterNode 结构，以此来记录其他节点状态。

typedef struct clusterNode {
    // 创建节点的时间
  mstime_t ctime;
  // 节点名称，由40个十六进制字符组成
  char name[CLUSTER_NAMELEN];
  // 节点标识，使用各种不同的标识值记录节点的角色（主节点或从节点）以及节点目前所处的状态（在线或下线）
  int flags;
  // 节点当前的配置纪元，用于实现故障转移
  uint64_t configEpoch;
  // 记录节点负责处理的槽,每个位代表一个槽，0、1代表有无处理
  unsigned char slots[CLUSTER_SLOTS/8];
  // 记录节点负责处理槽的数量
  int numslots;
  // 节点IP地址
  char ip[NET_IP_STR_LEN];
  // 节点端口号
  int port;
  // 保存连接节点所需的有关信息，比如套接字描述符
  clusterLink *link;
  ......
} clusterNode;

2. clusterLink

clusterLink 结构保存了连接节点所需的有关信息，比如：套接字描述、输入缓冲区、输出缓冲区。它是为了连接集群中的节点而使用的，为了向集群中的其他节点发送消息，比如：MEET、PING、PONG 消息等。

typedef struct clusterLink {
    // 连接的创建时间
    mstime_t ctime;   
    // TCP连接
    connection *conn;
    // 输出缓冲区，保存着等待发送给其他节点的消息
    sds sndbuf;
    // 输入缓冲区，保存着从其他节点接收到的消息
    char *rcvbuf;
    // 与这个连接相关联的节点，没有则为NULL
    struct clusterNode *node;
} clusterLink;

3. clusterState

每个节点也都保存了一个 clusterState 结构，这个结构记录了在当前节点的视角下，集群目前所处的状态，例如集群是在线还是下线、集群包含多少个节点、集群当前的配置纪元等。

typedef struct clusterState {
    // 指向当前节点的指针
    clusterNode *myself;
    // 集群当前的配置纪元，用于实现故障转移
    uint64_t currentEpoch;
    // 集群当前状态（在线或下线）
    int state;
    // 集群中至少处理着一个槽的节点的数量
    int size;
    // 集群节点名单（包括myself节点），字典键为节点名称，值为节点对应的clusterNode结构
    dict *nodes;
    // 记录集群中所有16384个槽的指派信息，每个数组项都是一个指向负责该槽的clusterNode结构的指针
    clusterNode *slots[CLUSTER_SLOTS];
    ......
} clusterState;

示例结构如下图所示，其中节点 7001 和节点 7002 为节点 7000 的从节点：

节点握手

连接各个节点的工作可以使用 CLUSTER MEET 命令来完成。向一个节点 node 发送 CLUSTER MEET 命令，可以让 node 节点与 ip 和 port 所指定的节点进行握手，当握手成功时，node 节点就会将 ip 和 port 所指定的节点添加到 node 节点当前所在的集群中。

比如节点 B 向节点 A 发送 CLUSTER MEET 命令，节点 A 收到命令后将与节点 B 进行握手以此来确认彼此的存在，整个握手的具体过程如下所示：

节点 A 会为节点 B 创建一个 clusterNode 结构，并将该结构添加到自己的 clusterState.nodes 字典。之后节点 A 将根据 CLUSTER MEET 命令给定的 IP 地址和端口号向节点 B 发送一条 MEET 消息

如果一切顺利，节点 B 将接收到节点 A 发送的 MEET 消息，节点 B 也会为节点 A 创建一个 clusterNode 结构，并将该结构添加到自己的 clusterState.nodes 字典

之后，节点 B 将向节点 A 返回一条 PONG 消息。节点 A 接收到节点 B 返回的 PONG 消息后也向节点 B 返回一条 PING 消息。如果节点 B 成功接收到节点 A 返回的 PING 消息，则表示握手完成。

之后，节点 A 会将节点 B 的信息通过 Gossip 协议传播给集群中的其他节点，让其他节点也与节点 B 进行握手，最终经过一段时间后，节点 B 会被集群中的所有节点认识。

槽指派

Redis 集群通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为 16384 个槽（slot），每个键值对都会根据它的 key 被映射到一个哈希槽中，数据库中的每个键都属于这 16384 个槽的其中一个，集群中的每个节点可以处理 0 个或最多 16384 个槽。当数据库中的 16384 个槽都有节点在处理时，集群处于上线状态；相反，如果数据库中有任何一个槽没有得到处理，那么集群处于下线状态。

通过向节点发送 CLUSTER ADDSLOTS 命令，我们可以将一个或多个槽指派给节点负责：

CLUSTER ADDSLOTS <slot> [slot ...]
# 或者
CLUSTER ADDSLOTSRANGE <start-slot> <end-slot>

当把数据库中的 16384 个槽都指派给相应节点处理后，集群进入上线状态。

1. 记录槽分配信息

clusterNode 结构中的 slots 属性和 numslot 属性记录了节点负责处理哪些槽：

typedef struct clusterNode {
  // 记录节点负责处理的槽,每个位代表一个槽，0、1代表有无处理
  unsigned char slots[CLUSTER_SLOTS/8];
  // 记录节点负责处理槽的数量，即slots数组中值为1的数量
  int numslots;
  ......
} clusterNode;

slots 属性是一个二进制位数组。Redis 以 0 为起始索引，16383 为终止索引对 slots 数组中的 16384 个二进制位进行编号，并根据索引 i 上的二进制位的值来判断节点是否负责处理槽 i 。这样，取出和设置 slots 数组中的任意一个二进制位的值的复杂度仅为 O(1)。

上图展示了一个 slots 数组示例：因为 slots 数组索引 0~7 上的二进制位的值都为 1，其余所有二进制位的值都为 0，这表示该节点负责处理槽 0 至槽 7。

2. 传播节点的槽指派信息

一个节点除了会将自己负责处理的槽记录在 clusterNode 结构的 slots 属性和 numslots 属性外，它还会将自己的 slots 数组通过消息发送给集群中的其他节点，以此来告知其他节点自己目前负责处理哪些槽。

当节点 A 通过消息从节点 B 那里接收到节点 B 的 slots 数组时，节点 A 会在自己的 clusterState.nodes 字典中查找节点 B 对应的 clusterNode 结构，并对结构中的 slots 数组进行保存或更新。因此，集群中的每个节点都会知道数据库中的 16384 个槽分别被指派给了集群中的哪些节点。

typedef struct clusterState {
    // 集群节点名单（包括myself节点），字典键为节点名称，值为节点对应的clusterNode结构
    dict *nodes;
    // 记录集群中所有16384个槽的指派信息，每个数组项都是一个指向负责该槽的clusterNode结构的指针
    clusterNode *slots[CLUSTER_SLOTS];
    ......
} clusterState;

clusterNode.slots：只记录了自身节点的槽指派信息，用于发送该节点的槽指派信息给其他节点。
clusterState.slots：记录所有槽的指派信息，用于知道槽 i 是否已经被指派或指派给了哪个节点。

如果只将槽指派信息保存在各个节点的 clusterNode.slots 数组里，会出现一些无法高效解决的问题，比如节点想知道槽 i 是否已经被指派或槽 i 被指派给哪个节点，只能遍历 nodes 字典中的所有 clusterNode 结构，这个过程的复杂度为 O(N)。但用 clusterNode 结构的 slots 数组来记录单个节点的槽指派信息还是有必要的，因为当程序需要将某个节点的槽指派信息通过消息发送给其他节点时，程序只需要将相应节点 clusterNode.slots 数组整个发送出去就可以了。

客户端重定向

在对数据库中的 16384 个槽都进行了指派之后，集群就会进入上线状态，这时客户端就可以向集群中的节点发送数据命令了。当客户端向节点发送与数据库键有关的命令时，接收命令的节点会计算出命令要处理的数据库键属于哪个槽，并检查这个槽是否指派给了自己：

如果键所在的槽正好就指派给了当前节点，那么节点直接执行这个命令。
如果键所在的槽并没有指派给当前节点，那么节点会向客户端返回一个 MOVED 错误，指引客户端转向正确的节点，并再次发送之前想要执行的命令。

MOVED 错误格式为：

MOVED <slot> <ip>:<port>

因为客户端会根据 MOVED 错误进行自动转向，所以我们是看不见节点返回的 MOVED 错误的：

127.0.0.1:7000> SET msg "hello redis"
-> Redirected to slot [6257] located at 127.0.0.1:7001
OK

具体的判断过程为：节点首先对键按照 CRC16 算法计算一个 16bit 的值；然后再用该值对 16384 取模，得到一个 0~16383 范围内的模数，每个模数代表一个相应编号的哈希槽。之后，节点会检查 clusterNode.slots 数组中的项 i 判断键所在的槽是否由自己负责。如果不是由当前节点负责的，节点会根据 clusterState.slots[i] 指向的 clusterNode 结构所记录的节点 IP 和端口号，向客户端返回 MOVED 错误，指引客户端转向至正在处理槽 i 的节点，并向该节点重新发送命令。

一个集群客户端通常会与集群中的多个节点创建套接字连接，而所谓的节点转向实际上就是换了一个套接字来发送命令。如果客户端尚未与想要转向的节点创建套接字连接，那么客户端会先根据 MOVED 错误提供的 IP 地址和端口号来连接节点，然后再进行转向。

如上图示例所示：由于负载均衡，Slot 2 中的数据已经从实例 2 迁移到了实例 3，但是，客户端缓存仍然记录着“Slot 2 在实例 2”的信息，所以会给实例 2 发送命令。实例 2 给客户端返回一条 MOVED 命令，把 Slot 2 的最新位置（也就是在实例 3 上）返回给客户端，客户端就会再次向实例 3 发送请求，同时还会更新客户端本地缓存，把 Slot 2 与实例的对应关系更新过来。

ASK 错误

Redis 集群的重新分片操作可以将任意数量已经指派给某个节点的槽改为指派给另一个节点，并且相关槽所属的键值对也会从源节点被移动到目标节点。重新分片操作可以在线（online）进行，在重新分片的过程中，集群不需要下线，并且源节点和目标节点都可以继续处理命令请求。

typedef struct clusterState {
    // 记录当前节点正在迁移至其他节点的槽
  clusterNode *migrating_slots_to[CLUSTER_SLOTS];
  // 记录当前节点正在从其他节点导入的槽
  clusterNode *importing_slots_from[CLUSTER_SLOTS];
  ......
} clusterState;

在进行重分片期间，源节点向目标节点迁移一个槽的过程中，可能会出现这样一种情况：属于被迁移槽的一部分键值对保存在源节点里面，而另一部分键值对则保存在目标节点里面。当客户端向源节点发送一个与数据库键有关的命令，并且命令要处理的数据库键恰好就属于正在被迁移的槽时：

源节点会先在自己的数据库里面查找指定的键，如果找到就直接执行客户端发送的命令。

如果源节点没能在自己的数据库里找到指定键，节点会检查自己的 clusterState.migrating_slots_to[i]，看键所属的槽 i 是否正在迁移，如果槽 i 的确在进行迁移的话，节点将向客户端返回一个 ASK 错误，引导客户端转向正在导入槽的目标节点，并再次发送命令。

接到 ASK 错误的客户端会根据错误提供的 IP 地址和端口，转向至正在导入槽的目标节点，然后首先向目标节点发送一个 ASKING 命令，然后才发送命令。这是因为如果客户端不发送 ASKING 命令，那么客户端发送的命令将被节点拒绝执行，并返回 MOVED 错误，如此一来就形成了重定向循环。

如下图示例所示：Slot 2 正在从实例 2 往实例 3 迁移，key1 和 key2 已经迁移过去，key3 和 key4 还在实例 2 上。当客户端向实例 2 请求 key2 后，就会收到实例 2 返回的 ASK 命令。

和 MOVED 命令不同，ASK 命令并不会更新客户端缓存的哈希槽分配信息。所以，在上图中，如果客户端再次请求 Slot 2 中的数据，它还是会给实例 2 发送请求。这也就是说，ASK 命令的作用只是让客户端能给新实例发送一次请求，而不像 MOVED 命令那样，会更改本地缓存，让后续所有命令都发往新实例。

集群主从复制

Redis 集群中的节点分为主节点（master）和从节点（slave），其中主节点用于处理槽，而从节点则用于复制某个主节点，并在被复制的主节点下线时，代替下线主节点继续处理命令请求。向一个节点发送 CLUSTER REPLICATE <node_id> 命令可以让接收命令的节点成为 node_id 所指定节点的从节点，并开始对主节点进行复制（集群模式下 REPLICAOF 命令不支持）：

接收到该命令的节点首先会在自己的 clusterState.nodes 字典中找到 node_id 对应节点的 clusterNode 结构，并将自己的 clusterNode.slaveof 指针指向这个结构，以此来记录这个节点正在复制的主节点。

然后节点会修改自己节点的 clusterNode.flags 属性值，关闭 master 标识，打开 slave 标识，表示这个节点经由原来的主节点变成了从节点。

最后，节点会对主节点进行复制，这一过程和单机 Redis 服务器的复制功能一样。

一个节点成为从节点，并开始复制某个主节点这一信息会通过消息发送给集群中的其他节点，最终集群中的所有节点都会知道某个从节点正在复制某个主节点。集群中的所有节点都会在代表主节点的 clusterNode 结构的 slaves 属性和 numslaves 属性中记录正在复制这个主节点的从节点名单。

typedef struct clusterNode {
    // 正在复制这个主节点的从节点数量
    int numslaves;
    // 每个数组项指向一个正在复制这个主节点的从节点的clusterNode结构
    struct clusterNode **slaves;
    // 如果这是一个从节点，则指向主节点
    struct clusterNode *slaveof;
    ......
} clusterNode;

集群主从复制时的结构如下所示：

集群故障转移

1. 故障检测

集群中的每个节点都会定期地向集群中的其他节点发送 PING 消息，以此来检测对方是否在线，如果接收 PING 消息的节点没有在规定的时间内返回 PONG 消息，那么发送 PING 消息的节点就会将接收 PING 消息的节点标记为疑似下线（probable fail，PFAIL）。超时时间通过 cluster-node-timeout 指定：

集群中的各个节点会通过互相发送消息的方式来交换集群中各个节点的状态信息，例如某个节点是处于在线状态、疑似下线状态（PFAIL）还是已下线状态（FAIL）。当一个主节点 A 通过消息得知主节点 B 认为主节点 C 进入了疑似下线状态时，主节点 A 会在自己的 clusterState.nodes 字典中找到主节点 C 所对应的 clusterNode 结构，并将主节点 B 的下线报告（failure report）添加到 clusterNode 结构的 fail_reports 链表里面：

typedef struct clusterNode {
    // 该链表记录了所有其他节点对该节点的下线报告
    list *fail_reports;
    ......
} clusterNode;

每个下线报告由一个 clusterNodeFailReport 结构表示：

typedef struct clusterNodeFailReport {
    // 报告目标节点已经下线的节点
    struct clusterNode *node;
    // 最后一次从node节点收到下线报告的时间，与当前时间相差太久的下线报告会被删除
    mstime_t time;
} clusterNodeFailReport;

如果在一个集群里面，半数以上负责处理槽的主节点都将某个主节点 x 报告为疑似下线，那么这个主节点 x 将被标记为已下线（FAIL），将主节点 x 标记为已下线的节点会向集群广播一条关于主节点 x 的 FAIL 的消息，所有收到这条 FAIL 消息的节点（包括故障节点的从节点）都会立即将主节点 x 标记为已下线。

2. 故障转移

当一个从节点通过内部定时任务发现自己正在复制的主节点进入了已下线状态时，从节点将开始对下线主节点进行故障转移，以下是故障转移的执行步骤：

复制下线主节点的所有从节点里面，会有一个从节点被选中。
被选中的从节点会执行 REPLICAOF no one 命令，成为新的主节点。
新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己。
新的主节点向集群广播一条 PONG 消息，可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点已经接管了原本由已下线节点负责处理的槽。
新的主节点开始接收和自己负责处理的槽有关的命令请求，故障转移完成。
3. 选主过程
新的主节点是通过选举产生的，以下是集群选举新的主节点的过程：

1）集群的配置纪元是一个自增计数器，它的初始值为 0。当集群里的某个节点开始一次故障转移操作时，集群配置纪元的值会加一。对于每个配置纪元，集群里每个负责处理槽的主节点都有一次投票的机会，而第一个向主节点要求投票的从节点将获得主节点的投票。

2）当从节点发现自己正在复制的主节点进人已下线状态时，从节点会向集群广播一条消息，要求所有收到这条消息、并且具有投票权的主节点向这个从节点投票。如果一个主节点具有投票权（它正在负责处理槽）并且尚未投票给他从节点，那么主节点投给该从节点，表示这个主节点支持从节点成为新的主节点。

注意：从节点会根据节点优先级、复制偏移量等因素延迟投票，目的是保证具有更高优先级、更大的复制偏移量的节点比其他从节点提前发起投票，以获得更多的票数。

3）每个参与选举的从节点都会统计自己获得了多少主节点的支持。如果集群里有 N 个具有投票权的主节点，那么当一个从节点收集到大于等于 N/2 + 1 张支持票时，这个从节点就会当选为新的主节点。因为在一个配置纪元里，每个具有投票权的主节点只能投一次票，所以如果有 N 个主节点投票，那么具有大于等于 N/2 + 1 张支持票的从节点只会有一个，这确保了新的主节点只会有一个。

4）如果在一个配置纪元里面没有从节点能收集到足够多的支持票，那么集群会进入一个新的配置纪元，并再次进行选举，直到选出新的主节点为止。选举新主节点的方法和选举领头 Sentinel 的方法非常相似，因为两者都是基于 Raft 算法的领导者选举（Leader Election）方法来实现的。

集群功能限制

key 批量操作支持有限。如 mset、mget，目前只支持具有相同 slot 值的 key 执行批量操作。不过，我们可以利用 hash_tag 机制让不同的键映射到相同的槽中，以支持集群环境下的批量操作命令。
key 事务操作支持有限。只支持多 key 在同一节点上的事务操作。
不支持多数据库空间。单机 Redis 可支持 16 个数据库，集群模式下只能使用一个数据库空间。
复制结构只支持一层，从节点只能复制主节点，不支持嵌套树状复制结构。

Redis Cluster