请选择 进入手机版 | 继续访问电脑版

Redis中国用户组(CRUG)论坛

 找回密码
 立即注册

扫一扫,访问微社区

搜索
热搜: 活动 交友 discuz
查看: 2011|回复: 1

Redis Cluster 源码分析

[复制链接]

该用户从未签到

6

主题

13

帖子

76

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
76

论坛元老

发表于 2016-8-18 09:59:40 | 显示全部楼层 |阅读模式
作者介绍
姓名:李航
工作经历:   5年多互联网工作经验,先后在58同城,汽车之家,优酷土豆集团工作。目前主要在优酷土豆集团任职高级开发工程师,目前主要负责大数据基础平台Redis集群开发及运维等工作。主要关注领域NginxRedis,分布式系统,分布式存储。本文来源自“Redis技术交流群”线上分享。李航IDLucien_168。群主IDgnuhpc。后期的分享我们会同期进行。
这次主要是给大家分享的提纲如下:
1.          简介
2.          数据分布及槽信息
3.          数据迁移
4.          故障转移
5.          集群通信
1.1.     简介
Redis Cluster是由多个同时服务于一个数据集合的Redis实例组成的整体,对于用户来说,用户只关注这个数据集合,而整个数据集合的某个数据子集存储在哪个节点对于用户来说是透明的。Redis Cluster具有分布式系统的特点,也具有分布式系统如何实现高可用性与数据一致性的难点,由多个Redis实例组成的Redis Cluster结构通常如下:

Redis Cluster功能特点如下:
l  所有的节点相互连接;
l  集群消息通信通过集群总线通信,,集群总线端口大小为客户端服务端口+10000,这个10000是固定值;
l  节点与节点之间通过二进制协议进行通信;
l  客户端和集群节点之间通信和通常一样,通过文本协议进行;
l  集群节点不会代理查询;
l  集群节点挂掉会自动故障转移
l  可以相对平滑扩/缩容节点
1.2.     数据分布及槽信息1.2.1 槽(slot)概念
Redis Cluster中有一个16384长度的槽的概念,他们的编号为0123……1638216383。这个槽是一个虚拟的槽,并不是真正存在的。正常工作的时候,Redis Cluster中的每个Master节点都会负责一部分的槽,当有某个key被映射到某个Master负责的槽,那么这个Master负责为这个key提供服务,至于哪个Master节点负责哪个槽,这是可以由用户指定的,也可以在初始化的时候自动生成(redis-trib.rb脚本)。这里值得一提的是,在Redis Cluster中,只有Master才拥有槽的所有权,如果是某个Masterslave,这个slave只负责槽的使用,但是没有所有权。
1.2.2 数据分片
Redis Cluster中,拥有16384slot,这个数是固定的,存储在Redis Cluster中的所有的键都会被映射到这些slot中。数据库中的每个键都属于这 16384 个哈希槽的其中一个,集群使用公式 CRC16(key) % 16384 来计算键 key 属于哪个槽,其中 CRC16(key) 语句用于计算键 key CRC16 校验和。集群中的每个节点负责处理一部分哈希槽。
1.2.3 节点的槽指派信息
clusterNode结构的slots属性和numslot属性记录了节点负责处理那些槽:
struct clusterNode {
           //…
           unsignedchar slots[16384/8];
};
Slots属性是一个二进制位数组(bitarray),这个数组的长度为16384/8=2048个字节,共包含16384个二进制位。
Master节点用bit来标识对于某个槽自己是否拥有。比如对于编号为1的槽,Master只要判断序列的第二位(索引从0开始)是不是为1即可。时间复杂度为O1)。
1.2.4 集群所有槽的指派信息
通过将所有槽的指派信息保存在clusterState.slots数组里面,程序要检查槽i是否已经被指派,又或者取得负责处理槽i的节点,只需要访问clusterState.slots的值即可,复杂度仅为O1)。
图片 1.jpg
1.2.5 请求重定向
由于每个节点只负责部分slot,以及slot可能从一个节点迁移到另一节点,造成客户端有可能会向错误的节点发起请求。因此需要有一种机制来对其进行发现和修正,这就是请求重定向。有两种不同的重定向场景:
a)             MOVED错误
l  请求的key对应的槽不在该节点上,节点将查看自身内部所保存的哈希槽到节点 ID 的映射记录,节点回复一个 MOVED 错误。
l  需要客户端进行再次重试。
图片 1.jpg
b)            ASK错误
l  请求的key对应的槽目前的状态属于MIGRATING状态,并且当前节点找不到这个key了,节点回复ASK错误。ASK会把对应槽的IMPORTING节点返回给你,告诉你去IMPORTING的节点尝试找找。
l  客户端进行重试 首先发送ASKING命令,节点将为客户端设置一个一次性的标志(flag),使得客户端可以执行一次针对 IMPORTING 状态的槽的命令请求,然后再发送真正的命令请求。
l  不必更新客户端所记录的槽至节点的映射。
1.3.     数据迁移
当槽x从一个NodeA向另一个Node B迁移时,Node A和Node B都会有这个槽x,Node A上槽x的状态设置为MIGRATING,NodeB上槽x的状态被设置为IMPORTING。
MIGRATING状态
key存在则成功处理
key不存在,则返回客户端ASK,仅当这次请求会转向另一个节点,并不会刷新客户端中node的映射关系,也就是说下次该客户端请求该key的时候,还会选择Node A节点
key包含多个命令,如果都存在则成功处理,如果都不存在,则返回客户端ASK,如果一部分存在,则返回客户端TRYAGAIN,通知客户端稍后重试,这样当所有的key都迁移完毕的时候客户端重试请求的时候回得到ASK,然后经过一次重定向就可以获取这批键
IMPORTING状态
正常命令会被MOVED重定向,如果是ASKING命令则命令会被执行,从而key没有在老的节点已经被迁移到新的节点的情况可以被顺利处理
Key不存在则新建
没有ASKING的请求和正常请求一样被MOVED,这保证客户端node映射关
系出错的情况下不会发生写错
1.3.1 读写请求
槽里面的key还未迁移,并且槽属于迁移中
假如k1属于槽x,并且k1还在Node A
图片 1.jpg
1.3.2 MOVED请求
槽里面的key已经迁移过去,并且槽属于迁移完
假如k1属于槽x,并且k1不在Node A,而且槽x已经迁移到Node B
图片 1.jpg
1.3.3 ASK请求
槽里面的key已经迁移完,并且槽属于迁移中
假如k1属于槽x,并且k1不在Node A,而且槽x还是MIGRATING状态

图片 1.jpg
1.4.     故障转移
slave发现自己的master变为FAIL状态时,便尝试进行Failover,以期成为新的master。由于挂掉的master可能会有多个slaveFailover的过程需要经过类Raft协议的过程在整个集群内达到一致,其过程如下:
l  slave发现自己的master变为FAIL
l  将自己记录的集群currentEpoch加1,并广播FailoverRequest信息
l  其他节点收到该信息,只有master响应,判断请求者的合法性,并发送FAILOVER_AUTH_ACK,对每一个epoch只发送一次ack
l  尝试failover的slave收集FAILOVER_AUTH_ACK
l  超过半数后变成新Master
l  广播Pong通知其他集群节点
node 标记为 FAIL 需要满足以下两个条件:
1.          有半数以上的主节点将 node 标记为 PFAIL 状态。
2.          当前节点也将 node 标记为 PFAIL 状态。
图片 1.jpg
1.5.     集群通信1.6.1 CLUSTER MEET
图片 1.jpg
需要组建一个真正的可工作的集群,我们必须将各个独立的节点连接起来,构成一个包含多个节点的集群。
连接各个节点的工作使用CLUSTER MEET命令来完成。
CLUSTER MEET <ip> <port>
CLUSTERMEET命令实现:
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会被集群中的所有节点认识。
1.6.2 集群消息处理 clusterProcessPacket
l  根据收到的消息更新自己的epoch和slave的offset信息
l  处理MEET消息,使加入集群
l  从goosip中发现未知节点,发起handshake
l  对PING,MEET回复PONG
l  根据收到的心跳信息更新自己clusterState中的master-slave,slots信息
l  对FAILOVER_AUTH_REQUEST消息,检查并投票
l  处理FAIL,FAILOVER_AUTH_ACK,UPDATE信息
图片 1.jpg
1.6.3 定时任务clusterCron
定时任务clusterCron
a)             对handshake节点建立Link,发送Ping或Meet
b)            选择合适的clusterNode发送Ping
c)             如果是从查看是否需要做Failover
d)            统计并决定是否进行slave的迁移,来平衡不同master的slave数
e)             判断所有pfail报告数是否过半数
图片 1.jpg
1.6.4 心跳数据
l  Header,发送者自己的信息
n  所负责slots的信息
n  主从信息
n  ip port信息
n  状态信息
l  Gossip,发送者所了解的部分其他节点的信息
n  ping_sent, pong_received
n  ip, port信息
n  状态信息,比如发送者认为该节点已经不可达,会在状态信息中标记其为PFAIL或FAIL
图片 1.jpg
clusterMsg结构的currentEpochsendermyslots等属性记录了发送者自身的节点信息,接收者会根据这些信息,在自己的clusterState.nodes字典里找到发送者对应的clusterNode结构,并对结构进行更新。
图片 1.jpg
Redis集群中的各个节点通过Gossip协议来交换各自关于不同节点的状态信息,其中Gossip协议由MEETPINGPONG三种消息实现,这三种消息的正文都由两个clusterMsgDataGossip结构组成。
每次发送MEETPINGPONG消息时,发送者都从自己的已知节点列表中随机选出两个节点(可以是主节点或者从节点),并将这两个被选中节点的信息分别保存到两个结构中。
当接收者收到消息时,接收者会访问消息正文中的两个结构,并根据自己是否认识clusterMsgDataGossip结构中记录的被选中节点进行操作:
1.          如果被选中节点不存在于接收者的已知节点列表,那么说明接收者是第一次接触到被选中节点,接收者将根据结构中记录的IP地址和端口号等信息,与被选择节点进行握手。
2.          如果被选中节点已经存在于接收者的已知节点列表,那么说明接收者之前已经与被选中节点进行过接触,接收者将根据clusterMsgDataGossip结构记录的信息,对被选中节点对应的clusterNode结构进行更新。

图片 1.jpg
1.6.5 数据结构
clusterNode 结构保存了一个节点的当前状态, 比如节点的创建时间, 节点的名字, 节点当前的配置纪元, 节点的 IP 和地址, 等等。
a)             slots:位图,由当前clusterNode负责的slot为1
b)            salve, slaveof:主从关系信息
c)             ping_sent, pong_received:心跳包收发时间
d)            clusterLink *link:Node间的连接
e)             list *fail_reports:收到的节点不可达投票
图片 1.jpg
clusterState 结构记录了在当前节点的视角下, 集群目前所处的状态。
a)             myself:指针指向自己的clusterNode
b)            currentEpoch:当前节点见过的最大epoch,可能在心跳包的处理中更新
c)             nodes:当前节点感知到的所有节点,为clusterNode指针数组
d)            slots:slot与clusterNode指针映射关系
e)             migrating_slots_to,importing_slots_from:记录slots的迁移信息
f)              failover_auth_time,failover_auth_count, failover_auth_sent, failover_auth_rank,failover_auth_epoch:Failover相关
图片 1.jpg
clusterLink 结构保存了连接节点所需的有关信息, 比如套接字描述符, 输入缓冲区和输出缓冲区。
图片 1.jpg
图片 1.jpg

图片 1.png

该用户从未签到

0

主题

1

帖子

20

积分

新手上路

Rank: 1

积分
20
发表于 2018-7-18 17:50:08 | 显示全部楼层
关于这句话“通过将所有槽的指派信息保存在clusterState.slots数组里面,程序要检查槽i是否已经被指派,又或者取得负责处理槽i的节点,只需要访问clusterState.slots的值即可,复杂度仅为O(1)。”。我理解的是:检查槽是否在自己节点判断slots数组对应下标的值是否为1即可,但是怎么通过这个数组找到负责处理槽i的节点呢
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|Redis中国用户组 ( 京ICP备15003959号

GMT+8, 2018-10-16 01:38 , Processed in 0.200723 second(s), 34 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表