Redis集群实现原理

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

        节点
        一个 Redis 集群通常由多个节点（node）组成。一个节点就是运行在集群模式下的一台 Redis 服务器，Redis 服务器在启动时会根据 cluster-enabled 配置选项来决定是否开启集群模式。
        每个 Redis 节点开始时都处于一个只包含自己的集群当中，要组建一个真正可工作的集群，必须将各个独立的节点连接起来，这可以通过“CLUSTER MEET <ip> <port>”命令来完成。该命令会让当前节点与指定的节点进行握手（handshake），握手成功后，指定的节点就会被添加到当前节点所在的集群中（可通过命令“CLUSTER NODES”查看当前集群中的节点信息）。
        节点会继续使用所有在单机模式中使用的服务器组件，比如继续使用文件事件处理器来处理命令请求和返回命令回复，继续使用 redisServer 和 redisClient 结构来保存服务器和客户端的状态等，但同时对于那些只有在集群模式下才会用到的数据，它则是使用了专门的数据结构：clusterNode、clusterLink 和 clusterState 结构。
        每个节点都会使用一个 clusterNode 结构来记录自己当前的状态，比如创建时间、节点名字等，并为集群中的所有其他节点（包括主节点和从节点）都创建一个相应的 clusterNode 结构，以此来记录其他节点的状态。此外，每个节点还使用了一个 clusterState 结构来记录在当前节点的视角下，集群目前所处的状态，比如是在线还是下线、包含的节点数等。

struct clusterNode{
    mstime_t ctime;              // 创建节点的时间
    char name[REDIS_CLUSTER_NAMELEN];    // 节点名字，由 40 个十六进制字符组成
    // 节点标识
    // 使用各种不同的标识值来记录节点的角色（比如主节点或从节点）
    // 以及节点目前所处的状态（比如在线或者下线）
    int flags;
    uint64_t configEpoch;        // 当前的配置纪元，用于实现故障转移
    char ip[REDIS_IP_STR_LEN];   // 节点的 IP 地址
    int port;                    // 节点的端口号
    clusterLink *link;           // 保存连接节点所需的有关信息

    unsigned char slots[16384/8];       // 分配的槽
    int numslots;                       // 分配的槽的数量

    struct clusterNode *slaveof;    // 如果这是一个从节点，则指向对应的主节点
    int numslaves;                  // 正在复制这个主节点的从节点数量
    struct clusterNode **slaves;    // 每个项指向一个正在复制这个主节点的从节点

    list *fail_reports;          // 记录了所有其他节点对该节点的下线报告
    // ...other fields
};

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


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

    clusterNode *slots[16384];   // 记录了数据库中的槽的指派信息

    zskiplist *slots_to_keys;    // 记录槽和键之间关系的跳跃表

    clusterNode *importing_slots_from[16384];  // 记录正在从其他节点导入的槽
    clusterNode *migrating_slots_to[16384];    // 记录正在迁移至其他节点的槽
    // ...other fields
}clusterState;

        了解了这几个结构，接下来看看节点 A 在收到客户端发送过来的“CLUSTER MEET”命令后与指定节点 B 的握手过程：
        1）节点 A 会为节点 B 创建一个 clusterNode 结构，并将其添加到自己的 clusterState.nodes 字典里面，之后向节点 B 发送一条 MEET 消息。
        2）节点 B 收到 MEET 消息后也会为 A 创建一个 clusterNode 结构，并将其添加到自己的 clusterState.nodes 字典里面，然后向 A 返回一条 PONG 消息。
        3）节点 A 收到 B 返回的 PONG 消息后，知道 B 已经成功收到了自己发送的 MEET 消息，之后会再向 B 返回一条 PING 消息。
        4）节点 B 通过收到 PING 消息可以确认 A 已经成功接收到自己的 PONG 消息，握手完成。
        握手完成后，节点 A 会将节点 B 的信息通过 Gossip 协议传播给集群中的其他节点，让它们也与 B 进行握手。因此，经过一段时间后，节点 B 就会被集群中的所有节点认识。

        槽指派
        Redis 集群通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为 16384 个槽（slot），数据库中的每个键都属于其中的一个槽，每个节点可以处理 0 个或最多 16384 个槽。当所有的槽都有节点在处理时，称集群处于上线状态（ok），否则称之为下线状态（fail）（可使用“CLUSTER INFO”命令来查看集群信息）。
        clusterNode 结构的 slots 和 numslot 属性记录了节点负责处理的槽，其中 slots 属性是一个二进制位数组，其长度为 16384/8=2048 个字节。Redis 以 0 为起始索引，依次对 slots 数组中的 16384 个二进制位进行编号，并根据索引 i 上的二进制位来判断节点是否处理该槽。通过向节点发送“CLUSTER ADDSLOTS <slot> [slot ...]”命令，可以将一个或多个槽指派给该节点负责。
        一个节点除了会记录自己处理的槽，还会将自己的 slots 数组发送给集群中的其他节点，以此告知自己目前负责处理哪些槽。当节点 A 通过消息接收到节点 B 的 slots 数组时，就会在 clusterState.nodes 字典中查找节点 B 对应的 clusterNode 结构，然后对结构中的 slots 属性进行保存或者更新。因此，集群中的每个节点都会知道数据库中的槽被指派给了哪些节点。
        由于只将槽指派信息保存在各个节点的 clusterNode.slots 数组里时，会出现一些无法高效地解决的问题，比如，为了知道槽 i 是否被指派，或者被指派给了哪个节点，程序需要遍历 clusterState.nodes 字典中的所有 clusterNode 结构的 slots 数组，直到找到负责处理槽 i 的节点为止，该过程的复杂度为 O(N)。所以为了在 O(1) 的时间内知道槽 i 的指派情况，clusterState 结构中使用了 slots 数组属性来记录了集群中的所有槽的指派情况：如果 slots[i] 指针为 NULL，表示槽 i 尚未分配给任何节点；否则，表示槽 i 已经被指派给了 clusterNode 结构所代表的节点。不过虽然 clusterState.slots 数组记录了集群中的槽的指派情况，但使用 clusterNode 结构中的 slots 数组来记录单个节点的槽指派信息仍然是必要的，比如，在每次要将节点 A 的槽指派信息传播给其他节点时，如果不使用 clusterNode.slots 数组，那么程序必须先遍历整个 clusterState.slots 数组，记录节点 A 处理的槽，然后才能发送，这边直接发送 clusterNode.slots 数组要麻烦和低效得多。
        在对所有槽都进行了指派后，集群就会进入上线状态，这时客户端就可以向其中的节点发送数据库命令了。
        当客户端向节点发送与数据库键有关的命令时，接收命令的节点会根据算法“CRC(16) & 16383”计算出该键属于哪个槽，并检测这个槽是否指派给了自己：如果是，则直接执行这个命令；否则，当前节点会向客户端返回一个 MOVED 错误（格式为：MOVED <slot> <ip:port>，不过这个错误仅在单机模式下才会显示，因为此时的客户端不清楚 MOVED 错误的作用，而在集群模式下会对客户端隐藏，取而代之的是显示一条 “Redirected to...”转向信息），指引客户端转向至正确的节点来处理这个命令。使用“CLUSTER KEYSLOT <key>”命令可以查看一个给定键属于哪个槽。

        节点数据库的实现
        集群节点保存键值对以及键值对过期时间的方式，都与单机 Redis 服务器的保存方式完全相同，两者在数据库方面的一个区别是：集群节点只能使用 0 号数据库，而单机服务器则无此限制。此外，集群节点还会用 clusterState 结构中的 slots_to_keys 跳跃表来保存槽和键之间的关系。跳跃表中每个节点的分值都是一个槽号，而每个节点的成员都是一个数据库键。通过在跳跃表中记录各个数据库键所属的槽，集群节点可以很方便地对属于某个或某些槽的所有数据库键进行批量操作，例如使用“CLUSTER GETKEYSINSLOT <slot> <count>”命令可以返回最多 count 个属于槽 slot 的数据库键。

        重新分片
        使用 Redis 集群管理软件 redis-trib 可以对集群执行重新分片操作，以将任意数量已经指派给某个集群节点（源节点）的槽改为指派给另一个节点（目标节点），并且相关槽中的键值对也会一并迁移。这一操作可以在线进行，不需要集群下线，并且源节点和目标节点都可以继续处理命令请求。
        redis-trib 对集群的单个槽 slot 进行重新分片的过程如下：
        1）向目标节点发送“CLUSTER SETSLOT <slot> IMPORTING <source_id>”命令，让目标节点装备好从源节点导入属于槽 slot 的键值对。clusterState 结构的 importing_slots_from 数组记录了当前节点正在从其他节点导入的槽，如果 importing_slots_from[i] 的值不为 NULL，则表示正在从指向的 clusterNode 结构所代表的节点导入槽 i。
        2）向源节点发送“CLUSTER SETSLOT <slot> MIGRATING <target_id>”命令，让源节点准备好将槽 slot 的键值对迁移至目标节点。clusterState 结构的 migrating_slots_to 数组记录了当前节点正在迁移至其他节点的槽，migrating_slots_to[i] 不为 NULL 时，表示正在将槽 i 迁移至指向的 clusterNode 结构所代表的节点。
        3）向源节点发送“CLUSTER GETKEYSINSLOT <slot> <count>”命令，获得最多 count 个属于槽 slot 的数据库键。对于其中的每个键，向源节点发送一个“MIGRATE <target_ip> <target_port> <key_name> 0 <timeout>”命令，将其原子地迁移至目标节点。重复这一步骤，直到迁移完槽 slot 中的键值对。
        4）向集群中的任一节点发送“CLUSTER SETSLOT <slot> NODE <target_id>”命令，表示已将槽 slot 指派给目标节点，这一信息最终会通过消息发送至整个集群。
        如果重新分片涉及多个槽，那么 redis-trib 将对每个给定的槽分别执行这一过程。
        如果节点收到一个关于键 key 的命令请求，并且其所属的槽 i 正好就指派给了这个节点，则节点会尝试在自己的数据库里查找该键，若没有找到，节点会再检查  migrating_slots_to[i]，看槽 i 是否正在进行迁移，如果是，则向客户端发送一个 ASK 错误，接到 ASK 错误的客户端会根据错误提供的 IP 和端口，转向至正在导入槽的目标节点，然后首先向目标节点发送一个 ASKING 命令，之后再重新发送原本想要执行的命令。
        ASKING 命令唯一要做的进行打开发送该命令的客户端的 REDIS_ASKING 标识。一般情况下，如果客户端向节点发送一个关于槽 i 的命令，而槽 i 又没有指派给这个节点的话，那么节点将返回一个 MOVED 错误；但如果节点的 importing_slots_from[i] 显示正从某一节点导入槽 i，并且发送命令的客户端带有 REDIS_ASKING 标识，那么节点将破例执行关于这个槽 i 的命令一次。要注意的是，REDIS_ASKING 标识是一个一次性标识，当节点执行了一个带有 REDIS_ASKING 标识的客户端发送的命令后，客户端的这个标识就会被移除，下次需要使用 ASKING 命令重新打开。


参考书籍：
1、《Redis设计与实现》第17章——集群。