读书笔记:《Redis设计与实现》之集群

集群

概览

• Redis集群是Redis提供的分布式数据库方案，集群通过分片（sharding）来进行数据共享，并提供复制和故障转移功能

节点

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

CLUSTER MEET ＜ip＞ ＜port＞

启动节点

• Redis服务器在启动时会根据cluster-enabled配置选项是否为yes来决定是否开启服务器的集群模式
• 节点会继续使用所有在单机模式中使用的服务器组件
• 只有在集群模式下才会用到的数据，节点将它们保存到了cluster.h/clusterNode结构、cluster.h/clusterLink结构，以及cluster.h/clusterState结构里面

槽指派

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

记录节点的槽指派信息

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

struct clusterNode {
    // ...
    unsigned char slots[16384/8];
    int numslots;
    // ...
};

• Redis以0为起始索引，16383为终止索引，对slots数组中的16384个二进制位进行编号，并根据索引i上的二进制位的值来判断节点是否负责处理槽i

传播节点的槽指派信息

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

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

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

CLUSTER ADDSLOTS命令的实现

• CLUSTER ADDSLOTS命令接受一个或多个槽作为参数，并将所有输入的槽指派给接收该命令的节点负责

CLUSTER ADDSLOTS ＜slot＞ [slot ...]

CLUSTER ADDSLOTS 伪代码

def CLUSTER_ADDSLOTS(*all_input_slots):
    #遍历所有输入槽，检查它们是否都是未指派槽
    for i in all_input_slots:
        #如果有哪怕一个槽已经被指派给了某个节点
        #那么向客户端返回错误，并终止命令执行
        if clusterState.slots[i] != NULL:
            reply_error()
            return
    #如果所有输入槽都是未指派槽
    #那么再次遍历所有输入槽，将这些槽指派给当前节点
    for i in all_input_slots:
        #设置clusterState结构的slots数组
        #将slots[i]的指针指向代表当前节点的clusterNode结构
        clusterState.slots[i] = clusterState.myself
        #访问代表当前节点的clusterNode结构的slots数组
        #将数组在索引i上的二进制位设置为1
        setSlotBit(clusterState.myself.slots, i)

在集群中执行命令

• 在对数据库中的16384个槽都进行了指派之后，集群就会进入上线状态
• 当客户端向节点发送与数据库键有关的命令时，接收命令的节点会计算出命令要处理的数据库键属于哪个槽，并检查这个槽
  • 如果键所在的槽正好就指派给了当前节点，那么节点直接执行这个命令
  • 如果键所在的槽并没有指派给当前节点，那么节点会向客户端返回一个MOVED错误，指引客户端转向（redirect）至正确的节点，再次发送之前想要执行的命令。
    例子
    集群三个节点:7000,7001,7002
  • 客户端向7000节点发送命令，如果正好槽点由7000负责，则7000将会执行这个任务
  • 如果7000没有负责，那么它会向客户端返回一个MOVED错误，内容为正确节点节点的地址，客户端收到错误后，直接连接正确节点，再次发送相同命令

计算键属于那个槽

• 使用如下算法计算key属于哪个槽

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

判断槽点由谁负责

当计算出键属于哪个槽点之后，节点就会根据自己的clusterState.slots数组中的信息判断该槽点由谁负责

• 如果在clusterState.slots数组中找到了一个指向其他节点的指针，那么节点会返回错误给客户端
• 如果在clusterState.slots数组中找到了一个指向代表自己节点的clusterNode结构，那么节点就可以执行命令

MOVED错误

• 当节点发现键所在的槽并非由自己负责处理的时候，节点就会向客户端返回一个MOVED错误，指引客户端转向至正在负责槽的节点。
• 客户端收到MOVED错误之后，会将错误中的地址解析出来作为正确的节点地址，然后直接连接正确的节点，再次发送相同命令

MOVED ＜slot＞ ＜ip＞:＜port＞

例如:

MOVED 10086 127.0.0.1:7002

• 集群模式收到MOVED错误后不会抛出异常，而是将错误信息传递给客户端
• 单点模式收到MOVED错误会抛出异常，因为单机模式的redis-cli客户端不清楚MOVED错误的作用，所以它只会直接将MOVED错误直接打印出来，而不会进行自动转向

节点数据库的实现

• 集群节点保存键值对以及键值对过期时间的方式，与单机Redis服务器保存键值对以及键值对过期时间的方式完全相同。区别是，节点只能使用0号数据库，而单机Redis服务器则没有这一限制。
• 除了将键值对保存在数据库里面之外，节点还会用clusterState结构中的slots_to_keys跳跃表来保存槽和键之间的关系

typedef struct clusterState {
    // ...
    zskiplist *slots_to_keys;
    // ...
} clusterState;

slots_to_keys跳跃表每个节点的分值（score）都是一个槽号，而每个节点的成员（member）都是一个数据库键：

• 每当节点往数据库中添加一个新的键值对时，节点就会将这个键以及键的槽号关联到slots_to_keys跳跃表。
• 当节点删除数据库中的某个键值对时，节点就会在slots_to_keys跳跃表解除被删除键与槽号的关联。

重新分片

Redis集群可以重新分片，将任意数量已经指派给某个节点(源节点)的槽改为指派给另一个节点，并且相关槽所属的键也会转移到目标节点上。
重新分片可以在线完成，源节点和目标节点都可以继续命令请求。

重新分片原理

由Redis集群管理软件redis-trib执行，Redis提供了进行重新分片的命令，redis-trib通过向源节点和目标节点发送命令实现重新分片操作。
步骤:

• 1）redis-trib对目标节点发送CLUSTER SETSLOT＜slot＞IMPORTING＜source_id＞命令，让目标节点准备好从源节点导入（import）属于槽slot的键值对。
• 2）redis-trib对源节点发送CLUSTER SETSLOT＜slot＞MIGRATING＜target_id＞命令，让源节点准备好将属于槽slot的键值对迁移（migrate）至目标节点。
• 3）redis-trib向源节点发送CLUSTER GETKEYSINSLOT＜slot＞＜count＞命令，获得最多count个属于槽slot的键值对的键名（key name）​。
• 4）对于步骤3获得的每个键名，redis-trib都向源节点发送一个MIGRATE＜target_ip＞＜target_port＞＜key_name＞0＜timeout＞命令，将被选中的键原子地从源节点迁移至目标节点。
• 5）重复执行步骤3和步骤4，直到源节点保存的所有属于槽slot的键值对都被迁移至目标节点为止。每次迁移键的过程如图17-24所示。
• 6）redis-trib向集群中的任意一个节点发送CLUSTER SETSLOT＜slot＞NODE＜target_id＞命令，将槽slot指派给目标节点，这一指派信息会通过消息发送至整个集群，最终集群中的所有节点都会知道槽slot已经指派给了目标节点。

ASK错误

进行重新分片期间，会出现一种情况，即源节点在执行向目标节点迁移键值对的操作时，当发现目标节点已经不再处理这个槽，那么节点就会返回ASK错误给发请求的redis-trib，同时返回新的目标节点ID。

• 客户端收到ASK错误后，会再次发送一次MOVED重定向，将错误发给客户端，之后客户端按照正常程序再次发MOVED错误。

CLUSTER SETSLOT IMPORTING命令的实现

• clusterState结构的migrating_slots_to数组记录了当前节点正在迁移至其他节点的槽：

typedef struct clusterState {
   // ...
   clusterNode *migrating_slots_to[16384];
   // ...
} clusterState;

• migrating_slots_to[i]的值不为NULL，而是指向一个clusterNode结构，那么表示当前节点正在将槽i迁移至clusterNode所代表的节点

ASKING命令

• 如果节点的clusterState.importing_slots_from[i]显示节点正在导入槽i，并且发送命令的客户端带有REDIS_ASKING标识，那么节点将破例执行这个关于槽i的命令一次
• 当客户端接收到ASK错误并转向至正在导入槽的节点时，客户端会先向节点发送一个ASKING命令，然后才重新发送想要执行的命令，这是因为如果客户端不发送ASKING命令，而直接发送想要执行的命令的话，那么客户端发送的命令将被节点拒绝执行，并返回MOVED错误
• ASKING 是一个一次性标识

ASK错误和MOVED错误的区别

• MOVED: 向客户端表示，槽的节点已经改变，客户端需要连接到新的节点，然后发送命令
  • 客户端收到错误之后将错误内容原封不动地发给新的目标节点，新的目标节点将MOVED中的<new_ip:new_port>替换为自己的地址
• ASK: 向客户端表示，当前节点正在导入属于槽的键值对，客户端可以暂时连接到源节点，但是需要发送ASKING命令，这样源节点就可以执行这个命令，属于一种临时措施。

故障检测

集群中的每个节点都会向其他节点发送ping消息，用来检测对方是否在线，如果没有接受到PONG响应，那么就认为节点是下线状态（down），如果节点长时间没有接受到其他节点发送的ping消息，那么节点会认为自己是下线状态（down）

CLUSTER NODES命令

• CLUSTER NODES命令会向集群中的所有节点发送CLUSTER NODES消息，并接收到CLUSTER NODES应答的所有节点的数据。
• 从clusterNodes函数的返回值中可以找到对应的数据库键和值，这样redis-trib就可以用这些数据库键和值来计算源节点和目标节点之间的迁移数据量。

故障转移

集群中的一个或多个节点可以因为各种各样的原因而进入一种特殊的工作状态，被称为临时下线状态（temporary down）
1、节点正在进行集群配置更新的操作（CLUSTER NODES命令的INFO部分的“update”字段为“0”，表示未进行更新操作）。
2、节点正在进行分片的重新分配（CLUSTER NODES命令的INFO部分的“migratring”字段为"0"，表示没有进行分片重新分配操作）。

节点的故障转移（failover）是在故障发生时自动完成的，不需要人工干预。
步骤:

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

选举新主节点

• 基于Raft算法的领头选举（leader election）方法来实现的
  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）如果在一个配置纪元里面没有从节点能收集到足够多的支持票，那么集群进入一个新的配置纪元，并再次进行选举，直到选出新的主节点为止。

消息

消息分类

• MEET消息
  • 用于请求接收者加入到发送者当前所处集群
• PING消息
  • 检测是否在线
• PONG消息
  • 消息回应
• FAIL消息
  • 当一个主节点A判断另一个主节点B已经进入FAIL状态时，节点A会向集群广播一条关于节点B的FAIL消息，所有收到这条消息的节点都会立即将节点B标记为已下线
• PUSHLIST消息
  • 当节点接收到一个PUBLISH命令时，节点会执行这个命令，并向集群广播一条PUBLISH消息，所有接收到这条PUBLISH消息的节点都会执行相同的PUBLISH命令

消息组成

消息头

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

消息正文

union clusterMsgData {
    // MEET、PING、PONG消息的正文
    struct {
        //每条MEET、PING、PONG消息都包含两个
        // clusterMsgDataGossip结构
        clusterMsgDataGossip gossip[1];
    } ping;
    // FAIL消息的正文
    struct {
        clusterMsgDataFail about;
    } fail;
    // PUBLISH消息的正文
    struct {
        clusterMsgDataPublish msg;
    } publish;
    //其他消息的正文...
};