分布式一致性协议Gossip和Redis 集群原理解析

Gossip-分布式协议、Redis Cluster 原理、Codis 分布式方案

1. Redis 单机模式

顾名思义,单机模式指 Redis 主节点以单个节点的形式存在,这个主节点可读可写,上面存储数据全集。在 3.0 版本之前,Redis 只能支持单机模式,出于可靠性考量,通常单机模式为“1 主 N 备”的结构,如下所示:

单机模式不支持自动故障转移(指的是主节点故障的时候,副节点不可以升主),扩容能力有限

需要说明的是,即便有很多个 Redis 主节点,只要这些主节点以单机模式存在,本质上仍为单机模式。单机模式比较简单,足以支撑一般应用场景,但单机模式具有固有的局限性:不支持自动故障转移,扩容能力极为有限(只能 Scale Up,垂直扩容),存在高并发瓶颈。

1.1 Sentinel-System(哨兵系统)

Sentinel-System(哨兵系统)由一个或者多个 sentinel 实例组成,可以监控 Redis 的主节点以及从节点

Sentinel-System(哨兵系统)是 Redis 的一个的高可用方案

当由一个或者多个 sentinel 实例组成的 Sentinel-System(哨兵系统)监控到 Redis 的主节点下线的时候,会根据特定的选举规则从主节点的从节点中选取一个最优的从节点升主。然后由最新的主节点处理请求。

1.2 单机扩容能力极为有限

这一点应该很好理解,单机模式下,只有主节点能够写入数据,那么,最大数据容量就取决于主节点所在物理机的内存容量,而物理机的内存扩容(Scale Up)能力目前仍是极为有限的。

1.3 高并发瓶颈

Redis 是单线程的 IO 复用模型,单线程可以将单纯的 IO 操作的速度发挥到最大,但是 Redis 的简单的计算操作阻塞整个 IO 调度。

Redis 使用单线程的 IO 复用模型,对于单纯的 IO 操作来说,单线程可以将速度优势发挥到最大,但 Redis 也提供了一些简单的计算功能,比如排序、聚合等,对于这些操作,单线程模型实际会严重影响整体吞吐量,CPU 计算过程中,整个 IO 调度都会被阻塞住。因此,单机模式下并发支持能力很容易陷入瓶颈。

2. Redis Cluster

解决并发局限问题:Redis 号称单例 10 万并发。但也仅仅是 10 万并发。

解决容量问题:在一些应用场景下,数据规模可达数十 G,甚至数百 G。而物理机的资源却是有限的。

Redis Cluster 是 Redis 官方推出的一个原生的分布式方案。

2.1 Redis Cluster 特点

节点之间采用 PING-PONG 互联,采用二进制协议

所有的 Redis 节点彼此互联(PING-PONG 机制),内部使用二进制协议优化传输速度和带宽;

不存在中心节点,节点之间通过 Gossip 协议实现一致

Redis Cluster 不存在中心节点,每个节点都记录有集群的状态信息,并且通过 Gossip 协议,使每个节点记录的信息实现最终一致性;

客户端直连 Redis Cluster 中间一个可用的节点

客户端与 Redis 节点直连,不需要中间 Proxy 层,客户端不需要连接集群所有节点,连接集群中任何一个可用节点即可;

Redis Cluster 的键空间被分片,分的片被分别分配给主节点(主节点的概念个中心节点的概念还是不同的)

Redis Cluster 的键空间被分割为 16384 个 Slot,这些 Slot 被分别指派给主节点,当存储 Key-Value 时,根据 CRC16(key) Mod 16384 的值,决定将一个 Key-Value 放到哪个 Slot 中;

集群中的一个节点,当其他超过半数的节点检测到它失效,那么它就被判定为失效。

对于集群中的任何一个节点,需要超过半数的节点检测到它失效(pFail),才会将其判定为失效(Fail)

当某个主节点故障,其他主节点从该节点的从节点中选举主节点。(自动选举)

当集群中某个主节点故障后(Fail),其它主节点会从故障主节点的从节点中选举一个“最佳”从节点升主,替代故障的主节点;

集群模式下,使用相同的)号数据库

集群模式下,由于数据分布在多个节点,不支持单机模式下的集合操作,也不支持多数据库功能,集群只能使用默认的 0 号数据库;

集群规模推荐是 1000

官方推荐的最大节点数量为 1000 个左右,这是因为当集群规模过大时,Gossip 协议的效率会显著下降,通信成本剧增 。

2.2 Redis-Cluster 实现基础:分片

理论:集群的基础肯定离不开数据分片,即先把数据分片,然后指派给多个 Redis 实例。

Redis 集群实现的基础是分片,即将数据集有机的分割为多个片,并将这些分片指派给多个 Redis 实例,每个实例只保存总数据集的一个子集。利用多台计算机内存和来支持更大的数据库,而避免受限于单机的内存容量;通过多核计算机集群,可有效扩展计算能力;通过多台计算机和网络适配器,允许我们扩展网络带宽。

实现:Hash Slot 。每个物理节点对应一个 Slot。Redis Cluster 把所有的物理节点映射(指向)到预先分好的 16384 个 Slot 上,当需要在 Redis 集群中放置一个 Key-Value 时,根据 CRC16(key) Mod 16384 的值,决定将一个 Key 放到哪个 Slot 中。

2.3 Redis Cluster 请求路由方式

重定向到正确的节点:

正是因为数据分片,当客户端直连到集群 Redis Cluster 中间一个可用的节点的时候,如果进行读写操作的 KEY 对应的 Slot 不在当前直连的节点上,那么就重定向到正确的节点。

重定向的操作不是由一个 Redis 节点到另外一个 Redis 节点,而是借助客户端转发到正确的节点。

和普通的查询路由相比,Redis Cluster 借助客户端实现的请求路由是一种混合形式的查询路由,它并非从一个 Redis 节点到另外一个 Redis,而是借助客户端转发到正确的节点。

实际应用中,可以在客户端缓存 Slot 与 Redis 节点的映射关系,当接收到 MOVED 响应时修改缓存中的映射关系。如此,基于保存的映射关系,请求时会直接发送到正确的节点上,从而减少一次交互,提升效率。

3.Redis Cluster 节点通信原理:Gossip 算法

Gossip 算法源自流行病学的研究,经过不断的发展演化,作为一种分布式一致性协议而得到广泛应用,如 Cassandra、Akka、Redis 都有用到。

3.1 Gossip 背景

Gossip 给传播算法的提供语义和证明

Gossip 算法如其名,在办公室,只要一个人八卦一下,在有限的时间内所有的人都会知道该八卦的信息,这种方式也与病毒传播类似,因此 Gossip 有众多的别名,如“闲话算法”、“疫情传播算法”、“病毒感染算法”、“谣言传播算法”。但 Gossip 并不是一个新东西,之前的泛洪查找、路由算法都归属于这个范畴,不同的是 Gossip 给这类算法提供了明确的语义、具体实施方法及收敛性证明。

3.2 Gossip 特点

在杂乱无章中寻求一致

Gossip 算法又被称为反熵(Anti-Entropy),熵是物理学上的一个概念,代表杂乱无章,而反熵就是在杂乱无章中寻求一致,这充分说明了 Gossip 的特点:在一个有界网络中,每个节点都随机地与其它节点通信,经过一番杂乱无章的通信,最终所有节点的状态都会达成一致。每个节点可能知道所有其它节点,也可能仅知道几个邻居节点,只要这些节可以通过网络连通,最终它们的状态都是一致的。

3.3 Gossip 本质

Gossip 是带冗余的容错算法。

Gossip 是最终一致性算法。

Gossip 适用于“最终一致性”的场景:失败检测,路由同步,负载均衡

3.4 Gossip 在 Redis Cluster 中的作用

分布式系统中间需要:维护节点元数据(元数据是指:节点负责哪些数据,节点的主从属性,是否出现故障)

常见的维护方式:集中式和无中心式(Gossip 是无中心式)

Gossip 在 Redis Cluster 中的两大作用:

  • 去中心化
  • 失败检测

3.5 节点通信基础

Redis Cluster 中的每个 Redis 实例监听两个 TCP 端口,6379(默认)用于服务客户端查询,16379(默认服务端口+10000)用于集群内部通信。

集群中节点通信方式如下:

  • 每个节点在固定周期内部通过特定的规则选择几个节点发送 Ping 信息
  • 接收到 Ping 消息的节点用 Pong 消息作为响应。

集群中每个节点通过一定规则挑选要通信的节点,每个节点可能知道全部节点,也可能仅知道部分节点,只要这些节点彼此可以正常通信,最终它们会达到一致的状态。当节点故障、新节点加入、主从关系变化、槽信息变更等事件发生时,通过不断的 Ping/Pong 消息通信,经过一段时间后所有的节点都会知道集群全部节点的最新状态,从而达到集群状态同步的目的。

3.6 Gossip 消息种类

Gossip 协议的主要职责就是信息交换。信息交换的载体就是节点彼此发送的 Gossip 消息,常用的 Gossip 消息可分为:Ping 消息、Pong 消息、Meet 消息、Fail 消息。

Meet 消息用来通知新节点加入集群 Meet 消息:用于通知新节点加入。消息发送者通知接收者加入到当前集群,Meet 消息通信正常完成后,接收节点会加入到集群中并进行周期性的 Ping、Pong 消息交换;

Ping 包含了自己本身的状态和其他节点的状态

Ping 消息:集群内交换最频繁的消息,集群内每个节点每秒向多个其它节点发送 Ping 消息,用于检测节点是否在线和交换彼此状态信息。Ping 消息发送封装了自身节点和部分其它节点的状态数据;

Pong 一方面确认通信,另外可以广播自身的 Pong 来通知集群对自己的状态进行更新

Pong 消息:当接收到 Ping、Meet 消息时,作为响应消息回复给发送方确认消息正常通信。Pong 消息内部封装了自身状态数据。节点也可以向集群内广播自身的 Pong 消息来通知整个集群对自身状态进行更新;

Fail 当节点判定另外一个节点下线的时候,通过广播一个 Fail 消息,变更节点信息为下线状态

Fail 消息:当节点判定集群内另一个节点下线时,会向集群内广播一个 Fail 消息,其他节点接收到 Fail 消息之后把对应节点更新为下线状态。

4 Redis Cluster 节点通信

4.1 节点间是如何交换信息的?

Redis 节点启动之后,会每间隔 100ms 执行一次集群的周期性函数 clusterCron()。在 Redis 源码 server.c 中可见:

 /* Run the Redis Cluster cron. */
    run_with_period(100) {
        if (server.cluster_enabled) clusterCron();
    }

而 clusterCron() 中又会调用 clusterSendPing() 函数,该函数用于将随机选择的节点的信息加入到 Ping 消息体中,然后发送出去。

当前节点向另一个节点发送 Ping 消息时,携带的其它节点的消息数量至少为 3,最大等于集群节点总数-2;

为 Ping 消息体中选择携带的其它节点的信息时,采用的是混合选择模式:随机选择+偏好性选择,这样不仅可以保证 Gossip 协议随机传播的原则,还可以尽量将当前节点掌握的其它节点的故障信息传播出去。

void clusterSendPing(clusterLink *link, int type) {
    unsigned char *buf;
    clusterMsg *hdr;
    int gossipcount = 0; /* Number of gossip sections added so far. */
    int wanted; /* Number of gossip sections we want to append if possible. */
    int totlen; /* Total packet length. */
    // freshnodes = 集群总节点数 - (2=当前节点+发送消息的目的节点)
    // freshnodes 的值是ping消息体中可以携带节点信息的最大值
    int freshnodes = dictSize(server.cluster->nodes)-2;
    // wanted 的值是集群节点的十分之一向下取整,并且最小等于3
    // wanted 表示ping消息体中期望携带的其它节点信息个数
    wanted = floor(dictSize(server.cluster->nodes)/10);
    if (wanted < 3) wanted = 3;
    // 因此 wanted 最多等于 freshnodes。
    if (wanted > freshnodes) wanted = freshnodes;

    // 计算分配消息的最大空间
    totlen = sizeof(clusterMsg)-sizeof(union clusterMsgData);
    totlen += (sizeof(clusterMsgDataGossip)*wanted);
    // 消息的总长最少为一个消息结构的大小
    if (totlen < (int)sizeof(clusterMsg)) totlen = sizeof(clusterMsg);
    // 分配空间
    buf = zcalloc(totlen);
    hdr = (clusterMsg*) buf;
    // 设置发送PING命令的时间
    if (link->node && type == CLUSTERMSG_TYPE_PING)
        link->node->ping_sent = mstime();
    // 构建消息的头部
    clusterBuildMessageHdr(hdr,type);
    int maxiterations = wanted*3;
    // 循环体,构建消息内容
    while(freshnodes > 0 && gossipcount < wanted && maxiterations--) {
        // 随机选择一个集群节点
        dictEntry *de = dictGetRandomKey(server.cluster->nodes);
        clusterNode *this = dictGetVal(de);
        clusterMsgDataGossip *gossip;
        int j;

        // 1. 跳过当前节点,不选myself节点,myself代表当前节点
        if (this == myself) continue;

        // 2. 偏爱选择处于下线状态或疑似下线状态的节点
        if (maxiterations > wanted*2 &&
            !(this->flags & (CLUSTER_NODE_PFAIL|CLUSTER_NODE_FAIL)))
            continue;

        // 以下节点不能作为被选中的节点:
        /*
            1. 处于握手状态的节点
            2. 带有NOADDR标识的节点
            3. 因为不处理任何槽而断开连接的节点
        */
        if (this->flags & (CLUSTER_NODE_HANDSHAKE|CLUSTER_NODE_NOADDR) ||
            (this->link == NULL && this->numslots == 0))
        {
            freshnodes--; /* Tecnically not correct, but saves CPU. */
            continue;
        }
    }
//(中间部分代码省略.............)
    // 发送消息
    clusterSendMessage(link,buf,totlen);
    zfree(buf);
}

4.2 如何保证消息传播的效率?

前面已经提到,集群的周期性函数 clusterCron() 执行周期是 100ms,为了保证传播效率,每 10 个周期,也就是 1s,每个节点都会随机选择 5 个其它节点,并从中选择一个最久没有通信的节点发送 ing 消息,

当然,这样还是没法保证效率,毕竟 5 个节点是随机选出来的,其中最久没有通信的节点不一定是全局“最久”。因此,对哪些长时间没有“被” 随机到的节点进行特殊照顾:每个周期(100ms)内扫描一次本地节点列表,如果发现节点最近一次接受 Pong 消息的时间大于 cluster_node_timeout/2,则立刻发送 Ping 消息,防止该节点信息太长时间未更新。

关键参数 cluster_node_timeout

从上面的分析可以看出,cluster_node_timeout 参数对消息发送的节点数量影响非常大。当带宽资源紧张时,可以适当调大这个参数,如从默认 15 秒改为 30 秒来降低带宽占用率。但是,过度调大 cluster_node_timeout 会影响消息交换的频率从而影响故障转移、槽信息更新、新节点发现的速度,因此需要根据业务容忍度和资源消耗进行平衡。同时整个集群消息总交换量也跟节点数成正比。

消息体与集群规模

每个 Ping 消息的数据量体现在消息头和消息体中,其中消息头空间占用相对固定。消息体会携带一定数量的其它节点信息用于信息交换,消息体携带数据量跟集群的节点数息息相关,更大的集群每次消息通信的成本也就更高,因此对于 Redis 集群来说并不是越大越好

5 故障转移

5.1 故障检测

单节点视角检测,检测(故障)信息传播,下线判决

单点视角检测

检测对方有没有下线

集群中的每个节点都会定期通过集群内部通信总线向集群中的其它节点发送 Ping 消息,用于检测对方是否在线。如果接收 Ping 消息的节点没有在规定的时间内向发送 Ping 消息的节点返回 Pong 消息,那么,发送 Ping 消息的节点就会将接收 Ping 消息的节点标注为疑似下线状态(Probable Fail,Pfail)。

检测信息传播

没回复我就判断他疑似下线,该疑似下线信息就会被告知其他节点,其他节点就会保存该节点的下线报告

集群中的各个节点会通过相互发送消息的方式来交换自己掌握的集群中各个节点的状态信息,如在线、疑似下线(Pfail)、下线(Fail)。例如,当一个主节点 A 通过消息得知主节点 B 认为主节点 C 疑似下线时,主节点 A 会更新自己保存的集群状态信息,将从 B 获得的下线报告保存起来。

基于检测信息作下线判决

超过半数的节点都保存了该节点的下线信息的时候,那么所有收到 Fail 消息的节点 就会把该节点标记为下线(Fail),并广播出去,

如果在一个集群里,超过半数的持有 Slot(槽)的主节点都将某个主节点 X 报告为疑似下线,那么,主节点 X 将被标记为下线(Fail),并广播出去,所有收到这条 Fail 消息的节点都会立即将主节点 X 标记为 Fail。至此,故障检测完成。

5.2 选举

感知到下线的从节点就会向集群广播,请求给自己投票

基于故障检测信息的传播,集群中所有正常节点都将感知到某个主节点下线的信息,当然也包括这个下线主节点的所有从节点。当从节点发现自己复制的主节点状态为已下线时,从节点就会向集群广播一条请求消息,请求所有收到这条消息并且具有投票权的主节点给自己投票。

拉票优先级 严格的讲,从节点在发现其主节点下线时,并非立即发起故障转移流程而进行“拉票”的,而是要等待一段时间,在未来的某个时间点才发起选举。这个时间点有如下计算表达式:

mstime() + 500ms + random()%500ms + rank*1000ms

其中,固定延时 500ms,是为了留出时间,使主节点下线的消息能传播到集群中其他节点,这样集群中的主节点才有可能投票;随机延时是为了避免两个从节点同时开始故障转移流程;rank 表示从节点的排名,排名是指当前从节点在下线主节点的所有从节点中的排名,排名主要是根据复制数据量来定,复制数据量越多,排名越靠前,因此,具有较多复制数据量的从节点可以更早发起故障转移流程,从而更可能成为新的主节点。

主节点投票 如果一个主节点具有投票权(负责处理 Slot 的主节点),并且这个主节点尚未投票给其它从节点,那么这个主节点将向请求投票的从节点返回一条回应消息,表示支持该从节点升主。

根据投票结果决策 在一个具有 N 个主节点投票的集群中,理论上每个参与拉票的从节点都可以收到一定数量的主节点投票,但是,在同一轮选举中,只可能有一个从节点收到的票数大于 N/2 + 1,也只有这个从节点可以升级为主节点,并代替已下线的主节点继续工作。

选举失败 跟生活中的选举一样,选举可能失败——没有一个候选从节点获得超过半数的主节点投票。遇到这种情况,集群将会进入下一轮选举,直到选出新的主节点为止。

选举算法 选举新主节点的算法是基于 Raft 算法的 Leader Election 方法来实现 Raft 算法。

5.3 故障转移

5.3 故障转移 选举完成后,获胜的从节点将发起故障转移(Failover),角色从 Slave 切换为 Master,并接管原来主节点的 Slots,详细过程如下。

身份切换 通过选举晋升的从节点会执行一系列的操作,清除曾经为从的信息,改头换面,成为新的主节点。

接管职权 新的主节点会通过轮询所有 Slot,撤销所有对已下线主节点的 Slot 指派,消除影响,并且将这些 Slot 全部指派给自己。

广而告之 升主了嘛,必须让圈子里面的都知道,新的主节点会向集群中广播一条 Pong 消息,将自己升主的信息通知到集群中所有节点。

履行义务 在其位谋其政,新的主节点开始处理自己所负责 Slot 对应的请求,至此,故障转移完成。

5.4 Redis Cluster 扩容

随着应用场景的升级,缓存可能需要扩容,扩容的方式有两种:垂直扩容(Scale Up)和水平扩容(Scale Out)。垂直扩容无需详述。实际应用场景中,采用水平扩容更多一些,根据是否增加主节点数量,水平扩容方式有两种。

比如,当前有一台物理机 A,构建了一个包含 3 个 Redis 实例的集群;扩容时,我们新增一台物理机 B,拉起一个 Redis 实例并加入物理机 A 的集群;B 上 Redis 实例对 A 上的一个主节点进行复制,然后进行主备倒换;如此,Redis 集群还是 3 个主节点,只不过变成了 A2-B1 的结构,将一部分请求压力分担到了新增的节点上,同时物理容量上限也会增加,主要步骤如下:

将新增节点加入集群; 将新增节点设置为某个主节点的从节点,进而对其进行复制; 进行主备倒换,将新增的节点调整为主。

方式 2:增加主节点数量。

不增加主节点数量的方式扩容比较简单,但是,从负载均衡的角度来看,并不是很好的选择。例如,如果主节点数量较少,那么单个节点所负责的 Slot 的数量必然较多,很容易出现大量 Key 的读写集中于少数节点的现象,而增加主节点的数量,可以更有效的分摊访问压力,充分利用资源。主要步骤如下:

将新增节点加入集群; 将集群中的部分 Slot 迁移至新增的节点。

6 其它分布式 Redis 方案

6.1 基于客户端的分片

如下图所示,客户端与 Redis 节点直连,为了提高可用性,每个主节点挂一个从节点,故障倒换可由“哨兵”系统实现(其它方案也可实现)。客户端对任何一个主节点的读写操作本质上就是单机模式下的读写操作;对于一个 Key-Value,其读写节点完全由客户端决定。比如,采用 Hash 算法:

但是,Hash 算法有很多缺陷:

不支持动态增加节点:当业务量增加,需要增加服务器节点后,上面的计算公式变为:hash(key)%(N+1),那么,对于同一个 Key-Value,增加节点前后,对应的 Redis 节点可能是完全不同的,可能导致大量之前存储的数据失效;为了解决这个问题,需要将所有数据重新计算 Hash 值,再写入 Redis 服务器。 不支持动态减少节点,原理同上。 鉴于 Hash 算法的不足,在实际应用中一般采用“一致性哈希”算法,在增删节点的时候,可以保证尽可能多的缓存数据不失效。关于一致性哈希算法,网上文章很多,读者可自行研读。

采用客户端分片具有逻辑简单,性能高的优点,但缺点也很明显,主要有业务逻辑与数据存储逻辑耦合,可运维性差;多业务各自使用 Redis,集群资源难以管理。

6.2 基于代理的分片

为了克服客户端分片业务逻辑与数据存储逻辑耦合的不足,可以通过 Proxy 将业务逻辑和存储逻辑隔离。客户端发送请求到一个代理,代理解析客户端的数据,将请求转发至正确的节点,然后将结果回复给客户端。这种架构还有一个优点就是可以把 Proxy 当成一个中间件,在这个中间件上可以做很多事情,比如可以把集群和主从的兼容性做到几乎一致,可以做无缝扩减容、安全策略等。

基于代理的分片已经有很多成熟的方案,如开源的 Codis,阿里云的 ApsaraDB for Redis/ApsaraCache,腾讯的 CRS 等。很多大企业也在采用 Proxy+Redis-Server 的架构。

Tags: 分布式
Share: X (Twitter) Facebook LinkedIn