Redis Cluster原理分析
文章较长，如需转载可分段。转载请标明作者以及文章来源，谢谢！
作者介绍
姓名：李航
工作经历：多互联网工作经验，先后在58同城，汽车之家，优酷土豆集团，滴滴工作。主要关注领域Nginx，Redis，分布式系统，分布式存储。
这次主要是给大家分享的提纲如下：
1.简介
2.集群通信
3.数据分布及槽信息
4.数据迁移
5.通信故障
1.简介
继上次分享的优酷土豆的Redis服务平台化之路，这次着重来分享下Redis Cluster浅析，欢迎大家互相多交流学习。
Redis Cluster是一个高性能高可用的分布式系统。由多个Redis实例组成的整体，数据按照Slot存储分布在多个Redis实例上，通过Gossip协议来进行节点之间通信。
Redis Cluster功能特点如下：
1)所有的节点相互连接
2)集群消息通信通过集群总线通信，，集群总线端口大小为客户端服务端口+10000，这个10000是固定值
3)节点与节点之间通过二进制协议进行通信
4)客户端和集群节点之间通信和通常一样，通过文本协议进行
5)集群节点不会代理查询
6)数据按照Slot存储分布在多个Redis实例上
7)集群节点挂掉会自动故障转移
8)可以相对平滑扩/缩容节点
2.集群通信
2.1 CLUSTER MEET
需要组建一个真正的可工作的集群，我们必须将各个独立的节点连接起来，构成一个包含多个节点的集群。
连接各个节点的工作使用CLUSTER MEET命令来完成。
CLUSTER MEET <ip> <port>
CLUSTER MEET命令实现：
1)节点A会为节点B创建一个clusterNode结构，并将该结构添加到自己的clusterState.nodes字典里面。
2)节点A根据CLUSTER MEET命令给定的IP地址和端口号，向节点B发送一条MEET消息。
3)节点B接收到节点A发送的MEET消息，节点B会为节点A创建一个clusterNode结构，并将该结构添加到自己的clusterState.nodes字典里面。
4)节点B向节点A返回一条PONG消息。
5)节点A将受到节点B返回的PONG消息，通过这条PONG消息节点A可以知道节点B已经成功的接收了自己发送的MEET消息。
6)之后，节点A将向节点B返回一条PING消息。
7)节点B将接收到的节点A返回的PING消息，通过这条PING消息节点B可以知道节点A已经成功的接收到了自己返回的PONG消息，握手完成。
8)之后，节点A会将节点B的信息通过Gossip协议传播给集群中的其他节点，让其他节点也与节点B进行握手，最终，经过一段时间后，节点B会被集群中的所有节点认识。
2.2集群消息处理clusterProcessPacket
1)更新接收消息计数器
2)查找发送者节点并且不是handshake节点
3)更新自己的epoch和slave的offset信息
4)处理MEET消息，使加入集群
5)从goosip中发现未知节点，发起handshake
6)对PING，MEET回复PONG
7)根据收到的心跳信息更新自己clusterState中的master-slave，slots信息
8)对FAILOVER_AUTH_REQUEST消息，检查并投票
9)处理FAIL，FAILOVER_AUTH_ACK，UPDATE信息
2.3定时任务clusterCron
定时任务clusterCron
1)对handshake节点建立Link，发送Ping或Meet
2)向随机几点发送Ping
3)如果是从查看是否需要做Failover
4)统计并决定是否进行slave的迁移，来平衡不同master的slave数
5)判断所有pfail报告数是否过半数
2.4心跳数据
发送消息头信息Header
1)所负责slots的信息
2)主从信息
3)ip port信息
4)状态信息
发送其他节点Gossip信息
1)ping_sent, pong_received
2)ip, port信息
3)状态信息，比如发送者认为该节点已经不可达，会在状态信息中标记其为PFAIL或FAIL
clusterMsg结构的currentEpoch、sender、myslots等属性记录了发送者自身的节点信息，接收者会根据这些信息，在自己的clusterState.nodes字典里找到发送者对应的clusterNode结构，并对结构进行更新。
Redis集群中的各个节点通过Gossip协议来交换各自关于不同节点的状态信息，其中Gossip协议由MEET、PING、PONG三种消息实现，这三种消息的正文都由两个clusterMsgDataGossip结构组成。
每次发送MEET、PING、PONG消息时，发送者都从自己的已知节点列表中随机选出两个节点(可以是主节点或者从节点),并将这两个被选中节点的信息分别保存到两个结构中。
当接收者收到消息时，接收者会访问消息正文中的两个结构，并根据自己是否认识clusterMsgDataGossip结构中记录的被选中节点进行操作：
1.如果被选中节点不存在于接收者的已知节点列表，那么说明接收者是第一次接触到被选中节点，接收者将根据结构中记录的IP地址和端口号等信息，与被选择节点进行握手。
2.如果被选中节点已经存在于接收者的已知节点列表，那么说明接收者之前已经与被选中节点进行过接触，接收者将根据clusterMsgDataGossip结构记录的信息，对被选中节点对应的clusterNode结构进行更新。
2.5数据结构
clusterNode结构保存了一个节点的当前状态，比如节点的创建时间，节点的名字，节点当前的配置纪元，节点的IP和地址，等等。
1)slots：位图，由当前clusterNode负责的slot为1
2)salve, slaveof：主从关系信息
3)ping_sent, pong_received：心跳包收发时间
4)clusterLink *link：节点间的连接
5)list *fail_reports：收到的节点不可达投票
clusterState结构记录了在当前节点的集群目前所处的状态。
1)myself：指针指向自己的clusterNode
2)currentEpoch：当前节点的最大epoch，可能在心跳包的处理中更新
3)nodes：当前节点记录的所有节点，为clusterNode指针数组
4)slots：slot与clusterNode指针映射关系
5)migrating_slots_to,
importing_slots_from：记录slots的迁移信息
6)failover_auth_time,failover_auth_count,failover_auth_sent,failover_auth_rank,
failover_auth_epoch：Failover相关信息
clusterLink结构保存了连接节点所需的有关信息，比如套接字描述符，输入缓冲区和输出缓冲区。
3.数据分布及槽信息
3.1槽（slot）概念
Redis Cluster中有一个16384长度的槽的概念，他们的编号为0、1、2、3……16382、16383。这个槽是一个虚拟的槽，并不是真正存在的。正常工作的时候，Redis Cluster中的每个Master节点都会负责一部分的槽，当有某个key被映射到某个Master负责的槽，那么这个Master负责为这个key提供服务，至于哪个Master节点负责哪个槽，这是可以由用户指定的，也可以在初始化的时候自动生成（redis-trib.rb脚本）。这里值得一提的是，在Redis Cluster中，只有Master才拥有槽的所有权，如果是某个Master的slave，这个slave只负责槽的使用，但是没有所有权。
3.2数据分片
在Redis Cluster中，拥有16384个slot，这个数是固定的，存储在Redis Cluster中的所有的键都会被映射到这些slot中。数据库中的每个键都属于这16384个哈希槽的其中一个，集群使用公式CRC16(key) % 16384来计算键key属于哪个槽，其中CRC16(key)语句用于计算键key的CRC16校验和。集群中的每个节点负责处理一部分哈希槽。
3.3节点的槽指派信息
clusterNode结构的slots属性和numslot属性记录了节点负责处理那些槽：
struct clusterNode {
//…
unsignedchar slots[16384/8];
};
Slots属性是一个二进制位数组(bit
array)，这个数组的长度为16384/8=2048个字节，共包含16384个二进制位。
Master节点用bit来标识对于某个槽自己是否拥有。比如对于编号为1的槽，Master只要判断序列的第二位（索引从0开始）是不是为1即可。时间复杂度为O（1）。
3.4集群所有槽的指派信息
通过将所有槽的指派信息保存在clusterState.slots数组里面，程序要检查槽i是否已经被指派，又或者取得负责处理槽i的节点，只需要访问clusterState.slots[i]的值即可，复杂度仅为O（1）。
3.5请求重定向
由于每个节点只负责部分slot，以及slot可能从一个节点迁移到另一节点，造成客户端有可能会向错误的节点发起请求。因此需要有一种机制来对其进行发现和修正，这就是请求重定向。有两种不同的重定向场景：
a)MOVED错误
1.请求的key对应的槽不在该节点上，节点将查看自身内部所保存的哈希槽到节点ID的映射记录， 节点回复一个MOVED错误。
2.需要客户端进行再次重试。
b)ASK错误
1.请求的key对应的槽目前的状态属于MIGRATING状态，并且当前节点找不到这个key了，节点回 复ASK错误。ASK会把对应槽的IMPORTING节点返回给你，告诉你去IMPORTING的节点尝试找找。
2.客户端进行重试首先发送ASKING命令，节点将为客户端设置一个一次性的标志（flag），使得 客户端可以执行一次针对IMPORTING状态的槽的命令请求，然后再发送真正的命令请求。
3.不必更新客户端所记录的槽至节点的映射。
4.数据迁移
当槽x从Node A向Node B迁移时，Node A和Node B都会有这个槽x，Node A上槽x的状态设置为MIGRATING，Node B上槽x的状态被设置为IMPORTING。
MIGRATING状态
1)如果key存在则成功处理
2)如果key不存在，则返回客户端ASK，客户端根据ASK首先发送ASKING命令到目标节点，然后发送请求的命令到目标节点
3)当key包含多个命令，
a)如果都存在则成功处理
b)如果都不存在，则返回客户端ASK
c)如果一部分存在，则返回客户端TRYAGAIN，通知客户端稍后重试，这样当所有的 key都迁移完毕的时候客户端重试请求的时候回得到ASK，然后经过一次重定向就 可以获取这批键
4)此时不刷新客户端中node的映射关系
IMPORTING状态
1)如果key不在该节点上，会被MOVED重定向，刷新客户端中node的映射关系
2)如果是ASKING命令则命令会被执行，key不在迁移的节点已经被迁移到目标的节点
3)Key不存在则新建
4.1读写请求
槽里面的key还未迁移，并且槽属于迁移中
假如k1属于槽x，并且k1还在Node A
4.2 MOVED请求
槽里面的key已经迁移过去，并且槽属于迁移完
假如k1属于槽x，并且k1不在Node A，而且槽x已经迁移到Node B
4.3 ASK请求
槽里面的key已经迁移完，并且槽属于迁移中
假如k1属于槽x，并且k1不在Node A，而且槽x还是MIGRATING状态
5.通信故障
5.1故障检测
集群中的每个节点都会定期地向集群中的其他节点发送PING消息，以此交换各个节点状态信息，检测各个节点状态：在线状态、疑似下线状态PFAIL、已下线状态FAIL。
当主节点A通过消息得知主节点B认为主节点D进入了疑似下线(PFAIL)状态时,
主节点A会在自己的clusterState.nodes字典中找到主节点D所对应的clusterNode结构，
并将主节点B的下线报告(failure report)添加到clusterNode结构的fail_reports链表中
struct clusterNode {
//...
//记录所有其他节点对该节点的下线报告
list*fail_reports;
//...
};
每个下线报告由一个clusterNodeFailReport结构：
struct clusterNodeFailReport{
//报告目标节点已经下线的节点
structclusterNode *node;
//最后一次从node节点收到下线报告的时间
mstime_ttime;
}typedef clusterNodeFailReport;
如果集群里面，半数以上的主节点都将主节点D报告为疑似下线，那么主节点D将被标记为已下线(FAIL)状态，将主节点D标记为已下线的节点会向集群广播主节点D的FAIL消息，
所有收到FAIL消息的节点都会立即更新nodes里面主节点D状态标记为已下线。
将node标记为FAIL需要满足以下两个条件：
1.有半数以上的主节点将node标记为PFAIL状态。
2.当前节点也将node标记为PFAIL状态。
5.2多个从节点选主
选新主的过程基于Raft协议选举方式来实现的
1)当从节点发现自己的主节点进行已下线状态时，从节点会广播一条
CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST消息，要求所有收到这条消息，并且具有投票权的主节点向这个从节点投票
2)如果一个主节点具有投票权，并且这个主节点尚未投票给其他从节点，那么主节点将向要求投票的从节点返回一条，CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息，表示这个主节点支持从节点成为新的主节点
3)每个参与选举的从节点都会接收CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息,并根据自己收到了多少条这种消息来统计自己获得了多少主节点的支持
4)如果集群里有N个具有投票权的主节点，那么当一个从节点收集到大于等于集群N/2+1张支持票时，这个从节点就成为新的主节点
5)如果在一个配置纪元没有从能够收集到足够的支持票数，那么集群进入一个新的配置纪元，并再次进行选主，直到选出新的主节点为止
5.3故障转移
当从节点发现自己的主节点变为已下线(FAIL)状态时，便尝试进Failover，以期成为新的主。
以下是故障转移的执行步骤：
1)从下线主节点的所有从节点中选中一个从节点
2)被选中的从节点执行SLAVEOF NO NOE命令，成为新的主节点
3)新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己
4)新的主节点对集群进行广播PONG消息，告知其他节点已经成为新的主节点
5)新的主节点开始接收和处理槽相关的请求