江苏龙网

  1. 主页 > 生活百科 > >

Raft一致性算法( 六 )

算法


不同的服务器节点可能多次观察到任期之间的转换，但在某些情况下，一个节点也可能观察不到任何一次选举或者整个任期全程 。任期在 Raft 算法中充当逻辑时钟的作用，任期使得服务器可以检测一些过期的信息：比如过期的领导人 。每个节点存储一个当前任期号，这一编号在整个时期内单调递增 。每当服务器之间通信的时候都会交换当前任期号；如果一个服务器的当前任期号比其他人小，那么他会更新自己的任期号到较大的任期号值 。如果一个候选人或者领导人发现自己的任期号过期了，那么他会立即恢复成跟随者状态 。如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求 。
Raft 算法中服务器节点之间通信使用远程过程调用（RPCs），并且基本的一致性算法只需要两种类型的 RPCs 。请求投票（RequestVote） RPCs 由候选人在选举期间发起（章节 5.2），然后附加条目（AppendEntries）RPCs 由领导人发起，用来复制日志和提供一种心跳机制（章节 5.3） 。第 7 节为了在服务器之间传输快照增加了第三种 RPC 。当服务器没有及时的收到 RPC 的响应时，会进行重试，并且他们能够并行的发起 RPCs 来获得最佳的性能 。
5.2 领导人选举
Raft 使用一种心跳机制来触发领导人选举 。当服务器程序启动时，他们都是跟随者身份 。一个服务器节点继续保持着跟随者状态只要他从领导人或者候选人处接收到有效的 RPCs 。领导人周期性的向所有跟随者发送心跳包（即不包含日志项内容的附加条目（AppendEntries） RPCs）来维持自己的权威 。如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可用的领导人,并且发起选举以选出新的领导人 。
要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态 。然后他会并行地向集群中的其他服务器节点发送请求投票的 RPCs 来给自己投票 。候选人会继续保持着当前状态直到以下三件事情之一发生：(a) 他自己赢得了这次的选举，(b) 其他的服务器成为领导人，© 一段时间之后没有任何一个获胜的人 。这些结果会分别的在下面的段落里进行讨论 。
当一个候选人从整个集群的大多数服务器节点获得了针对同一个任期号的选票，那么他就赢得了这次选举并成为领导人 。每一个服务器最多会对一个任期号投出一张选票，按照先来先服务的原则（注意：5.4 节在投票上增加了一点额外的限制） 。要求大多数选票的规则确保了最多只会有一个候选人赢得此次选举（图 3 中的选举安全性） 。一旦候选人赢得选举，他就立即成为领导人 。然后他会向其他的服务器发送心跳消息来建立自己的权威并且阻止发起新的选举 。
在等待投票的时候，候选人可能会从其他的服务器接收到声明它是领导人的附加条目（AppendEntries）RPC 。如果这个领导人的任期号（包含在此次的 RPC中）不小于候选人当前的任期号，那么候选人会承认领导人合法并回到跟随者状态 。如果此次 RPC 中的任期号比自己小，那么候选人就会拒绝这次的 RPC 并且继续保持候选人状态 。
第三种可能的结果是候选人既没有赢得选举也没有输：如果有多个跟随者同时成为候选人，那么选票可能会被瓜分以至于没有候选人可以赢得大多数人的支持 。当这种情况发生的时候，每一个候选人都会超时，然后通过增加当前任期号来开始一轮新的选举 。然而，没有其他机制的话，选票可能会被无限的重复瓜分 。
Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况，就算发生也能很快的解决 。为了阻止选票起初就被瓜分，选举超时时间是从一个固定的区间（例如 150-300 毫秒）随机选择 。这样可以把服务器都分散开以至于在大多数情况下只有一个服务器会选举超时；然后他赢得选举并在其他服务器超时之前发送心跳包 。同样的机制被用在选票瓜分的情况下 。每一个候选人在开始一次选举的时候会重置一个随机的选举超时时间，然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性 。9.3 节展示了这种方案能够快速的选出一个领导人 。
领导人选举这个例子，体现了可理解性原则是如何指导我们进行方案设计的 。起初我们计划使用一种排名系统：每一个候选人都被赋予一个唯一的排名，供候选人之间竞争时进行选择 。如果一个候选人发现另一个候选人拥有更高的排名，那么他就会回到跟随者状态，这样高排名的候选人能够更加容易的赢得下一次选举 。但是我们发现这种方法在可用性方面会有一点问题（如果高排名的服务器宕机了，那么低排名的服务器可能会超时并再次进入候选人状态 。而且如果这个行为发生得足够快，则可能会导致整个选举过程都被重置掉） 。我们针对算法进行了多次调整，但是每次调整之后都会有新的问题 。最终我们认为随机重试的方法是更加明显和易于理解的 。


推荐阅读


上一篇：选Redis做MQ的人，是脑子里缺根弦儿吗？

下一篇：Python面向对象详解