Raft算法

uh7074 4年前
   <p>前段时间一直在学习mit的分布式课程 <a href="/misc/goto?guid=4959751063951179883" rel="nofollow,noindex">Distributed Systems</a> ,仔细阅读了raft论文,但是中间又跑去搞docker了,所以一直没有整理raft相关的文章,今天就来总结一下。</p>    <p>文章中没有多少详细的图片,但是大家可以边看文章边看 <a href="/misc/goto?guid=4959629313917510424" rel="nofollow,noindex">Raft演示动画</a></p>    <p>之前介绍的Paxos算法一直都是分布式一致性协议的标准,但是Paxos难以理解,更难以理解。于是Stanford的教授提出了Raft协议,它是一个为真实世界应用建立的协议,主要注重协议的落地性和可理解性。这里有Raft的 <a href="/misc/goto?guid=4959751064082435796" rel="nofollow,noindex">论文</a> ,大家有兴趣可以自行阅读一下。</p>    <p>Raft是为了managing a replicated log。Raft会首先选举一个leader,然后让这个leader来管理replicated log。Raft将consensus问题(也就是一致性问题)划分成三个相互独立的子问题:</p>    <ul>     <li>leader election</li>     <li>log replication</li>     <li>safety</li>    </ul>    <h2>Raft basis</h2>    <p>任何时间每个server都处于下列三个状态之一:leader,follower,或在candidate之一。在正常状态下,整个集群只会有一个leader并且其他所有server都处于followers状态下。followers是被动的,它们只会对leader的request进行反应。第三个状态candidate是用来选举新的leader的。</p>    <p>Raft以Term来划分运行时间,你可以将其理解为任期。Term以连续的整数来命名,每个Term都以一个election开始。在一次选举中,一个或多个candidate试图成为leader。如果一个candidate赢得了election,那么它就成为leader。如果一次election中没有candidate获胜,那么就进行下一个Term,重新进行election。每个Term最多只有一leader,否则进入下一个Term,这样Term就可以作为一个logical clock。</p>    <p>Raft服务器通过RPC来交互,只需要两个RPC操作,RequestVote RPCs and AppendEntries RPCs。RequestVote用于选举而AppendEntries用于leader发送请求进行relicate log entries和心跳。</p>    <h2>Leader election</h2>    <p>Raft通过心跳机制来触发leader selection。当一个服务器启动时,默认位于followers状态,并且一直持续知道它一直接受到leader的RPC请求。leader会周期性发送心跳给所有的followers。如果follower一段时间内没有接受到心跳,那么就认为当前没有leader应该开始leader selection。</p>    <p>开始election后,server将其Term进行加一,然后转变成candidate状态,并且给其他所有server发送RequestVote RPC请求来进行vote。这个过程一直持续到:server自己赢得election,其他的server赢得election,或者这个Term期间没有server获胜,进入下一个Term。</p>    <p>candidate收到半数以上server的vote就赢得了election。每个server在一个Term中只会vote一次。server基于first-come-and-first-serve的规则来进行投票。一旦某个candidate赢得了election, 就变成了leader,并且开始周期性发送心跳。</p>    <p>当等待投票时,candidate受到了其他candidate发送的AppendEntries PRC请求,如果candiate发现在包含在请求当中的Term数值大于或则等于自己的Term数值,那么该candiate主动退回到follower状态,否在拒绝该请求,继续保持candidate状态。</p>    <p>当很多server变成candidate状态进行election时,选举失败的可能性就很高了。那么每个candiate会推迟随机时间之后进入下一个Term并进行新的election。以此来避免大量的选举失败的情况发生。</p>    <h2>Log replication</h2>    <p>一旦一个leader被选举成功,它就开始处理client请求。每个client请求都包含一个需要被replicated state machine处理的命令,leader将这些命令当作一个新的entry添加到log中。然后给follower发送AppendEntries RPCs请求来复制这个log entry。当一个entry被safely relicated(在下一小结中会讲解),leader就会将entry交给state machine进行执行,并且将结果返回。</p>    <p>当一个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来执行。</p>    <p>当followers crash或则网络丢包时,leader会一直发送AppendEntries RPCs直到所有followers都存储了entry。</p>    <p><img src="https://simg.open-open.com/show/6c36743be9521fda30a772a1cd6d8524.png"></p>    <p>每个Log entry都有其唯一标识,entry中包括了 leader Term,index和要执行的comand。index是指entry在Log中的位置。Raft通过Log Machine Property来维护Log的合理性:</p>    <ul>     <li>如果两个entries在不同的logs中(存储在不同的server上)拥有相同的index和term,那么他们包含相同的command。</li>     <li>如果两个entries在不同的logs中拥有相同的index和term,那么他们之前的entries也都是一致或在内容相同的。<br> 第一条规定保证leader每个Term中的每个index最多只能创建一个entry。而第二条规定使得followers在处理AppendEntries RPCs请求时要进行一致性检测。leader在AppendEntries请求中带上了自己logs中排在新entry之前的那个entry的index和term,如果follower在自己的logs中找不到该entry,那么就拒绝添加new entry。这样就保证了第二条规定不会被违反。<br> 正常情况下,leader和followers的logs都是一致的,但是当一系列的leader crash,followers crash和election之后,followers的logs可能会被当前leader的logs多出一些entry,也可能会少一些entry。在Raft中,leader通过强迫followers的logs复制leader的logs来保持一致性。这就意味着follower logs中的冲突的entry会被重写。</li>    </ul>    <p><img src="https://simg.open-open.com/show/f61522bff9d20ea700ff0a5256fc154e.png"></p>    <p>为了一致化logs,leader的logs需要和follower的logs进行对比,找出它们之间最后一条相同的entry。然后将follower logs中那条entry之后的所有entry删除,并发送leader logs中那条entry之后的entry给follower。这些行为都发生在AppendEntries RPCs的一致性检查过程中。</p>    <p>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。</p>    <h2>Safety</h2>    <p>这一小节主要描述在leader election过程中的一些限定。这些限定保证任何一个Term的leader的logs都包含了之前Term中所有committed的entry。这也是所谓的Leader Completeness Property。</p>    <h2>Election限制</h2>    <p>Raft规定:在election过程中,new leader本身必须有之前Term中所有committed的log entry。也就是说每次election成功的leader必然包含之前所有的committed的log entry。这样保证了log的单向流动,一定是从leader到follower。</p>    <p>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约新。</p>    <h2>Committing entries from previous terms</h2>    <p>如果旧的leader在committing an entry时crash了,那么新的leader是否需要重新commit这个entry呢?但是为了简化,Raft重来不会提交之前Term的log entry。没有被committed的log entry就会被重写。</p>    <h2>Followers and candidate crashs</h2>    <p>如果followers或在candidate在接受到RPC之前crash,leader会一直重试发送RPC。如果是在接受处理之后crash,没有发送回复,leader也是会重复发送RPC,但是因为RPC都是幂等的,所以不会造成额外的影响。</p>    <h2>后记</h2>    <p>Raft的应用十分广泛,比如etcd项目就是使用Raft来保证分布式一致性的,之后我也想去研究一下etcd中Raft的实现,毕竟之前都是理论。</p>    <p> </p>    <p>来自:http://remcarpediem.com/2017/07/25/Raft算法/</p>    <p> </p>