读论文《In Search of an Understandable Consensus Algorithm》 --- raft (1)

前言

  最近读了raft共识算法的论文,对其有更深且进一步的理解。raft是一种用来管理复制日志的一致性共识算法。它的作用跟Paxos相同,并且效率差距也不大。但是,raft最大的特点就是容易理解。这才得以让raft在工程实践里面,大规模应用。

  按照我个人的理解,让一个集群里面的服务器保持一致性或者说达成某种共识,实质上就是让log/command在所有服务器上都按照同一种顺序被执行。raft为了简化这个设计,参考了gfs选出了一个master,让其他所有服务器都服从master的执行顺序。

  为了减少复杂性,raft把一致性共识的关键leader选举,日志复制,安全性,集群配置更新,这几部分分割开来。下面的篇幅我们来讨论一下算法的种种细节

一致性共识算法

规则

  raft是如何实现一致性共识的?它是通过选举出一个leader,然后让其负责协调集群的日志复制工作。当其他的follower收到日志之后,便可以在合适的时机,把log里面的command作用到自己的状态机里面。

  上面已经提到过了,跟gfs一样,让一个master协调日志的顺序,这样做会简化很多设计(不然的话要加很多复杂的措施)。显然,在分布式的系统当中不得不考虑系统的容错性还有网络等问题,这些因素都会造成该集群中leader不可通信的情况。为了集群的高可用性,这时候就必须选举出一个新的leader

  为了达成共识,需要遵守一些规则进行的。

state

image-20220103150743291

这里的状态是所有在集群里面的server都要有的

  • currentTerm:这里是server存储,目前它已知的最新的term
  • voteFor:当选举发生时,candidate向所有人请求投票,这个标记着投票给哪个candidate
  • **log[ ]**:就是log-entry,里面的内容包括该条日志包含的command和term(标记该log在哪个term里main生成)还有logIndex(一般情况,这是一个单调递增的)

image-20220103151942895

这里的标识是用来协调日志的:

  • commitIndex:服务器缓存日志的记录,标记该server已经缓存到了哪条日志,有了该标识方便master发送下一条log
  • lastApplied:标记着最新一条应用到状态机的index

image-20220108130032476

用来维护该发送哪条日志的

  • nextIndex[ ]:nextIndex[i]表示,要发送给follower(i)的下一条日志,初始化的值是leader最新的日志+1

  • matchIndex[ ]:matchIndex[i]表示,已经复制到follower(i)的日志,初始值是0,单调递增

AppendEntried RPC

  这是一个RPC接口,被master调用,用来向follower进行日志的复制,还有进行heart beat

image-20220103154050554

这里是该函数的入参

  • term:调用RPC接口时,会把leader目前的term传过去
  • leaderId:我也不知道干啥的…后面论文中好像也没看到具体的应用
  • prevLogIndex,prevLogTerm:leader追加的该条日志的上一条日志**(下面统一叫prevLog)他的lndex还有term。这里是为了实现Log Complete Property**
  • **entries[ ]**:跟上面的logEntries[ ]一样
  • leaderCommit:目前leader最新的commit-index

函数的返回值:

  • term:每次Leader和follower进行交互的时候,都会比较他们的term,这样就能方便互相都能及时进行更新
  • success:表示追加是否成功,这里不想解释了看上面的英文吧

image-20220103155638087

该接口的一些细节:

(1)如果 当前server的term大于leader的term(该leader可能是以前的leader),那么显然就该拒绝这次追加请求

(2)如果 当前server的日志里面没有包含leader的prevLog,那么就拒接这次追求请求,并让leader把logIndex-1再进行重试。这样是为了在日志的序列里面找到,follower是从哪条日志开始与leader不一致的。这个机制保证了,Log Complete Property

(3)如果 追加日志时发生了冲突了,通常情况是同一个Index但是Term不一样,代表其中必然有一个是old leader产生的。因此,要删除old leader产生的还有该日志后面的日志

(4)follower追加没有缓存的记录,只有prevLog有包含

(5)这里没想明白为啥要做这个 leader和follower commitIndex的判断,到时候再看看

RequestVote RPC

  这是一个Candidate调用的接口,用来收集选票来达成leader的选举

image-20220103162625445

接口函数的入参:

  • term:candidate的term,用来辨别是否要响应该投票
  • candidateId:记录投票给谁,对用voteFor
  • lastLogIndex,lastLogTerm:candidate最新的log,这个是作用update - to - date机制的,是决定是否投票的限制

接口的返回值:

  • term:在RPC交互之后,用来更新term
  • voteGranted:表示调用的candidate是否得到选票

image-20220103164055533

接口得到一些细节:

(1)跟上面的差不多,这里是为了比较是否是old term,如果是就要拒绝该请求

(2)如果该follower还没有投票,并且candidate的最新日志比该follower的要大,就证明candidatefollower更加up - to -date,这样把票投给它

(3)其实不仅如此,还有一个限制。有时候只有一个follower断开了和leader的连接,这时候该follower会成为candidate并发起一次选举。但是别的follower都没有问题。所以,只要别的follower确认leader还在存活,就拒绝该次投票请求。

Rule for server

image-20220108121000192

(1)是把缓存的log / command添加到状态机的规则,lastApplied表示最新添加到状态机的日志索引,只要缓存索引 > 已经添加的索引,就表示可以继续该过程(add log to state machine)

(2)如果,收到一个RPC request,该请求中所携带的term比自身服务器记录的term还要大,则证明该服务器可能错过了某些时候的选举过程,因此需要重新设置term还有回到follower状态(如果服务器先前是leader)

image-20220108121905228

(1)follower只会回复来自他们两个的rpc请求,并且follower不会主动调用请求。

(2)如果某个follower长时间没有收到来自leader的heartbeat,那么follower就会转变成candidate发起一次选举,等待成为leader

image-20220108122938660

(1)leader由选举产生,当选出一个leader之后,要发出一个heartbeat来向集群传递,新的leader已经出来了。

(2)客户端的命令会先转发给leader,然后leader缓存该客户端请求到自己的local log,等到该请求应用到了state machine里面时,便会回复给到客户端。 (这里这个过程其实还有一点限制,下民的篇幅在展开细说)

(3)在向follower同步日志的过程里面,如果最新的日志索引 > 要给follower发送的下个日志的索引,那么就发送日志。**如果向follower追加日志失败,证明prvLog并不匹配,因此master会把nextIdx -1 然后重试追加日志的过程。

(4)如果存在一条日志索引N,N大于leader的commitIndex,且该日志索引N已经存储在大部分服务器上面。那么leader把其commitIndex设置为N。 (如果加了某个限制条件之后,该情况久不会发生,下面有讲解)

Five basic properties

image-20220108131654159

(1)选举安全性质:每在一个term中,只有一个leader能够被选出来

(2)只有leader能追加日志:不解释了

(3)日志比较规则:如果两条日志它们的term和index都是一样的话,那么它们就是同一条日志

(4)日志完整性:如果leader中的某条日志已经提交到了某个follower上,那么该条日志前面的所有日志都已经被提交到了follower上,不会出现日志空洞,缺失日志的情况(除非是磁盘问题)

(5)状态机的安全:先不解释,后面会细说

Raft Basic

奇数节点

  在一个raft集群中,有一个很重要的原则就是,集群里面的节点个数必须是基数的,通常情况采用的是3 / 5。 因为只有奇数才能达成majority,偶数就没有这种效果,因为可能出现五五开的场景。

  在通常情况下,当一个决策(日志的提交,选举leader),只要该决策被大部分的节点承认,那么就可以把结果返回给外界。采用了这种majority的机制,有以下的好处:

  • 首先,从性能的角度来看,这种majority显然要不等待所有节点同步要高
  • 其次,因为有majority,这样能够保证在相邻的两次决策,必然存在一个节点都commit了两次决策。

决策继承

节点的三种状态

  集群的所有节点只处于以下三种状态之一:Follower,Candidate,Leader。并且正常的情况下,只会有一个Leader,并且其他剩余的节点是Follower

  在这之中,Leader负责处理所有的客户端请求;Follower只会被动地执行Leader 或 Candidate的rpc请求,并不会自己主动地去做一些其他的事情;Candidate,当某个Follower觉得集群可能出现问题的时候,就会转变进入该状态,发起一次选举,保证系统的正常运转。

​ 下面是,集群的状态机转换,有几个特别的点我们需要注意:

状态转换

  • Follower只会在超时的情况下转变状态,进入Candidate
  • Candidate在一次选举中,获得大部分选票,就会成为新的Leader
  • Candidate在发现一个大于自己的Term或者是一条声明(某个节点赢得了选举,成为了Leader),则进入Follower状态。
  • Leader只有在收到一个更大的Term才会转变状态,变为Follower

Term

  term是一个逻辑上单调递增的序列,并且该序列是与Leader election捆绑在一起的,是用来标记着该Leader是由第几次选举产生的。

  每一次Leader election都会产生一个term,在一次选举中可能会有一个或多个候选人,若是一次选举中某个节点成为了Leader,那么就会用该次选举的term作为ConcurrentTerm,去发送heartbeat让剩余的节点重新成为Follower

  但是,一次选举中可能会出现多个候选人,很可能会出现票数被多个候选者平均掉了,因此会出现没有任何一个节点能够获得大部分的票数。那么这种情况,要怎么进行处理呢?继续用该Term发起一次选举吗?

  在Raft中,允许某次选举中没有选出Leader当一次选举因为票数分散导致选举不出一个Leader,它会把term + 1然后重新发起一次选举。在论文中,作者并没有说明为什么要这样做,但是我猜测Raft的设计者是这样考虑的,如果一次再发起一次选举,仍就是使用上一次选举的term的话,那么就无法再次收获票数了。因为Follower已经记录了在该Term的选举中投过票了。

term divdied

  由于篇幅问题,这篇文章就先介绍这些内容。关于Leader electionlog replicate的内容放在下一篇文章