0%

6.824 2018 Lecture 6 Fault Tolerance Raft

Readings - In Search of an Understandable Consensus Algorithm (Extended Version) (Section 6 to end)论文

集群成员变更

实际应用中,常常会有配置变更的需求,即:成员变更。手动的方式有下面两种,

  • 把集群整体下线,配置修改完毕以后再上线是可行的,但会造成服务不可用。
  • 新server可以通过获取其ip来替换集群成员,需要保证被替换的server不会再加入集群。

但这两个方式都有明显的弊端,且任何手动的步骤都有引起错误的可能。

配置切换需要保证安全性,在同一个term内,集群不能够同时存在两个leader。由于无法一次性原子的切换所有server的配置,一次增减多个server并直接切换配置可能会出现disjoint majorities的情况。

raft变更的方案有两种:

  1. single-server change
  2. 使用joint consensus

single-server change

每次增减一个server。

配置的变更
具体变更过程如下,

  1. leader收到变更请求,AppendEntries RPC按新配置发送$C_{new}$。
  2. 每个server收到$C_{new}$后立即生效
  3. 新配置下,$C_{new}$复制到大多数server,则达成committed。
    • 此时,就算有剩下的server未得到新配置,也不会构成多数派,
    • 且,未得到新配置的server也不被选举为leader。

$C_{new}$提交后,

  1. leader可以响应client,告知本次配置变更已经完成。
  2. 如果配置是移除一个server,那么这个server可以下线了。
  3. 可以开始下一次配置更新。

安全性
-w543

总共有四种情况:

member change 变更后达成disjoint majorities的条件
奇数个成员,增加一个 2k+1 -> 2k+2 old = k+1, new = k+2
奇数个成员,减少一个 2k+1 -> 2k old = k+1, new = k+1
偶数个成员,增加一个 2k -> 2k+1 old = k+1, new = k+1
偶数个成员,减少一个 2k -> 2k-1 old = k+1, new = k

任意一种情况对应的条件都是不可能同时达成的,因为要求的成员数目都大于真正的成员数目,不会产生同一个term两个leader的现象。换句话说,旧配置集群与新配置集群的任意多数派必然有交集,即:至少存在一个voter(接受旧leader的$C_{new}$,并且为新leader投票),不会出现disjoint majorities。

因此增减一个server情况,直接切换配置是安全的。

这个交集也保证了在变更配置的过程中,在$C_{old}$中、以及变更期间复制的日志,最后一定会出现在$C_{new}$。

何时开始下一次变更
能够开始下一次配置更新的前提是当前的配置已经commit,否则无法保证安全性。如果server在$C_{new}$commit以后才使用$C_{new}$,会带来很多不必要的、额外的维护工作,

  1. leader很难知道旧配置集群的多数派使用$C_{new}$的时间。
  2. 需要跟踪哪些server知道了commit,且做持久化。但这些是raft本身不具备的功能。
  3. 如果leader改变了,那么需要移除$C_{new}$的entry,此时,server还需要准备回滚到上一个配置。

majority的是对谁而言的
对于选举和append entry,都是仅由调用方来判断是否达成多数派,接收方不负责,否则会存在类似“鸡生蛋蛋生鸡”的问题。

可用性
配置变更给保证集群的可用性带来了几个问题。

  1. Catching up new servers
    -w517

    一个新server加入集群,新server通常并不包含任何entry,那么可能需要花费较长的时间来同步日志。在这段时间,集群更容易出现不可用的问题。例如:3->4,此时要求的majority是3,但是s3挂了。

    为了最小化不可用的出现,需要保证不可用的时间在一次election timeout内

    -w530

    具体方法是,

    • 新加入的server先作为non-voting成员。
    • 复制到新server的过程分为多个round,每个round都复制leader所有的entry。
    • 当前复制的round内,leader可能又有新的entry了,下一个round会进行复制。
    • 在固定round内(例如:10),如果最后一个round的时间 < election timeout,此时假设不存在更多的entry会导致明显的不可用,添加新server。
    • 否则leader终止变更配置。
  2. Removing the current leader
    如果使用joint Consensus,或没有leadership transfer的情况下,需要一个leader下线的方法:旧leader等到$C_{new}$ commit以后让位(转变为follower状态)。

    在commit之前,当前leader管理集群不包含leader自己,复制和投票的时候不把自己算入majority。

  3. Disruptive servers
    被排除在$C_{new}$之外的server,由于不再收到heartbeat,会不断的发起投票。虽然新选出的leader始终会出现在$C_{new}$中,但是这干扰了集群正常的工作。

    第一个思路是引入一个Pre-Vote阶段,在发起选举前,检查自己是否有成为leader的资格,即:candidate的log比大多数server更新。但并不总是有效。例如:{ABCD}->{ABC}的时候,A是Leader,在尝试复制$C_{new}$到BC的时候,D可能发起了Pre-Vote,D的log相对于BC足够新,可以获得BC的投票成为leader。因此检查log的方式是不可行的。

    raft使用的方式是,如果一个server获得上一次heartbeat的时间在最小election timeout内,这个server收到RequestVote时就不更新term或投票。

    如果确实需要发起选举,例如:进行leadership transfer的时候,可以用一个标志位来区分。

bug in single-server change
如果配置变更是在同一个term内完成的,那么不会有问题。但如果出现在跨term且并发的配置变更,就不一定了。

例如先后增减一个server,具体过程如下,
-w630

2中,s1把D复制到s1和s5然后挂了,接着s2接受s2、s3、s4的投票(使用C判断majority)成为term2的leader。5中,s2把E复制到s2和s3,并标记为committed(使用E判断majority)。然后s1恢复,接受s1、s4、s5的投票(使用D判断majority)成为term3的leader,继续复制D,最后在7中覆盖已提交的E。

这个问题类似提交上一个term的entry,解决方法是一样的,leader当选以后,直到当前term的entry提交以后,才能开始下一次配置变更。可以通过append一个no-op entry来实现。

原文的single-server change保证了,在同一个term内不会出现未提交的configuration entry。这个patch保证了,来自先前term未提交的configuration entry永远不会被提交。

回到前面的例子,3中s2成为term2的leader以后立即append no-op entry,此时使用C判断majority,假设复制到s2、s3、s4的index 2。接着s2继续把E复制到s2和s3。如果接下来s1恢复并发生了选举,s1不可能成为leader,因而避免了已提交的E被覆盖的情况。

使用joint consensus

这个方法并不建议在工程中使用,更简单的single-server change足以将集群变更为任何期望的配置。

-w344

joint consensus
joint consensus状态混合了新旧配置,允许每个server在不同的时间安全地切换配置,且在这个过程中能持续提供服务,这个状态中,

  • entry会被复制到所有新旧配置。
  • 来自任何配置的机器都可以被选举为leader。
  • 选举和append的majority,需要分别来自新旧配置。

相比single-server change,joint consensus引入了一个中间的entry $C_{old,new}$,具体过程是,

  1. 将新旧配置存储到$C_{old,new}$,并复制,进入joint consensus状态。
  2. 每个server收到$C_{old,new}$后立即生效,leader使用$C_{old,new}$来判断是否提交。
    $C_{old,new}$复制的过程中,如果leader挂了,那么新的leader可能在$C_{old,new}$或$C_{old}$中选举出。无论leader来自哪个配置,$C_{new}$不能单方进行决策。
  3. $C_{old,new}$提交后,leader可以复制$C_{new}$。
    一旦$C_{old,new}$提交,$C_{new}$或$C_{old}$都不能单方进行决策。
  4. leader使用$C_{new}$来判断是否提交,提交后,完成配置变更。

安全性
在joint consensus过程中,发生选举时,可能从以下情况选出leader(按joint consensus的步骤顺序列举),

  1. 来自$C_{old}$,log不包含$C_{old,new}$。
  2. 来自$C_{old}$,log包含$C_{old,new}$。
  3. 来自$C_{new}$,log包含$C_{old,new}$。
  4. 来自$C_{new}$,log包含$C_{new}$。

而任何两个leader的组合都是不可能同时出现的。

leader组合 不可能出现的原因
1+1 or 4+4 选举规则限制
1+2 先看2的选举,需要分别来自新旧配置的多数派,此时已经不能再从$C_{old}$中选举1
1+3 类似1+2
1+4 a. 先看4,既然$C_{new}$出现了,那么$C_{old,new}$肯定提交了,这个提交需要分别来自新旧配置的多数派,因此$C_{old}$中不包含$C_{old,new}$的server无法选举为leader
b. $C_{new}$是在$C_{old,new}$提交后才复制,如果选举出4,1就不会存在
2+2 类似1+2
2+3 类似1+2
2+4 类似1+2
3+3 类似1+2
3+4 类似1+2

因此不会出现disjoint majorities的情况。

是否受single-server change的bug影响
不受。

日志压缩

raft的日志随着客户端不断的请求增长。一旦entry已经提交并执行,那么中间的状态和操作就不再需要,可以被压缩。

文章讨论了几种进行日志压缩的方法,

  • Snapshotting memory-based state machines
  • Snapshotting disk-based state machines
  • Incremental cleaning approaches
  • Leader-based approaches

这几个方法有一些核心概念基本都是相通的,

  1. 每个server独立的负责日志压缩,而非由leader集中决定。
  2. raft向状态机转移维护prefix of the log的职责。
  3. raft丢弃部分日志前缀a prefix of the log后,状态机会承担两个新的职责
    1. 如果server重启,状态机在apply entry前,需要先load那些被丢弃的日志。
    2. 为了落后较多的server或新server能够追上,状态机可能需要输出一个状态的镜像。

Snapshotting memory-based state machines

适用于状态机的数据是存放在内存的情况。每个server独立的创建已经提交entry的snapshot。主要过程是,

  • 状态机序列化当前状态。
  • 一旦状态机完成snapshot的写入以后,日志就可以被截断了,raft首先保存snapshot中lastIncludedIndex和lastIncludedTerm,以及这个index对应的lastIncludedConf。
  • raft可以丢弃截止index的entry和先前的snapshot。

-w318

InstallSnapshot
为了落后较多的server或新server能够追上,这个方法里使用InstallSnapshot来实现。leader仅当丢弃了需要复制的next entry的时候,才发送snapshot,snapshot以chunks的形式有序发送。

并发创建
创建snapshot时,状态机需要维持一个不变的状态,但进行序列化和落盘需要较长的时间,因此创建的过程需要与普通操作并发执行。可以使用copy-on-write实现,有两种方法,

  1. 状态机使用不可变数据结构。
  2. 依赖os的copy-on-write支持,例如:linux的fork。

copy-on-write占用额外的内存,在创建的过程中,占用的额外内存与状态的修改成正相关,因此需要事先计划和管理。如果在snapshot的过程中,内存满了,那么server只能暂停服务,此时集群可能还是可用的。最好不要终止稍后重试,下次创建的时候很可能还会有类似的问题。

何时创建
如果创建的过于频繁,会浪费磁盘带宽和其他资源,如果过于稀少,会导致创建出过大的snapshot,增加传输和回放的时间。

有这么几个判断的方法,

  • 如果size(log)明显大于一个预定的值。
    当这个值明显大于snapshot的大小时,磁盘写入开销会很小。但对于较小的状态机,需要等待较长的时间才会有满足大小要求的log。
  • 如果size(log)大于size(snapshot)的倍数。
    不过判断当前状态机的snapshot大小并不容易。
  • 如果size(log)大于size(prev snapshot)的倍数,expansion factor。
    expansion factor控制了磁盘带宽的开销。

还可以仅在少数派server上创建snapshot,不影响服务client。

Client交互

查找cluster

如果配置固定,这个过程很简单。难点在于成员不断变更的情况,可用的方法有,

  • 广播,但受限于特定的网络环境。
  • 使用外部的目录服务,例如:DNS。需要在变更的过程中增减相应的server。

路由请求到leader

client的请求是由leader处理的,因此client需要找到leader,可以随机的选取一个server发起请求,如果不是leader,server拒绝,client重试直到找到为止,尝试次数期望是$(n+1)/2$。在此基础上可以做一些优化,

  • server拒绝的时候返回leader。
  • server做代理,转发请求到leader。

还需要避免过期的leader信息导致处理client请求的时候产生不必要的延迟,

  • leader:如果产生网络分区,且client向拥有少数派的leader发送了请求,在分区恢复前,这个请求一直都无法得到处理。因此当超过election timeout以后,leader都没有向多数派成功的发送心跳,那么leader让位
  • follower:如果follower发起新的选举或者term变更,那么follower丢弃当前维护的leader信息。
  • client:当丢失与某个server的连接,应该随机选取一个server进行重试。

线性一致性

截止目前,raft提供了at-least-once的语义。client重试、以及网络导致请求重复会导致命令被执行多次。但是at-least-once对于一个基于共识的系统是不够的,raft需要可线性化的语义,通过对请求去重,可以实现这一点。

使用session去重
每个client分配一个唯一id,每个请求分配一个唯一的递增序号。server维护每个client的session,这个session跟踪了每个client的最新序号和对应的response,如果收到了一个已经处理过的序号,那么直接返回。

这样每个命令就做到了以log中第一次出现的顺序立即生效且只执行一次。

对于来自同一个client的并发请求,server维护一个<序号,response>的集合。每个请求中携带一个client未收到的最小序号,server丢弃小于这个序号的response。

session保存的多久
受存储的限制,session不能永久保存,server需要对何时过期session达成共识。

  • 一个方法是设置存储session数的上限,并使用lru淘汰session。
  • 另一个方法是基于对时间源达成的共识来淘汰session(原文中的描述不是非常清晰,待补充)。

处理session过期的client请求
当session过期后,client还继续操作时,这被看做异常情况(待补充)。

更高效的处理read-only请求

raft日志的目的是以相同的顺序把变更复制到server上,并保证读写时候的线性一致性语义。read-only命令只涉及查询状态机,可以绕开日志的复制,避免同步磁盘写入,会大大的提升性能。但如果没有额外的控制,client会读取到过期的值。

为了使得绕开raft日志的read-only请求保持线性一致性,针对每次read-only请求,leader需要,

  1. 如果当前term还没有提交过entry,等待直到有。如果是刚成为leader,则需要先提交一个no-op entry。
  2. leader将当前的commit index记录到本地变量readIndex,这个会作为read-only操作的下界。
  3. leader需要自己的身份是有效的,不存在在自己不知情的情况下(网络分区)选举出了新的leader。这里的方法与路由请求到leader中避免过期的leader类似,如果成功向多数派发送了heartbeat,那么leader可以知道在发送heartbeat的时候,身份仍然是有效的。
  4. leader等待lastApplied >= readIndex,此时的readIndex是能保证线性一致性的最小index
  5. leader向自己的状态机发起查询请求,并返回结果。

优化leadership确认
每次查询请求都需要执行3,可以把所有累计的查询通过一次heartbeat来确认leadership。

follower分担read-only负载
同样需要保证不读取到过期的数据,保证线性一致性。为此follower可以向leader发送一个查询当前readIndex的请求,然后leader执行上面的1-3,follower执行4-5。

使用时钟减少heartbeat带来的延迟
虽然有batch优化,read-only查询仍然需要做一次heartbeat来确认leadership,可以用时钟来避免heartbeat带来的延迟。

-w262

  • leader使用heartbeat来维持一个lease,如果leader成功向多数派发送了heartbeat,那么leader可以认为在接下来的election time时间内都不会有新的leader产生,这个lease可以扩展到$start+\frac{\textit{election timeout}}{\textit{clock drift bound}}$,在这个时间之前都不用执行上面的步骤3。
  • 在进行leadership transfer的时候需要将lease主动过期,因为会导致更早的产生新leader。

要注意的是,使用lease的方式假设了server之间时钟漂移的上界(在给定的一段时间内,没有server的时钟增加的时间会超过这个上界),找到并维护这个值会增加额外的运维成本。如果假设失效了,系统可能会返回任意过期的信息。

可以使用一个的扩展来增强对client提供的保证,即使上述假设失效的情况下,读操作满足线性一致性,不至于错的离谱。具体方法是,

  1. server返回client的时候,带上状态机状态对应的index。
  2. client跟踪自己看到的与结果对应的最新index,发送请求的时候带上这个index。
  3. 如果server收到的index > lastApplied,那么server暂时不处理这次请求。

问题

  1. 创建snapshot的时候,有什么限制?
    • 不能丢弃未提交的和未执行的
    • 已执行的entry可能需要用于使其他server更新
  2. snapshot和log的关系?
    snapshot反映的是已经执行的log。
  3. server持久化了哪些数据在磁盘上?
    • 截止到某个entry的snapshot + 后续的log = server完整的log。
    • 其他状态信息,如:currentTerm,votedFor等。
  4. 如果某个follower落后了,同时leader丢弃了follower的所需的log,怎么办?
    nextIndex将无法会退到那个entry,leader会使用InstallSnapshot RPC。
  5. leader何时会向落后follower发送InstallSnapshot RPC?
    上面的问题即为答案。
  6. 为何leader不仅仅丢弃所有follower都有的entry?
    • 每个server是独立创建snapshot的。
    • 少数落后或失败的follower会导致leader log的持续增加。
  7. snapshot包含什么信息?
    • term
    • lastIncludedIndex
    • lastIncludedTerm of lastIncludedIndex
    • lastIncludedConf at lastIncludedIndex
    • snapshot data
  8. follower InstallSnapshot RPC的流程是什么?
    • 检查term
    • 检查是否已包含lastIncludedIndex/lastIncludedTerm
    • set lastApplied = lastIncludedIndex,写入data
    • 使用snapshot重置状态机
  9. server收到InstallSnapshot RPC以后,有没有可能会导致状态机的状态回退?
    不会。follower会检查是否已经包含lastIncludedIndex/lastIncludedTerm。
  10. 为什么在处理read-only请求的时候需要提交一个no-op entry?
    问题类似于提交上一个term的entry,新leader并不知道先前term的entry是否已提交。需要append一个no-op entry,如果成功提交,那么表示在此之前的所有entry都是已提交了的。
  11. 配置变更时,从集群移除的server如果发起选举,会[影响集群的可用性](#single-server change),为何不直接把离开集群的server关闭?
    $C_{new}$不会复制到那些离开集群的server,因此无法做到$C_{new}$提交以后,就立即下线这些server。在关闭前的这段时间里,这些server可能会影响集群的可用性。
  12. joint consensus过程中,选举和提交需要同时获得新旧配置的多数派,这对性能的影响有多大?
    • 在大多数不发生错误的情况下,获得新旧配置的多数派应该是一个比较快的过程。
    • 获得新旧配置的多数派仍然会比普通的commit要慢,但考虑到配置变更并不经常发生,所以这个代价可以忍。
  13. joint consensus过程中,选举和提交需要同时获得新旧配置的多数派是否是必须的?
    是,这是为了确保安全性所必须的。在joint consensus关于[安全性的讨论中](#使用joint consensus),列举了如果leader失败,发生选取时的情况,除特殊的两个外,获得新旧配置多数派的要求避免了disjoint majority出现
  14. 配置变更时,新server是作为non-voting成员加入的,这个要求为何可以提升可用性?
    当$C_{old,new}$提交以后,集群才可以继续处理请求。而$C_{old,new}$的提交需要新配置的多数派复制成功,空server会拖慢达这个过程。
  15. 离开集群的server发起投票会影响集群的可用性,为何不直接使用当前配置来判断,看发起请求的server是否在配置中?
  16. joint consensus的起止时刻是什么?
    • 开始:leader append $C_{old,new}$。
    • 终止:
      • leader未成功提交$C_{old,new}$就挂了。
      • leader成功提交$C_{new}$。
  17. 配置的entry是否可能被后续leader覆盖?
    可能。如果前任leader未成功提交$C_{old,new}$就挂了。
  18. 如果log和创建的snapshot大小差别不大,那snapshot是否还有用(例如:k/v server大量插入新key)?
    有。
    • 避免raft log entry一直占用内存。
    • 恢复服务时,使用snapshot可能会比直接使用log能更快(比如snapshot数据的组织方式更好)。
  19. InstallSnapshot会占用带宽不?
    会,如果状态很大的话。可以用一些方式来减少InstallSnapshot RPC的调用,
    • 考虑让leader保留更久的log,来应对follower的lag或暂时的下线。
    • 只发送两个server diff的部分。
  20. follower的entry是否有可能不在收到的snapshot里面?
    有可能,例如:leader尚未提交的entry。
  21. InstallSnapshot是否是原子的?如果在InstallSnapshot执行途中,follower挂了,重发InstallSnapshot是否ok?
    是原子的、幂等的。

Lecture

性能问题

raft牺牲了性能来换取简洁的设计:

  1. follower拒绝乱序的append,不允许日志有空洞。
  2. 尚未支持batch或pipeline方式的append。
  3. 对于大的状态,snapshot比较浪费。
  4. 慢leader会影响系统的性能。

References

  1. Raft One-Server成员变更
  2. 一文看尽 Raft 一致性协议的关键点
  3. ongardie/raft-single-server-changes-safety
  4. bug in single-server membership changes
  5. raft/JOINT-CONSENSUS.md