分布式系统通过复制状态机来解决分布式的容错。对于多副本，如何保持一致性是很难的。raft作为分布式共识算法来解决一致性问题。以前有过mit的实验总结，这篇对于概念做一个总结，用自己的语言复一下论文。
paxos的优缺点
1 | paxos的缺点： |
raft特点
raft一致性算法的特性：
- 安全性保证
- 可用性
- 不依赖时序保证一致性
- 小部分较慢的节点不会影响系统整体的性能
- 日志不允许有空洞(如果两个日志在某一索引位置term任期号相同，则认为从头到该索引的所有日志都相同)
raft的优点：
- 工程实现简单
- 易于理解
- 操作的高效性
- 状态的数量少，考虑的情况没那么复杂
领导人选举
通过领导人保证日志的一致性，由领导人告诉节点日志条目应该放在日志中的位置，而不需要和其他节点进行商议。领导人失去连接后，新的领导人会被选出来。
节点初始状态是跟随者，只能响应领导者和候选者的rpc,如果跟随者一段时间内都没有收到消息，则会给自己的term加一，然后发起选举，争取投票，这个过程可能产生3种结果
成为领导人
每一个服务器给一个任期最多只投一张票，按照先来先服务的原则，保证同一任期内最多有1个领导人。一旦获得了多数票，则切换自己的状态为领导人，并发送附加日志的rpc心跳包(日志内容为空)来维持自己的领导，组织其他的选举发生
其他节点成为领导人
作为候选者，收到了其他节点的附加rpc请求，该节点的任期号不小于自己的节点，则承认对方为领导人，自己切换回跟随者状态。如果对方的任期号比自己的小，则拒绝，继续收集选票。
一段时间内都没有领导人选举成功
当有多个候选者收集选票的时候，选票会被瓜分，以至于没有人成功获选直至超时后大家都给任期号加1，再次尝试选举。这个过程可能一直僵持下去。
raft通过随机生成选举超时时间，来避免多个节点同时发起选举。解决这个问题。通过这种不确定性来保证算法的可理解性和正确性。
日志复制
由领导人接收客户端的日志，然后复制到集群中的其他节点，强制其他节点的日志和自己保持一致
日志由日志的索引，任期号，指令组成。领导人发送附加日志rpc给其他节点，当大多数节点都将该日志复制成功，领导人将该日志状态设为已提交，已提交的会被持久化，并保证所有节点最终都会应用该日志。已提交日志之前的所有日志也认为是已提交的。
raft维护着以下特性：
- 如果不同的日志中的两个日志条目拥有相同的索引号和任期号，那么他们存储了相同的指令
- 如果不同的日志中的两天日志条目拥有相同的索引号和任期号，那么他们前面的所有日志是相同的
第一个特性是这样保证的：
一个任期最多只会有1个领导人，所有相同任期的领导人是相同的。然后领导人只会增加日志(跟随者可能会覆盖老的日志)，不会删除修改老的日志，一个索引位置的日志是不会改变的。
第二个特性是这样保证的：
每一个附加日志rpc都会额外发送前一个日志的索引和任期号，当跟随者发现自己的prev日志的索引和任期号对不上则会拒绝接收新的日志条目，领导者需要再返回更老的日志条目来让跟随着对齐(通过领导者给每一个跟随者维护一个nextindex)。即s(n) = t(n), 且s(n-1) = t(n-1), 则[0,n]上s和t是一样的
安全性
如果一个服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他的服务器节点不能在同一个日志索引位置应用一个不同的指令。
由于领导人只追加日志，不会修改删除自己的老的日志，并通过强制其他节点和自己保持一致来保证整体的一致性，所以领导人自己需要有领导人完整特性的保证，确保选举出来的领导人，拥有自己任期之前的所有已提交的日志。这需要一些特性来保证，如下：
选举限制：选举需要获得大多数节点的选票，日志的提交也需要大多数节点的确认，所以如果一个节点成功当选领导人，那么它肯定不会被拥有最新提交日志的节点拒绝。从而保证自己拥有最新的提交日志。选举的时候，候选者会在rpc中带上自己的最新的日志，跟随者/候选者会比对自身的日志，如果收到的日志比自己的旧，则不会同意当选，新的定义是：
- 如果任期不一样，则任期大的是新的
- 如果任期一样，则日志长的(日志索引更大的)是新的
领导人提交自己任期内的日志： 领导人拥有的老的任期内的日志，即使在大多数节点上保存了，也不能确保该日志是已经提交的，这里，领导人只能对自己任期内的日志通过大多数确认来提交。就是说领导人通过限制计算自己任期内的日志的大多数节点来维持的已提交状态，可以保证自己这个日志之前的所有在自己机器上的老的日志，也是已提交的(大多数写了)
成员变更
如果跟随者或者候选者崩溃了，raft通过无限的重试来解决，这里raft的rpc请求保证都是幂等(全局的序列号)的，所以重试不会有问题。
集群变化
这个挺复杂的，简单记录下，后面看看源码实现再分析。
首先这里存在出现2个相同任期下的不同领导人问题：
这里有个前提是lerder可以拿到新加入节点的信息，集群总数也会更新，然后这里出现问题的一种场景：
- s3作为old的leader(term=1),在集群新增了s4/s5后，s3宕机
- 然后s1通过term=2拿到了s1/s2的选票成为leader.
- s3恢复，用term=2拿到了S4/s5的选票成为leader
- s1和s3都是leader,并且term相同
论文中提到了2阶段的方案，通过共同一致来实现：
- old的集群拥有old的配置，比如(123)
- 新的集群拥有新的配置，比如(4,5)
- s3的配置是(123-45)
s3需要同步(123-45给其他节点)，提交成功后，再提交一个(12345)给所有节点，这时候第二阶段下才是新的集群完全生效的时候，如果s3提交(12345)前失败了，对于new(45)的节点，不能单独依赖自己单一节点的大多数来选举，只有old和接收old-new的节点可以当选。
以后再补充吧
日志压缩
时间久了日志太占空间了，可以对已经提交的持久化了的日志进行压缩，这个不需要领导人协调，因为已提交日志本身就是领导人确认的，这里可以通过lsm树做日志的压缩，还需要保存压缩日志最后的索引和任期号，用于后续日志的同步。如果作为领导人，有节点日志落后太多，也可以发送快照给他来同步。
客户端交互
客户端随机发给一个节点，如果该节点不是领导人则会重定向到领导人，如果领导人崩溃了，则会超时，后面重新选举。
如果领导人提交了日志，但是响应客户端前崩溃了，客户端可能重新提交请求，导致新的领导人再次执行了。这里需要做幂等处理，可能的方案是用全局的序列号。
脏数据问题？对于只读的请求，领导人可能已经被废弃了，这时候可能返回脏数据给客户端，raft是这样处理的:
- 领导人返回只读请求前，先发一个空的提交日志给其他节点，保证自己前面的日志都被大多数节点持久化为已提交，考虑前面那个图，4任期日志前面的2只有在附加4的时候，才能保证2都被写提交。就是说领导人只能提交自己当前任期内的大多数日志，所以需要当前任期由日志写才能保证老的日志真的已提交了
- 第二点是返回只读请求前，领导人需要和大多数节点确认下，自己是不是最新的唯一的领导人，这个可以通过心跳包来确认(给大多数节点心跳来确认)，也可以通过租约机制？
reference
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md