本文转载于 SegmentFault 社区
作者：gosh
一、概述
最近终于有时间去看看 raft 算法的论文，raft 作为一个易于理解和实现的一致性算法
（毕竟我这样的菜🐶都能看懂）
，已经应用到很多系统的构建上
（分布式数据库 TIDB，RocketMq 的 Dledger 等）
，是非常值得去深入理解和研究的。本文主要是学习 raft 论文的总结以及自己的一些想法。如果大家对论文已经足够了解。那就不用继续往下看了。光看看文末的个人想法
（愚见）
，欢迎来和我探讨！
二、Raft 算法概述
raft 算法之所以容易理解，其一是他将一致性问题划分成几个子问题，这几个子问题都是独立、可理解和解释的。从传统的思维来讲，对于一个复杂的系统或者工程，都是大化小，分解实现，然后去尝试融合解决整体逻辑。包括
CS 系统
的设计也是如此。
一致性算法的目标
1. 安全性：在非拜占庭错误情况下，包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。
2. 可用性：只要集群中大多数节点处于
runing
，并且不分区，和客户端能通信，那么我们需要保证这个集群可用。
3. 对于数据同步，小部分慢节点的不会影响系统性能。因为对于日志复制，我们如果等待所有节点响应，那么系统的性能会存在短板效应。
说白了，就是如果一个集群中，如果大多数节点可用
（网络、服务）
，那么通过 raft 算法，我们就能保证整个系统可用
（可处理请求，数据一致性）
。后面我们主要研究的就是 raft 是如何做到的。
首先我们要知道，Raft 算法将其问题划分为
对于一个集群只有一个
leader
（领导）
，那么我们就很容易理解。只要领导操作同步到对应的
followers
（跟随者）
，数据必然一致。当
leader 宕机
，需要进行领导选举。
日志复制其实就是同步操作数据的过程。leader 将操作日志同步到其他节点。
安全性：如何安全的同步，在不同的情况，我们都能保证一致性，这也就是安全性需要考虑的问题。
其实就是如此，raft 首先假设了领导选举。然后实现了日志复制，最后在安全问题上解决上面的漏洞问题。
三、领导选举
目的：当集群初始化或者领导 gg 的时候选出一个新的领导。毕竟一个集群不能没有领导，如果没有，那么这个集群就不可用了。
触发机制：通过心跳。
这幅图展现了跟随者、候选者和领导者之间的状态转换关系，下面主要介绍他们的转换流程。
跟随者
如果他能持续从领导者或者候选者接收到有效的
RPCs
，那么他的状态就不会变。一直保持跟随者身份。但如果没有持续接受，也就是在一段时间没收到有效的
RPCs
，那就选举超时，他会变成候选者。
候选者
要变为候选者，也就意味着他要开启一轮新的选举。那么跟随者会增加自己的任期号，转为候选者。
成为候选者后，自己会并行发送一个为自己投票的
RPCs
请求 给其他服务器。
成为候选者的整个过程也会保持当前状态，知道满足下面三个条件
-
-
-
一段时间没有任何人获胜。说明选票被瓜分，重复执行。
这里需要注意的点：
1. 对于同一任期号，每个节点一会投一张票。比如服务器 A 作为候选者生成了编号为 5 的任期号，那么如果接收到其他节点的编号为 5 的任期号的投票请求，他会忽略。这个过程遵循的是先来先投的原则。
2. 候选者接收到领导者的声明。会判声明中 RPC 的任期号，如果比自己的还小，那么他还会保持候选者身份，否则转为跟随者。
3. 对于上面第三点，重复执行，Raft 采用随机超时选举时间进行了优化。降低选票瓜分的可能性。
四、Raft 日志复制
直接去理解日志复制，是很容易的，客户端的一条指令到达，领导者会为这条指令创建一条日志条目，并且并行发送到其他跟随者。当日志被安全复制
（所谓安全复制后面会有）
，领导会将日志应用到状态机
（比如如果是 mysql 的 insert，那么就是执行 insert 操作）
，然后响应客户端。
如上图，每条日志都会有对应的任期号，和指令。
每个日志都会有对应的索引。
1. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
2. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。
第一点：一个任期只有一个领导人，并且领导人在一个任期中对于同一索引日志，只会创建一条日志，是不会改变的，是确定的。这就保证第一点成立。
第二点：要想全部相同，就要保证跟随者得到的日志是领导者发送的顺序附加上去的。领导者在发送新的日志时，会附加这条日志之前日志的索引和任期号。如果跟随者发现数据匹配，才会附加上去，否则拒绝。就是一个个状态保证了日志的匹配特性。
对于日志不一致的现象，raft 是通过跟随者强制复制领导者的日志来保证的。
如上图，对于 a-f，最终都会和
leader
同步，也就是说，d 会丢弃日志。f的对应日志也会被丢弃和覆盖。
其实就是通过日志覆盖解决。但是对于日志覆盖，我们就会想到一个问题，会不会覆盖已经提交的日志
（日志对应指令已经返回给客户端）
。那当然不会，如果真有这样，就会有不一致，或者指令丢失现象。
其实就是跟随者在
append
日志的时候，会进行错误校验。
在候选者成为领导者的时候，会为每个跟随者初始化一个
nextIndex
数组，数组的值初始化为自己最后条日志 +1，其实就是理想化状态，默认认为日志都已经同步成功。但是理想总会因为各种原因导致不正确，就用上面那张图。
leader
会初始化所有
nextIndex
为 11，但是在同步日志的过程中。f 节点会出现校验错误的响应。因为 f 节点 10 索引对应的日志和
leader10
索引对应的日志不相同
（主要是根据任期号判断）
这里再强调一下为什么根据任期号就可以判断日志是否一致，就是上面所说的日志匹配原则。
五、安全性
我们明白了如何选举和日志复制，但是没有考虑安全性问题。其实我上慢提到，比如一个宕机很久的跟随着会被选为领导者，进行日志覆盖操作会有丢失问题。
其实解决这个办法很简单，就是在领导选举的时候，只能让安全的节点当 leader，所谓安全，就是对应节点拥有当前领导者已经提交的所有日志。Raft 就是这么做的。
Raft 中节点在投票的时候，会判断被投票的候选者对应的日志是否至少和自己一样新。如果不是，则不会给该候选者投票。
1. 最后一条日志的任期号。如果大说明新。如果小，说明不新。如果相等。跳到2
2. 判断索引长度。大的更新。
还有一个问题，就是领导人不能保证一个已经在大多数节点存在的日志是否已经提交。
（a）S1 是 leader。同步任期 2 的数据给 S2
（b）S1 宕机，S5 当选
（S3、S4、S5 投票）
，产生任期 3 的日志
（c）S5 宕机，S1 恢复当选
（同步任期 2 的数据给 S3）
。
（d）S1 宕机，S5 当选
（因为他的任期日志比其他的都新）
，复制了任期 3 的所有数据。
假如说在 c 阶段，S1 提交了任期 2 的数据，那么如果出现 d，则会导致任期 2 数据被覆盖，丢失。也就是说，S1 在任期 4 时候，不能保证已经在大多数节点存在的日志
（任期 2 的日志）
是否提交。
所以 raft 永远不会通过计算副本数目的方式
（大多数存在）
去提交一个之前任期内
（任期 2）
的日志条目。只有领导人当前任期里的日志条目通过计算副本数目可以被提交
（e 阶段）
。这样之前任期的数据也会被提交。
那这里我理解一点就是，加入 S1 当选为 leader，如图 c 状态，那么，如果不再有新的日志出现，任期 2 对应的日志就不会提交。那么会导致客户端对应的任期 2 请求失败。
六、跟随者和候选人宕机
这个就比较容易理解了，宕机的话
RPCs
就会失败，Raft 通过无限重试却解决这个问题。
所以对于每个
RPCs
，做到幂等和无限重试，在节点恢复后，就还是会保证一致性状态。
七、Raft 集群成员变化
对于集群成员配置变化，如果直接更新每台机器配置，那么就会有安全性问题。以为对于同一时刻，不同节点使用的不同的配置去执行算法逻辑，这就是不安全的。
如图，蓝色代表新的配置。绿色代表老的配置。Old 状态有三台机器 Server1、2、3。New 加入两台 server4、5。
那么随着配置时间应用的不同，可能会导致选举出两个
leader
。
比如
server1、2
使用老配置，那么1和2都有可能被当选为
leader
。
3、4、5
使用心得配置，他们之中的一个也会被当选为
leader
。
