Raft算法
Raft将一致性算法分解为几个关键模块，如首领选举、日志复制和安全性。本文将基于raft论文简要分析Raft算法。
Raft是强势领袖模式，一切由领袖主导。例如，日志只能从领导者复制到其他服务器。所以领袖的选举是非常重要的一部分。
首先，介绍了raft算法的三种服务状态:
一个集群中任何时候都只能有一个领导者。
Raft使用心跳机制实现领袖选举。当服务启动时，它处于跟随者角色。需要注意的是，服务于领导的每个心跳的超时时间是随机的(150-300ms)。
如上图所示，集群中有A、B、C三个点，超时时间分别为150ms、200ms、300ms。最开始的术语编号都是0，都是跟随者角色。节点A和leader的心跳超时时间最短，所以先从跟随者状态变为候选，增加任期数。首先，他们为自己投票，并将投票信息发送到集群中的其他节点。当节点B和C收到A的投票请求时，接受A的投票请求而不投票给本阶段的其他节点，期限为1。此时节点A接受了集群中超过半数节点的投票，以1的任期成为盟主。
申诉是最简单的选举过程，有很多概念需要解释，比如为什么加班时间不一样？什么是学期编号？投票比较的规则是什么？
1.术语编号
每个领导人在选举期间都有自己的任期数，在全世界都是单调递增的数。每个节点存储当前领导者的任期号，当处于候选阶段时，发起投票时当前任期号将加1。
此外，当一个节点接收到一个比它自己的术语更高的请求时，它将把它的术语号更新到一个更高的术语号。如果当前角色是领导者，它将从领导者角色变为追随者角色。当接收到一个项数小于自身的请求时，节点会直接拒绝该请求。
2.投票比较规则
A.先到先服务:一个节点在一个任期内只能投票一次。如果节点A和B都请求节点C投票，如果节点C先投票给A，它将拒绝节点B的投票请求。
b .日志完整性:如果一个节点接受的投票信息的日志小于自己的，它会拒绝投票请求。
C.一半策略:当一个节点收到集群中超过一半节点的投票时，成为该任期的领导者，并向其他节点发送领导者心跳。
D.在等待投票时，候选人可能会从另一个声称是领导者的服务器节点接收AppendEntries RPC。如果领导者的任期数(包含在RPC中)不小于候选人的当前任期数，则候选人将承认领导者的合法地位，并返回追随者地位。
3.随机超时
如上所述，每个点与领导的心跳超时时间不同。这样做的好处是避免分票的情况，快速进行领导人选举。如果每个节点的超时都一样，就很容易分票了。如果每个节点都没有获得过半选票，就要进行下一轮选举，选举时间会很长。使用随机超时机制，正常情况下，一个时间段内只有一个节点发起投票请求。
下图是整个集群中服务角色变化的流程图。
选举出首领后，它为客户端提供服务，将接收到的指令作为新的日志条目追加到日志中，然后并行向其他服务器发起AppendEntries RPC，使它们可以复制日志条目。当日志条目被安全复制后(超过一半的节点已被复制)，领导者会将日志条目应用到其状态机(状态机执行指令)，然后将执行结果返回给客户端。如果跟随者崩溃或者运行缓慢，或者网络丢包，那么领导者会一直尝试AppendEntries RPC(即使他已经回复了客户端)，直到所有跟随者最终存储了所有日志。
上图显示了日志的格式，一个日志条目包含三个部分。
领导者通过AppendEntries RPC将日志复制到其他节点。
AppendEntries RPC:
接收器实现:
上诉是AppendeEntries RPC参数的接受过程。引入$ term和leaderId非常简单，但是prevLogIndex和prevLogTerm的作用是检查日志的一致性。如果跟随者在其日志中找不到具有相同索引位置和术语编号的条目，他将拒绝新的日志条目。一致性检查就像一个归纳步骤:首先，空日志状态必须满足日志匹配属性，然后一致性检查确保日志扩展时的日志匹配属性。因此，每当AppendEntries RPC成功返回时，领导者就知道跟随者的日志必须与自己的日志相同(从第一个日志条目到最新的条目)。
在正常操作期间，领导者和跟随者的日志是一致的，因此AppendEntries RPC的一致性检查永远不会失败。但是，领导者的崩溃会使日志处于不一致的状态(旧领导者可能没有完全复制其日志中的所有条目)。以下情况:
在Raft算法中，领导者通过强制追随者复制其日志来解决不一致性问题。这意味着跟随者中与领导者冲突的日志条目将被领导者的日志条目覆盖。
领导者为每个追随者维护nextIndex，指示领导者将发送给追随者的下一个日志条目的索引。当选择了新的领导者时，领导者将nextIndex的所有值初始化为他的最后一个日志条目的索引加上1。如果跟随者的日志与领导者的日志不一致，那么AppendEntries RPC中的一致性检查下次将会失败。在被追随者拒绝后，leaer将减少nextIndex值并重试AppendEntries RPC。最终，nextIndex将使领导者和追随者的日志在某个点上一致。此时，AppendEntries RPC将成功，删除follower中与leader冲突的所有日志条目，然后在leader中追加日志条目(如果有)。一旦AppendEntries RPC成功，跟随者的日志将与领导者的日志保持一致，并在学期的剩余时间内保持一致。
本机简单介绍一下raft的领袖选举和日志复制。当然，raft还有本文没有介绍的其他特性。建议阅读raft的论文，对raft有一个完整的了解。
我之前关于zab协议的文章分析了zookeeper的ZAB协议，在这里我比较一下两者的异同。
最后/blob/master/raft-zh _ cn.md。