你好，我是微扰君。
今天我们要来谈一谈分布式系统中一个非常重要的问题：分布式共识问题，也就是一致性问题。
我们知道，分布式系统的诞生，主要是为了提供单机无法进行的计算和存储、提高吞吐量、增加容错性等。而在现在的互联网架构下，分布式系统由于大量使用廉价的商用机器，节点故障是不可避免的。
在这种情况下，多个机器如何像一个整体一样工作，是件很困难的事情，这里一致性算法就起到了至关重要的作用。
以分布式KV存储系统为例，我们来先搞清楚分布式一致性到底解决的是什么问题。
之前在操作系统章节中讲过，数据库常用 redo-log 来实现事务等能力，那当这样的存储系统不再是单机节点，我们通常也需要采用多台机器来存储日志，把同样的日志在不同的节点都存储一份。这样如果有一台节点挂了，整个系统还可以用备份节点来提供日志的能力。
让多台服务器存储相同顺序的多条相同指令，也就是“日志”，可以帮助我们实现复制状态机。
每一个状态的变更记录都会先在日志中存储并commit，之后才apply到状态机中修改对应的状态，这个设计能在分布式系统中解决许多和容错性相关的问题。
既然涉及多个节点存储同样的一份东西，怎样才能保证多个独立的节点所存储的内容是一致的呢？这就是我们常说的“一致性问题”了。
客户端通常只会向分布式系统中的某个服务器发起请求，然后由这个服务器的一致性模块，在多个复制状态机之间进行消息的同步，正常情况下，多个节点同步都会成功，这样不同节点的日志自然也都是一致的，所有的节点都会以相同的顺序包含相同的请求，从外界看起来，行为也就像是一台机器一样。
但是在服务器发生故障时，依然要保持正确的复制变成了困难。
一种最暴力的做法可能是：定义一个主节点，每一次写请求都请求到主节点，等主节点一致性模块向集群中的每个节点都成功写入了同样一份数据，再返回给客户端成功的消息，进行消息的commit。只要有一个失败，就不进行消息的commit。
但是我们看这个方案，显然不是很高效。无论是存在慢节点，会导致整体响应被拖的很慢，还是一台节点挂了，会导致整个集群不可用，都是不可接受的。
那我们分析一下在实际系统中，一致性算法通常会存在哪些问题：
接下来我们要学习的Raft算法就很好地考虑了这些问题。
Raft提出之前，在非拜占庭条件下，分布式一致性领域里，Paxos算法，一直占据着统治性的地位，但 Paxos 是出了名的难理解，工程实践也比较困难。
拜占庭条件源自一篇论文，也是Paxos的作者写的，他用一组将军围困一座城市的假想问题，描述当点对点通信的节点中出现了恶意节点传播不正确消息时，达成共识的困难处境。非拜占庭条件指的就是所有节点都是正常工作，只可能出现消息不可达，不会有消息错误的情况。拜占庭将军问题本身也非常有趣，你感兴趣的话可以自行搜索了解一下。
Paxos的艰深难懂其实也是Raft算法提出的主要动机。Raft和Paxos都是只要有超过一半的服务器可以运行并互相可通信，就可以保证整个系统可用。
和Paxos不同的是，一致性问题，被Raft明确拆解成了三个比较独立的、更好理解的子问题，并且团队在许多实现细节上做了很多努力和权衡，也增强了系统里的许多限制，简化了需要考虑的状态，尽量让过程和接口的设计变得清晰易懂。比如，Raft中就引入了Leader，由Leader进行全局消息的把控，也不允许日志中存在空洞的情况，都是一些比较常见的权衡。
接下来我们就来逐一学习Raft拆解出来用于达成分布式共识的三个子问题：领导人选举、日志复制、安全性。
Raft引入Leader的概念，也就是领导人节点的思路，和两阶段提交里的协调者性质其实差不多的。
本质上，都是因为在分布式的系统中，各个节点不具备全局的信息，那为了感知到不同节点对请求的响应情况，我们通常就会引入一个主节点，由它进行统一的控制和调度，这样整个分布式的处理逻辑就会变得比较简单。
在Raft中，Leader就负责接收客户端的请求，由它统一向其他节点同步消息，等收到半数的节点Commmit日志的响应后，就会把状态应用到状态机，并返回。
思路很简单，但是Leader节点如何被选出呢？
Raft设计了一套节点状态机制，每个节点永远处于三个状态之一：
Follower 追随者：所有节点初始化或重启的时候都处于Follower状态。它不会接受请求，也不会发起请求，只响应由Leader发起的AppendEntries和Candidate发起的RequestVote请求。
Candidate 候选人：是 Follower 晋升为 Leader 的中间状态，从语义上就能看出来这个阶段是需要投票的。Follower 如果在一段时间没有收到领导人的消息，就会变成 Candidate 并发起选举，也就是向集群中所有节点发出 RequestVote 请求，如果收到半数以上也就是 (n/2+1) 的通过，就可以成功晋升为新的 Leader 。
Leader 领导人： 系统大部分时候只有一个节点处于Leader状态，如果有两个节点同时处于Leader状态，也最多只有一个是真正有效的。Leader会不断的向Follower发起请求，告知它们自己还在正常工作。这里的请求就是后面用于复制日志的AppendEntries请求，我们马上展开讲解。
每一任新的领导人出现，都会带有一个任期（term）。任期时长不确定，只要网络不发生大面积分区，而且超过半数的节点和Leader一直可以正常工作，这届任期可能就会非常长。
任期编号是单调增的，1、2、3……，在每一次选举发起的时候产生。
候选人发起选举的时候会把当前的任期加1，再发给其他节点投票，如果其他Follower收到的请求带的是过期的任期，就会直接拒绝这次请求，对应的Leader和Follower发现后也会立刻变成Follower状态，因为这意味着此时已经出现过一个任期更高的合法Leader了。
大致设计就是这样，但是我们把这套规则应用到真实系统中就会存在一些问题。你可以先暂停思考一下预计会出现哪些问题，如何解决，我们再一起讨论。
首先当同时有多个Candidate产生，发起票选，每个Candidate的票数都不足n/2+1的时候会发生什么呢？
这个很简单，平局收场，Term再加1，我们重新选举一轮就可以。所以Candidate也会维护一个定时器，用于处理这种超时的情况。网络分区中的Candidate可能会不断的提高自己的Term，但是因为它没有任何新的数据被写入，网络恢复的时候它自己也能很快感知到这点，从而恢复到Follower的身份。
看到这里你可能又想到新问题了：如果碰到了这样的情况，多个Candidate一起超时，又会触发下一轮票选瓜分，岂不是永远选不出Leader了？
解决这个问题的方法，也很简单常用。我们可以在选举超时时间中引入一定的随机性，而不是一个固定值，比如150-300ms，这样多个Candidate在下一轮超时的时候，肯定就会错开发起选举请求的时间了。
当然，这也需要我们保证有良好的网络环境，选取发出-被收到的时间一定要比较短才行。
广播时间（broadcastTime） << 选举超时时间（electionTimeout）
不过这里还有一个问题不知道你有没有思考，为什么我们一定要要求半数以上的票选才能晋升呢？
这其实也是在分布式系统中非常常见的做法。容斥原理我们知道，能获得半数以上票选的候选人只可能有一个。所以半数机制，如果遇到网络分区，网络分区少数的那一方就肯定不会产生Leader；同样，同一个Term下全局也只会有一个Leader，不会出现脑裂也就是同时有多个leader的情况。
现在Leader选举完成，它就要扛起接受客户端请求并复制日志的大旗了，主要职责就是发起AppendEntries请求，这里的Entries主要指的就是日志记录，它可以做两件事。
当Follower收到这样的请求时，只要请求的任期没有过期，Follower就会接受这个请求，知道Leader还正常工作，自己也就没有必要揭竿而起，成为Candidate了。这个和很多系统中的心跳机制是一样的。
当Leader接收了客户端的请求，它就会并行地请求其他节点，带上客户端请求的指令，要求其他节点进行复制并返回结果。当Leader觉得日志被安全地复制了之后，才会将指令应用到状态机中并返回客户端。
什么是安全的复制呢？就是指一旦决定这个日志可以被应用到状态机（我们也叫“已提交的日志CommittedEntries”），即使之后任何节点出现不可用的情况，已提交的日志一定不会丢失，且最终会被集群中所有正常工作的节点应用到状态机。
而Raft对“已提交”的条件定义也很简单有效，如果一个日志被Leader复制到大多数节点，日志就算被提交了，反之则没有，还有可能被其他更新的任期的日志所覆盖。这一点约束我们稍后马上会展开讨论。
另外，Raft在记录日志的时候，除了会记录日志任期、具体操作，也会给每条记录都赋予一个日志索引，这样可以帮助节点定位自己所持有的日志具体是哪些。
有了index和term的概念，Raft通过引入一些约束，使得所有的日志始终拥有着“日志匹配”的特性，主要是两条规则：
前面我们已经说了，Raft同一个任期里肯定只有一个Leader，如果这个Leader写了某条日志，它在不同节点上日志的索引一定是相同的。
这是因为AppendEntries被接收时，会执行一致性检查，Leader提交请求的时候会带上自己的prevLogIndex和prevLogTerm，表示上一个日志条目的索引和任期。如果Follower发现自己的日志里找不到这个任期和索引对应的条目，会拒绝此次AppendEntries请求，这个就是Raft协议很关键的一个约束；所以当AppendEntrires成功时，Leader能保证prevLogIndex之前所有的记录都是相同的。
这个逻辑你仔细顺一下就很清晰了，具体的证明有点像数学归纳法，初始状态是满足日志匹配的，如果执行了一致性检查，那么后续的所有状态，日志匹配特性也都是满足的。
如果Leader和Follower由于崩溃，出现日志记录不同的时候，Leader就会要求Follower，按照自己的日志覆写。Leader为每一个Follower都记录了一个nextIndex的字段，表示下次应该发给Follower的日志，在Leader刚刚晋升的时候，Leader就会将这个值初始化为自己的最后一条日志的索引+1。
如果Follower日志和Leader日志有所冲突，Leader会尝试减小nextIndex的值，直至两者nextIndex所对应的日志相同；此时，LeaderAppend的记录就包含了从nextIndex开始的全部日志，Follower收到之后就会把不同的部分覆写；如果成功，Leader也会修正nextIndex的值。
基于这样的约束，整个覆写的过程一定是单向的，只会发生在Follower节点上，Leader从来不会修改自己的日志。
但到目前为止，Raft协议还有一个重要的特性没有得到保证，就是“领导人完整性”，也就是需要保证：如果某个日志条目在某个任期号中已经被提交，该记录必定出现在更大任期号的所有领导人中。
这是一个非常重要的特性，不然会无法保证某个领导人在任期内提交的日志不会被后来者所覆盖。Raft对这个问题作出了另一个简单的限制，相比于一些其他的一致性算法，显得更加清晰。限制Candidate提交选举请求的时候，必须至少和Follower的日志一样新，才可以获得选票。
这就意味着，如果Candidate获得了超过半数的选票，说明至少有半数的Follower节点，日志条目和自己一样新，而所有commit了的记录，也一定在半数的节点中出现了。
根据容斥原理，半数同意的节点一定会和commit了某个日志的节点有所重叠，新的Leader至少拥有了所有被commit日志一样新的日志。这样，被commit的日志，一定会被更大任期的领导所包含。
但是这里还有一个比较重要的约束，Raft要求每个节点进行提交的时候只能提交自己任期的日志而不能提交之前任期的日志，也就是说需要通过提交自己任期日志的方式顺带提交之前任期的日志。
为什么呢？这里就需要考虑一种比较极端的情况，在论文中的figure8讨论的就是这个问题，我把图片贴在了文稿中。
假设一开始，S1成为了任期为2的领导者，并开始发送任期2所对应的日志，随后在b时刻，S1挂了，此时，S5拿到了S3、S4的选票成为了领导者，任期为3，进入c时刻。
如果S5又宕机且S1又再次获得了选票，成为了任期4的领导者。这个时候，S1可以复制之前任期为2的日志至S3，任期2的日志其实已经被大部分节点所持有了，但是我们可以提交吗？
如果允许提交。假设S1在d时刻中又崩溃了，S5再次获得更高任期的选票并当选，S5就可以像d那样覆写所有之前任期的日志，就会出现已经提交的日志被覆写的情况。所以我们不能允许提交。
而另一种情况，如果在崩溃之前，S1就对多数节点当前任期的日志进行了复制并提交，e时刻S5就不再有被选举上的可能性，因为多数节点都拥有更新的日志。这个时候任期2的日志自然也被一起提交了。
总的来说，只要我们只允许领导提交任期内的日志，且必须确保被大部分节点所复制，Raft的数据安全性就是有保证的，被提交的日志一定是不会被覆写的。
原论文中还提到了一些简单的优化，比如日志压缩、采用Chubby和Zookeeper用的快照技术等，减少因为日志增长越来越多空间被占用和对应的同步成本问题等等，如果你感兴趣可以看看原论文。
Raft协议，除了各种协议细节，今天学习的几个比较有价值的技巧对你工作也很有帮助。
我们为了避免票选被多个同时称为cadidate的节点平分，进入无限循环，可以在选举超时时间里引入随机性，避免多个节点继续在同一时间发起票选请求。分布式系统多个节点存在时，往往会采用奇数的节点，这样就可以通过少数服从多数的机制，在集群中保证同一时间只会有一个主节点了。
Raft将复杂问题拆解成多个明确清晰的子问题，分而治之，也是一种系统设计的哲学，你可以好好体会。
Raft算法逻辑还是比较清晰的，但是有很多细节和边界问题需要我们反复琢磨，不自己动手实践一遍，理解程度一定还是比较有限，所以这里也推荐MIT 6.824，供你练手学习，Lab就是基于Raft和Golang语言实现一个简单的分布式KV存储（18年我做过一次，当时有几个case没有跑过，就弃坑了，但整体还是收获很大，而且过程颇为有趣，祝你也能研究顺利）。
最后也留一个思考题给你。Raft在现实的工程实践中还有许许多多的优化，不知道你听完了今天的讲解之后有什么觉得可以优化的想法吗？
这里给你抛砖引玉一下，Leader给Follower同步日志的时候，nextIndex是一步步向下尝试的，如果中间缺失了很多日志，效率其实可能比较低？你有什么办法吗？
如果你还有想法也欢迎在留言区和我讨论。如果觉得有帮助的话，也请转发给你的朋友一起学习。我们下节课见。