redis cluster（4）- redis集群原理

https://www.jianshu.com/p/0232236688c1

1、集群架构

Redis集群设计 总体架构

在这个图中，每一个蓝色的圈都代表着一个redis的服务器节点。它们任何两个节点之间都是相互连通的。客户端可以与任何一个节点相连接，然后就可以访问集群中的任何一个节点。对其进行存取和其他操作。

集群节点属性

集群中每个Master node负责存储数据、集群状态，包括slots与nodes对应关系。Master nodes能够自动发现其他nodes，检测failure节点，当某个Master节点失效时，集群能将核实的Slave提升为Master。下图是节点的关联信息，节点定时会将这些信息发送给其他节点：

1fc2412b7429e4ab5d8704fcd39520815ea2727b 10.9.42.37:6103 master - 0 1494082584680 9 connected 10923-13652 
08e70bb3edd7d3cabda7a2ab220f2f3610db38cd 10.9.33.204:6202 slave ad1334bd09ee73fdeb7b8f16194550fc2bf3a038 0 1494082586686 8 connected 
edaafc250f616e9e12c5182f0322445ea9a89085 10.9.33.204:6203 slave 1fc2412b7429e4ab5d8704fcd39520815ea2727b 0 1494082586184 9 connected 
06cd6f24caf98a1c1df0862eadac2b05254f909d 10.9.33.204:6201 slave d458c22ccced2f29358b6e6814a206d08285374e 0 1494082584179 7 connected 
3892b7fb410a4d6339364dbdda2ebc666ffee843 10.9.42.37:6203 slave 73f7d44c03ada58bf5adaeb340359e2c043ecfa0 0 1494082582679 12 connected 
73f7d44c03ada58bf5adaeb340359e2c043ecfa0 10.9.33.204:6103 master - 0 1494082585181 3 connected 13653-16383 
4004a64211bea5050a8f46b8436564d40380cd60 10.9.33.204:6101 master - 0 1494082583678 1 connected 2731-5460 
d458c22ccced2f29358b6e6814a206d08285374e 10.9.42.37:6101 master - 0 1494082588189 7 connected 0-2730 
f8868d59c0f3d935d3dbe35601506039520f7107 10.9.42.37:6201 slave 4004a64211bea5050a8f46b8436564d40380cd60 0 1494082587187 10 connected 
45ba0d6fc3d48a43ff72e10bcc17d2d8b2592cdf 10.9.33.204:6102 master - 0 1494082583179 2 connected 8192-10922 
007d7e17bfd26a3c1e21992bb5b656a92eb65686 10.9.42.37:6202 slave 45ba0d6fc3d48a43ff72e10bcc17d2d8b2592cdf 0 1494082588189 11 connected 
ad1334bd09ee73fdeb7b8f16194550fc2bf3a038 10.9.42.37:6102 myself,master - 0 0 8 connected 5461-8191 

从左至右分别是：

节点ID、IP地址和端口，节点角色标志、最后发送ping时间、最后接收到pong时间、连接状态、节点负责处理的hash slot。

集群可以自动识别出ip/port的变化，并通过Gossip（最终一致性，分布式服务数据同步算法）协议广播给其他节点知道。Gossip也称“病毒感染算法”、“谣言传播算法”（附录一）。

2、集群通信

---

2.1 集群发现：MEET

最开始时，每个Redis实例自己是一个集群，我们通过cluster meet让各个结点互相“握手”。这也是Redis Cluster目前的一个欠缺之处：缺少结点的自动发现功能。

需要组建一个真正的可工作的集群，我们必须将各个独立的节点连接起来，构成一个包含多个节点的集群。

连接各个节点的工作使用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)新的主节点开始接收和处理槽相关的请求