第17章 集群
Redis集群是一个分布式数据库方案，可以通过分片来进行数据共享，并提供复制和故障转移功能。
节点
节点只是一个运行在集群模式下的Redis服务器，由启动时配置中的cluster-enabled属性决定。
集群数据结构
使用clusterNode结构可以保存了一个节点的当前状态，例如创建时间，名字，配置纪元，IP，端口等。 
clusterNode结构的link属性是一个clusterLink结构，该结构保存了连接节点所需的有关信息，比如套接字描述符，输入缓冲区和输出缓冲区等。（有点类似于redisClient结构中用于连接客户端的套接字，缓冲区） 
每个节点都保存着一个clusterState结构，这个结构记录了在当前节点的视角下，集群目前所处的状态，例如集群是在线还是下线，集群包含多少个节点，集群当前的配置纪元等。 
槽指派 Redis集群通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为16384个槽（slot），分配给每个节点处理，数据库中的每个键都属于这16384个槽的其中一个。可以使用CLUSTER MEET命令对槽进行分配。 clusterNode结构中的slots属性和numslot属性记录了节点处理哪些槽，numslot属性记录了当前节点处理的槽的数量，slots属性是一个二进制位数组，一共有16384位，数组第i位上的值代表节点是否处理槽i。 
下图展示了一个slots数组示例：这个数组索引0至索引7上的二进制位的值都为1，其余所有二进制位的值都为0，这表示节点负责处理槽0至槽7。 
记录集群所有槽的指派信息
除了记录自身节点负责的槽位信息以外，clusterState结构中的slots数组记录了集群中所有16384个槽的指派信息。 
slots数组包含16384个项，每个数组项都是一个指向对应的槽所在的clusterNode结构的指针，如果slots[i]指针指向NULL，那么表示槽i尚未指派给任何节点。 clusterNode.slots 与 clusterState.slots 如果只有clusterNode.slots ，想要知道某个槽被指派给哪个节点，需要以O（N）的复杂度对clusterState.Nodes字典中每个节点的slots数组进行遍历，而通过clusterState.slots查找只需要O（1）复杂度。 如果只有clusterState.slots ，想要将某个节点的槽指派信息发送给其他节点，需要以O（N）的复杂度对clusterState.slots数组进行遍历，而通过clusterState.slots可以直接发送。
#####在集群中执行命令 在对数据库中的16384个槽都进行了指派之后，集群就会进入上线状态，这时客户端就可以向集群中的节点发送数据命令了。 当客户端向节点发送与数据库键有关的命令时，接收命令的节点会计算出命令要处理的数据库键属于哪个槽，并检查这个槽所在的节点，如果键所在的槽正好就指派给了当前节点，那么节点直接执行这个命令。如果键所在的槽并没有指派给当前节点，那么节点会向客户端返回一个MOVED错误，指引客户端转向（redirect）至正确的节点，并客户端会向正确的节点再次发送之前想要执行的命令，并且之后这个槽的对应的键也会直接往正确的节点发送。 #####“计算键属于哪个槽 节点使用以下算法来计算给定键key属于哪个槽
def slot_number(key): return CRC16(key) & 16383点击复制代码复制出错复制成功
其中CRC16（key）语句用于计算键key的CRC-16校验和，而&16383语句则用于计算出一个介于0至16383之间的整数作为键key的槽号。 #####“节点数据库的实现 集群节点保存键值对以及键值对过期时间的方式，与的单机Redis服务器保存键值对以及键值对过期时间的方式完全相同。节点和单机服务器在数据库方面的一个区别是，节点只能使用0号数据库。 下图展示了节点7000的数据库状态，数据库中包含列表键"lst"，哈希键"book"，以及字符串键"date"，其中键"lst"和键"book"带有过期时间。 
除了将键值对保存在数据库里面之外，节点还会用clusterState结构中的slots_to_keys跳跃表来保存槽和键之间的关系。slots_to_keys跳跃表每个节点的分值保存键对应的槽位，每个节点的成员都是一个数据库键，如下图所示： 
重新分片
Redis集群的重新分片操作可以将任意数量已经指派给某个节点（源节点）的槽改为指派给另一个节点（目标节点），并且相关槽所属的键值对也会从源节点被移动到目标节点。 重新分片操作可以在线（online）进行，在重新分片的过程中，集群不需要下线，并且源节点和目标节点都可以继续处理命令请求。 “重新分片的实现原理 Redis集群的重新分片操作是由Redis的集群管理软件redis-trib负责执行的，Redis提供了进行重新分片所需的所有命令，而redis-trib则通过向源节点和目标节点发送命令来进行重新分片操作。 redis-trib对集群的单个槽slot进行重新分片的步骤如下： 1）redis-trib对目标节点发送CLUSTER SETSLOTIMPORTING命令，让目标节点准备好从源节点导入（import）属于槽slot的键值对。 2）redis-trib对源节点发送CLUSTER SETSLOTMIGRATING命令，让源节点准备好将属于槽slot的键值对迁移（migrate）至目标节点。 3）redis-trib向源节点发送CLUSTER GETKEYSINSLOT命令，获得最多count个属于槽slot的键值对的键名（key name）。 “重新分片的实现原理 Redis集群的重新分片操作是由Redis的集群管理软件redis-trib负责执行的，Redis提供了进行重新分片所需的所有命令，而redis-trib则通过向源节点和目标节点发送命令来进行重新分片操作。 redis-trib对集群的单个槽slot进行重新分片的步骤如下： 1）redis-trib对目标节点发送CLUSTER SETSLOTIMPORTING命令，让目标节点准备好从源节点导入（import）属于槽slot的键值对。 2）redis-trib对源节点发送CLUSTER SETSLOTMIGRATING命令，让源节点准备好将属于槽slot的键值对迁移（migrate）至目标节点。 3）redis-trib向源节点发送CLUSTER GETKEYSINSLOT命令，获得最多count个属于槽slot的键值对的键名（key name）。 4）对于步骤3获得的每个键名，redis-trib都向源节点发送一个MIGRATE0命令，将被选中的键原子地从源节点迁移至目标节点。 5）重复执行步骤3和步骤4，直到源节点保存的所有属于槽slot的键值对都被迁移至目标节点为止。每次迁移键的过程如图17-24所示。 6）redis-trib向集群中的任意一个节点发送CLUSTER SETSLOTNODE命令，将槽slot指派给目标节点，这一指派信息会通过消息发送至整个集群，最终集群中的所有节点都会知道槽slot已经指派给了目标节点。 
槽迁移相关
typedef struct clusterState { clusterNode *importing_slots_from[16384]; clusterNode *migrating_slots_to[16384]; } clusterState;点击复制代码复制出错复制成功
clusterState结构的importing_slots_from数组记录了当前节点正在从其他节点导入的槽,如果importing_slots_from[i]的值不为NULL，而是指向一个clusterNode结构，那么表示当前节点正在从clusterNode所代表的节点导入槽i。同理migrating_slots_to数组记录了当前节点正在导出到其他节点的槽。 当对集群进行重新分片时，源节点会对migrating_slots_to数组进行更新，目标节点会对importing_slots_from数组进行更新。
#####ASK错误 在进行重新分片期间，源节点向目标节点迁移一个槽的过程中，可能会出现这样一种情况：属于被迁移槽的一部分键值对保存在源节点里面，而另一部分键值对则保存在目标节点里面。 当客户端向源节点发送一个与数据库键有关的命令，并且命令要处理的数据库键恰好就属于正在被迁移的槽时： ·源节点会先在自己的数据库里面查找指定的键，如果找到的话，就直接执行客户端发送的命令。 ·相反地，如果源节点没能在自己的数据库里面找到指定的键，那么这个键有可能已经被迁移到了目标节点，源节点将向客户端返回一个ASK错误，指引客户端转向正在导入槽的目标节点，在向目标节点发送之前想要执行的命令之前，需要先发送ASKING命令，将客户端的REDIS_ASKING标识打开，否则目标节点不会对正在迁移的槽执行相关的命令。（客户端的REDIS_ASKING标识是一个一次性标识，当节点执行了一个带有REDIS_ASKING标识的客户端发送的命令之后，客户端的REDIS_ASKING标识就会被移除。） ASK 
#####ASK错误和MOVED错误的区别 ASK错误和MOVED错误都会导致客户端转向，它们的区别在于： ·MOVED错误代表槽的负责权已经从一个节点转移到了另一个节点：在客户端收到关于槽i的MOVED错误之后，客户端每次遇到关于槽i的命令请求时，都可以直接将命令请求发送至MOVED错误所指向的节点，因为该节点就是目前负责槽i的节点。 ·与此相反，ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施：在客户端收到关于槽i的ASK错误之后，客户端只会在接下来的一次命令请求中将关于槽i的命令请求发送至ASK错误所指示的节点，但这种转向不会对客户端今后发送关于槽i的命令请求产生任何影响，客户端仍然会将关于槽i的命令请求发送至目前负责处理槽i的节点，除非ASK错误再次出现。 #####复制和故障转移 Redis集群中的节点分为主节点（master）和从节点（slave），其中主节点用于处理槽，而从节点则用于复制某个主节点，并在被复制的主节点下线时，代替下线主节点继续处理命令请求。
故障检测
集群中的每个节点都会定期地向集群中的其他节点发送PING消息，以此来检测对方是否在线，如果接收PING消息的节点没有在规定的时间内，向发送PING消息的节点返回PONG消息，那么发送PING消息的节点就会将接收PING消息的节点标记为疑似下线（probable fail，PFAIL）。 集群中的各个节点会通过互相发送消息的方式来交换集群中各个节点的状态信息，例如某个节点是处于在线状态、疑似下线状态（PFAIL），还是已下线状态。 一个主节点A通过消息得知主节点B认为主节点C进入了疑似下线状态时，主节点A会在自己的clusterState.nodes字典中找到主节点C所对应的clusterNode结构，并将主节点B的下线报告（failure report）添加到clusterNode结构的fail_reports链表里面 
#####故障转移 当一个从节点发现自己正在复制的主节点进入了已下线状态时，从节点将开始对下线主节点进行故障转移，以下是故障转移的执行步骤： 1）复制下线主节点的所有从节点里面，会有一个从节点被选中。 2）被选中的从节点会执行SLAVEOF no one命令，成为新的主节点。 3）新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己。 4）新的主节点向集群广播一条PONG消息，这条PONG消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点已经接管了原本由已下线节点负责处理的槽。 5）新的主节点开始接收和自己负责处理的槽有关的命令请求，故障转移完成。 #####选举新的主节点 新的主节点是通过选举产生的，这个选举新主节点的方法和第16章介绍的选举领头Sentinel的方法非常相似，因为两者都是基于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）如果在一个配置纪元里面没有从节点能收集到足够多的支持票，那么集群进入一个新的配置纪元，并再次进行选举，直到选出新的主节点为止。 #####消息 集群中的各个节点通过发送和接收消息（message）来进行通信， 节点发送的消息主要有以下五种： ·MEET消息： 当发送者接到客户端发送的CLUSTER MEET命令时，发送者会向接收者发送MEET消息，请求接收者加入到发送者当前所处的集群里面。 PING消息 集群里的每个节点默认每隔一秒钟就会从已知节点列表中随机选出五个节点，然后对这五个节点中最长时间没有发送过PING消息的节点发送PING消息，以此来检测被选中的节点是否在线。除此之外，如果节点A最后一次收到节点B发送的PONG消息的时间，“距离当前时间已经超过了节点A的cluster-node-timeout选项设置时长的一半，那么节点A也会向节点B发送PING消息，这可以防止节点A因为长时间没有随机选中节点B作为PING消息的发送对象而导致对节点B的信息更新滞后。 PONG消息 当接收者收到发送者发来的MEET消息或者PING消息时，为了向发送者确认这条MEET消息或者PING消息已到达，接收者会向发送者返回一条PONG消息。另外，一个节点也可以通过向集群广播自己的PONG消息来让集群中的其他节点立即刷新关于这个节点的认识，例如当一次故障转移操作成功执行之后，新的主节点会向集群广播一条PONG“消息，以此来让集群中的其他节点立即知道这个节点已经变成了主节点，并且接管了已下线节点负责的槽。 FAIL消息 当一个主节点A判断另一个主节点B已经进入FAIL状态时，节点A会向集群广播一条关于节点B的FAIL消息，所有收到这条消息的节点都会立即将节点B标记为已下线。 PUBLISH消息 当节点接收到一个PUBLISH命令时，节点会执行这个命令，并向集群广播一条PUBLISH消息，所有接收到这条PUBLISH消息的节点都会执行相同的PUBLISH命令
