6.824 2018 Lecture 6 Fault Tolerance Raft

Posted on 2019-08-19 Edited on 2021-06-27 In distritubed system Disqus:

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](/images/2019/15662902585664.jpg)

具体方法是，
* 新加入的server先作为non-voting成员。
* 复制到新server的过程分为多个round，每个round都复制leader所有的entry。
* 当前复制的round内，leader可能又有新的entry了，下一个round会进行复制。
* 在固定round内（例如：10），如果最后一个round的时间 < election timeout，此时假设不存在更多的entry会导致明显的不可用，添加新server。
* 否则leader终止变更配置。

Removing the current leader 如果使用joint Consensus，或没有leadership transfer的情况下，需要一个leader下线的方法：旧leader等到\(C_{new}\) commit以后让位（转变为follower状态）。

在commit之前，当前leader管理集群不包含leader自己，复制和投票的时候不把自己算入majority。
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足以将集群变更为任何期望的配置。

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。

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带来的延迟。

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暂时不处理这次请求。

问题

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

Lecture

性能问题

raft牺牲了性能来换取简洁的设计： 1. follower拒绝乱序的append，不允许日志有空洞。 2. 尚未支持batch或pipeline方式的append。 3. 对于大的状态，snapshot比较浪费。 4. 慢leader会影响系统的性能。