Redis Cluster 数据分片
介绍 Redis Cluster
Redis 集群是 Redis 提供的分布式数据库方案， 集群通过分片（sharding） 来进行数据共享， 并提供复制和故障转移功能。
节点
一个 Redis 集群通常由多个节点（node） 组成， 在刚开始的时候，每个节点都是相互独立的，它们都处于一个只包含自己的集群当中， 要组建一个真正可工作的集群， 我们必须将各个独立的节点连接起来，构成一个包含多个节点的集群。
连接各个节点的工作可以使用 cluster meet 命令来完成， 该命令的格式如下：cluster meet < ip > < port >。节点通过握手来将其他节点添加到自己所处的集群当中。向一个 node 节点发送 cluster meet 命令， 可以让 node 节点与 ip 和 port 所指定的节点进行握手（handshake），当握手成功时， node 节点就会将 ip 和 port 所指定的节点添加到 node 节点当前所在的集群中。
一个节点就是一个运行在集群模式下的 Redis 服务器，Redis 服务器在启动时会根据 cluster-enabled 配置选项是否为 yes 来决定是否开启服务器的集群模式。启动服务器时，服务器判断是否开启集群模式：
- 如果 cluster-enabled 选项的值为 yes，则开启服务器的集群模式，成为一个节点；
- 如果 cluster-enabled 选项的值不为 yes，则开启服务器的单机（stand alone）模式，成为一个普通的 Redis 服务器。
节点会继续使用 redisServer 结构来保存服务器的状态， 使用 redisClient 结构来保存客户端的状态，至于那些只有在集群模式下才会用到的数据，节点将它们保存到了cluster.h/clusterNode 结构、 cluster.h/clusterLink 结构，以及 cluster.h/clusterState 结构里面。
槽指派
Redis 集群通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为 16384 个槽（slot），数据库中的每个键都属于这 16384 个槽的其中一个，集群中的每个节点可以处理 0 个或最多 16384 个槽。
通过向节点发送 cluster addslots 命令，我们可以将一个或多个槽指派（assign）给节点负责：cluster addslots < slot > [slot …]。
在 cluster addslots 命令执行完毕之后，节点会通过发送消息告知集群中的其他节点，自己目前正在负责处理哪些槽。也就是说，每个节点都会记录哪些槽指派给了自己，而哪些槽又被指派给了其他节点。
集群的在线状态：
- 上线状态：当数据库中的 16384 个槽都有节点在处理时，集群处于上线状态（ok）；
- 下线状态：相反地，如果数据库中有任何一个槽没有得到处理，那么集群处于下线状态（fail）。
节点保存槽指派信息
Redis 集群的每个节点都会记录自己负责处理哪些槽。
clusterNode 结构的 slots 属性和 numslot 属性记录了节点负责处理哪些槽：
struct clusterNode {
// ...
unsigned char slots[16384/8];
int numslots;
// ...
};
slots 属性是一个二进制位数组，这个数组的长度为 16384 / 8 = 2048 个字节，共包含 16384 个二进制位。Redis 以 0 为起始索引，16383 为终止索引，对 slots 数组中的 16384 个二进制位进行编号，并根据索引 i 上的二进制位的值来判断节点是否负责处理槽 i：
- 如果 slots 数组在索引 i 上的二进制位的值为 1，那么表示节点负责处理槽 i。
- 如果 slots 数组在索引 i 上的二进制位的值为 0，那么表示节点不负责处理槽 i。
numslots 属性则记录节点负责处理的槽的数量，也即是 slots 数组中值为 1 的二进制位的数量。
节点之间传播槽指派信息
一个节点除了会将自己负责处理的槽记录在 clusterNode 结构的 slots 属性和 numslots 属性之外，它还会将自己的 slots 数组通过消息发送给集群中的其他节点，以此来告知其他节点自己目前负责处理哪些槽。
当节点 A 通过消息从节点 B 那里接收到节点 B 的 slots 数组时， 节点 A 会在自己的 clusterState.nodes 字典中查找节点 B 对应的 clusterNode 结构，并对结构中的 slots 数组进行保存或者更新。
因为集群中的每个节点都会将自己的 slots 数组通过消息发送给集群中的其他节点， 并且每个接收到 slots 数组的节点都会将数组保存到相应节点的 clusterNode 结构里面， 因此， 集群中的每个节点都会知道数据库中的 16384 个槽分别被指派给了集群中的哪些节点。
记录集群所有槽的指派信息
Redis 集群的每个节点都会记录集群所有槽的指派信息
clusterState 结构中的 slots 数组记录了集群中所有 16384 个槽的指派信息：
typedef struct clusterState {
// ...
clusterNode *slots[16384];
// ...
} clusterState;
slots 数组包含 16384 个项，每个数组项都是一个指向 clusterNode 结构的指针：
- 如果 slots[i] 指针指向 NULL，那么表示槽 i 尚未指派给任何节点。
- 如果 slots[i] 指针指向一个 clusterNode 结构，那么表示槽 i 已经指派给了 clusterNode 结构所代表的节点。
如果只将槽指派信息保存在各个节点的 clusterNode.slots 数组里，会出现一些无法高效地解决的问题，而 clusterState.slots 数组的存在解决了这些问题：
- 如果节点只使用 clusterNode.slots 数组来记录槽的指派信息，那么为了知道槽 i 是否已经被指派，或者槽 i 被指派给了哪个节点，程序需要遍历 clusterState.nodes 字典中的所有 clusterNode 结构，检查这些结构的 slots 数组，直到找到负责处理槽 i 的节点为止，这个过程的复杂度为 O(N)，其中 N 为 clusterState.nodes 字典保存的 clusterNode 结构的数量。
- 而通过将所有槽的指派信息保存在 clusterState.slots 数组里面，程序要检查槽 i 是否已经被指派，又或者取得负责处理槽 i 的节点，只需要访问 clusterState.slots[i] 的值即可，这个操作的复杂度仅为 O(1)。
clusterState.slots 数组记录了集群中所有槽的指派信息，而 clusterNode.slots 数组只记录了 clusterNode 结构所代表的节点的槽指派信息，这是两个 slots 数组的关键区别所在。
客户端向集群的节点发送命令
在对数据库中的 16384 个槽都进行了指派之后，集群就会进入上线状态，这时客户端就可以向集群中的节点发送数据命令了。
当客户端向节点发送与数据库键有关的命令时，接收命令的节点会计算出命令要处理的数据库键属于哪个槽，并检查这个槽是否指派给了自己：
- 如果键所在的槽正好就指派给了当前节点，那么节点直接执行这个命令。
- 如果键所在的槽并没有指派给当前节点，那么节点会向客户端返回一个 moved 错误，指引客户端转向（redirect）至正确的节点，并再次发送之前想要执行的命令。
1、计算键属于哪个槽
节点使用以下算法来计算给定键 key 属于哪个槽：
def slot_number(key):
return CRC16(key) & 16383
其中 CRC16 (key) 语句用于计算键 key 的 CRC-16 校验和，而 &16383 语句则用于计算出一个介于 0 至 16383 之间的整数作为键 key 的槽号。
使用 cluster keyslot < key > 命令可以查看一个给定键属于哪个槽，这个命令就是通过调用上面给出的槽分配算法来实现的。
2、判断槽是否由当前节点负责处理
当节点计算出键所属的槽 i 之后，节点就会检查 clusterState.slots 数组中的项 i，判断键所在的槽是否由自己负责：
- 如果 clusterState.slots[i] 等于 clusterState.myself，那么说明槽 i 由当前节点负责，节点可以执行客户端发送的命令。
- 如果 clusterState.slots[i] 不等于 clusterState.myself，那么说明槽 i 并非由当前节点负责，节点会根据 clusterState.slots[i] 指向的 clusterNode 结构所记录的节点 IP 和端口号，向客户端返回 moved 错误，指引客户端转向至负责处理槽 i 的节点。
3、moved 错误的实现方法
当节点发现键所在的槽并非由自己负责处理的时候，节点就会向客户端返回一个 moved 错误，指引客户端转向至负责处理槽的节点。
moved 错误的格式为：moved < slot > < ip > : < port >。其中 slot 为键所在的槽，而 ip 和 port 则是负责处理槽 slot 的节点的 IP 地址和端口号。
当客户端接收到节点返回的 moved 错误时，客户端会根据 moved 错误中提供的 IP 地址和端口号，转向至负责处理槽 slot 的节点，并向该节点重新发送之前想要执行的命令。
一个集群客户端通常会与集群中的多个节点创建套接字连接，而所谓的节点转向实际上就是换一个套接字来发送命令。 如果客户端尚未与想要转向的节点创建套接字连接，那么客户端会先根据 moved 错误提供的 IP 地址和端口号来连接节点，然后再进行转向。
被隐藏的 moved 错误：集群模式的 redis-cli 客户端在接收到 moved 错误时，并不会打印出 moved 错误，而是根据 moved 错误自动进行节点转向，并打印出转向信息，所以我们是看不见节点返回的 moved 错误的。但是，如果我们使用单机（stand alone）模式的 redis-cli 客户端，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 跳跃表解除被删除键与槽号的关联。
通过在 slots_to_keys 跳跃表中记录各个数据库键所属的槽，节点可以很方便地对属于某个或某些槽的所有数据库键进行批量操作，例如命令 cluster getkeysinslots < slot > < count > 命令可以返回最多 count 个属于槽 slot 的数据库键，而这个命令就是通过遍历 slots_to_keys 跳跃表来实现的。
重新分片
介绍重新分片
Redis 集群的重新分片操作可以将任意数量已经指派给某个节点 （源节点）的槽改为指派给另一个节点（目标节点），并且相关槽所属的键值对也会从源节点被移动到目标节点。
重新分片操作可以在线（online）进行，在重新分片的过程中，集群不需要下线，并且源节点和目标节点都可以继续处理命令请求。
重新分片的实现原理
Redis 集群的重新分片操作是由 Redis 的集群管理软件 redis-trib 负责执行的，Redis 提供了进行重新分片所需的所有命令，而 redis-trib 则通过向源节点和目标节点发送命令来进行重新分片操作。
redis-trib 对集群的单个槽 slot 进行重新分片的步骤如下：
- 目标节点准备导入槽 slot 的键值对：redis-trib 对目标节点发送 cluster setslot < slot > importing <source_id> 命令，让目标节点准备好从源节点导入（import）属于槽 slot 的键值对。
- 源节点准备迁移槽 slot 的键值对：redis-trib 对源节点发送 cluster setslot < slot > migrating <target_id> 命令，让源节点准备好将属于槽 slot 的键值对迁移（migrate）至目标节点。
- redis-trib 向源节点发送 cluster getkeysinslot < slot > < count > 命令，获得最多 count 个属于槽 slot 的键值对的键名（key name）。
- 对于步骤 3 获得的每个键名，redis-trib 都向源节点发送一个 migrate <target_ip> <target_port> <key_name> 0 < timeout > 命令，将被选中的键原子地从源节点迁移至目标节点。
- 将属于槽 slot 的键全部迁移至目标节点：重复执行步骤 3 和步骤 4，直到源节点保存的所有属于槽 slot 的键值对都被迁移至目标节点为止。
- 将槽 slot 指派给目标节点：redis-trib 向集群中的任意一个节点发送 cluster setslot < slot > node <target_id> 命令，将槽 slot 指派给目标节点，这一指派信息会通过消息发送至整个集群，最终集群中的所有节点都会知道槽 slot 已经指派给了目标节点。
- 如果重新分片涉及多个槽，那么 redis-trib 将对每个给定的槽分别执行上面给出的步骤。
ask 错误
在进行重新分片期间，源节点向目标节点迁移一个槽的过程中，可能会出现这样一种情况：属于被迁移槽的一部分键值对保存在源节点里面，而另一部分键值对则保存在目标节点里面。
当客户端向源节点发送一个与数据库键有关的命令，并且命令要处理的数据库键恰好就属于正在被迁移的槽时：
- 源节点会先在自己的数据库里面查找指定的键，如果找到的话，就直接执行客户端发送的命令。
- 相反地，如果源节点没能在自己的数据库里面找到指定的键，那么这个键有可能已经被迁移到了目标节点，源节点将向客户端返回一个 ask 错误，指引客户端转向正在导入槽的目标节点，并再次发送之前想要执行的命令。
如果节点 A 正在迁移槽 i 至节点 B，那么当节点 A 没能在自己的数据库中找到命令指定的数据库键时，节点 A 会向客户端返回一个 ask 错误，指引客户端到节点 B 继续查找指定的数据库键。
源节点判断是否需要向客户端发送 ask 错误的整个过程。
被隐藏的 ask 错误：和接到 moved 错误时的情况类似，集群模式的 redis-cli 在接到 ask 错误时也不会打印错误，而是自动根据 ask 错误提供的 IP 地址和端口进行转向动作。
ask 错误
如果节点收到一个关于键 key 的命令请求，并且键 key 所属的槽 i 正好就指派给了这个节点，那么节点会尝试在自己的数据库里查找键 key：
- 如果找到了的话，节点就直接执行客户端发送的命令。
- 与此相反，如果节点没有在自己的数据库里找到键 key，那么节点会检查自己的 clusterState.migrating_slots_to[i]，看键 key 所属的槽 i 是否正在进行迁移，如果槽 i 的确在进行迁移的话，那么节点会向客户端发送一个 ask 错误，引导客户端到正在导入槽 i 的节点去查找键 key。
接到 ask 错误的客户端会根据错误提供的 IP 地址和端口号，转向至正在导入槽的目标节点，然后首先向目标节点发送一个 asking 命令， 之后再重新发送原本想要执行的命令。
asking 错误
当客户端接收到 ask 错误并转向至正在导入槽的节点时，客户端会先向节点发送一个 asking 命令，然后才重新发送想要执行的命令，这是因为如果客户端不发送 asking 命令，而直接发送想要执行的命令的话，那么客户端发送的命令将被节点拒绝执行，并返回 moved 错误。
asking 命令唯一要做的就是打开发送该命令的客户端对应的实例结构的 REDIS_ASKING 标识，以下是该命令的伪代码实现：
def ASKING():
# 打开标识
client.flags |= REDIS_ASKING
# 向客户端返回OK 回复
reply("OK")
在一般情况下，如果客户端向节点发送一个关于槽 i 的命令，而槽 i 又没有指派给这个节点的话，那么节点将向客户端返回一个 moved 错误；但是，如果节点的 clusterState.importing_slots_from[i] 显示节点正在导入槽 i，并且发送命令的客户端带有 REDIS_ASKING 标识，那么节点将破例执行这个关于槽 i 的命令一次。
需要注意的是，客户端的 REDIS_ASKING 标识是一个一次性标识，当节点执行了一个带有 REDIS_ASKING 标识的客户端发送的命令之后，客户端的 REDIS_ASKING 标识就会被移除。
节点判断是否执行客户端命令的过程
ask 错误和 moved 错误都会导致客户端转向，它们的区别在于：
- moved 错误代表槽的负责权已经从一个节点转移到了另一个节点：在客户端收到关于槽 i 的 moved 错误之后，客户端每次遇到关于槽 i 的命令请求时，都可以直接将命令请求发送至 moved 错误所指向的节点，因为该节点就是目前负责槽 i 的节点。
- 与此相反，ask 错误只是两个节点在迁移槽的过程中使用的一种临时措施：在客户端收到关于槽 i 的 ask 错误之后，客户端只会在接下来的一次命令请求中将关于槽 i 的命令请求发送至 ask 错误所指示的节点， 但这种转向不会对客户端今后发送关于槽 i 的命令请求产生任何影响， 客户端仍然会将关于槽 i 的命令请求发送至目前负责处理槽 i 的节点，除非 ask 错误再次出现。
参考资料
《Redis 设计与实现》书籍
