5.2 Leader 选举

Raft 使用一种心跳机制来触发 Leader 的选举。当服务器启动时，它们会初始化为 Follower。一台服务器会一直保持 Follower 的状态，只要它们能够收到来自 Leader 或者 Candidate 的有效 RPC。Leader 会向所有 Follower 周期性发送心跳（不带有任何日志条目的 AppendEntries RPC）来保证它们的 Leader 地位。如果一个 Follower 在一个周期内没有收到心跳信息，就叫做选举超时，然后它就会认为没有可用的 Leader，并且开始一次选举以选出一个新的 Leader。

为了开始选举，一个 Follower 会自增它的当前任期并且转换状态为 Candidate。然后，它会给自己投票并且给集群中的其他服务器发送 RequestVote RPC。一个 Candidate 会一直处于该状态，直到下列三种情形之一发生：

• 它赢得了选举；
• 另一台服务器赢得了选举；
• 一段时间后没有任何一台服务器赢得了选举。

这些情形会在下面的章节中分别讨论。

如果一个 Candidate 在一个任期内收到了来自集群中大多数服务器的投票，就会赢得选举。在一个任期内，一台服务器最多能给一个 Candidate 投票，按照先到先服务原则（注意：在5.4节针对投票添加了一个额外的限制）。大多数原则使得在一个任期内最多有一个 Candidate 能赢得选举（表-3 中提到的选举安全原则）。一旦有一个 Candidate 赢得了选举，它就会成为 Leader。然后，它会向其他服务器发送心跳信息来建立自己的 Leader 地位，并且组织新的选举。

当一个 Candidate 等待别人的选票时，它有可能会收到来自其他服务器发来的声明其为 Leader 的 AppendEntries RPC。如果这个Leader 的任期（包含在它的 RPC 中）比当前 Candidate 的当前任期要大，则 Candidate 认为该 Leader 合法，并且转换自己的状态为 Follower。如果在这个 RPC 中的任期小于 Candidate 的当前任期，则候选人会拒绝此次 RPC， 继续保持 Candidate 状态。

第三种情形是，一个 Candidate 既没有赢得选举，也没有输掉选举：如果许多 Follower 在同一时刻都成为了 Candidate，选票会被分散，可能没有 Candidate 能获得大多数的选票。当这种情形发生时，每一个 Candidate 都将会超时，并且通过自增任期号和发起另一轮 RequestVote RPC 来开始新的选举。然而，如果没有其它手段来分配选票的话，这种情形可能会无限的重复下去。

Raft 使用随机的选举超时时间来确保第三种情形很少发生，并且能够快速解决。为了防止在一开始是选票就被瓜分，选举超时时间是在一个固定的间隔内随机选出来的（例如150-300ms）。这种机制使得各个服务器能够分散开来，在大多数情况下只有一个服务器会率先超时；它会在其它服务器超时之前赢得选举，并且向其它服务器发送心跳信息。同样的机制被用于选票被瓜分的情况。每一个 Candidate 在开始一次选举的时候会重置一个随机的选举超时时间，等待直到超时后，再进行下一次选举。这能够减小在新的选举中一开始选票就被瓜分的可能性。9.3节展示了这种方法能够快速的选出一个 Leader。

选举，是一个引导我们设计替代算法具备可理解性的例子。最开始时，我们计划使用一种排名系统：给每一个 Candidate 分配一个唯一的排名，用于在竞争的 Candidate 之中选出 Leader。如果一个 Candidate 发现了另一个比它排名高的 Candidate，那么它会回到 Follower 的状态，这样排名高的 Candidate 会很容易地赢得选举。但是我们发现这种方法在可用性方面有一点问题（一个低排名的服务器在高排名的服务器宕机后，需要等待超时才能再次成为 Candidate，但是如果它这么做的太快，它能重置选举 Leader 的过程）。我们对这个算法做了多次调整，但是每次调整后都会出现一些新的问题。最终我们认为随机重试的方法是更明确的，并且更易于理解。