Leader选举

节点启动时，默认处于Follower的状态，所以开始时所有节点均是Follower，那么什么时候触发选主呢？Raft用“心跳”的方式来保持主从节点的联系，如果长时间没有收到主节点的心跳，则开始选主。这里会涉及到两个时间：

• 心跳间隔，主节点隔多长时间发送心跳信息
• 等待时间(election timeout)，如果超过这个时间仍然没有收到心跳，则认为主节点宕机。一般每个节点各自在150 ～ 300ms间随机取值。

当一个节点在等待时间内没有收到主节点的心跳信息，它首先将自己保存的term增加1并进入Candidate状态。此时它会先投票给自己，然后并行发送RequestVote消息给其它所有节点，请求这些节点投票给自己。然后等待直到以下3种情形之一发生：

• 赢得了多数的选票，成功选举为Leader；Candidate节点需要收到集群中与自己term相同的所有节点中大于一半的票数（当然如果节点term比自己大，是不会理睬自己的选举消息的）。节点投票时会采取先到先得的原则，对于某个term，最多投出一票（后面还会再对投票加一些限制）。这样能保证某个term中，最多只会产生一个leader。当一个Candidate变成主节点后，它会向其它所有节点发送心跳信息，这样其它的Candidate也会变成Follower。

• 收到了Leader的消息，表示有其它服务器已经抢先当选了Leader；在等待投票的过程中，Candidate收到其它主节点的心跳信息（只有主节点才会向其它节点发心跳），且信息中包含的term大于等于自己的term，则当前节点放弃竞选，进入Follower状态。当然，如前所说，如果心跳中的term小于自己，则不予理会。

• 没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。一般发生在多个Follower同时触发选举，而各节点的投票被分散了，导致没有Candidate能得到多数票。超过投票的等待时间后，节点触发新一轮选举。理论上，选举有可能永远平票，Raft中由于各个节点的超时时间是随机的，实际上平票不太会永远持续下去。

Leader后，Leader通过定期向所有Followers发送心跳信息维持其统治。若Follower一段时间未收到Leader的心跳则认为Leader可能已经挂了，再次发起Leader选举过程。Raft保证选举出的Leader上一定具有最新的已提交的日志。

成员变更

成员变更是在集群运行过程中副本发生变化，如增加/减少副本数、节点替换等。成员变更也是一个分布式一致性问题，既所有服务器对新成员达成一致。但是成员变更又有其特殊性，因为在成员变更的一致性达成的过程中，参与投票的进程会发生变化。

如果将成员变更当成一般的一致性问题，直接向Leader发送成员变更请求，Leader复制成员变更日志，达成多数派之后提交，各服务器提交成员变更日志后从旧成员配置（Cold）切换到新成员配置（Cnew）。

双多数派问题

一种方法是先停止所有节点，修改配置增加新的节点，再重启所有节点，但是这样服务起停时就会中断服务，同时也可能增加人为操作失误的风险。另一种方法配置好新的节点直接加入集群，这样也会出问题：在某个时刻使用不同配置的两部分节点可能会各自选出一个主节点。因为各个服务器提交成员变更日志的时刻可能不同，造成各个服务器从旧成员配置（Cold）切换到新成员配置（Cnew）的时刻不同。成员变更不能影响服务的可用性，但是成员变更过程的某一时刻，可能出现在Cold和Cnew中同时存在两个不相交的多数派，进而可能选出两个Leader，形成不同的决议，破坏安全性。

如下图：

图中绿色为旧的配置，蓝色为新的配置，在中间的某个时刻，Server 1/2/3可能会选出一个主节点，而Server 3/4/5可能会选出另一个，从而破坏了一致性。

两阶段的成员变更

由于成员变更的这一特殊性，成员变更不能当成一般的一致性问题去解决。为了解决这一问题，Raft提出了两阶段的成员变更方法。集群先从旧成员配置Cold切换到一个过渡成员配置，称为共同一致（joint consensus），共同一致是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew，一旦共同一致Cold U Cnew被提交，系统再切换到新成员配置Cnew。

Raft两阶段成员变更过程如下：

1. Leader收到成员变更请求从Cold切成Cnew；
2. Leader在本地生成一个新的log entry，其内容是Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该log entry复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认；
3. Follower收到Cold∪Cnew的log entry后更新本地日志，并且此时就以该配置作为自己的成员配置；
4. 如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，Leader就提交这条log entry；
5. 接下来Leader生成一条新的log entry，其内容是新成员配置Cnew，同样将该log entry写入本地日志，同时复制到Follower上；
6. Follower收到新成员配置Cnew后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在Cnew这个成员配置中会自动退出；
7. Leader收到Cnew的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功。

异常分析：

• 如果Leader的Cold U Cnew尚未推送到Follower，Leader就挂了，此后选出的新Leader并不包含这条日志，此时新Leader依然使用Cold作为自己的成员配置。
• 如果Leader的Cold U Cnew推送到大部分的Follower后就挂了，此后选出的新Leader可能是Cold也可能是Cnew中的某个Follower。
• 如果Leader在推送Cnew配置的过程中挂了，那么同样，新选出来的Leader可能是Cold也可能是Cnew中的某一个，此后客户端继续执行一次改变配置的命令即可。
• 如果大多数的Follower确认了Cnew这个消息后，那么接下来即使Leader挂了，新选出来的Leader肯定位于Cnew中。

两阶段成员变更比较通用且容易理解，但是实现比较复杂，同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性，因此我们期望增强成员变更的限制，以简化操作流程。两阶段成员变更，之所以分为两个阶段，是因为对Cold与Cnew的关系没有做任何假设，为了避免Cold和Cnew各自形成不相交的多数派选出两个Leader，才引入了两阶段方案。

如果增强成员变更的限制，假设Cold与Cnew任意的多数派交集不为空，这两个成员配置就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。那么如何限制Cold与Cnew，使之任意的多数派交集不为空呢？方法就是每次成员变更只允许增加或删除一个成员。可从数学上严格证明，只要每次只允许增加或删除一个成员，Cold与Cnew不可能形成两个不相交的多数派。

一阶段成员变更：

• 成员变更限制每次只能增加或删除一个成员（如果要变更多个成员，连续变更多次）。
• 成员变更由Leader发起，Cnew得到多数派确认后，返回客户端成员变更成功。
• 一次成员变更成功前不允许开始下一次成员变更，因此新任Leader在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。
• Leader只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步。