引言

• Redis集群是Redis提供的分布式数据库方案(每个数据库保存一部分数据)，集群通过分片来进行数据共享，并提供复制和故障转移功能
• 集群中的16384(2018*8个二进制位)个槽，可以分别指派给集群中的各个节点(一个槽只能指定给一个节点)，每个节点都会记录哪些槽指派给了自己，而哪些槽又指派给了其他节点；
• 当节点接收到一个命令请求时，会先检查这个命令请求要处理的键所在的槽是否由自己负责，如果不是的话，节点将会向客户端返回一个MOVE错误，MOVE错误携带的信息可以指引客户端转向正在负责相关槽的节点；
• slot_number(key)方法用来计算键属于哪个槽，通过计算key的CRC-16校验和，然后生成介于0到16383之间的整数值；

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

• Redis集群在运行过程中，可以通过重新分片操作将任意数量已经指定给某个节点(源节点)的槽改为指派给另一个节点(目标节点)；
• Redis集群中的节点可以分为主节点和从节点，多个主节点分配处理集群中的槽，主节点下的从节点复制主节点的操作，在主节点下线时，可以代替主节点成为新的主节点，处理命令请求；
• 集群中的节点通过发送和接收消息来进行通信，常见的消息包括:MEET、PING、PONG、PUBLISH、FAIL五种；

客户端命令

• 客户端命令是指可以在以集群模式启动的客户端向集群节点发送的命令；

CLUSTER MEET

• 将节点添加到自己所在的集群

CLUSTER MEET <ip> <port>

CLUSTER ADDSLOTS

• 将一个或多个槽指派给节点负责

CLUSTER ADDSLOTS <slot> [slot ...]

CLUSTER REPLICATE

• 将节点指定为node_id所指定节点的从节点，并开始对主节点进行复制

CLUSTER REPLICATE <node_id>

1. 集群节点

• 一个集群节点就是一个运行在集群模式下的Redis服务器，Redis服务器在启动时会根据cluster-enabled配置来决定是否开启服务器的集群模式，默认情况下是不开启集群模式的

# Normal Redis instances can't be part of a Redis Cluster; only nodes that are
# started as cluster nodes can. In order to start a Redis instance as a
# cluster node enable the cluster support uncommenting the following:
#
# cluster-enabled yes

• 一个Redis集群通常由多个节点组成，在刚开始的时候，每个节点都是互相独立的，它们都处于一个只包含自己的集群中；
• 要组建一个真正可工作的集群，首先要将各个独立的节点连接起来，构成一个包含多个节点的集群，连接各个节点的工作可以使用cluster meet命令完成

CLUSTER MEET <ip> <port>

• 执行CLUSTER MEET命令的节点(源节点)，可以将ip:port节点(目标节点)，拉入源节点所在的集群；
• 连接集群节点，执行集群命令(如 CLUSTER开头的命令)的客户端，需要以集群模式启动(加-c参数)

[~]$ redis-cli -c -p 6379

1.1 集群数据结构

• 集群模式下运行的Redis节点，除了会使用redisServer和redisClient结构保存服务器和客户端状态外，还会使用clusterNode、clusterLink、clusterState结构保存集群信息；

clusterState结构

• clusterState结构记录在当前节点的视角下集群目前的状态，例如：集群是否上线、集群包含多少个节点、集群当前的配置纪元等；
• 每个节点都保存一个clusterState结构；

typedef struct clusterState{// 指向当前节点的指针clusterNode *myself;// 集群当前的配置纪元，用于实现故障转移uint64_t currentEpoch;// 集群当前的状态：是在线还是下线int state;// 集群中至少处理着一个槽的节点的数量int size;// 集群节点名单（包括myself节点）// 字典的键为节点的名字、字典的值为节点对应的clusterNode结构dict *nodes;// 每个槽处理的节点clusterNodes *slots[16384];// ...
}

clusterNode结构

• clusterNode结构保存了一个节点的当前状态，比如节点的创建时间、节点的名字、节点当前的配置纪元、节点的IP地址和端口号信息等；
• 每个节点都会使用一个clusterNode结构来记录自己的状态，并为集群中的所有其他节点都创建一个相应的clusterNode结构来记录其他节点的状态；

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;// 记录节点负责处理的槽位// 是一个二进制数组，索引位置为1的槽，表示是当前节点负责处理的// 2048个字节，共 2048*8=16384位unsigned char slots[2048];// 记录当前节点处理的槽数量int numbers;// ...
}

clusterLink结构

• clusterLink结构保存了连接该节点所需的有关信息，比如套接字描述符，输入缓冲区和输出缓冲区；

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

1.2 节点启动

• 一个集群节点就是一个运行在集群模式下的Redis服务器，Redis服务器在启动时会根据cluster-enable配置选项来决定是否开启服务器的集群模式；
• 运行在集群模式下的Redis服务器，会继续使用所有在单机模式(一个Redis作为一个完整的服务器)下使用的服务器组件，包括持久化、主从复制等；
• 通过客户端(加-c以集群模式启动)向节点A发送CLUSTER MEET <ip> <port>命令，可以让节点A将另一个节点B(ip:port)添加到节点A所在的集群里面(拉入集群)；
• 节点A会与节点B进行握手，在这个过程中会为节点B创建一个clusterNode结构，并将该结构添加到自己的clusterState.nodes字典里；
• 节点A与节点B握手完成后，会将节点B的信息通过Gossip协议传播给集群中的其他节点，其他节点收到消息后也会节点B握手，最终经过一段时间后，节点B会被集群中的所有节点认识；

2. 槽指派

• Redis集群通过分片的方式来保存数据库中的键值对(不同的键值对保存在不同的集群节点上)；
• 集群的整个数据库被分为16834(2048*8)个槽(slot),集群中的每个节点可以处理0个或最多16834个槽；
• 当数据库中的16384个槽都有节点在处理时，集群处于上线状态，相反地，如果数据库中有任何一个槽没有得到处理，那么集群处于下线状态；
• 集群节点保存键值对以及键值对过期的方式与单机Redis服务器方式完全相同；与单机服务器在数据库方面的一个区别是：节点只能使用0号数据库；
• cluster addslot <number>命令将一个或多个槽位指派给节点负责；

2.1 记录节点的槽指派信息

每个节点的clusterNode结构都有一个slots和numslot属性(数据结构见上)：

• slots是一个二进制位数组，负责记录当前节点处理的槽位。数组的长度是2048个字节，共包含16384个二进制位，以0位起始索引，以16383为终止索引，如果数组在索引i上的二进制位的值为1，那么表示该节点负责处理槽位i;
• numslot记录当前节点处理的槽位数量；

2.2 传播节点的槽指派信息

• 一个节点除了会将自己负责处理的槽位记录在clusterNode结构的slots属性和numslots属性外，还会将自己的slots数组通过消息发送给集群中的其他节点，以此来告知节点自己目前负责处理哪些槽；
• 集群中每个节点都会将自己的slots数组通过消息发送给集群中的其他节点，并且每个接收到slots数组的节点都会将数组保存到相应节点的clusterNode结构里，因此，集群中的每个节点都会知道数据库中的16384个槽分别被指派给了集群中的哪些节点；

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

• 除了在节点结构里记录各自节点处理的槽，clusterState结构里还记录了集群中所有16384个槽对应的处理节点；
• clusterState结构的slots数组元素是一个指向clusterNode结构的指针，指向处理槽i的节点（数据结构见上）；

同时使用clusterState的slots记录所有槽的指派节点，和使用clusterNode结构的slots记录当前节点处理的槽信息，使查找槽指派信息更高效：

• 使用clusterState里的slots属性，使得查询槽i是否被指派，或者槽i被指派给了哪些节点的操作更高效，如果从clusterNode的slots结构查询，则需要遍历所有clusterNode结构；
• 使用clusterNode里的slots属性，使得每个节点给其他节点传播自己处理的槽信息时比较高效，否则程序需要先遍历整个clusterState.slots数组；

3. 在集群中执行命令

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

当客户端(集群模式启动)向集群中某一个节点，发送与数据库键有关的命令时，接收命令的节点会计算键属于哪个槽，并检查这个槽是否指派给了自己：

• 如果键所在的槽正好就指派给了自己，那么该节点直接执行这个命令；
• 如果键所在的槽没有指派给自己，那么节点会向客户端返回一个MOVE错误消息，该消息里携带处理这个槽的节点信息，客户端接收到MOVE错误消息后，转向连接这个节点，并再次发送要执行的命令；

说明：

• 以集群模式启动的客户端，在接收到MOVE错误消息后，会执行自动转向，连接向处理该槽位的节点，然后将命令发送给该节点。在进行连接转移过程中只会打印Redirected to slot [6257] located at 127.0.0.1:7001一条这样的语句，并不会将MOVE错误打印出来；
• 如果客户端没有以集群模式启动，那么客户端不清楚MOVE错误的作用，所以不会自动转向，只会将错误信息直接打印出来；

3.1 计算键属于的槽

• slot_number(key)方法用来计算键属于哪个槽，通过计算key的CRC-16校验和，然后生成介于0到16383之间的整数值；

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

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

当节点计算出键所属的槽i之后，会检查自己在clusterState.slots数组中的项i,判断键所在的槽是否由自己负责：

• 如果clusterState.slots[i]等于clusterState.myself，那么说明槽i由当前节点负责，节点可以执行客户端发送的命令；
• 如果clusterState.slots[i]不等于clusterState.myself，那么说明槽i并非由当前节点负责，节点会根据clusterState.slots[i]执向的clusterNode结构所记录的节点IP和端口号，向客户端返回MOVE错误，指引客户端转向正在处理槽i的节点；

4. 重新分片

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

4.1 重新分片原理

Redis集群的重新分片操作由Redis的集群管理软件redis-trib负责执行；

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

• redis-trib对目标节点发送CLUSTER SETSLOT <slot> IMPORTING <source_id>命令，让目标节点准备好从源节点导入属于槽slot的键值对；
• redis-trib对源节点发送CLUSTER SETSLOT <slot> MIGRATING <target_Id>命令，让源节点准备好将属于槽slot的键值对迁移至目标节点；
• redis-trib向源节点发送CLUSTER GETKEYSINSLOT <slot> <count>命令，获得最多count个属于槽slot的键值对的键名；
• 对获得的属于槽slot的每个键，redis-trib都向源节点发送一个MIGRATE <target_ip> <target_port> <key_name> 0 <timeout>命令，将被选中的键原子地从源节点迁移至目标节点；
• 重复执行获取槽slot的count个键，和迁移到目标节点，直到源节点保存的所有属于槽slot的键值对都被迁移至目标节点为止；
• redis-trib向集群中任意一个节点发送CLUSTER SETSLOT <slot> NODE <target_id>命令，将槽slot指派给目标节点，这一指派信息会通过消息发送至整个集群，最终集群中的所有节点都会知道槽slot已经指派给了目标节点；

如果重新分片涉及多个槽，那么redis-trib将对每个给定的槽分别执行上面给出的步骤；

4.2 ASK错误

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

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

• 源节点会先在自己的数据库里查找键，如果找到的话，就执行客户端发送的命令；
• 如果源节点没能在自己的数据库里找到键，那么这个键有可能已经被迁移到目标节点，源节点将向客户端发送一个ASK错误，指引客户端转向正在导入槽的目标节点，并再次发送之前想要执行的命令(由以集群模式启动的客户端自动转向请求目标节点)；

和接到MOVED错误类似，集群模式的客户端在接到ASK错误时也不会打印错误，而是会自动根据错误提供的IP地址和端口进行转向操作；但是，如果客户端不是以集群模式启动，则客户端不清楚ASK错误的作用，只是会把错误信息打印出来；

4.3 ASKING命令

接到ASK错误的客户端在向目标节点发送请求时，会先发送一个ASKING命令，打开该客户端的REDIS_ASKING标识，之后再重新发送原本想要执行的命令：

• 在一般情况下，如果客户端向节点发送一个关于槽i的命令，而槽i又没有指派给这个节点的话，那么节点将向客户端返回一个MOVED错误，指引客户端转向连接处理这个槽的节点；
• 如果节点的clusterState.importing_slots_from[i]显示节点正在导入槽i,则节点会判断客户端是否带有ASKING标识，对于带有ASKING标识的客户端命令，节点将执行这个关于槽i的命令一次，如果客户端没有ASKING标识，则节点拒绝执行，并返回MOVED错误；

分析:

• 重新分片过程中，槽i的所有键值对都从源节点转移到目标节点后，才会向集群通知槽i的处理指派给目标节点，所以在转移过程中，所有的MOVED错误都会将处理槽i的节点指向源节点；
• 但是在转移过程中，已经有部分键值对转移到了目标节点，向源节点发送命令处理这部分键时，源节点会返回ASK错误，指引客户端连向目标节点，客户端发送键处理命令之前先发送ASKING命令，表示客户端是由源节点指引来的；这时目标节点如果判断节点正在导入槽，则破例执行一次客户端发送的命令；

注意：

• ASKING命令的作用是打开客户端的REDIS_ASKING标识；
• 客户端的REDIS_ASKING标识是一个一次性标识，当节点执行了带有该标识的客户端发送的命令后，客户端的REDIS_ASKING标识就会被移除，意思是客户端的ASKING命令只对接下来的一个命令有效；

4.4 ASK错误与MOVED错误的区别

ASK错误和MOVED错误都会导致客户端转向，它们的区别是：

• MOVED错误代表槽的负责权已经从一个节点转移到了另一个节点，在客户端接收到关于槽i的MOVED错误之后，客户端每次遇到关于槽i的命令请求时，都可以直接将命令请求发送至MOVED错误所指向的节点；
• ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施，在客户端收到关于槽i的ASK错误之后，客户端只会在接下来的一次命令请求中将关于槽i的命令发送至ASK错误所指示的节点，但这种转向不会对客户端今后发送关于槽i的命令请求产生影响；

5. 复制与故障转移

5.1 主从节点

• Redis集群中的节点分为主节点和从节点，其中主节点用于处理槽，而从节点则用于复制某个主节点，并在被复制的主节点下线时代替主节点继续处理命令请求；
• 向一个节点发送CLUSTER REPLICATE <node_id>可以让该节点成为node_id所指定节点的从节点，并开始对主节点进行复制（不是执行单机复制的slaveof命令）；

5.2 故障检测

• 集群中每个节点(主节点和从节点)都会定期向集群中的其他节点发送PING消息(心跳检测)，如果接收PING消息的节点没有在规定的时间内返回PONG消息，那么发送节点就会将接收节点标记为疑似下线（probable fail）;
• 如果一个集群里面，半数以上负责处理槽的主节点将某个主节点x标记为疑似下线，那么这个主节点x将被标记为已下线（FAIL）,将主节点x标记为已下线的节点会向集群广播一条关于主节点x的FAIL消息，所有收到这条消息的节点(主节点和从节点)都会立即将主节点x标记为已下线；

5.3 故障转移

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

• 检测到主节点下线的从节点向集群广播一条CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST消息，要求所有收到这条消息、并且具有投票权的主节点向这个从节点投票；
• 如果一个从节点收集到大于等于N/2+1个主节点的投票时(N是具有投票权的主节点数)，会被选举为新的主节点；执行SLAVEOF no one命令，成为新的主节点；
• 新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己；
• 新的主节点向集群广播一条PONG消息，这条消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点接管了原本由已下线主节点负责处理的槽；
• 新的主节点开始接收和处理自己负责的槽有关的命令请求，故障转移完成；

5.4 选举新的主节点

• 当从节点发现自己复制的主节点进入已下线状态时，会向集群广播一条CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST消息，要求所有收到这条消息、并且具有投票权的主节点向这个从节点投票；
• 有投票权的主节点会将票投给第一个给自己发送投票消息的从节点，并且一个配置纪元里，一个主节点只能投票给一个从节点；
• 从节点收集自己的票数，当一个从节点收集到大于等于N/2+1(N是具有投票权的主节点的数量)张票后，这个从节点会被选为新的主节点；
• 如果在一个配置纪元里，没有从节点能收集到足够多的支持票，那么集群进入下一个新的配置纪元，并再次进行选举，直到选出新的主节点为止；

6. 集群消息

集群消息是用于集群节点之间相互通信用的(不是集群节点和客户端通信)，集群中的各个节点通过发送和接收消息来进行通信。

节点发送的消息主要有以下五种：

• MEET消息：当节点接收到客户端的CLUSTER MEET命令时(将目标节点拉入自己所在的集群)，节点会向目标节点发送MEET消息，请求目标节点加入自己所处的集群；
• PING消息：心跳检测消息，集群中每个节点默认每隔一秒会从已知节点列表中随机选择5个节点，然后向最长时间没有发送过PING消息的节点发送PING消息；另外，如果节点A最后一次接收到节点B发送的PONG消息距离当前时间超过了节点A的cluster-node-timeout设置的一半，那么也会向节点B发送PING消息；
• PONG消息：对MEET消息或PING消息的回复，也可以通过PONG消息向集群中广播自己的信息(自己的信息在消息头里)
• FAIL消息：当一个主节点A判断到另一个主节点B已经进入下线状态时，节点A会向集群中广播一条关于节点B的FAIL消息，所有接收到这条消息的节点都会立即将节点B标记为已下线；
• PUBLISH消息：广播命令，当节点接收到一个PUBLISH命令时，节点会执行这个命令，并向集群中广播一条PUBLISH消息，所有接收到这条PUBLISH消息的节点都会执行相同的PUBLISH命令；

6.1 消息结构

节点发送的所有消息都由一个消息头包裹，消息头除了包含消息正文之外，还记录了消息发送者自身的一些消息。使用结构clusterMsg表示；

typedef struct {// 消息的长度（包括这个消息头和消息正文的长度）uint32_t totlen;// 消息的类型uint16_t type;// 消息正文包含的节点信息数量// 只在发送 PING、PONG 、MEET 时使用uint16_t count;// 发送者所处的配置纪元uint64_t currentEpoch;// 如果发送者是一个主节点，那么这里记录的是发送者的配置纪元// 如果发送者是一个从节点，那么这里记录的是发送者正在复制的主节点的配置纪元uint64_t configEpoch;// 发送者的名字（ID）char sender[REDIS_CLUSTER_NAMELEN];// 发送者目前的槽指派信息unsinged char myslots[REDIS_CLUSTER_SLOTS/8];// 如果发送者是一个主节点，这里记录的是REDIS_NODE_NULL_NAME// 如果发送者是一个从节点，这里记录的是发送者正在复制的主节点的名字char slaveof[REDIS_CLUSTER_NAMELEN];// 发送者的端口号uint16_t port;// 发送者的标识值uint16_t flags;// 发送者所处的集群的状态unsigned char state;// 消息的正文union clusterMsgData data;}clusterMsg;

7. Gossip协议

• Gossip是八卦的意思，Gossip算法又叫谣言传播算法或病毒传播算法等，
• 它的作用是在有限的时间内，让所有人都知道一个消息；
• Gossip过程由一个种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围的几个节点散播消息，收到消息的节点也会重复该过程，直到网络中的所有节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，只能保证理论上最终节点都会收到消息，因此它是一个最终一致性协议。

Gossip协议特点：

• 周期性散播消息；
• 被感染节点随机选择K个邻接节点散播消息；
• 每次散播消息都选择对尚未发送过消息的节点散播；
• 收到消息的节点不再向发送节点散播；

参考文献

• 《Redis设计与实现》黄建宏 著，机械工业出版社.