数据一致性是分布式服务的一大难题。假设我们能无成本的保证数据一致性，在分布式环境中就可以使用无限扩容来分发流量。那么数据一致性，何为数据 ？往往日志log是一应用的可靠性的保障，例如 mysql的binlog,redis 的aof日志。通过分析日志从机子可以达到和本机子相同的状态。因此数据一致性的问题，化简为日志一致性问题。Raft则是一个用于管理日志一致性的协议。
Raft又称 木筏协议，一种共识算法，旨在替代PaxOS，相比容易理解许多。斯坦福大学的两个博士Diego Ongaro和John Ousterhout两个人以易懂为目标设计的一致性算法，2013以论文方式发布。由于易懂，不从论文发布到不到两年的时间，即出现大量的Raft开源实现。为简化PaxOS的晦涩，它采用分而治之的办法，将算法分为三个子问题：选举（Leader Election）、日志复制（Log Replication）、安全性（Safety）和集群成员动态变更（Cluster Membership Changes）。
Raft 中node 的 3 种角色/状态
Follower：完全被动，不能发送任何请求，只接受并响应来自 Leader 和 Candidate 的 Message，每个节点启动后的初始状态一定是 Follower；Leader：处理所有来自客户端的请求，以及复制 Log 到所有 Followers；Candidate：用来竞选一个新 Leader （Candidate 由 Follower 触发超时而来）。获取Leader结点特性 1.有最大的Term； 2. 如果Term相同，则有最大的Index； 3. 如果Term相同，Index也相同，就看谁最先发起；
日志复制是分布式一致性算法的核心，所谓的一致性，就是集群多节点的数据一致性。
Raft 把每条日志都附加了任期号和下标来保证日志的唯一性。如果 2 个日志的相同的索引位置的日志条目的任期号相同，那么 Raft 就认为这个日志从头到这个索引之间全部相同。
下图，所有的 follower 都和 leader 的日志冲突了，leader 的最后一条日志的任期是 6， 下标是 10 ，而其他 follower 的日志都与 leader 不匹配。 一致性操作：
a follower 不需要删除任何条目，b 也不需要删除c follower 需要删除最后一个条目d follower 需要删除最后 2 个任期为 7 的条目，e 需要删除最后 2 个任期为 4 的条目，f 则比较厉害，需要删除 下标为 3 之后的所有条目。具体思路：
Leader 为每一个 follower 维护一个下标，称之为 nextIndex，表示下一个需要发送给 follower 的日志条目的索引。当一个新 leader 刚获得权力的时候，他将自己的最后一条日志的 index + 1，也就是上面提的 nextIndex 值，如果一个 follower 的日志和 leader 不一致，那么在下一次 RPC 附加日志请求中，一致性检查就会失败（不会插入数据）。如果检查失败，leader 就会把 nextIndex 递减进行重试，直到遇到匹配到正确的日志。当匹配成功之后，follower 就会把冲突的日志全部删除，此时，follower 和 leader 的日志就达成一致。Raft在非拜占庭错误情况下，包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确，不会返回错误结果，这就是安全性保证。
Leader选举之后，如果Follower与Leader日志有冲突该如何处理？ 答：通过强制 follower直接复制 leader 的日志解决，详情见上文。如果上述情况©中,term=2,index=2的日志条目被复制到大多数后，如果此时当选的S1提交了该日志条目，则后续产生的term=3，index=2会覆盖它，此时就可能会在同一个index位置先后提交一个不同的日志，这就违反了状态机安全性，产生不一致。 答：为了消除上述场景就规定Leader可以复制前面任期的日志，但是不会主动提交前面任期的日志。而是通过提交当前任期的日志，而间接地提交前面任期的日志。
网络分区会不会产生不一致的状况 答：机子是2n+1的个数。如产生分区，机子小于等于n的分区，将不会产生日志数据以及term不再增加。如果分区合并，n分区的机子板本落后也不可能成为Leader
所谓线性一致性，就是在 t1 的时间我们写入了一个值，那么在 t1 之后，我们的读一定能读到这个值，不可能读到 t1 之前的值。
Mysql 主从异步复制，你t1时间向主库插入数据x，t2时间去从库读数据x,是有可能读不到的。而线性一致性系统则是必须读到，即CAP理论中的C.
Raft中有一个状态机，专门用来执行日志，相当于Mysql的解析执行器。状态机执行是要花时间的，Follower没这么快。
点评：非常方便的实现线性 read，但每次read 都需要走 Raft流程，全部依赖Leader, Follower在浪费。
ReadIndex Read 读请进来，将Leader commit index 记录到一个 local 变量 ReadIndex向其他节点发起一次 heartbeat，如果大多数节点返回了对应的 heartbeat response，那么 leader 就能够确定现在自己仍然是 leader。(防止网络分区了，自己不知道)将Leader commit index （Follower通过网络获取）记录到一个 local 变量 ReadIndex等待自己的状态机执行，直到 apply index 超过了 ReadIndex点评：Follower可通过网络获取ReadIndex。Follower帮助分担了Learder的部份压力，向其他节点发起一次 heartbeat仍是Learder的负担
Lease Read - 读请进来，将Leader commit index 记录到一个 local 变量 ReadIndex - heartbeat + election timeout内默认自己是leader。超过时间 向其他节点发起一次 heartbeat并刷新heartbeat - 将Leader commit index （Follower通过网络获取）记录到一个 local 变量 ReadIndex - 等待自己的状态机执行，直到 apply index 超过了 ReadIndex
点评：优化了ReadIndex Read ，进一步节省了heartbeat对Leader的负担
在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃。
集群配额从 3 台机器变成了 5 台，可能存在这样的一个时间点，两个不同的领导者在同一个任期里都可以被选举成功（双主问题），一个是通过旧的配置，一个通过新的配置。
Raft解决方法是每次成员变更只允许增加或删除一个成员（如果要变更多个成员，连续变更多次）。
在Paxos base协议中存在3种角色: acceptor, proposer, learner.
Proposer向Acceptor提交提案（proposal），提案中含有决议（value）。Acceptor审批提案。Learner执行通过审批的提案中含有的决议。 Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | |<---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->|->|->| | | Accept!(1,V) | |<---------X--X--X------>|->| Accepted(1,V) |<---------------------------------X--X Response | | | | | | | Request, 客户端发送请求Prepare，Proposer提交提案编号为n；Promise，Acceptor审核提案，如果Acceptor当前提案内容大于等于n，则不接受，小于则成功。Promise sucess, Proposer结果成功数是多数，进行AcceptPromise fail, Proposer结果成功数是少数，提案编号n+1跳回PrepareAccept, Proposer将编号为n的提案内容发过去Accepted，如果Acceptor中最大编号没超过n，则写入提案及Learner做备份。否则重新到PrepareResponse，返回结果。点评：
当Proposer高并发的时候，可能出现活锁的现象，谁也提交不了？当发生冲突的时候，进行编号小的进行休眼，迟点发起。影响效率。每次请求都要经2轮RPC通信，影响效率。因为上述的问题，对Paxos base进行优化变成 Multi Paxos
项目启动时，通上Paxos base流程，先对Proposer选出Leader。之前client语法只通过Leader来提案，流程如下 Client P（leader） Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Accept!(1,V) | |<---------X--X--X------>|->| Accepted(1,V) |<---------------------------------X--X Response | | | | | | |点评： Proposer，Acceptor，Learner可以合到一个Server里面,然后通过状态来区分他们。这样Multi Paxos 和Raft模式已经很接近了
zab同raft一样，也是由Multi Paxos变型过来的。也有三个状态LOOKING/FOLLOWING/LEADING。
LOOKING: 节点正处于选主状态，不对外提供服务，直至选主结束；FOLLOWING: 作为系统的从节点，接受主节点的更新并写入本地日志；LEADING: 作为系统主节点，接受客户端更新，写入本地日志并复制到从节点选主过程：
LOOKING向其它机子发送（sid,zxid）sid：机子编号。不同机子不同的编号 zxid：高32为epoch 轮数，相当于Raft中的term；低32位表示自增ID由0开始,相当于Raft中的Index.每次选出新的Leader，epoch会递增，同时zxid的低32位清0。
集群其他节点，这些节点会为发起选主的节点进行投票zxid(A) > zxid(B) sid(A) > sid(B)
点评： ZAB和Raft在选主上面不是极其相似的。估计日志复制的细节上面有所差异
运行结果：
[localhost:8771] electionTime:500 [localhost:8774] electionTime:6785 [localhost:8772] electionTime:4948 [localhost:8775] electionTime:3759 [localhost:8773] electionTime:4643 [localhost:8772] stepDown become FOLLOWER [localhost:8774] stepDown become FOLLOWER [localhost:8774] agree [localhost:8771] [localhost:8775] stepDown become FOLLOWER [localhost:8775] agree [localhost:8771] [localhost:8772] agree [localhost:8771] [localhost:8773] stepDown become FOLLOWER [localhost:8773] agree [localhost:8771] [localhost:8771] become leader leader node is localhost:8771 LEADER[localhost:8771] write [{index=0, term=2, command=Command(key=yoyo, value=eee)}] FOLLOWER[localhost:8772] write [{index=0, term=2, command=Command(key=yoyo, value=eee)}] FOLLOWER[localhost:8773] write [{index=0, term=2, command=Command(key=yoyo, value=eee)}] FOLLOWER[localhost:8774] write [{index=0, term=2, command=Command(key=yoyo, value=eee)}] FOLLOWER[localhost:8775] write [{index=0, term=2, command=Command(key=yoyo, value=eee)}] LEADER[localhost:8771] apply [{index=0, term=2, command=Command(key=yoyo, value=eee)}] ok FOLLOWER[localhost:8772] apply [{index=0, term=2, command=Command(key=yoyo, value=eee)}] FOLLOWER[localhost:8774] apply [{index=0, term=2, command=Command(key=yoyo, value=eee)}] FOLLOWER[localhost:8773] apply [{index=0, term=2, command=Command(key=yoyo, value=eee)}] FOLLOWER[localhost:8775] apply [{index=0, term=2, command=Command(key=yoyo, value=eee)}] FOLLOWER[localhost:8772] ReadIndex to [0] with value:eee eee资源地址：https://download.csdn.net/download/y3over/12577334
SOFAJRaft 是一个基于 Raft 一致性算法的生产级高性能 Java 实现，是从百度的 braft 移植而来，做了一些优化和改进。 《SOFAStack 开源 SOFAJRaft：生产级 Java Raft 算法库》 《SOFAJRaft 选举机制剖析 | SOFAJRaft 实现原理》 《SOFAJRaft 线性一致读实现剖析 | SOFAJRaft 实现原理》 《SOFAJRaft 实现原理 - 生产级 Raft 算法库存储模块剖析》 《SOFAJRaft 实现原理 - SOFAJRaft-RheaKV 是如何使用 Raft 的》 《SOFAJRaft—初次使用》
《Raft 日志复制 Log replication》 《编写你的第一个 Java 版 Raft 分布式 KV 存储》 《Raft协议安全性保证》 《TiKV 功能介绍 - Lease Read 》 《RAFT算法详解》 《从Paxos到Zookeeper：分布式一致性原理与实践》
