菜鸟笔记
提升您的技术认知

Raft协议浅析

Raft协议浅析

什么是Raft协议?

  • 对于分布式系统而言,与单机系统相比优势之一就是有更好的容错性。比如当一台机器上的磁盘损坏,数据丢失,可以从另一台机器上的磁盘恢复(分布式系统会对数据做备份),集群中某些机器宕机,整个集群还可以对外提供服务。实现的方法很自然的想到的就是备份。
  • 一个系统的工作模式:接受客户端的command,系统进行处理,将处理的结果返回给客户端。由此可见,系统里的数据可能会因为command而变化。
  • 实现备份的做法之一就是复制状态机(Repilcated State Machine,RSM),它有一个很重要的性质——确定性(deterministic):如果两个相同的、确定性的状态从同一状态开始,并且以相同的顺序获得相同的输入,那么这两个状态机将会生成相同的输出,并且结束在相同的状态
      也就是说,如果我们能按顺序将command作用于状态机,它就可以产生相同的状态和相同的输出。

      那么,状态机该如何实现?见下图(来自raft协议)

  上图中,每个RSM都有一个replicated log,存储的是来自客户端的commands。每个RSM中replicate log中commads的顺序都是相同的,状态机按顺序处理replicate log中的command,并将处理的结果返回给客户端。由于状态机具有确定性,因此每个状态机的输出和状态都是相同的。
Consensus Module模块的作用是:保证每个server上Log的一致性!如果不做任何保障,直接将commad暴力写入,一旦服务器宕机或者出现什么其他故障,就会导致这个Log丢失,并且无法恢复。而出现故障的可能性是很高的,这就导致系统不可用。

  因此,raft就是Consensus Module的一个实现,是用来保障servers上副本一致性的一种算法,它是一个为真实世界应用建立的协议,主要注重协议的落地性和可理解性。

Consensus一致性

  再了解raft协议之前,首先了解一下一致性这个概念。Consensus一致性是指多个服务器在状态达成一致,但是在一个分布式系统中,因为各种意外可能,有的服务器可能会崩溃或变得不可靠,它就不能和其他服务器达成一致状态。这样就需要一种Consensus协议,一致性协议是为了确保容错性,也就是即使系统中有一两个服务器当机,也不会影响其处理过程。

Raft为了实现Consensus一致性这个目标,过程如同选举一样,参选者需要说服大多数选民(服务器)投票给他,一旦选定后就跟随其操作。在Raft中,任何时候一个服务器可以扮演下面角色之一:

  • Leader: 处理所有客户端交互,日志复制等,一般一次只有一个Leader.
  • Follower: 类似选民,完全被动
  • Candidate候选人: 类似Proposer律师,可以被选为一个新的领导人

      通常情况下(无主备切换时),一个leader其他是follower。Follower处于被动的状态,它不能发起任何请求,只能回应leader和candidate的请求。Leader处理客户端的请求,如果客户端请求发到了follower,follower负责将请求重定向到leader。Candidate是选主过程中用于选出新主。

Term

  Raft将时间划分为Term。Term可以是任意长度的时间段。Term有一个连续递增的id。每个term以选主开始,选主过程中,若干candidate尝试成为leader。选主过程成功之后进度normal operation的阶段,leader开始服务。选主可能因为选票分裂而失败,此时当前term没有leader,在下一个term继续选主。

  Term是需要持久化保存的。因为是分布式环境,所以不同的机器维护的term可能不一样,term是一个逻辑时钟(参见分布式系统下的时间 时钟 事件序 论文解读),因此,当一台机器在与其他机器通信时发现自己的term比较小,应该推进本地的term。如果一台机器发现请求方的term比较小,则要拒绝请求。如果一个candidate发现自己的term落后了,就要退回到follower。

  机器之间使用rpc通信,Raft中只有两种RPC:RequstVote和AppendEntries。RequstVote RPC用于candidate在选主期间拉票。AppendEntries RPC用于leader复制日志到follower,同时也作为主备之间的心跳RPC。RPC请求收不到任何结果时,要定时重试。为了优化性能,RPC可以并发发起。

raft协议原理:

  • Election Safty :每一个任期内只能有一个领导人
  • Leader Append-Only:leader只能追加日志条目,不能重写或者删除日志条目
  • Log Maching:如果两个日志条目的index和term都相同,则两个如果日志中,两个条目及它们之前的日志条目也完全相同
  • Leader Completeness:如果一条日志被commited过,那么大于该日志条目任期的日志都应该包含这个点,也就是说当一个新的leader产生时它一定包含着前一个leader所处理过的commited点。
  • State Machine Safety :如果一个server将某个特定index的日志条目交由状态机处理了,那么对于其他server,交由状态及处理的log中相同index的日志条目应该相同

如何保证Election Safty

  raft中,只要candidate获得多数投票,就可以成为领导人。follower在投票的时候遵循两个条件:

  1. 先到先得
  2. cadidate的term大于follower的term,或者两个term相等,但cadidate的index大于follower的index

对于选举结果来说:

  1. 如果票被瓜分,产生两个leader,这次选举失效,进行下一轮的选举
  2. 只有一个leader的情况是被允许的

      这里重要的一点是:如何保证在有限的时间内确定出一个候选人,而不会总是出现票被瓜分的情况?*raft使用了一个比较优雅的实现方式,随机选举超时(randomize election timeouts)。*这就使得每个server的timeout不一样,发起新一轮选举的时候,有些server还不是投票者;或者一些符合条件的candidate还没有参加下一轮。这种做法使得单个leader会很快被选举出来。

如何保证Log Matching

  Leader在进行AppendEntry RPCs(添加消息)的时候,这个消息中会携带preLogIndex和preLogTerm这两个信息,follower收到消息的时候,首先判断它最新日志条目的index和term是否和rpc中的一样,如果一样,才会append。

  这就保证了新加日志和其前一条日志一定是一样的。从第一条日志起就开始遵循这个原理,很自然地可以作出这样的推断。
  
  

如何保证Leader Completeness

  假设leaderU是第一个没有包含leaderT中commitT点(T

raft协议中有一个约定,不能提交之前任期内log 记录作为commit点。

  • 原因是如果在这一过程中,发生了网络分区或者网络通信故障,使得Leader不能访问大多数Follwers了,那么Leader只能正常更新它能访问的那些Follower服务器,而大多数的服务器Follower因为没有了Leader,他们重新选举一个候选者作为Leader,然后这个Leader作为代表于外界打交道,如果外界要求其添加新的日志,这个新的Leader就按上述步骤通知大多数Followers,如果这时网络故障修复了,那么原先的Leader就变成Follower,在失联阶段这个老Leader的任何更新都不能算commit,都回滚,接受新的Leader的新的更新。

选主过程

  Raft使用了心跳机制来触发选主。Server刚启动时,状态处于follower,只要follewer一直收到leader或者candidate发来的rpc,就保持为follower。Leader周期性地向follower发送心跳(用的是AppendEntries RPC,里面不带日志内容)来保持leader的权限。如果一个follower在election timeout时间内没有收到leader的心跳,follower就认为没有leader了,就会开始选主。

  开始选主时,follower先递增本地term(要持久化),然后主机状态切换为candidate。然后主机向其他发送拉票请求,同时也给自己投票。Candidate在这个状态等待,直到如下三种情况发生:
  

  • 该candidate赢得了选主
  • 其他机器成为了leader
  • 超时间内未能选主成功

      一个candidate赢得选主的判定:在相同的term内,收到了多数派的投票。在给定的term内,每台机器都只能按照先来先服务的规则投一个candidate(要持久化)。收到多数派才可能成为leader,可以避免出现双主。选主成功之后,新主向其他主机发送心跳AppendEntries RPC,宣告自己当选了。
    在选主时间内, candidate如果收到了其他主机宣告当选的心跳AppendEntries RPC且RPC中携带的term比本机维护的term更大或相等,本机就自动退为follower。
      超时时间未能内选主成功,可能是发生了选票分裂。同时有若干参与者拉票,选票分流,没有candidate能够拉倒多数派的选票。选主失败时,所有candidate递增term开始下一轮。为了减少选票分裂出现的概率,选举超时时间使用随机化的方法避开多个candidate同时拉票。
      
    Raft的选主方案的进化。一开始Raft使用的是ranking system,每个candidate都分配一个唯一的rank,低rank的主机收到高rank的主机的拉票请求,就把自己转为follower,这样rank高的就能尽快被选出来(可能在下一轮选主中)。这个方案有些微妙的可用性问题:如果高rank的主机宕机了,低rank的主机还要等超时才有机会转为candidate。这个方案调整了几次,每次调整都引入新的corner case。最后才选择了这个随机化方案。
      Raft的选主方案还要加上一些约束,以支持log replication实现。

日志同步

  Leader被选出来之后,就开始服务客户端的请求。Leader收到客户端请求之后,将命令记入日志并同步到follower。当这条日志被确认之后,就把日志对应的命令应用到状态机。如果某个follower没有收到AppendEntries RPC,leader会不停地重试,确保follower最终有全部的日志。
 日志组织发方式如下图所示:
 

  • 每条日志都记录了term值,这个值是提交这条日志的leader当时的term值。这个term值可以用以检测不一致性。
  • 当leader将日志复制到多数派的时候,这条日志就commit了。Raft保证任何commit的日志最终都会被副本的状态机执行。
  • Raft约束日志是连续commit的,leader维护最大已经commit的日志id,并将这个信息附加到AppendEntries告知follower,follower了解到之后即可将本机已有的且已经commit的日志应用到本地的状态机。
  • Raft维护了更高级别的不同主机之间的日志的一致性,简化了系统的行为、使得系统行为更加可预测、更容易保证safety。

      正常运行时,主备之间通常都是一致的,AppendEntries RPC也一直成功。但是如果有leader宕机了,就会有不一致。例如如图。
      
      
      

最上面这个是新Leader,a~f是Follower,每个格子代表一条log entry,格子内的数字代表这个log entry是在哪个term上产生的。再上面的图中x<-1,y<-2这种写法代表每一次日志记录的内容。

  主备不一致可能有如下几种情况:

  • 少了一些日志(term可能相同或者少了)比如b;
  • 多了一些未commit的日志(term可能多了也可能少了)比如d;
  • 某些term多了一些日志且某些term少了一些日志,比如f。

Raft中如何解决这些不一致呢?leader强制让follower的日志文件复制leader的日志文件,即follower上不一致的日志文件内容被覆写。新主上任之后,在和某个follower同步日志时,先确定和这个follower最后一条相同的日志,然后用leader上的内容覆盖之后不相同的部分。

  Leader确定与follower不一致点的方法:

  • leader维护一个log index,表示leader给各个follower发送的**下一条**log entry在log中的index。初始化为leader的最后一条log entry的下一个位置。
  • 然后发送AppendEntries RPC到follower。follower在收到AppendEntries之后,检查RPC中携带的leader上被追加的这条日志的前面一条日志的term和log index(logindex-1)。
  • 如果follower本地没有这条日志,就拒绝此次AppendEntries RPC,leader就能知道follower的同步点更靠前,逐渐就能知道同步点的位置。当然,实际实现时,会使用更有效率的方法。

以leader和b为例:

  • 初始化,logIndex为11,leader给b发送AppendEntriesRPC(6,10),b在自己log的10号槽位中没有找到term_id为6的log entry。则给leader回应一个拒绝消息。
  • 接着,leader将logIndex减1,变成10,然后给b发送AppendEntriesRPC(6, 9),b在自己log的9号槽位中同样没有找到term_id为6的log entry。
  • 循环下去,直到leader发送了AppendEntriesRPC(4,4),b在自己log的槽位4中找到了term_id为4的log entry。接收了消息。
  • 随后,leader就可以从槽位5开始给b推送日志了。

Safety

Election restriction(选主限制)-哪些follower有资格称为leader。

  如果不对选主加约束,那么,可能一个落后的follower被选为主,落后的那些日志可能已经commit了,要保证提交的日志匹配,就必然要有从旧主或者其他不落后的follower上拉取这些已经提交的日志。
  
Raft使用的方案是:确保包含所有commit日志的candidate才能有机会被选为leader。因为一条日志commit,必然在任意一个多数派中,至少有一台主机包含了这条日志。选举时,candidate要和至少多数派的主机通信,通信时带上自己本地的日志信息(本地最后一条的term和log index),接收消息的主机发现发送消息的candidate的日志并不比我本地更新,就拒绝投票。也就是说,candidate至少是某个多数派中拥有最新日志的主机,才能被选为leader。日志比较的原则是,如果本地的最后一条log entry的term id更大,则更新,如果term id一样大,则日志更多的更大(index更大)。

哪些日志记录被认为是commited?

  • leader正在复制当前term(即term 2)的日志记录给其它Follower,一旦leader确认了这条log entry被大多数写盘了,这条log entry就被认为是committed。如图下雨,S1作为当前term即term2的leader,log index为2的日志被大多数写盘了,这条log entry被认为是commited。

      

  • leader正在replicate更早的term的log entry给其它follower。图b的状态是这么出来的:

    • S1作为term2的leader,给S1和S2 replicate完log index=2的日志后宕机,当前状态为:

      S1 1 2 宕机

      S2 1 2

      S3 1

      S4 1

      S5 1

    • S5被选为term3的leader(由于S5的最后一条log entry比S3,S4的最后一条log entry更新或一样新,接收到S3,S4,S5的投票),自己产生了一条term3的日志,没有给任何人复制,就crash了,当前状态如下:

      S1 1 2

      S2 1 2

      S3 1

      S4 1

      S5 1 3 宕机

    • 接着S1重启后,又被选为term4的leader(接收到S1,S2,S3的投票,文中没有指出S4?),然后S1给S3复制了log index为2的log entry,当前状态如下:

      S1 1 2

      S2 1 2

      S3 1 2

      S4 1

      S5 1 3 宕机

    • 这个时候S5重启,被选为了term5的主(接收了S2,S3,S4,S5的投票),那么S5会把log index为2的日志3复制给其它server,那么日志2就被覆盖了。

    所以虽然这里日志2被majority的server写盘了,但是并不代表它是commited的。

    对commit加一个限制:主的当前term的至少一条log entry要被大多数写盘。如:c图中,就是主的当前term 4的一条log entry被majority写盘了,假设这个时候S1宕机了,S5是不可能变成主的。因为S2和S3的log entry的term为4,比S5的3大。

日志压缩

在实际的系统中,不能让日志无限增长,否则系统重启时需要花很长的时间进行回放,从而影响可用性。Raft采用对整个系统进快照行来处理,快照之前的日志都可以丢弃。

每个server独立的对自己的系统状态进行快照,并且只能对已经committed log entry(已经应用到了状态机)进行快照,快照有一些元数据,包括last_included_index,即快照覆盖的最后一条commited log entry的 log index,和last_included_term,即这条日志的termid。这两个值在快照之后的第一条log entry的AppendEntriesRPC的一致性检查的时候会被用上,之前讲过。一旦这个server做完了快照,就可以把这条记录的最后一条log index及其之前的所有的log entry都删掉。
snapshot的缺点就是不是增量的,即使内存中某个值没有变,下次做snapshot的时候同样会被转存到磁盘。

当leader需要发给某个follower的log entry被丢弃了(因为leader做了快照),leader会将快照发给落后太多的follower。或者当新加进一台机器时,也会发送快照给它。

发送快照时使用新的RPC,InstalledSnapshot。

做snapshot有一些需要注意的性能点:

  1. 不要做太频繁,否则消耗磁盘带宽。
  2. 不要做的太不频繁,否则一旦server重启需要回放大量日志,影响availability。系统推荐当日志达到某个固定的大小做一次snapshot。
  3. 做一次snapshot可能耗时过长,会影响正常log entry的复制。这个可以通过使用写时复制的技术来避免快照过程影响正常log entry的复制。

集群拓补变化

集群拓扑变化的意思是在运行过程中多副本集群的结构性变化,如增加/减少副本数、节点替换等。Raft协议定义时也考虑了这种情况,从而避免由于下线老集群上线新集群而引起的系统不可用。Raft也是利用上面的Log Entry和一致性协议来实现该功能。假设在Raft中,老集群配置用Cold表示,新集群配置用Cnew表示,整个集群拓扑变化的流程如下:

  1. 当集群成员配置改变时,leader收到人工发出的重配置命令从Cold切成Cnew;
  2. Leader副本在本地生成一个新的log entry,其内容是Cold∪Cnew,代表当前时刻新旧拓扑配置共存,写入本地日志,同时将该log entry推送至其他Follower节点
  3. Follower副本收到log entry后更新本地日志,并且此时就以该配置作为自己了解的全局拓扑结构,
  4. 如果多数Follower确认了Cold U Cnew这条日志的时候,Leader就Commit这条log entry;
  5. 接下来Leader生成一条新的log entry,其内容是全新的配置Cnew,同样将该log entry写入本地日志,同时推送到Follower上;
  6. Follower收到新的配置日志Cnew后,将其写入日志,并且从此刻起,就以该新的配置作为系统拓扑,并且如果发现自己不在Cnew这个配置中会自动退出
  7. Leader收到多数Follower的确认消息以后,给客户端发起命令执行成功的消息
异常分析
  • 如果Leader的Cold U Cnew尚未推送到Follower,Leader就挂了,此时选出的新的Leader并不包含这条日志,此时新的Leader依然使用Cold作为全局拓扑配置
  • 如果Leader的Cold U Cnew推送到大部分的Follower后就挂了,此时选出的新的Leader可能是Cold也可能是Cnew中的某个Follower;
  • 如果Leader在推送Cnew配置的过程中挂了,那么和2一样,新选出来的Leader可能是Cold也可能是Cnew中的某一个,那么此时客户端继续执行一次改变配置的命令即可
  • 如果大多数的Follower确认了Cnew这个消息后,那么接下来即使Leader挂了,新选出来的Leader也肯定是位于Cnew这个配置中的,因为有Raft的协议保证。
问题分析

这里为什么要弄这样一个两阶段协议,而不能直接从Cold切换至Cnew?

  • 这是因为,如果直接这么简单粗暴的来做的话,可能会产生多主。
    • 假设Cold为拓扑为(S1, S2, S3),且S1为当前的Leader。
    • 假如此时变更了系统配置,将集群范围扩大为5个,新增了S4和S5两个服务节点,这个消息被分别推送至S2和S3,但是假如只有S3收到了消息并处理,S2尚未得到该消息。
    • 这时在S2的眼里,拓扑依然是(S1, S2, S3),而在S3的眼里拓扑则变成了(S1, S2, S3, S4, S5)。假如此时由于某种原因触发了一次新的选主,S2和S3分别发起选主的请求:
    • 最终,候选者S2获得了S1和S2自己的赞成票,那么在它眼里,它就变成了Leader,而S3获得了S4、S5和S3自己的赞成票,在它眼里S3也变成了Leader,那么多Leader的问题就产生了。而产生该问题的最根本原因是S2和S3的系统视图不一致。