本文内容为《redis设计与实现》一书学习笔记。本文主要概述十七章内容。
第十七章 集群
集群通过分片（sharding）来进行数据共享，并提供复制和故障转移功能。
17.1 节点
一个Redis集群通常由多个节点（node）组成，连接各个节点的工作可以使用CLUSTER MEET命令来完成：
CLUSTER MEET [ip] [port]
向一个节点node发送CLUSTER MEET命令，可以让node节点与ip和port所指定的节点进行握手（handshake），当握手成功时，node节点就会将ip和port所指定的节点添加到node节点当前所在的集群中。
一个节点就是一个运行在集群模式下的Redis服务器，Redis服务器在启动时会根据cluster-enabled配置选项是否为yes来决定是否开启服务器的集群模式，如下图。
集群模式的Redis服务器依然会继续使用单机模式下的Redis服务器组件，比如复制等功能。至于那些只有在集群模式下才会用到的数据，节点将它们保存到了clusterNode结构、clusterLink结构、clusterState结构。
每个节点都会使用一个clusterNode结构来记录自己的状态，并为集群中的所有其他节点（包括主节点和从节点）都创建一个相应的clusterNode结构，以此来记录其他节点的状态。
clusterNode结构的link属性如下图所示：
每个节点都保存着一个clusterState，记录着当前节点的视角下集群目前所处的状态。
以包含三个节点127.0.0.1：7000、127.0.0.1：7001、127.0.0.1：7002的集群为例，节点127.0.0.1：7000创建的clusterState结构如下：
CLUSTER MEET命令的实现：
通过向节点A发送CLUSTER MEET命令，可以让节点A将另外一个节点B添加到节点A当前所在的集群里面，收到命令的节点A将于节点B进行握手，以此来确认彼此的存在。握手过程如下：
- 节点A会为节点B创建一个clusterNode结构，并将该结构添加到自己的clusterState.nodes字典里面；
- 节点A将给节点B发送一条MEET消息；
- 节点B接收到节点A发送的MEET消息，B会为A创建一个clusterNode结构，并将该结构添加到自己的clusterState.nodes字典里面；
- 节点B将给节点A返回一条PONG消息；
- 节点A收到B的PONG消息，A就知道B已经成功的接收到自己的消息了；
- 节点A将给B发送一条PING消息；
- 节点B收到A的PING消息，B就知道A已经接收到自返回的PONG消息，握手结束；
最后，节点A会将B的信息通过Gossip协议传播给集群中的其他节点，让其他节点也与B握手，最终，经过一段时间，节点B会被集群中的所有节点认识。
17.2 槽指派
Redis集群通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为16384（2^14）个槽（slot），数据库中的每个键都属于这16384个槽的其中一个，集群中的每个节点可以处理0个或最多16384个槽。 当数据库中的16384个槽都有节点在处理时，集群处于上线状态（ok）；相反地，如果数据库中有任何一个槽没有得到处理，那么集群处于下线状态（fail）。
通过向节点发送CLUSTER ADDSLOTS命令，可以将一个或多个槽指派（assign）给节点负责。 还是上面的例子，可以执行以下命令将槽0至槽5000指派给节点7000负责：
127.0.0.1:7000> CLUSTER ADDSLOTS 0 1 2 3 4 ... 5000
OK
将槽5001至槽10000指派给节点7001负责：
127.0.0.1:7001> CLUSTER ADDSLOTS 5001 5002 5003 5004 ... 10000
OK
将槽10001至槽16383指派给7002负责：
127.0.0.1:7002> CLUSTER ADDSLOTS 10001 10002 10003 10004 ... 16383
OK
当以上三个CLUSTER ADDSLOTS命令都执行完毕之后，数据库中的16384个槽都已经被指派给了相应的节点，集群进入上线状态：
127.0.0.1:7000> CLUSTER INFO
cluster_state:ok
...
17.2.1 记录节点的槽指派信息
clusterNode结构的slots属性和numslots属性记录了节点负责处理哪些槽
slots属性是一个二进制位数组，这个数组的长度是16384 / 8 = 2048个字节，一共包含16384个二进制位。以0为起始索引，16383为终止索引，并根据第i位上的二进制值来判断槽是否是该节点负责，以下图为例，该节点负责槽0至槽7。
因为取出和设置slots数组中任意二进制位的复杂度仅为O(1)，所以对于给定的slots数组来说，程序检查节点是否负责处理某个槽，或者将某个槽指派给节点负责，这两个动作的复杂度都是O(1)。
numslots属性记录节点负责处理的槽的数量，即slots数组中值为1的二进制位的数量。
17.2.2 传播节点的槽指派信息
一个节点除了会将自己负责处理的槽记录在clusterNode结构的slots属性和numslots属性之外，它还会将自己的slots数组通过消息发送给集群中的其他节点，以此来告知其他节点自己目前负责处理哪些槽。
17.2.3 记录集群所有槽的指派信息
clusterState结构中的slots数组记录了集群中所有16384个槽的指派信息：
slots数组包含16384个项，每个数组项都是指向clusterNode结构的指针：
- slots[i]指针指向NULL，表示槽i尚未指派给任何节点
- slots[i]指针指向clusterNode结构，表示槽i已指派给clusterNode结构代表的节点
clusterState.slots数组记录集群中所有槽指派信息，clusterNode.slots数组记录clusterNode结构所代表的节点的槽指派信息。
为什么不可以只将槽指派信息保存在各个节点的clusterNode.slots里，而需要存在clusterState.slots数组里呢 ?
- 如果只使用clusterNode.slots来记录，想要知道槽i是否已经被指派的话，需要遍历clusterState.nodes字典中所有的clusterNode结构，检查这些结构的slots数组，直到找到负责处理槽i的节点为止，这个过程的复杂度为O(N)，其中N为clusterState.nodes字典保存的clusterNode结构数量。
- 如果将所有槽指派信息保存在clusterState.slots数组里，想要知道槽i是否已经被指派，访问clusterState.slots[i]即可，这个操作O(1)。
虽然clusterState.slots数组记录集群中所有槽指派信息，但使用clusterNode.slots数组记录单个节点的槽指派信息仍有必要。
- 节点需要将自己负责的槽指派信息传播给其他节点，现在只需要将clusterNode.slots发送出去即可。但是如果没有clusterNode.slots，就需要在clusterStste.slots里面遍历，找出所有某个节点负责的slot，然后再发送给其他节点，这就太麻烦了。
17.3 在集群中执行命令
在对集群中的16384个槽都指派完成之后，集群就进入上线状态，这时客户端就可以向集群发送数据命令了。
当客户端向节点发送与数据库键有关的命令时，接收命令的节点会计算出命令要处理的数据库键属于哪个槽，并检查这个槽是否指派给了自己：
- 如果键所在的槽正好就指派给了当前节点，那么节点直接执行这个命令。
- 如果键所在的槽并没有指派给当前节点，那么节点会向客户端返回一个MOVED错误，指引客户端转向（redirect）至正确的节点，并再次发送之前想要执行的命令。
判断客户端是否需要转向的流程如下：
17.3.1 计算槽属于哪个键
节点首先需要计算出键所对应的槽，Redis使用CRC16（key） & 16383来计算这个值
17.3.2 判断槽是否由当前节点处理
节点计算出键所属的槽i后，检查clusterState.slots[i] 是否等于 clusterState.myself，从而判断键所在槽是否由自己处理，等于则自己处理，不等则根据clusterState.slots[i]指向的clusterNode结构所记录的节点IP和端口号，向客户端返回MOVED错误，指引客户端转向至正在处理槽i的节点。
17.3.3 MOVED错误
当客户端接收到节点返回的MOVED错误时，客户端会根据MOVED错误中提供的IP地址和端口号，转向至负责处理槽slot的节点，并向该节点重新发送之前想要执行的命令。
集群模式的redis-cli客户端在接收到MOVED错误时，并不会打印出MOVED错误，而是根据MOVED错误自动进行节点转向，并打印出转向信息，所以看不见节点返回的MOVED错误。而单机(stand alone)模式的redis-cli客户端，会打印MOVED错误。这是因为单机模式的redis-cli客户端不清楚MOVED错误的作用，只会直接将MOVED错误打印出来，不会自动转向。
17.3.4 节点数据库的实现
需要注意的是，节点只能使用0号数据库，而单机则没有这个限制。
17.4 重新分片
Redis集群的重新分片操作可以将任意已经分配给某个节点的槽改为指派给其他的另外一个节点，且相关槽所属的键值对也会从源节点移动到目标节点。
重新分片操作可以在线进行，集群不需要下线，源节点和目标节点都可以继续处理命令请求；
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的键值对的键名字；
- 对于步骤3得到的每个键，redis-trib都将向源节点发送命令，原子的将这些键迁移到目标节点；
- 重复步骤3和4，直到源节点保存的所有属于槽slot的键值对都被迁移到目标节点为止；
- redis-trib会向集群中的任意一个节点发送CLUSTER SETSLOT <slot> NODE <taregt_id>命令，将槽slot指派给目标节点，这一信息会通过消息发送给集群中的所有节点，最终集群中的所有节点都将知道槽slot已经指派给了目标节点；
整个过程如下图所示：
17.5 ASK错误
在进行重新分片的过程中，可能属于被迁移槽的一部分键在源节点中，而另一部分已经迁移到目标节点。这时候如果客户端向源节点发送一个数据库操作命令，而这个被操作的键刚好在被迁移的键中时：
- 源节点会先在自己的数据库中查找给定的键，如果找到了，就直接执行客户端发送的命令。
- 如果没找到，这个键可能已经被迁移到了目标节点，那么源节点会向客户端返回一个ASK错误，指引客户端转向目标节点发起请求。
整个过程如下图所示：
当客户端接收到ASK错误并转向至正在导入槽的节点时，客户端会先向节点发送一个ASKING命令，然后才重新发送想要执行的命令。原因：如果客户端不发送ASKING命令，而直接发送想要执行的命令的话，客户端发送的命令将被节点拒绝执行，并返回MOVED错误。以将节点7002中的槽16198导入节点7003为例，虽然节点7003正在导入槽16198，但槽16198目前还是指派给节点7002的，所以如果直接发送GET命令，节点7003会向客户端返回MOVED错误，并指引客户端转向至节点7002；但如果在发送GET命令前，先向节点7003发送一个ASKING命令，GET命令就会被节点7003执行。
ASK错误和MOVED错误的区别：
- MOVED错误代表槽的负责权已经从一个节点转移到了另一个节点：在客户端收到关于槽i的MOVED错误之后，客户端每次遇到关于槽i的命令请求时，都可以直接将命令请求发送至MOVED错误所指向的节点。
- ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施，是一次性的：在客户端收到关于槽i的ASK错误之后，客户端只会在接下来的一次命令请求中将关于槽i的命令请求发送至ASK错误所指示的节点，但这种转向不会对客户端今后发送关于槽i的命令请求产生任何影响，客户端仍然会将关于槽i的命令请求发送至目前负责处理槽i的节点，除非ASK错误再次出现。
17.6 复制和故障转移
Redis集群中的节点分为主节点（master）和从节点（slave），其中主节点用于处理槽，而从节点则用于复制某个主节点，并在被复制的主节点下线时，代替下线主节点继续处理命令请求。
17.6.1 设置从节点
向一个节点发送命令：
CLUSTER REPLICATE <node_id>
可以让接收命令的节点成为node_id所指定节点的从节点，并开始对主节点进行复制。
- 接收到命令的节点首先会在自己的clusterState.modes字典中找到主节点的clusterNode结构，然后将自己的clusterState.myself.slaveof指针指向这个clusterNode，以此来表示当前节点正在复制这个主节点。
- 然后会修改自己的clusterState.myself.flags中的属性，关闭原本的master属性，打开slave属性，表示节点变成一个从节点。
- 调用复制代码，对主节点进行复制。复制代码和单机Redis服务器的复制功能使用了相同代码，所以相当于给从节点发送命令SLAVEOF<master_ip><master_port>
一个节点成为从节点，并开始复制某个主节点这一信息会通过消息发送给集群中的其他节点，集群中的所有节点都会在代表主节点的clusterNode结构的slaves属性和numslaves中记录正在复制该节点的从节点信息。
17.6.2 故障检测
集群中的每个节点都会定期地向集群中的其他节点发送PING消息，以此来检测对方是否在线，如果接收PING消息的节点没有在规定的时间内，向发送PING消息的节点返回PONG消息，那么发送PING消息的节点就会将接收PING消息的节点标记为疑似下线（probable fail，PFAIL）。
如果在一个集群里面，半数以上负责处理槽的主节点都将某个主节点x报告为疑似下线，那么这个主节点x将被标记为已下线（FAIL），将主节点x标记为已下线的节点会向集群广播一条关于主节点x的FAIL消息，所有收到这条FAIL消息的节点都会立即将主节点x标记为已下线。
17.6.3 故障转移
当一个从节点发现自己正在复制的主节点进入了已下线状态时，从节点将开始对下线主节点进行故障转移：
- 复制下线主节点的所有从节点里面，会有一个从节点被选中。
- 被选中的从节点会执行SLAVEOF no one命令，成为新的主节点。
- 新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己。
- 新的主节点向集群广播一条PONG消息，这条PONG消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点已经接管了原本由已下线节点负责处理的槽。
- 新的主节点开始接收和自己负责处理的槽有关的命令请求，故障转移完成。
17.6.4 选举新的主节点
与16章选举领头Sentinel的方法类似，两者都是基于Raft算法的领头选举（leader election）方法实现的。
17.7 消息
集群中的各个节点通过发送和接收消息（message）来进行通信。节点发送的消息主要有以下五种：
- MEET消息：当发送者接到客户端发送的CLUSTER MEET命令时，发送者会向接收者发送MEET消息，请求接收者加入到发送者当前所处的集群里面。
- PING消息：集群里的每个节点默认每隔一秒钟就会从已知节点列表中随机选出五个节点，然后对这五个节点中最长时间没有发送过PING消息的节点发送PING消息，以此来检测被选中的节点是否在线。除此之外，如果节点A最后一次收到节点B发送的PONG消息的时间，距离当前时间已经超过了节点A的cluster-node-timeout选项设置时长的一半，那么节点A也会向节点B发送PING消息。
- PONG消息：当接收者收到发送者发来的MEET消息或者PING消息时，为了向发送者确认这条MEET消息或者PING消息已到达，接收者会向发送者返回一条PONG消息。另外，一个节点也可以通过向集群广播自己的PONG消息来让集群中的其他节点立即刷新关于这个节点的认识。
- FAIL消息：当一个主节点A判断另一个主节点B已经进入FAIL状态时，节点A会向集群广播一条关于节点B的FAIL消息，所有收到这条消息的节点都会立即将节点B标记为已下线。
- PUBLISH消息：当节点接收到一个PUBLISH命令时，节点会执行这个命令，并向集群广播一条PUBLISH消息，所有接收到这条PUBLISH消息的节点都会执行相同的PUB-LISH命令。
17.7.2 MEET、PING、PONG命令的实现
Redis集群的各个节点通过Gossip协议来交换各自关于不同结点的状态信息，Gossip协议由 MEET、PING、PONG三种消息实现。这三种消息使用相同的消息正文（正文由两个clusterMsgDataGossip结构组成），通过消息头的type属性进行区分。
每次发送MEET、PING、PONG命令时，发送者都从自己的已知节点列表里随机选出两个节点（可以是主节点也可以是从节点），并将这两个被选中的节点的信息分别保存到两个clusterMsgDataGossip结构里。
当接收者收到MEET、PING、PONG命令时，接收者会访问消息正文中的两个clusterMsgDataGossip结构，并根据自己是否认识这两个节点选择操作：
- 如果被选中节点不存在于接收者的已知节点列表，那么说明接收者是第一次接触到被选中节点，接收者将根据结构中记录的IP地址和端口号等信息，与被选中节点进行握手。
- 如果被选中节点已经存在于接收者的已知节点列表，那么说明接收者之前已经与被选中节点进行接触，接收者将根据clusterMsgDataGossip结构记录的信息，对被选中该节点所对应的clusterNode结构进行更新。
下图是一个在包含六个节点（A、B、C、D、E、F）的集群中发送PING消息和PONG消息的例子：
17.7.3 FAIL消息的实现
FAIL消息可见17.6.2
在集群节点数量较大时，使用Gossip协议来传播节点的已下线信息会给节点的信息更新带来一定延迟，因为Gossip协议消息通常需要一段时间才能传播至整个集群，而发送FAIL信息可以让集群里的所有节点立即知道某个主节点已下线，从而尽快判断是否需要将集群标记为下线或者对下线主节点进行故障转移。
17.7.4 PUBLISH消息的实现
