| 编辑推荐: |
本文主要介绍了分布式共识算法之Raft算法的领导者选举、任期编号、日志复制日志复制异常及单节点变更内容。
本文来自csdn，由火龙果软件Linda编辑、推荐。 |
|
Raft算法是一切以领导者为主，在分布式系统中，就一系列值达成共识与日志的一致。是一种强领导者模型，领导者的性能决定了整个集群的性能。它是现今最常用的一种分布式共识算法。
领导者选举
Raft算法使用如下的三个角色，描述每个节点的状态。
1、领导者(Leader)：集群中的霸道总裁，其主要职能是处理写请求、同步日志给其余节点与发送心跳信息。领导者通过心跳信息，告诉其他节点我还活着，别进行领导者选举。在正常情况下，选举出来的领导者会一直是领导者。
2、跟随者(Follower)：默默的接受领导者节点的日志复制与心跳超时RPC。当跟随者在随机的超时时间内，没有收到领导者的心跳信息，那么就推举自己为候选者，发起领导者选举。
3、候选者(Candidate)：领导者选择过程中的一个中间状态。这个状态下的节点会向其他节点发送请求投票的RPC请求，当候选者在超时时间内收到超过过半数的选票，就确认自己是领导者，否则就等待随机的超时时间，发起下一轮领导选举。Raft算法通过这个随机的超时时间，可以高效的选举出领导者，一般一轮选举就可以选举出领导者。
为了描述方便，下文的图表分别使用这三个角色的首字母，代码这三种状态。
下文以一个三节点的集群，说明领导者选举的过程。
1、集群刚上线的时候，他们都处于Follower状态 
2、假设三个节点的随机超时时间分别是：1000ms、1100ms、1200ms，任期编号都为0。由于节点A的超时时间最短，所以它会率先推荐自己为候选者。
3、A节点自增任期编号，给自己投上一张选票，且发送自增后的任期编号1的请求投票RPC。当B节点收到A的投票请求，由于B节点当前的任期编号为0，故会更新任期编号为1，且将选票投给节点A。并且B承诺不在投票给任期编号小于等于1的投票请求（一个任期编号内只能投一张选票）。C节点也一样的。
4、如果节点A再领导者选举的超时时间内，赢得大多数节点的选票，那么就会成为本届任期内的领导者。开始接受客户端的写请求、发送日志复制与心跳RPC给其他节点。
任期编号
像议会的议员一样，每个议员都有一个任期，任期结束后需要重新发起选举。Raft算法也类似。Raft算法的任期编号是由一个自增的整数类型表示，随着选举的举行而改变，再一个领导者的任期内，任期编号不变。其包含如下的含义：
1、任期编号是由候选者产生的，每次领导者选举都会自增任期编号。
2、再一个领导者的任期内，任期编号的值都不变，直到某个跟随者获取心跳信息超时，发起领导者选举。
3、某个节点如果收到比其任期编号大的任期编号，则更新其任期编号到更大的值。
4、领导者或者候选者收到任期编号更大的其他节点的请求，则立即更新为跟随者
5、如果某个节点收到的请求的任期编号比其小，则拒绝请求。
6、领导者选择过程中，某个节点对于某个任期编号仅可以投一张选票。
7、如果候选者在领导者选举的超时时间内，未获取到超过半数的选票，则等待随机的超时时间，在发起选举。Raft算法通过2个超时时间，减小多个节点瓜分选票导致领导者选举失败的情况出现。实际上通过随机超时时间，很少出现选票被瓜分的情况。
8、领导者选举过程中，日志完整度高的节点拒绝投票给日志相对旧的节点，保证每次选举出领导者后，不丢已应用的日志，注意这里是已经提交的日志。
日志复制
Raft日志是由日志项组成，每个日志项包括指令、索引与任期编号。
指令：是客户端发送给领导者的一条条数据。
索引：也就是日志的唯一ID，它是一个单调递增的整数。
任期编号：创建这条日志项的领导者任期编号。
Raft的日志复制过程，其实是个优化了的二阶段提交算法，如下图所示： 
1、当领导者收到来自客户端的请求，添加索引与任期编号后，写入本地日志且通过日志复制RPC发送给跟随者。
2、跟随者收到来自领导者日志复制RPC请求，写入本地日志成功。
3、写入本地日志成功后，回复领导者日志写入成功。
4、当领导者收到超过半数的成功响应，会应用本地日志。
5、回复客户端，处理结果。
从上面的流程中可以看出，Raft领导者应用日志的时候，并没有发送跟随者也应用日志。其实领导者在心跳与日志复制RPC的请求中携带上了领导者已经应用的日志的领导者任期编号与索引。当跟随者收到心跳与领导者选举的请求时，会应用日志到相应的任期编号与索引。
日志复制异常
上面分析的都是正常的场景，但分布式系统往往有各种各样的问题，比如网络分区，节点挂机、领导者选举等，都会导致跟随者与领导者的日志不一致。如下图就是一总不一致的场景：
那么当跟随者收到领导者请求的任期编号与索引不一致时，就会查找领导者与跟随者的任期编号与索引相同的最大的索引值，领导者会强制跟随者覆盖不一致的日志。Raft通过这种强制跟随者覆盖与领导者不一致的日志，来实现各节点间日志的一致性。
单节点变更
假设我们要扩充一个3节点的集群到5节点，如果我们一次性扩充2个节点，那么在如下的网络分区的情况下，可能会出现2个领导者节点。
如果扩充的2个节点D与E，与C节点网络是通的，但是与A、B节点网络不通。那么就会形成如下的分区：
从图中可以看出，集群分成了2个集群A与B，C、D与E。其中C、D与E组成了集群的超过半数的节点。由于C、D与E会等待领导者节点A的心跳RPC超时，为此会触发领导者选举，从而选出C节点作为领导者。从而导致集群有2个领导者。
为此Raft作者提出了单节点变更，一次只添加或者删除一个节点，避免出现多个领导者的情况。其流程如下：
1、向集群中添加节点D，由于节点D是新加入的节点，还没有日志，为此领导者A会强制节点D复制自己的日志。
2、待日志复制完后，领导者A创建一条包含节点A、B、C与D的日志项，同步给其余节点并提交，以完成单节点变更。
3、按类似的步骤添加节点E。
| 
