Redis Cluster 原理

一、CLUSTER MEET 命令的实现

通过向节点 A 发送 CLUSTER MEET 命令，客户端可以让接收命令的节点 A 将另一个节点 B 添加到节点 A 当前所在的集群里面：

CLUSTER MEET

收到命令的节点 A 将与节点 B 进行握手（handshake），以此来确认彼此的存在，并为将来的进一步通信打好基础：

1）节点 A 会为节点 B 创建一个 clusterNode 结构，并将该结构添加到自己的 clusterState.nodes 字典里面。

2）之后，节点 A 将根据 CLUSTER MEET 命令给定的 IP 地址和端口号，向节点 B 发送一条 MEET 消息。

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

4）之后，节点 B 将向节点 A 返回一条 PONG 消息。

5）如果一切顺利，节点 A 将收到节点 B 返回的 PONG 消息，通过这条 PONG 消息节点 A 可以知道节点 B 已经成功地接收到了自己发送的 MEET 消息。

6）之后，节点 A 将向节点 B 返回一条 PING 消息。

7）如果一切顺利，节点 B 将接收到节点 A 返回的 PING 消息，通过这条 PING 消息节点 B 可以知道节点 A 已经成功地接收到了自己返回的 PONG 消息，握手完成。

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

二、槽指派

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

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

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

CLUSTER ADDSLOTS [slot . . .]

127.0.0.1:7000> CLUSTER ADDSLOTS 0 1 2 3 4 . . . 5000

OK

127.0.0.1:7000> CLUSTER INFO

cluster_state:ok

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

struct clusterNode {

// ...

unsigned char slots[16384/8];

int numslots;

// ...

};

slots属性是一个二进制位数组（bit array），这个数组的长度为2048个字节，共包含16384个二进制位。如果slots数组在索引i上的二进制位的值为1，那么表示节点负责处理槽i，为0表示不负责。

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

clusterState结构中的slots数组记录了集群中所有16384个槽的指派信息：

typedef struct clusterState {

// ...

clusterNode *slots[16384]; // 每个数组项指向一个clusterNode

// ...

} clusterState;

三、在集群中执行命令

在对数据库中的16384个槽都进行了指派之后，集群就会进入上线状态，这时客户端就可以向集群中的节点发送数据命令了。

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

如果指派给了当前节点，节点直接执行这个命令。否则，节点会向客户端返回一个MOVED错误，指引客户端转向（redirect）至正确的节点，并再次发送之前想要执行的命令。

计算键属于那个槽：

def slot_number(key):

return CRC16(key) & 16383

// CRC-16校验和

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

clusterState.slots[i] == clusterState.myself

一个集群客户端通常会与集群中的多个节点创建套接字连接，而所谓的节点转向实际上就是换一个套接字来发送命令。

节点和单机服务器在数据库方面的一个区别是，节点只能使用0号数据库。

四、重新分片

Redis集群的重新分片操作可以将任意数量已经指派给某个节点（源节点）的槽改为指派给另一个节点（目标节点），并且相关槽所属的键值对也会从源节点移动到目标节点。（这里的重新分片不是rehash，请注意与客户端一致性hash分片区分开来）

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

重新分片操作由Redis的集群管理软件redis-trib负责执行，redis提供了进行重新分片所需的所有命令，而redis-trib则通过想源节点和目标节点发送命令来进行重新分片操作。

redis-trib对集群的单个槽slot进行重新分片的步骤如下：

1）redis-trib对目标节点发送CLUSTER SETSLOT IMPORTING <source_id>命令，让目标节点准备好从源节点导入（import）属于槽slot的键值对。

2）redis-trib对源节点发送CLUSTER SETSLOT MIGRATING <target_id>命令，让源节点准备好将属于槽slot的键值对迁移（migrate）至目标节点。

3）redis-trib向源节点发送CLUSTER GETKEYSINSLOT 命令，获得最多count个属于槽slot的键值对的键名。

4）对于步骤3获得的每个键名，redis-trib都向源节点发送一个MIGRATE <target_ip> <target_port> <key_name> 0 命令，将被选中的键原子地从源节点迁移至目标节点。

5）重复执行步骤3和步骤4，直到源节点保存的所有属于槽slot的键值对都被迁移至目标节点为止。

6）redis-trib向集群中的任意一个节点发送CLUSTER SETSLOT NODE <target_id>命令，将槽slot指派给目标节点，这一指派信息会通过消息发送至整个集群，最终集群中的所有节点都会知道槽slot已经被指派给了目标节点。

ASK错误：

在进行重新分片期间，源节点向目标节点迁移一个槽的过程中，可能会出现这样一种情况：属于被迁移槽的一部分键值对保存在源节点里面，而另一部分键值对则保存在目标节点里面。

当客户端向源节点发送一个与数据库键有关的命令，并且命令要处理的数据库键恰好就属于正在被迁移的槽时：

源节点会先在自己的数据库里面查找指定的键，如果找到的话，就直接执行客户端发送的命令。没找到的话，那么这个键有可能已经被迁移到了目标节点，源节点将向客户端返回一个ASK错误，指引客户端转向正在导入槽的目标节点，并再次发送之前想要执行的命令。

五、复制与故障转移

Redis集群中的节点分为主节点（master）和从节点（slave），其中主节点用于处理槽，而从节点则用于复制某个主节点，并在被复制的主节点下线时，代替下线主节点继续处理命令请求。

设置从节点 CLUSTER REPLICATE <node_id>

故障检测：

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

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

故障转移：

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

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

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

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

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

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

选举新的主节点：

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

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

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

4）档从节点发现自己正在复制的主节点进入已下线状态时，从节点会想集群广播一条CLUSTER_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）如果在一个配置纪元里面没有从节点能收集到足够多的支持票，那么集群进入一个新的配置纪元，并再次进行选举，知道选出新的主节点为止。

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