Raft的PreVote实现机制

1. 背景

在Basic Raft算法中，当一个Follower与其他节点网络隔离，如下图所示：

Follower_2在electionTimeout没收到心跳之后,会发起选举，并转为Candidate。每次发起选举时，会把Term加一。由于网络隔离，它既不会被选成Leader，也不会收到Leader的消息，而是会一直不断地发起选举。Term会不断增大。

一段时间之后，这个节点的Term会非常大。在网络恢复之后，这个节点会把它的Term传播到集群的其他节点，导致其他节点更新自己的term，变为Follower。然后触发重新选主，但这个旧的Follower_2节点由于其日志不是最新，并不会成为Leader。整个集群被这个网络隔离过的旧节点扰乱，显然需要避免的。

2. Provote算法

Raft作者博士论文《CONSENSUS: BRIDGING THEORY AND PRACTICE》的第9.6节 "Preventing disruptions when a server rejoins the cluster"提到了PreVote算法的大概实现思路。

在PreVote算法中，Candidate首先要确认自己能赢得集群中大多数节点的投票，这样才会把自己的term增加，然后发起真正的投票。其他投票节点同意发起选举的条件是（同时满足下面两个条件）：

没有收到有效领导的心跳，至少有一次选举超时。

Candidate的日志足够新（Term更大，或者Term相同raft index更大）。

PreVote算法解决了网络分区节点在重新加入时，会中断集群的问题。在PreVote算法中，网络分区节点由于无法获得大部分节点的许可，因此无法增加其Term。然后当它重新加入集群时，它仍然无法递增其Term，因为其他服务器将一直收到来自Leader节点的定期心跳信息。一旦该服务器从领导者接收到心跳，它将返回到Follower状态，Term和Leader一致。

3. Etcd的Provote实现流程

Etcd针对发起PreVote的节点增加了一个角色状态：StatePreCandidate。

3.1 节点发起PreVote流程

1.首先节点超时，会进入Step函数，然后触发选举流程，如果配置了prevote，则会进入预选举流程，代码片段如下所示：

2.节点调用r.campaign(campaignPreElection)，发送投票请求。函数流程如下所示：

3.当发起prevote节点收到响应消息以后，会进入stepCandidate函数，stepCandidate函数是PreCandidate状态和Candidate状态共用的。当收到其他节点对投票的响应时，重新计算自己的票数。如果达到大多数，PreCandidate会变为Candidate状态，发起真正的选举。代码片段如下所示：

3.2 节点响应PreVote流程

节点收到Prevote请求，都会进入Step函数，然后做相应的响应处理：1.如果当前节点未选举超时，并且存在Leader，则不响应投票请求2.如果满足投票要求，并且日志最新，则投赞成票，否则投反对票。

4. 总结

Prevote是一个典型的2PC协议，第一阶段先征求其他节点是否同意选举，如果同意选举则发起真正的选举操作，否则降为Follower角色。这样就避免了网络分区节点重新加入集群，触发不必要的选举操作。