随着接触各种开源的中间件或者数据库，总是会了解到他们必须保证多节点的一致性。比如Zookeeper使用了Zab来保证CP；Nacos既支持AP也支持CP，CP使用的是Zookeeper，AP则是raft；Rocketmq在主备切换的时候是Dledger（基于Raft），在最新的5.3版本我还看到可以选择使用JRaft或者Dledger；Kafka则准备抛弃Zokeeper，改用KRaft。
这些技术中绕不过去Raft，因此为了理解的更透彻，也为了更好的了解Zab和Raft的区别，我打算分为两部分，本文是先简单记录一下Raft最基本的内容，即论文的第5章的部分，至于后面的日志压缩、集群成员变化、客户端交互则由另一篇文章记录。
学习途径
不同于Zab官网没有介绍，Raft官网提供了两个非常友好的动画来辅助学习。
入门版（也可以用中文版）是让人在没有任何基础的情况下大致了解分布式共识的意义以及Raft的方案是什么。
Raft Scope则是一个可以让你模拟各种情况的可视化动画，包括选举和日志复制，甚至异常情况。通过这个动画你可以看到算法运行过程，以及最终的结果，可以去印证你的理解思路是否存在问题。
除了动画，官网的Talk区还有很多的介绍视频可以让你更快入门，虽然这里大部分都是YouTube上的，但是你在国内自己搜一下也不是没有。
不过，有能力最好还是通过读原论文的方式，从根源上去了解去确认其为何要这么设计。毕竟你无法去确认视频里的内容是否有错误，现在这个人云亦云的时代，千篇一律的博客，当你的认知和他人的内容出现差别的时候，最好还是去读一读最官方的原始资料。
实践版动画
虽然实践版动画很好很强大，但是他没有说明书，不清楚动画里各个组件的内容你可能很难尽快上手。所以本节做一个简单的介绍。
左上角是代表集群有5个节点，分别是S1-S5；
右上角是日志，表示每个节点在给自己的日志文件中的内容是什么情况。
两个进度条第一个是时间进度条，左边的按钮代表暂停/继续，可以拖动进度条回滚到之前的时间重新开始。
第二个进度条是速率，越往左越慢，越往右越快，我个人一般使用1/70x会多一些。
状态
节点有三个状态：Leader、Follower、Candidate
Leader状态下，外圈是黑色整圈，内部是周期数，不会随着时间缩圈
Follower状态下，外圈是一个灰色圈，内部是周期数，但会随着时间缩圈
Candidate状态下，外圈也是黑色圈，但是随着时间会缩圈，其内部是类似于左轮弹夹一样，“子弹数"代表收到同意的票数
操作
节点是可以单击或者右击的，单击显示该节点完整的状态
表格中vote granted列是指在上次选举时，每个节点收到的其他节点的投票信息；
两个Index列是只有当选Leader后，Leader所记录的每个节点的进度；nextIndex是只下一个可以写的索引位置，CommitIndex是指已经经过大多数节点认同的信息，对应到日志表格中，有着黑色边框的就是已经Commit的信息，虚线框的就是还未Commit的信息；箭头指向的就是nextIndex，圆点是matchIndex
详情看板上的按钮右击时也会出现
Stop是指当前节点下线
resume则是指当前节点重新上线，即重新变为Follower，但周期不变
restart 感觉和resume没有区别，只是从语义上说resume是恢复，restart是重启？
timeout会将当前节点立即变为候选人，即进入Candidate状态且周期+1
request仅有Leader可以操作，是指追加一条日志
RPC
RPC分为Request和Reply，并且可以通过单击或者右击丢弃掉这条信息
Request的样式在暂停状态下有箭头，正常播放情况下只有一个圆圈
Reply则有两种结果，同意的话圆圈内部是+号，拒绝是-号
公共信息是：
from（发送方）TO（接收方） sent（何时发送，一般是负数表示n毫秒前发送）deliver（何时到达，一般是正数，表示n毫秒后到达）
Rpc有两种业务：一种是投票（Vote），一种是追加日志（AppendEntries），具体字段的内容得了解Raft流程后才能理解，但其实都是字面意思。
基本理论
Raft主要由两部分组成：选举和日志复制。
选举
Raft算法认为分布式场景中多个节点中应该选出一个Leader节点，由此节点来负责和集群外的Client进行信息交换，每个Leader有自己的任期称之为Term，其他的节点只需要从Leader节点中不断地复制信息即可。
节点存在三个状态：Leader、Follower、Candidate。
Leader是指已经成为领导者，可以给其他节点发送日志信息
Follower是指具有投票权，在未超时的状态下会对其他节点的请求做出回复，在超时的状态会变为Candidate
Candidate是候选人状态，由Follower转变，当Follower超时，会自己投自己一票变为该状态，当前Term会+1，同时会给其他节点发送投票请求
何时选举
节点首次启动时Follower状态，Raft中每个节点设计了一个随机超时时间，当超时后会进入选举，即进入到Candidate状态；但如果在超时时间内接收到其他候选节点的投票信息或者Leader的rpc信息就会重置超时时间。
或者当Leader下线，所有的节点都是Follower，会再次进入选举流程
如何投票
每个节点每个周期仅可以投一票，即接受了S1的投票就无法接受S2的投票；同意投票的条件是周期（term）较大&日志（lastLogIndex）最长
其中要求日志最长是为了保障安全，比如S1节点有20条日志，S2只有0条日志，假如S2Term大因此竞选成功，那么会要求其他节点都和自己保持一致，会丢失过多信息。因此Raft要求Leader必须拥有最多的日志。
如何竞选成功
当Candidate节点收到整个集群内一半以上的票(n/2+1)表示竞选成功，包含自己投自己的一票；当竞选成功后会像其他节点发送Rpc消息，消息内可能有日志信息，也可能没有，没有的话就是普通的心跳机制。
存在多个候选人收到相同票数或者不满足(n/2+1)等无法决出Leader的情况，会进入下一轮选举重新尝试。基于随机超时的设计机制，并不会重复太多次。
比如下图S1是2票，S3和S5都是1票，无法选出Leader，会在S1超时后，以Term为9再次尝试
日志复制
日志复制本身是复制状态机的一种实现，其理论为对于多个拥有相同初始状态的状态机，在按照相同的顺序执行一系列输入之后，得到的一系列输出也是相同的。体现在Raft中，就是指多个Follower从Leader去同步复制并进行提交，以达到最终一致性。注意：Raft中数据只允许单向流动，即Leader—>Follower
来自客户端的写请求在日志中体现为一个entry，entry分为未提交和已提交两种，以2PC的模式去运行。
正常的流程如下：
Leader收到来自客户端的全新请求后，会先创建一个新的entry存储在自己的日志中，同时发送AppendEnties的RPC请求给其他Follower节点。
Follower节点收到之后会在指定位置追加该Entry，会回复给Leader成功或者失败以及命中的索引值。
Leader收到大多数节点的成功后再本地提交该entry到状态机，然后发送提交的消息给那些响应为成功的节点。假如响应的是失败，Leader会重新发送该消息。
Follower收到消息后，如果其CommitIndex大于自身的CommitIndex，就会将这些entry提交，并返回自己最新的CommitIndex给Leader
Follower启动时和Leader的日志不同如何处理？
当Leader当选之后，会先进行一致性检查。
首先Leader初始化所有节点的nextIndex值跟自己一样（只是修改Leader节点中的nextIndex数组），然后发送请求（携带prevLogIndex和prevLogTerm）给Follower。
Follwer应该有三种情况：
进度比Leader慢，即prevLogIndex内容为空
Follower会返回false，Leader收到False之后，会将prevLogIndex-1，然后再次发消息给Follower，直到找到相同的位置为止；当找到该位置之后，会将后面位置的消息一条一条发送给Follower，Follower收到并返回True后，Leader会更新该节点nextIndex的值，直到该节点的nextIndex和Leader自身相同
进度和Leader相同，且内容相同
直接返回True，Leader更新nextIndex和CommitIndex即可
进度和Leader相同，但内容不同
这种情况和下一种情况是从属关系，区别仅在于不同的位置后面还有没有其他值
进度大于等于Leader
这种情况常见于旧Leader挂掉然后又恢复了，但是旧Leader有一些新Leader没有的值。Follower在收到Leader最新的位置和值后，会直接抛弃不同的内容，然后将Leader的新值覆写
可以造一个和下面视频一样的情况，观察一下
假如Follower进度没有跟上，收到的消息还会按2pc处理还是说直接就可以Commit？
会收到消息立即Commit
新Leader是否会提交旧Leader未提交的内容?
会提交，但不是立即提交，是在提交当前Leader周期的内容时间接提交了之前周期的内容。
至于为什么会这样，我说一下我的理解，最大的原因是Leader假如立即提交的话，有可能在提交之后挂掉，导致其他和该节点不同的竞选为Leader后，无法处理这个情况。
比如论文中给的这个例子，假如在b阶段的时候S1下线，S5获得S3-S5三票成为leader，并写入3；然后到了c阶段，S5下线了，S1再次成为Leader，如果S1在提交之后再次下线，那么此时S1-S3的2的位置都是提交后的2，如果此时S5成为Leader（是有可能的，因为大家长度都一样，最多也就是2），那么S5就无法要求Follower和自己保持一致了，自己的2的位置上是3；
而如果是在提交自己周期内容时间接提交，会保证有多数的节点是要更长的，这样子，哪怕有些节点和自己的值不同，也不会当选为Leader了。
参考：
动画：Raft算法Leader选举、脑裂后选举、日志复制、修复不一致日志和数据安全