Raft算法

 前段时间一直在学习mit的分布式课程Distributed Systems，仔细阅读了raft论文，但是中间又跑去搞docker了，所以一直没有整理raft相关的文章，今天就来总结一下。
 文章中没有多少详细的图片，但是大家可以边看文章边看Raft演示动画
 之前介绍的Paxos算法一直都是分布式一致性协议的标准，但是Paxos难以理解，更难以理解。于是Stanford的教授提出了Raft协议，它是一个为真实世界应用建立的协议，主要注重协议的落地性和可理解性。这里有Raft的论文，大家有兴趣可以自行阅读一下。
 Raft是为了managing a replicated log。Raft会首先选举一个leader,然后让这个leader来管理replicated log。Raft将consensus问题(也就是一致性问题)划分成三个相互独立的子问题：

• leader election
• log replication
• safety

Raft basis

 任何时间每个server都处于下列三个状态之一：leader,follower,或在candidate之一。在正常状态下，整个集群只会有一个leader并且其他所有server都处于followers状态下。followers是被动的，它们只会对leader的request进行反应。第三个状态candidate是用来选举新的leader的。
 Raft以Term来划分运行时间，你可以将其理解为任期。Term以连续的整数来命名，每个Term都以一个election开始。在一次选举中，一个或多个candidate试图成为leader。如果一个candidate赢得了election,那么它就成为leader。如果一次election中没有candidate获胜，那么就进行下一个Term,重新进行election。每个Term最多只有一leader，否则进入下一个Term,这样Term就可以作为一个logical clock。
 Raft服务器通过RPC来交互，只需要两个RPC操作，RequestVote RPCs and AppendEntries RPCs。RequestVote用于选举而AppendEntries用于leader发送请求进行relicate log entries和心跳。

Leader election

 Raft通过心跳机制来触发leader selection。当一个服务器启动时，默认位于followers状态，并且一直持续知道它一直接受到leader的RPC请求。leader会周期性发送心跳给所有的followers。如果follower一段时间内没有接受到心跳，那么就认为当前没有leader应该开始leader selection。
 开始election后，server将其Term进行加一，然后转变成candidate状态，并且给其他所有server发送RequestVote RPC请求来进行vote。这个过程一直持续到：server自己赢得election,其他的server赢得election,或者这个Term期间没有server获胜，进入下一个Term。
 candidate收到半数以上server的vote就赢得了election。每个server在一个Term中只会vote一次。server基于first-come-and-first-serve的规则来进行投票。一旦某个candidate赢得了election, 就变成了leader,并且开始周期性发送心跳。
 当等待投票时，candidate受到了其他candidate发送的AppendEntries PRC请求,如果candiate发现在包含在请求当中的Term数值大于或则等于自己的Term数值，那么该candiate主动退回到follower状态，否在拒绝该请求，继续保持candidate状态。
 当很多server变成candidate状态进行election时，选举失败的可能性就很高了。那么每个candiate会推迟随机时间之后进入下一个Term并进行新的election。以此来避免大量的选举失败的情况发生。

Log replication

 一旦一个leader被选举成功，它就开始处理client请求。每个client请求都包含一个需要被replicated state machine处理的命令，leader将这些命令当作一个新的entry添加到log中。然后给follower发送AppendEntries RPCs请求来复制这个log entry。当一个entry被safely relicated(在下一小结中会讲解)，leader就会将entry交给state machine进行执行，并且将结果返回。
 当一个log entry可以被安全的交给state machine处理时，我们认为它是committed的。Raft保证所有committed的log entry一定是持久化的，并且一定被state machine执行。Log entry是committed一旦该entry在大多数follower上被replicated。一旦一个entry被committed,那么在它之前的所有log也是committed的。Leader会随时关注最大的committed的log的index,并在AppendEntries RPCs请求中携带该信息，这样follower就能知道哪些entry被committed，它们就会将其提交给自己的state machine来执行。
 当followers crash或则网络丢包时，leader会一直发送AppendEntries RPCs直到所有followers都存储了entry。

 每个Log entry都有其唯一标识，entry中包括了 leader Term，index和要执行的comand。index是指entry在Log中的位置。Raft通过Log Machine Property来维护Log的合理性：

• 如果两个entries在不同的logs中(存储在不同的server上)拥有相同的index和term,那么他们包含相同的command。
• 如果两个entries在不同的logs中拥有相同的index和term,那么他们之前的entries也都是一致或在内容相同的。
   第一条规定保证leader每个Term中的每个index最多只能创建一个entry。而第二条规定使得followers在处理AppendEntries RPCs请求时要进行一致性检测。leader在AppendEntries请求中带上了自己logs中排在新entry之前的那个entry的index和term,如果follower在自己的logs中找不到该entry,那么就拒绝添加new entry。这样就保证了第二条规定不会被违反。
   正常情况下，leader和followers的logs都是一致的，但是当一系列的leader crash，followers crash和election之后，followers的logs可能会被当前leader的logs多出一些entry,也可能会少一些entry。在Raft中，leader通过强迫followers的logs复制leader的logs来保持一致性。这就意味着follower logs中的冲突的entry会被重写。

 为了一致化logs,leader的logs需要和follower的logs进行对比，找出它们之间最后一条相同的entry。然后将follower logs中那条entry之后的所有entry删除，并发送leader logs中那条entry之后的entry给follower。这些行为都发生在AppendEntries RPCs的一致性检查过程中。
 leader会每个follower维护一个nextIndex来记录发送给这个follower的下一条log entry的index。nextIndex初始化为leader logs的最后一条entry之后的index。如果follower的logs和leader的logs不一致，那么AppendEntries RPCs的一致性检查就会失败。leader发现自己的请求被follower拒绝了，那么就减少该follower的nextIndex然后再次发送AppendEntries请求。最终nextIndex就会变成二者log中最后一个一致的entry的index。当上述情况发生之后，AppendEntries请求就会成功，就会删除follower中多的entry和添加缺少的entry。

Safety

 这一小节主要描述在leader election过程中的一些限定。这些限定保证任何一个Term的leader的logs都包含了之前Term中所有committed的entry。这也是所谓的Leader Completeness Property。

Election限制

 Raft规定：在election过程中，new leader本身必须有之前Term中所有committed的log entry。也就是说每次election成功的leader必然包含之前所有的committed的log entry。这样保证了log的单向流动，一定是从leader到follower。
 Raft通过election vote过程来保证上述限制。一个candidate必须得到集群中多于半数的server的vote，而每个committed的log entry一定也会存在于多于半数的server的logs中。也就是说在RequestVote RPC中包含了candidate自己logs中最后一个committed的log信息，接受到该请求的server会将其和自己log中最后一个committed的log进行对比，如果自己的log晚于candiate的，那么就同意该candiate成为leader,否在拒绝。这样的话，没有包含所有committed log entry的candidate就一定不会得到超过半数的server的vote。Raft根据entry的term和index来确定每个entry的先后顺序。较大term的log entry比较新，如果log entry的term一致，那就是越大的index约新。

Committing entries from previous terms

 如果旧的leader在committing an entry时crash了，那么新的leader是否需要重新commit这个entry呢？但是为了简化，Raft重来不会提交之前Term的log entry。没有被committed的log entry就会被重写。

Followers and candidate crashs

 如果followers或在candidate在接受到RPC之前crash，leader会一直重试发送RPC。如果是在接受处理之后crash，没有发送回复，leader也是会重复发送RPC,但是因为RPC都是幂等的，所以不会造成额外的影响。

后记

 Raft的应用十分广泛，比如etcd项目就是使用Raft来保证分布式一致性的，之后我也想去研究一下etcd中Raft的实现，毕竟之前都是理论。