Paxos，Raft，Zab一致性协议-Raft篇

Raft是一个一致性算法，旨在易于理解。它提供了Paxos的容错和性能。不同之处在于它被分解为相对独立的子问题，它清楚地解决了实际系统所需的所有主要部分。我们希望Raft能够为更广泛的受众提供共识，并且这个更广泛的受众将能够开发出比现在更多的高质量共识系统。

Raft是一个通过管理一个副本日志的一致性算法。它提供了跟(multi-)Paxos一样有效的功能，但是它的架构和Paxos不一样；它比Paxos更加容易理解，并且能用于生产环境中。为了加强理解，raft把一致性的问题分成了三个子问题，例如leader election, log replication, and safety,

Role

Leader，Follower，candidate

在Raft集群中，有且仅有一个Leader，在Leader运行正常的情况下，一个节点服务器要么就是Leader，要么就是Follower。Follower直到Leader故障了，才有可能变成candidate。

Leader负责把client的写请求log复制到follower。它会和follower保持心跳。每个follower都有一个timeout时间（一般为150ms~300ms），在接受到心跳的时候，这个timeout时间会被重置。如果follower没有接收到心跳，这些follower会把他们的状态变为candidate，并且开启新的一轮leader election。

term逻辑时钟

Term相当于paxos中的proposerID，相当于一个国家的朝代。term是一段任意的时间序号。每一任Leader都有一个与之前不同的term。

当Leader选举成功之后，一个节点成为了Leader，就会产生一个新的term，并且直到Leader故障，整个集群都会一直在这个term下执行操作。

如果leader选举失败了，则会再生成出一个term，再开启一轮leader选举。

Quorums：

多数派，意思是超过一半的机器存活，则这个机器可用，这个Quorums指的就是集群可用的指标。例如：集群中的节点数为2N，如果有N+1的机器存活，则代表集群可用，可接受请求，写入log，应用到state machine中去，执行操作。如果少于N+1个机器存活，则代表集群可用，可接受请求，可写入log，但不应用到state machine中去，不执行操作。

Leader Election

只有在下列两种情况下才会进行leader election：

在第一次启动raft集群的时候

在一个已存在的Leader故障的时候

选举流程：

如果以上两种任何一种发生了，所有的Follower无法再和Leader保持心跳，则它们都会等待一个（选举）timeout，如果其中一个Follower的timeout最先到时，则这个Follower变成candidate开始选举，

第一，增加term计数器，

第二，给自己投票并向所有其他的节点服务器请求投自己一票。

如果一个Follower在接受到投票请求时，接受到两个term相同的投票请求时（也就是说，产生了两个candidate），则在多个相同term的投票请求中，这个Follower只能给投给其中一个请求，只能投一票，并且按照先来先服务的原则投票。

如果这个candidate收到另外一个节点服务器的消息，并且这个节点服务器的term序号和当前的term序号一样大，甚至更大的话，则这个candidate选举失败，从而它的状态变成Follower，并且接受新的Leader。

如果一个candidate获得了Quorums选票N+1(2N为集群中节点的数目)，则它变成新的leader。

如果多个candidate和多个Follower投完票之后，有多个candidate获得了相同的票数，则会产生split vote，则新的term产生，重新选举。Raft用随机选举timeout迅速地解决split vote问题，这个方法就是对于产生spit vote的candidates各自随机生成一个选举timeout，谁先到时，谁当leader，其他candidate都变为Follower。

当一个leader被选举出来之后，就在Follower timeout到时变为candidate之前，发心跳信息给所有Followers。

Log Replication（Raft协议具体过程）

Leader负责把client的请求日志复制给其他Followers。

Raft协议具体过程就是通过复制状态机的架构实现的，如下：

步骤：

Client发送请求给Leader，其中每个请求都是一条操作指令。

Leader接受到client请求之后，把操作指令(Entry)追加到Leader的操作日志中。紧接着对Follower发起AppendEntries请求、尝试让操作指令(Entry)追加到Followers的操作日志中，即落地。如果有Follower不可用，则一直尝试。

一旦Leader接受到多数（Quorums）Follower的回应，Leader就会进行commit操作，每一台节点服务器会把操作指令交给状态机处理。这样就保证了各节点的状态的一致性。

各服务器状态机处理完成之后，Leader将结果返回给Client。

Saftety

Raft的安全性，体现在如下几个方面：

Election safety:在一个term下，最多只有一个Leader。

Leader Append-Only:一个Leader只能追加新的entries，不能重写和删除entries

Log Matching:集群中各个节点的log都是相同一致的

Leader Completeness:如果一个log entry被committed了，则这个entry一定会出现在Leader的log里。

State Machine Safety:如果一个节点服务器的state machine执行了一个某个log entry命令，则其他节点服务器，也会执行这个log entry命令，不会再执行其他命令

之前四条，在前面都有所提及，而State Machine Safety是在Leader election过程中用到过。

State Machine Safety

一个candidate在选举的时候，它会向其他节点服务器发送包含他的log的消息，获取票数，如果它的log是最新的，则会获取选票，如果它的log不是最新的，其他节点服务器还有更加新的log，则会拒绝给这个candidate投票。这就保证了State Machine Safety。

所以State Machine Safety保证的就是一个candidate必须拥有最新的log，才能获取票数，才有机会赢得Leader选举，才有机会成为Leader。

Follower crashes

如果一个follower故障了，则不会再接受AppendEntriesandvoterequests，并且Leader会不断尝试与这个节点保持心跳。

如果这个节点恢复了，则会接受Leader的最新的log，并且将log应用到state machine中去，执行log中的操作

方格指的是client发出的一条请求。

方格虚线，说明一条log entry写入了log。

方格实线，说明一条log entry应用到state machine中

Leader crashes

则会进行Leader election。

如果碰到Leader故障的情况，集群中所有节点的日志可能不一致。

old leader的一些操作日志没有通过集群完全复制。new leader将通过强制Followers复制自己的log来处理不一致的情况，步骤如下：

对于每个Follower，new leader将其日志与Followers的日志进行比较，找到他们的达成一致的最后一个log entry。

然后删除掉Followers中这个关键entry后面的所有entry，并将其替换为自己的log entry。该机制将恢复日志的一致性。

下面这种情况集群中所有节点的日志可能不一致：

总结

Raft要求具备唯一Leader，并把一致性问题具体化为保持日志副本的一致性，以此实现相较Paxos而言更容易理解、更容易实现的目标。Raft是state machine system，Zab是primary-backup system。

引用

https://en.wikipedia.org/wiki/Raft_(computer_science)

https://raft.github.io/

http://thesecretlivesofdata.com/raft/

https://raft.github.io/raft.pdf

https://www.cnblogs.com/bangerlee/p/5991417.html

https://www.bilibili.com/video/av21667358/

https://en.wikipedia.org/wiki/State_machine_replication

https://github.com/CNiceToUpp/notes/blob/master/paxos%2Craft%2Czab/paper/In%20Search%20of%20an%20Understandable%20Consensus%20Algorithm.pdf