Raft算法笔记之领导人选举(二)

Raft算法作者在设计算法过程中为了提升算法可理解性,决定将算法分解为三个模块,分别是领导人选举、日志复制和安全性证明。这种将一个大问题分解成小问题的思路还是不错的,所以我姑且将一篇大论文分成几篇小博文来单独分析,希望能得作者心法真传。本篇主要内容是领导人选举。

Raft 基础知识

状态

一个 Raft 集群包含若干个服务器节点;通常是 5 个,这允许整个系统容忍 2 个节点的失效。在任何时刻,每一个服务器节点都处于这三个状态之一:领导人、跟随者或者候选人。
在通常情况下,系统中只有一个领导人并且其他的节点全部都是跟随者。跟随者都是被动的:他们不会发送任何请求,只是简单的响应来自领导者或者候选人的请求。领导人处理所有的客户端请求(如果一个客户端和跟随者联系,那么跟随者会把请求重定向给领导人)。第三种状态,候选人,是用来描述的选举新领导人时使用。

任期

Raft 把时间分割成任意长度的任期,如下图。任期用连续的整数标记。每一段任期从一次选举开始,一个或者多个候选人尝试成为领导者。如果一个候选人赢得选举,然后他就在接下来的任期内充当领导人的职责。在某些情况下,一次选举过程会造成选票的瓜分。在这种情况下,这一任期会以没有领导人结束;一个新的任期(和一次新的选举)会很快重新开始。Raft 保证了在一个给定的任期内,最多只有一个领导者。

任期号

不同的服务器节点可能多次观察到任期之间的转换,但在某些情况下,一个节点也可能观察不到任何一次选举或者整个任期全程。任期在 Raft 算法中充当逻辑时钟的作用,这会允许服务器节点查明一些过期的信息比如陈旧的领导者。每一个节点存储一个当前任期号,这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号;如果一个服务器的当前任期号比其他人小,那么他会更新自己的编号到较大的编号值。如果一个候选人或者领导者发现自己的任期号过期了,那么他会立即恢复成跟随者状态。如果一个节点接收到一个包含过期的任期号的请求,那么他会直接拒绝这个请求。

RPCs

Raft 算法中服务器节点之间通信使用远程过程调用(RPCs),并且基本的一致性算法只需要两种类型的 RPCs。请求投票(RequestVote) RPCs 由候选人在选举期间发起,然后附加条目(AppendEntries)RPCs 由领导人发起,用来复制日志和提供一种心跳机制。为了在服务器之间传输快照增加了第三种 RPC。当服务器没有及时的收到 RPC 的响应时,会进行重试, 并且他们能够并行的发起 RPCs 来获得最佳的性能。

领导人选举

跟随者到候选人

Raft 使用一种心跳机制来触发领导人选举。当服务器程序启动时,他们都是跟随者身份。一个服务器节点要想继续保持着跟随者状态除非他从领导人或者候选者处接收到有效的 RPCs。领导者周期性的向所有跟随者发送心跳包(不包含日志项内容的附加日志项 RPCs)来维持自己的权威。如果一个跟随者在一段时间里没有接收到任何消息,也就是选举超时,然后他就会认为系统中没有可用的领导者然后开始进行选举以选出新的领导者。
要开始一次选举过程,跟随者先要增加自己的当前任期号并且转换到候选人状态。然后他会并行的向集群中的其他服务器节点发送请求投票的 RPCs 来给自己投票。候选人会继续保持着当前状态直到以下三件事情之一发生:(a) 他自己赢得了这次的选举,(b) 其他的服务器成为领导者,(c) 一段时间之后没有任何一个获胜的人。这些结果会分别的在下面的段落里进行讨论。

候选人的三种结局

赢得这次选举

当一个候选人从整个集群的大多数服务器节点获得了针对同一个任期号的选票,那么他就赢得了这次选举并成为领导人。每一个服务器最多会对一个任期号投出一张选票,按照先来先服务的原则(注意:5.4 节在投票上增加了一点额外的限制)。要求大多数选票的规则确保了最多只会有一个候选人赢得此次选举(图 3 中的选举安全性)。一旦候选人赢得选举,他就立即成为领导人。然后他会向其他的服务器发送心跳消息来建立自己的权威并且阻止新的领导人的产生。

其他服务器赢得选举

在等待投票的时候,候选人可能会从其他的服务器接收到声明它是领导人的附加日志项 RPC。如果这个领导人的任期号(包含在此次的 RPC中)不小于候选人当前的任期号,那么候选人会承认领导人合法并回到跟随者状态。 如果此次 RPC 中的任期号比自己小,那么候选人就会拒绝这次的 RPC 并且继续保持候选人状态。

选票瓜分,不赢不输

第三种可能的结果是候选人既没有赢得选举也没有输:如果有多个跟随者同时成为候选人,那么选票可能会被瓜分以至于没有候选人可以赢得大多数人的支持。当这种情况发生的时候,每一个候选人都会超时,然后通过增加当前任期号来开始一轮新的选举。然而,没有其他机制的话,选票可能会被无限的重复瓜分。

关于随机选举超时时间讨论

Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况,就算发生也能很快的解决。为了阻止选票起初就被瓜分,选举超时时间是从一个固定的区间(例如 150-300毫秒)随机选择。这样可以把服务器都分散开以至于在大多数情况下只有一个服务器会选举超时;然后他赢得选举并在其他服务器超时之前发送心跳包。同样的机制被用在选票瓜分的情况下。每一个候选人在开始一次选举的时候会重置一个随机的选举超时时间,然后在下次选举之前一直等待;这样减少了在新的选举中另外的选票瓜分的可能性。9.3 节展示了这种方案能够快速的选出一个领导人。我们针对算法进行了多次调整,但是每次调整之后都会有新的问题。最终我们认为随机重试的方法是更加明显和易于理解的。

-EOF-