MIT-6.824 Raft协议

释放双眼,带上耳机,听听看~!

摘要

raft是一种比paxos容易理解的一致性算法,实现起来比paxos简单许多。本文前部分描述算法的细节,后部分尝试探讨下该算法的原理。

算法描述

raft算法之所以简单的原因之一是它将问题分解成三个子问题,分别是:

  1. Leader选举
  2. Log复制
  3. 安全性保证

概述

raft协议中每个server都要维护一些状态,并且对外提供两个RPC调用分别是RequestVote RPC和AppendEntries RPC用于选举和log复制。
要想理解raft,其实就是搞明白:

  1. leader和follower需要维护哪些变量,每个变量的含义
  2. leader什么时候发送AppendEntries RPC,携带哪些参数,follower收到请求后做什么?leader收到响应后做什么?
  3. candidate什么时候发送RequestVote RPC,携带哪些参数,follower收到请求后做什么?candidate收到响应后做什么?

状态:

RequestVote RPC

AppendEntries RPC

raft所有的操作都是为了保证如下这些性质。

raft保证的性质

  1. Election Safety: at most one leader can be elected in agiven term.
  2. Leader Append-Only: a leader never overwrites or deletes entries in its log; it only appends new entries.
  3. Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.
  4. Leader Completeness: if a log entry is committed in agiven term, then that entry will be present in the logs of the leaders for all higher-numbered terms.
  5. State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.

暂时可以先不看,需要知道的是raft所有的规则都是为了保证上面的这些性质,而这些性质又是保证raft正确的前提。

Leader选举

Election Safety性质说的在某个term中最多只能选出一个leader。
有如下这些规则:

  1. raft将时间划分为term,每个term都有一个number,每个term以选举一个leader开始。
  2. 每个server有三种状态:leader, follower, candidate。
  3. 作为follower:有一个称为election timeout的倒计时,如果在倒计时内没有收到有效的AppendEntries RPC,将转换为candidate,增加自己的term number,投自己一票,然后通过RequestVote RPC通知集群中的其他server进行投票。当半数以上的RequestVote RPC返回true后,这个candidate将转换为leader。
  4. 某个server收到RequestVote RPC后如何确定要不要投赞同票?同时满足以下三个条件则投赞同,RequestVote RPC返回成功:
    1. 在当前周期内还没有投过票
    2. candidate中term不小于自己的term
    3. \"选举限制\":想要获得投票,candidate的logs必须比当前follower的logs更up-to-date。如何比较两个logs的up-to-date程度?最后一个log entry的term大的更up-to-date, 如果term一样,index越大越up-to-date。(论文5.4.1节)
  5. 作为leader:周期性的发送AppendEntries RPC。

Log replication

Entry格式

Logs由Entries组成,每个Entry包含一个term和命令,格式如下:

Entry如果已经确定可以安全apply到状态机的情况下,将被标志为commited。看上面state图中,每个server都维护两个变量commitIndexlastApplied。这两个变量都是初始化为0,比如Figure 6中leader的commitIndex就是6,这个值会在
AppendEntries RPC中以leaderCommit参数通知followers修改自己的commitIndex。

commitIndex和lastApplied有什么区别呢?lastApplied总是<=commitIndex,commitIndex表明的是到commitIndex为止可以被apply,lastApplied表明的是到lastApplied为止已经被apply。

什么情况下Entry可以被commit?满足以下两个条件:

  1. A log entry is committed once the leader that created the entry has replicated it on a majority of the servers.(leader将该entry拷贝到大部分server中)
  2. 不能commit term比当前leader的term小的Entry。这里不是很好理解,论文在5.4.2节给出了解释。
    如下图:

    (a):S1是leader(term=2),entry 2只拷贝到了S2就奔溃了。
    (b):S5成为新的leader(term=3),并且接收了entry 3,但是还没进行拷贝也崩溃了。
    (c):S1重新成为leader(只是term=4),并且将entry 2拷贝到了S3。如果没有条件2的限制,只看条件1,Entry 2已经被复制到了大部分的server中,就可以被commit了。那么问题来了,如果Entry 2被commit后S1又奔溃了,这时S5重新成为leader(根据上文给出的选举规则,S5最后一个Entry的term是3,可以获得S2, S3, S4和自己的投票,所以可以成为leader),并将Entry 3拷贝到其它的server(情况(d)),并且commit,这样之前commit的Entry 2就被覆盖了,这是绝对不允许的,已经被commit的Entry不能被覆盖。再次回到情况(c),这时如果S1不仅复制了Entry 2还复制了Entry 4(term=4)(情况(e)),这种情况下同时满足条件1和条件2,所以可以commit Entry 2和Entry 4,因为和之前不同的是,如果S1现在奔溃了,S5不可能成为leader(S5的最后一个Entry的term=3,S1, S2, S3都会拒绝投票,因为它们的logs更up-to-date),也就不可能出现commit的Entry被覆盖的情况。

这个图画的有点歧义,我总结下,(c)如果不考虑条件2的限制,可能会出现(d),(d)是不允许出现的。(c)如果同时考虑条件1和条件2,那么可能出现(e),(e)是合法的,绝不可能出现(d)这种情况。所以条件2是必要的。

日志拷贝的过程

  1. leader接收客户端的Entry,将Entry添加自己的logs中。
  2. leader周期性使用AppendEntries RPC将新的entry备份到其它server。
  3. follower收到AppendEntries RPC后做什么?进行一致性检查。根据参数中的prevLogIndex,检查自己的log的prevLogIndex处的Entry的term和参数中的prevLogTerm是否相同,如果相同则将参数中的entries拷贝到自己的log中,否则返回false,leader收到响应后如果发现是false,调整参数然后重新发送AppendEntries RPC。至于怎么调整参数见论文5.3节。

不严格的正确性解释

论文中指出raft正确性已经使用TLA+ specification language进行了证明,顺便搜了下这个TLA+ specification language,由Leslie Lamport发明,用来验证设计的正确性的语言,这个Leslie Lamport也是NB的一塌糊涂,Paxos算法也是他设计出来的。我没有仔细研究严格的证明,只是以一种不严格的方式试图解释下为什么raft可以保证一致性。

raft中所有的log都是由leader流向follower的,所以你leaader首先得保证拥有所有的committed log吧,这就是Leader Completeness属性。那么如何保证Leader Completeness属性呢。我认为以下这些规则保证了该属性:

  1. Entry需要被大部分server接收才能被commit。
  2. leader需要大部分server投赞成票才能成为leader。
  3. \"选举限制\":想要获得投票,candidate的logs必须比当前follower的logs更up-to-date。

可以用反证法来证明:
假设Leader Completeness属性不成立,term T的leader(T) commit了一个Entry,但是新的term U的leader(U)没有包含该Entry。
leader(T)已经commit了该Entry,所以该Entry肯定被大部分server接受了,leader(T)成为leader肯定收到了大部分server的投票,那么必定存在一个server既接受了该这个Entry也投了leader(T)一票。显然该server包含的log比leader(T)的要up-to-date,所以和规则3矛盾,所以假设不成立,Leader Completeness属性成立。

保证了源头log的正确性后,拷贝过程中也要保证和leader的log一致。Log Matching属性保证了这一点,该属性描述的是:如果两个server中logs中的某个index对应的log entry的term相同,那么这个index以及之前对应的log entry都应该保证一样。一致性检查规则可以保证该属性。

raft这些性质中最重要的就是保证State Machine Safety属性,该属性描述的是任何一个server在某个index apply一个Entry,其它server不会在该index处apply一个不同的Entry。Leader Completeness + Log Matching可以推出State Machine Safety

人已赞赏
随笔日记

《SpringMVC从入门到放肆》十四、SpringMVC分组数据校验

2020-11-9 3:57:01

随笔日记

开箱即用Bumblebee独立部署搭建webapi网关详解

2020-11-9 3:57:03

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索