Distritubed System

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+2old = k+1, new = k+2
奇数个成员，减少一个2k+1 -> 2kold = k+1, new = k+1
偶数个成员，增加一个2k -> 2k+1old = k+1, new = k+1
偶数个成员，减少一个2k -> 2k-1old = 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+4a. 先看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
comments powered by Disqus