Fork me on GitHub

Raft协议解读与实践

[TOC]

用Redis故障转移实践理解raft协议

本文分为三个部分

第一部分,尽可能以简明的语言阐述raft协议。

第二部分,通过kill掉Redis集群的主节点,以观察集群overfail的全过程,通过实践进一步理解raft协议。

第三部分,探讨raft论文的细节,针对原论文提出一些问题,并自问自答。

最后附上原论文链接,以及有帮助的参考资料。

一、raft解决了什么问题?怎么解决的?

Raft是分布式一致性协议,它是对分布式系统达成共识的一种解决方案,那么什么是分布式系统的共识问题呢?

拜占庭将军问题

这是Lamport(图灵奖得主)在其论文中提出的一个假设故事:

几个拜占庭将军准备攻城。将军们只有两种行动策略:进攻或撤离。将军们需要达成行动共识,因为只有绝大部分将军同时进攻/撤退,行动才能成功,将军可以彼此通信(但没法聚在一起开会)。棘手的是,这其中有不定数量的叛徒将军,叛徒将军将给出完全错误的信息阻碍达成共识。因此我们需要一种策略,使得将军们在叛徒们干扰的情况下,仍能达成共识。

如果将军根据最简单的策略:收到的多数投票行动,将会导致达成共识失败。假设有9位将军投票,其中1名叛徒。一半将军投票进攻,另一半投票撤退,这时候叛徒给4名投进攻的将军投票进攻,而给4名投撤退的将军投票撤退。这样一来在4名投进攻的将军看来,投票结果是5人投进攻,从而发起进攻;而在4名投撤退的将军看来则是5人投撤退。军队达成错误的共识,导致行动失败。

这个假设故事,映射到现实计算机,将军即分布式节点,每个节点可以彼此通信,但无法聚在一起“开会”,并且某节点或者某条通信网路可能出现错误(fault-tolerant),在这种情况下,分布式系统如何达成一致(consensus)?

Raft协议提供的解决方案简单来说是这样的:

Raft 通过首先从节点里选举一个leader,让它有最高权力,比如决定进攻还是撤退,来实现分布式系统的一致性,从节点的唯一任务就是备份主节点的数据。如果leader 宕机或失联,就选举出一个新的leader代替它,参加选举的节点叫candidate。之后如果老的leader重新上线,它会退化成普通节点,接受新leader的命令。

这里我们可知,在raft协议里每个节点有三个状态:leader、follower 或者 candidate 。

那么怎么进行选举呢?这不又回到了拜占庭将军问题吗,没错,这就是raft协议的重点之一,领导选举。下面简述选举过程:

Raft 使用一种心跳机制来触发 leader 选举,节点之间会用心跳保持联系。如果一个 follower 在一段选举超时时间内没有接收到任何消息,它会开始进行选举。首先,follower 先增加自己的当前任期号并且转换到 candidate 状态。然后投票给自己,并且让其他服务器节点投票给它。之后会有三种情况

第一种情况:当一个 candidate 获得集群中过半服务器节点针对同一个任期的投票,它就赢得了这次选举并成为 leader 。要求获得过半投票的规则确保了最多只有一个 candidate 赢得此次选举。

第二种情况:candidate 可能会收到另一个声称自己是 leader 的服务器节点发来的 AppendEntries RPC 。如果这个 leader 的任期号大于 candidate 当前的任期号,那么 candidate 会承认该 leader 的合法地位并回到 follower 状态。 如果 RPC 中的任期号比自己的小,那么 candidate 就会拒绝这次的 RPC 并且继续保持 candidate 状态。

第三种情况: candidate 既没有赢得选举也没有输:如果有多个 follower 同时成为 candidate ,那么选票可能会被瓜分以至于没有 candidate 赢得过半的投票。当这种情况发生时,每一个候选人都会超时,然后通过增加当前任期号来开始一轮新的选举。然而,如果没有其他机制的话,该情况可能会无限重复。我将在第三部分细节探讨raft提供了哪些解决方案避免无限重复选举发生。

这里提到了任期(term)的概念,任期在 Raft 算法中充当逻辑时钟的作用,每一个服务器节点存储一个当前任期号,该编号随着时间单调递增。

二、实践Redis的故障转移

Redis的分布式设计大部分都参考了Raft协议。网上虽然也有Raft协议的动画演示,但我认为以观察Redis的故障转移更能深刻理解Raft协议,毕竟Raft只是学术论文,Redis的分布式设计才是真正落地了的解决方案。

接下来就通过一次模拟Redis故障转移去观察raft协议的整个过程。

建立节点

首先需要租一个云服务器,在云服务器上分别设立Redis主节点、2个从节点和3个哨兵节点 。

哨兵 主节点 从节点
26379 6379 6380
26380 6381
26381

建立节点的过程因为和本文主题无关就不帖了。(如果读者有兴趣实践,一个小技巧是:只用租一台服务器,每个节点不同端口,就不用每个节点都租一台服务器了,而且方便查看日志。)

杀掉主节点

开始进入正题,首先干掉主节点,手动制造故障。先.查一下master的进程id ps -ef | grep Redis-server 进程id是22284,然后直接杀掉进程 kill -9 22284

哨兵和各节点之间用用流言协议来监控节点情况,哨兵会持续做如下3件事。

(1)每隔10s确认主从关系。

(2)每隔两秒,哨兵都会通过master节点内部的channel来交换信息(基于发布订阅)。

(3) 每隔一秒每个哨兵对其他的Redis节点(master,slave,哨兵)执行ping操作。

所以当我们kill掉主节点后,哨兵很快就会发现主节点挂掉了。

主观下线和客观下线

什么是主观下线和 客观下线呢?

  • sdown 是主观宕机,就一个哨兵如果自己觉得一个 master 宕机了,那么就是主观宕机
  • odown 是客观宕机,如果 quorum 数量的哨兵都觉得一个 master 宕机了,那么就是客观宕机

sdown 达成的条件很简单,如果一个哨兵 ping 一个 master,超过了 is-master-down-after-milliseconds 指定的毫秒数之后,就主观认为 master 宕机了;如果一个哨兵在指定时间内,收到了 quorum 数量的其它哨兵也认为那个 master 是 sdown 的,那么就认为是 odown 了。

什么是法定人数(quorum)?法定人数即哨兵决定表决的同意比,可以在sentinel的conf里配置,如下,后面的2就是法定人数

1
sentinel monitor mymaster 127.0.0.1 6379 2

法定人数需要比一般的哨兵数还大,如果小于,法定人数为一半以上的哨兵数。

回到实践中,让我们来查看哨兵26379的日志 cat 哨兵 26379.conf | grep -v "#" | grep -v "^$",会观察到几条关键日志

首先是哨兵的主观下线(sdown)日志,哨兵26379观察到了主节点6379失联。

22522:X 21 Aug 16:40:38.162 # +sdown master mymaster 127.0.0.1 6379

哨兵们进行通信后,出现了客观下线(odown)日志,表面超过法定人数的哨兵都认为主节点挂了。

1002:X 21 Aug 19:20:43.517 # +odown master mymaster 127.0.0.1 6379 #quorum 3/2

哨兵选举

这个哨兵尝试成为代表哨兵/领导者,为什么要选举呢?因为需要选举出一个哨兵去做故障转移。

哨兵选举的过程如下 :

  1. 每个做主观下线的哨兵节点向其他哨兵节点发送命令,要求将它设置为领导者。
  2. 收到命令的哨兵节点如果没有同意通过其他哨兵节点发送命令,那么将同意该请求,否则拒绝。
  3. 如果该哨兵节点发现自己的票数已经超过哨兵集合半数且超过quorum,那么它将成为领导者。
  4. 如果此过程有多个哨兵节点成为了领导者,那么将等待一段时间重新进行选举。

回到实践中,让我们来看看竞选者哨兵的日志,try-failover表示哨兵们确认master下线,要进行故障转移了。其中一个哨兵去竞选,接着它收到了两个哨兵的投票,成功成为领导者。

1
2
3
4
998:X 21 Aug 19:20:42.514 # +try-failover master mymaster 127.0.0.1 6379
998:X 21 Aug 19:20:42.515 # +vote-for-leader d192c1ac24df230470e06666d30414c1298e7479 1
998:X 21 Aug 19:20:42.517 # (哨兵一)450f7f7ea410c39d41e974affc83cda0113994f7 voted for d192c1ac24df230470e06666d30414c1298e7479 1
998:X 21 Aug 19:20:42.517 # (哨兵二)4cc8249091cded4f2eedeacc91fd42881c3a8f42 voted for d192c1ac24df230470e06666d30414c1298e7479 1

主节点的故障转移

哨兵的选举基本是根据raft协议的,代表哨兵只需要集群达成共识就行,其实哪个哨兵都可以去做。但是新主节点的选举是有条件的,会选举出一个最有“能力”的节点。、

首先如果一个 slave 跟 master 断开连接的时间已经超过了 down-after-milliseconds 的 10 倍,外加 master 宕机的时长,那么 slave 就被认为不适合选举为 master。在剩余的 slave里排序:

  1. 按照 slave 优先级进行排序,slave priority 越低,优先级就越高。
  2. 如果 slave priority 相同,那么看 replica offset,哪个 slave 复制了越多的数据,offset 越靠后,优先级就越高。
  3. 如果上面两个条件都相同,那么选择一个 run id 比较小的那个 slave。

回到实践中,从日志上可以看到,哨兵成为领导者后开始干活,它选择了6381节点作为新的主节点,进行故障转移

1
2
3
4
998:X 21 Aug 19:20:42.573 # +elected-leader master mymaster 127.0.0.1 6379
998:X 21 Aug 19:20:42.573 # +failover-state-select-slave master mymaster 127.0.0.1 6379
998:X 21 Aug 19:20:42.673 # +selected-slave slave 127.0.0.1:6381 127.0.0.1 6381 @ mymaster 127.0.0.1 6379
998:X 21 Aug 19:20:42.673 * +failover-state-send-slaveof-noone slave 127.0.0.1:6381 127.0.0.1 6381 @ mymaster 127.0.0.1 6379

slave 配置的自动纠正

哨兵会负责自动纠正 slave 的一些配置,比如 slave 如果要成为潜在的 master 候选人,哨兵会确保 slave 复制现有 master 的数据;如果 slave 连接到了一个错误的 master 上,比如故障转移之后,那么哨兵会确保它们连接到正确的 master 上。

slave上升为master日志中可以发现,这一条配置重写的日志

1
989:M 21 Aug 19:20:42.729 # CONFIG REWRITE executed with success.

##

最后的一条日志标志,master切换完成。

1002:X 21 Aug 19:20:43.759 # +switch-master mymaster 127.0.0.1 6379 127.0.0.1 6381

三、细节探讨

Redis的分布式设计和Raft协议有哪些不同?

虽然本文是用Redis故障转移实践理解raft协议,redis并不是完全基于raft实现的,两者还是有区别的。

两者的一致性级别要求不同:Raft中采用的是QUORUM, 即确保至少大部分节点都接收到写操作之后才会返回结果给Client, 而Redis默认采用的实际上是ANY/ONE, 即只要Master节点写入成功后,就立刻返回给Client,然后该写入命令被异步的发送给所有的slave节点。

Raft怎么避免多个condidate竞争导致的无限重复选举?

当follower判定当前的leader节点故障之后,follower会首先随机休眠一段时间,比如我们设置所有的节点休眠时间为150-300ms之间,即rand(150, 300),每个节点休眠结束后,便向其他的节点发起拉票。比如A节点先唤醒,唤醒后向B、C节点发起拉票。每个Term期间,每个节点只能至多投一票给别人。

参考资料

拜占庭将军问题:https://www.youtube.com/watch?v=e9KVmyI1eCg&t=303s

Redis与raft相同与不同之处:https://zhuanlan.zhihu.com/p/112651338