什么是集群

能够对外提供相同服务的多台服务器组成的集合。

为什么要建立集群

1.从可用性角度考虑，如果只有一台机器提供服务，一旦出现故障，那么整个服务不可用。

2.从容量角度考虑，当服务访问量上升，单台机器无法支撑访问量时，必然要扩容。

如何建立集群

当有新的节点要加入集群时，客户端可以任选集群中的一个节点，比如A，跟新节点B通过握手建立连接，然后A会将B加入的信息通过Gossip消息通知给集群中的其他节点，其他节点也通过握手跟新节点建立连接。

这里面有几个问题需要回答：

如何进行握手？

如何进行集群状态同步？

如何保存/寻址键值对？

如何进行扩容？

如何进行故障转移？

集群数据结构

在介绍具体功能之前，我们先介绍一下集群的数据结构。

typedef struct clusterState {
    // 指向当前节点的指针
    clusterNode *myself;
    // 集群当前的配置纪元，用于实现故障转移
    unit64_t currentEpoch;
    // 集群当前的状态：是在线还是下线
    int state;
    // 集群中至少处理着一个槽的节点的数量
    int size;
    // 集群节点名单（包括myself节点），字典的键为节点的名字，字典的值为节点对应的clusterNode结构
    dict *nodes;
    // 记录了集群中所有16384个槽的指派信息
    clusterNode *slots[16384];
    // 使用跳跃表保存槽和键之间的关系
    zskiplist *slots_to_keys;
    // 记录当前节点正在从其他节点倒入的槽
    clusterNode *importing_slots_from[16384];
    // 记录当前节点正在迁移至其他节点的槽
    clusterNode *migrating_slots_to[16384];

} clusterState;

struct clusterNode {
    // 创建节点的时间
    mstime_t ctime;
    // 节点的名字，由40个字十六进制字符串组成
    char name[REDIS_CLUSTER_NAMELEN];
    // 节点的标识，使用各种不同的标识值记录节点的角色（比如主节点或者从节点），以及节点目前所处的状态（比如在线或者下线）
    int flags;
    // 节点当前的配置纪元，用于实现故障转移
    uint64_t configEpoch;
    // 节点IP地址
    char ip[REDIS_IP_STR_LEN];
    // 节点的端口号
    int port;
    // 保存连接节点所需的有关信息
    clusterLink *link;
    // 二进制位数组，记录节点负责处理哪些槽
    unsigned char slots[16384/8];
    // 记录节点负责处理的槽的数量，即是slots数组中值为1的二进制位的数量
    int numslots;
    // 如果这是个从节点，指向要复制的主节点的clusterNode结构
    struct clusterNode *slaveof;
    // 正在复制这个主节点的从节点数量
    int numslaves;
    // 一个数据组，每个数组项指向一个正在复制这个主节点的从节点的clusterNode结构
    struct clusterNode **slaves;
    // 一个链表，记录了所有其他节点对该节点的下线报告， 每个下线报告由一个clusterNodeFailReport结构表示
    list *fail_reports;

};

typedef struct clusterLink {
    // 连接的创建时间
    mstime_t ctime;
    // TCP 套接字描述符
    int fd;
    // 输出缓冲区，保存着待发送给其他节点的消息（message）
    sds sndbuf;
    // 输入缓冲区，保存着从其他节点接收到的消息
    sds rcvbuf;
    // 与这个连接相关联的节点，如果没有的话就为NULL
    struct clusterNode *node;
} clusterLink;

struct clusterNodeFailReport {
    // 报告目标节点已经下线的节点
    struct clusterNode *node;
    // 最后一次从node节点收到下线报告的时间
    // 程序使用这个时间戳来检查下线报告是否过期
    // （与当前时间戳相差太久的下线报告会被删除）
    mstime_t time;
}

每个Redis服务器上都维护一个集群状态对象clusterState，记录了集群状态、集群版本号、当前节点、集群中所有的节点名单、槽指派信息、槽和键的关系、槽迁移信息，这些信息会在相应的场景中用到。

如何进行握手

通过MEET命令实现节点之间握手建联。

命令格式：

CLUSTER MEET <ip> <port>

首先客户端向节点A发送MEET命令，将节点B加入到A的集群状态对象中。然后A再向B发送MEET命令，将节点A加入到B的集群状态对象中，然后B向A发送一个PONG消息作为响应，A收到B的PONG消息再回复一个PING消息作为响应，这样通过3次握手，A跟B建立了连接。然后A通过Gossip消息广播给集群中的其他节点，其他节点以同样的方式跟B建立连接。

握手的过程：

假设节点A的IP、端口分别为127.0.0.1:7000，节点B的IP、端口分别为127.0.0.1:7001，节点C的IP、端口分别为127.0.0.1:7002，以下展示的是节点A的集群状态对象clusterState。

如何进行状态同步

刚刚讲到节点之间通过Gossip消息进行状态同步，感兴趣的可以了解一下Gossip协议介绍。

https://blog.csdn.net/qq_43590614/article/details/115131473

https://zhuanlan.zhihu.com/p/162970961

集群如何保存键值对

槽指派

集群的整个数据库被分为16384个槽，每个键值对都属于这16384个槽中的一个，每个节点可以处理0个或最多16384个槽。

当数据库中16384个槽都有节点在处理时，集群处于上线状态；相反地，如果有任何一个槽没有节点处理，那么集群处于下线状态。

通过CLUSTER ADDSLOTS <slot> [slot …]命令将槽指派给节点负责。

举例：

将槽0-5000指派给节点7000负责：

127.0.0.1:7000> CLUSTER ADDSLOTS 0 1 2 … 5000

将槽5001-10000指派给节点7001负责：

127.0.0.1:7001> CLUSTER ADDSLOTS 5001 5002 5003 … 10000

将槽10001-16383指派给节点7002负责：

127.0.0.1:7002> CLUSTER ADDSLOTS 10001 10002 10003 … 16383

进行槽指派前执行CLUSTER INFO：

127.0.0.1:7000> CLUSTER INFO

cluster_state:fail

进行槽指派后执行CLUSTER INFO：

127.0.0.1:7000> CLUSTER INFO

cluster_state:ok

说明槽指派完成后，集群进入上线状态。

接下来介绍节点保存槽指派信息的方法，以及节点之间传播槽指派信息的方法。

所谓槽，其实就是二进制位，节点用二进制数组来保存槽信息。

struct clusterNode {
    // ...
    
    // 二进制位数组，记录节点负责处理哪些槽
    unsigned char slots[16384/8];
    // 记录节点负责处理的槽的数量，即是slots数组中值为1的二进制位的数量
    int numslots;
    
    // ...
};

如果slots数组在索引i上的二进制位的值为1，那么表示节点负责处理槽i。

如果slots数组在索引i上的二进制位的值为0，那么表示节点不负责处理槽i。

传播节点的槽指派信息

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

当节点A通过消息从节点B那里接收到节点B的slots数组时，节点A会在自己的clusterState.nodes字典中查找节点B对应的clusterNode结构，并对结构中的slots数组进行保存或者更新。

这样集群中的每个节点都会知道数据库中的16384个槽分别被指派给了哪些节点。

记录集群所有槽的指派信息：

typedef struct clusterState {
    // ...
    
    // 记录了集群中所有16384个槽的指派信息
    clusterNode *slots[16384];
    
    // ...
} clusterState;

slots数组包含16384个项，每个数组项都是一个指向clusterNode结构的指针：

如果slots[i]指针指向NULL，那么表示槽i尚未指派给任何节点。

如果slots[i]指针指向一个clusterNode结构，那么表示槽i已经指派给了clusterNode结构所代表的节点。

集群如何寻址键值对

当客户端向节点发送数据库键命令，节点会计算出键属于哪个槽，再判断这个槽是否指派给了自己：

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

判断流程如下：

计算键属于哪个槽

def slot_number(key):
    return CRC16(key) & 16383

先计算key的CRC16校验码，再对16383取余，计算出一个介于0-16383之间的整数作为键的槽号。

判断槽是否由当前节点负责处理

判断clusterState.slots[i]对应的节点是否等于clusterState.myself，如果等于，由当前节点处理；不等于，返回MOVED错误，指向clusterState.slots[i]对应的节点。

MOVED错误

当节点发现键所在的槽不是由自己处理时，会向客户端返回一个MOVED错误，并将客户端重定向到正确的节点。

MOVED错误的格式：

MOVED <slot> <ip>:<port>

其中slot为键所在的槽，ip和port为负责处理槽的节点IP和端口号。

例如：

MOVED 10086 127.0.0.1：7002

表示槽10086由IP为127.0.0.1，端口号为7002的节点处理。

集群扩容/缩容如何重新分片

当集群需要扩容或缩容时，机器数变了，为了保证槽分布均匀，需要对槽重新指派，并且属于槽的键值对也要做相应的迁移。

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

重新分片的实现原理

ASK错误

在进行重新分片过程中，源节点的某个槽正在进行迁移，属于被迁移槽的一部分键值对保存在源节点里面，另一部分键值对保存在目标节点里面。这时候如果节点收到一个关于键的命令，需要判断键所属的槽是否发生迁移。

集群执行命令的完整过程（考虑MOVED错误和ASK错误）：

集群如何进行故障转移

节点N1、N4、N7是主节点，节点N2、N3、N5、N6、N8、N9为从节点。

集群进行故障检测到N1进入下线状态：

集群通过选举算法，从N1的从节点中选出新的主节点，比如N2被选为新的主节点：

当节点N1重新上线，成为N2的从节点：

这里涉及到几个重要的过程，故障检测、故障转移、选举主节点、设置从节点，下面详细说明。

故障检测

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

集群中各个节点会通过互相发送消息的方式来交换集群中各个节点的状态，例如某个节点是处于在线状态、疑似下线状态（PFAIL），还是已下线状态（FAIL）。

当一个节点A收到B的消息，B认为C疑似下线，A会在clusterState.nodes中找到C对应的clusterNode结构，将B的下线报告添加到clusterNode中的fail_reports链表里面。

如果A发现C的fail_reports中有超过半数的节点的下线报告，那么A会将C标记为已下线（FAIL），并将C已下线的消息广播给集群中的其他节点，所有收到FAIL消息的节点都会将C标记为已下线。

（1）N4检测N1心跳失败，生成N1的心跳失败记录。

（2）N7检测N1心跳失败，生成N1的心跳失败记录。

（3）N4、N7之间互相交换消息，N4收到N7的消息，合并心跳失败记录。

（4）N4检测到超过半数节点的下线报告，标记N1为已下线，并广播给其他节点。

故障转移

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

（1）复制下线主节点的所有从节点里面，会有一个从节点被选中。

（2）被选中的从节点会执行SLAVEOF no one命令，成为新的主节点。

（3）新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己。

（4）新的主节点向集群广播一条PONG消息，这条PONG消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点已经接管了原本由已下线节点负责处理的槽。

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

选举新的主节点

以下是集群选举新的主节点的方法：

（1）集群的配置纪元是一个自增计数器，它的初始值为0。

（2）当集群里的某个节点开始一次故障转移操作时，集群配置纪元的值会被增一。

（3）对于每个配置纪元，集群里每个负责处理槽的主节点都有一次投票的机会，而第一个向主节点要求投票的从节点将获得主节点的投票。

（4）当从节点发现自己正在复制的主节点进入已下线状态时，从节点会向集群广播一条CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST消息，要求所有收到这条消息、并且具有投票权的主节点向这个从节点投票。

（5）如果一个主节点具有投票权（它正在负责处理槽），并且这个主节点尚未投票给其他从节点，那么主节点将向要求投票的从节点返回一条CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息，表示这个主节点支持从节点成为新的主节点。

（6）每个参与选举的从节点都会接收CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息，并根据自己收到了多少条这种消息来统计自己获得了多少主节点的支持。

（7）如果集群里有N个具有投票权的主节点，那么当一个从节点收集到大于等于N/2+1张支持票时，这个从节点就会当选为新的主节点。

（8）因为在每一个配置纪元里面，每个具有投票权的主节点只能投一次票，所以如果有N个主节点进行投票，那么具有大于等于N/2+1张支持票的从节点只会有一个，这确保了新的主节点只会有一个。

（9）如果在一个配置纪元里面没有从节点能收集到足够多的支持票，那么集群进入一个新的配置纪元，并再次进行选举，直到选出新的主节点为止。

这个选举方法是基于Raft算法实现的。

设置从节点

向一个节点发送命令：

CLUSTER REPLICATE <node_id>

可以让接收命令的节点成为node_id所指定节点的从节点，并开始对主节点进行复制。

一个节点成为从节点，并开始复制某个主节点这一信息会通过消息发送给集群中的其他节点，最终集群中的所有节点都会知道某个从节点正在复制某个主节点。

集群中使用的消息

消息类型

消息体

MEET、PING、PONG消息的实现

Redis集群中的各个节点通过Gossip协议来交换各自关于不同节点的状态信息，其中Gossip协议由MEET、PING、PONG三种信息来实现，这三种消息的正文都由clusterMsgDataGossip结构组成的。

每次发送MEET、PONG、PING消息时，发送者都从自己的已知节点列表中随机选出两个节点（可以是主节点也可以是从节点），并将这两个被选中节点的信息分别保存到两个clusterMsgDataGossip结构里面。

clusterMsgDataGossip结构记录了被选中节点的名字，发送者与被选中节点最后一次发送和接收PING消息和PONG消息的时间戳，被选中节点的IP地址和端口号，以及被选中节点的标识值。

当接收者收到MEET、PING、PONG消息时，接收者会访问消息正文中的两个clusterMsgDataGossip结构，并根据自己是否认识clusterMsgDataGossip结构中记录的被选中节点来选择进行哪种操作：

如果被选中节点不存在于接收者的已知节点列表，那么说明接收者是第一次接触到被选中节点，接收者将根据结构中记录的IP地址和端口号等信息，与被选中节点进行握手。

如果被选中节点已经存在于接收者的已知节点列表，那么说明接收者之前已经与被选中的节点进行过接触，接收者将根据clusterMsgDataGossip结构记录的信息，对被选中节点所对应的clusterNode结构进行更新。

举个发送PING消息和返回PONG消息的例子，假设在一个包含A、B、C、D、E、F六个节点的集群里:

节点A向节点D发送PING消息，并且消息里面包含了节点B和节点C的信息，当节点D收到这条PING消息时，它将更新自己对节点B和节点C的认识。

之后，节点D将向节点A返回一条PONG消息，并且消息里面包含了节点E和节点F的消息，当节点A收到这条PONG消息时，它将更新自己对节点E和节点F的认识。

整个通信过程如下图所示

FAIL消息的实现