阅读 OSDI 2018 《Fault-Tolerance, Fast and Slow: Exploiting Failure Asynchrony in Distributed Systems 》觉得有点意思，所以在这里分享给大家，可以加深自己对共识算法的理解。

1. Introduce

在分布式系统中，通常会将数据复制到 2n+1 个节点中，从而可以容忍 n 个节点失效，以此来保证数据的高可靠和高可用，目前常见的数据复制协议包含 paxos/raft/zab/QJM/Perficia/Viewstamped replication 等，而这些协议又根据持久性状态分为两类：（1）Disk-durable，以 raft/paxos/Perficia/zab 等为代表，将数据持久化到 disk 中，优点是，可用性好，可靠性好，但是由于数据持久化到 disk 中，数据复制的性能不好；（2）Memory-durable，以 Viewstamped Replication 为代表，将数据持久化到内存中，优点是，性能好（Performance），但是可靠性（reliability）和可用性比较差，存在较大的丢失数据的风险（unsafety）。那么是否存在一个 Strong Reliability，并且 High Performance 的方案呢 ？

论文作者基于 NonSimultaneity Conjecture （NSC，非同时性猜想），也就是多个副本节点 crash 并不是严格同时，极大部分情况下节点之间的失效之间存在一定的时间差，所以再阅读后文的时候，务必带着 NSC 的前提来来看算法的合理性。当然作者也给了一些过往和研究和数据说明了猜想的合理性，感兴趣的可以参考论文相应的章节。基于这个猜想，作者提出了一种 situation-aware updates and crash recovery（SAUCR），整体复制框架还是 Leader-Follower，只是相较传统协议有一些差异，SAUCR 是集群状况感知（situation-aware）的，所谓的状态感知就是 SAUCR 根据集群的状况分为两种模式：（1）fast mode，如果 2n+1 个节点中，大于 n+1 个节点存活，那么就将数据 update in memory buffer；一旦发现只有 小于等于 n+1 个节点存活，就切换到（2）Slow mode，在此 mode 下，所有节点需要将数据持久化到 disk 中。

作者在 Zookeeper 中实现了 SAUCR，并通过实验论证了 SAUCR 的 Strong Reliability 和 High Performance。后文将详细描述在两种模式下的 update 和 recovery 的细节，以及 SAUCR safety 的论证。

2. Situation-aware

既然存在 Fast、Slow 两种 mode，那么首先来看看，两种 mode 是如何在 SAUCR 中存在的，以及何时切换，如何切换 ？

这里先假定一下集群的模型，后面的讨论都是基于一个拥有 2n+1 个副本（节点）的复制组。初始集群所有的节点都在线，这个时候所有节点处于 Fast mode，所有节点的副本写到到内存中。一旦发现节点 crash/隔离 下线，SAUCR 会根据一定的规则进行 mode 的切换，其实就是 Situation-aware，核心的就是 Failure Reaction，也就是如何分别应对 Leader 和 Follower 的 failure，并进行相应的 mode 切换 ？

• Follower Failures and Mode Switches

首先看 Follwer failure Leader 是如何处理的 ？

Leader 通过和 Follower 保持心跳，一旦超过一定时间未收到 Follower 回复，Leader 认为 Follower 已经离线，一旦 Leader 发现集群在线节点数（包括 Leader 自己在内） <= bare majority（n+1），那么立即切换到 Slow mode，并发送一个 special request 给所有的 Follower，所有 Follower 收到这个 Special request 之后，将会把所有的 memory buffer 中的数据持久化到 disk 中，并同时也切换到 Slow mode。

实际上即使在 Fast mode，所有节点也是后台 async 的方式将数据刷到盘中，当然是在不影响性能的情况下，这样有两个好处：

• 避免全部的数据丢失
• 加快 Fast mode 向 Slow mode 切换后，节点刷数据落盘所需的时间。因为如果不定期刷，那么在切换的时候再一起刷，数据量将太大。

Notes：

这里需要注意一个定义，就是何为 bare majority ？也就是对于 2n+1 的副本的复制组，bare majority 就是 n+1，后面会有更多 bare majority 的使用。

• Leader Failures and Flushes

Leader failure follower 该如何应对 ？

一旦 Follower 在超过一定时间没有收到 Leader 的 heartbeat，那么将认为 Leader 离线，立即将自己所有的数据刷到盘中。这里 Follower 对 Leader failure 的超时时间，可以相对设置得小一些（ms 级别），从而进一步保证数据的安全性，提高可用性

3. Situation-Aware Updates

接下来看看 SAUCR 的写入（Update）

• Slow mode

在 slow mode 下，所有的数据都是持久化到 disk 中，所以其写入和大多数的一致性复制协议基本一致的，就是当写入大多数之后（n+1），Op 就可以 commit，然后 applied RSM 中，返回 client 了。

• Fast mode

与 Slow mode 不一样的是，在 Fast mode 下，由于数据是写入 memory buffer的，所以，为了尽可能的保证数据的可靠性性，只有当数据写入 >= bare majority + 1 （>=n+2） 个副本，才会 commit，然后返回 client。这一点尤为重要，后面 crash recovery 保证 safety 和 availability 都是基于这个点。

Notes

这里需要注意的是，在非同时性猜想 NSC 的前提下，SAUCR 的可用性并没有降低，尽管在 fast mode 下，update 需要 >= bare majority + 1 复制成功才能提交，相比传统的 raft 等协议，只需要 bare majority 复制成功就可以提交，是不会影响可用性，其实并不会，因为一旦出现 < bare majority +1 个节点可用时，就切换到 slow mode，这个时候只需要复制到 bare majority 就可以提交了，相当于退化到和 raft 协议一致。当然 >= bare majority + 1 复制成功才能提交，对性能还是有一些影响的，但是如果在局域网中，性能应该也不会差，可以佐证的是 Pacifica，其只有当所有副本复制成功了才能提交。

下面给一个例子，如下图 Figure 3

S1、S2、S3、S4、S5 五个节点，其中 S1 是 leader，5个节点都在线，集群处于 fast mode，

• S1 将 entry 复制给了所有节点，提交 entry 1；
• S5 挂了，但是仍然有 > bare majority 个节点在线，集群仍然处于 fast mode，S1 将 entry 复制给 S1~S4，提交 entry 2
• S4 挂了，集群在线节点 = bare majority，退化为 slow mode
• S4 和 S5 恢复并 catch up，此时 > bare majority + 1 个节点在线，恢复到 fast mode，S1 提交 entry 3

4. Situation-Aware Recovery

接下来就要看 SAUCR 的重头戏 crash recovery。

4.1. Persistent Mode Markers

SAUCR 在不同的 mode 下，recovery 的策略和方法是不一样的，那么 crash 重启开始恢复的节点，首先需要知道自己之前处在一个什么 mode 下。（1）其中在 fast mode 下，节点在处理第一个 Op 的时候，会同时持久化一个 fast-switch-entry 到 disk 中，这个 entry 是当前的 epoch-index pair；（2）在切换到 slow mode 的时候，会刷 memory buffer 到盘中，同时也会刷 latest-on-disk-entry 到盘中，这个 entry 也是一个 epoch-index pair。这样，如果节点重启，发现 fast-switch-entry 在前面，则说明 crash 的时候，节点处于 fast mode，相反，如果 latest-on-disk-entry 在前面，说明节点 crash 的时候，节点处在 slow mode。

4.2. Crash Recovery

上面之所以加上一些特殊的 entry 来标识节点 crash 时的 mode，就是因为不同的 mode 下节点 recovery 的策略和方法是不一样的。首先来比较简单的 slow mode recovery。

（1）disk-durable system recovery（slow mode）

对于盘持久化的系统，实际上也就是 slow mode 的 recovery 流程如下：

• 从盘中恢复 （last logged entry ）LLE，实际上就是知道自己到底拥有多少日志
• 通过恢复的 LLE value 发起选举，实际上就是通过 LLE 来判断哪个节点的日志最新
• 如果是选举失败成为 Follower，那么从 Leader 中 recovery miss 的数据，否则，自己成为 leader，将其它 Follower miss 的数据复制给它们
• 这个过程和一般的一致性协议例如 raft 本质上是无差别。

（2）fast mode crash recovery

如果是在 fast mode 下 crash 的，然后开始恢复，其流程如下：

• carefully recover its LLE from the replicated LLE-MAPs on other nodes，因为是在 fast mode 下 crash 的，所以，重启之后，节点上并没有任何数据，所以只能从其他节点拉取 LLE，实际上 LLE 是记录在 LLE Map 中，下面单独描述；
• 恢复 lost data，无论其是否能够成为 leader，因为之前是 fast mode，crash 之后数据就丢了，都需要从其他节点恢复数据。

• LLE Map

因为 fast mode 下，数据都是写在 memory buffer 中，一旦重启了，数据就都没了，什么状态都没有了，为了提高可用性，让从 fast mode 重启恢复的节点也知道自己的状态并且在需要的时候能够进行选举，就需要记录即使是 fast mode 下的 LLE，为此设计了一种 LLE Map 的结构，上面记录了当前 leader 给各个节点复制的 log entry 的最新的 epoch index pair，这个 LLE Map 携带在每个 replicate request 中，例如，Leader S1，在 epoch e，复制 index=10 的 log entry 给 S2， S3， S4 的时候，S5 已经 crash 了在 request 5 的时候，那么 leader S1 携带的 LLE Map 就是：

<S1:e.10, S2:e.10, S3:e.10, S4:e.10, S5:e.5>

其中在 fast mode 的时候，LLE map 写在内存中，在 slow mode 的时候 LLE Map 写在 disk 中。 这里需要特别说明的是LLE Map 中存放的是 last (potentially) logged entry，也就是正在复制的 log entry index，而不是已经成功复制的 log entry index，这样是为了保证 crash 起来的节点获取到的 LLE 一定是包含已经 commit 的 log 的，这样才不会出现数据丢失。

• max-among-minority algorithm

下面详细描述 fast mode 下第 1 步恢复 LLE 的过程，这里被称为 max-among-minority algorithm，它是保证数据不会被丢失的关键：

• 标记自己为 recovering 状态
• 向其他所有节点 查询 LLE，其中只有处于 recovered 状态的节点会回复，其它的节点会忽略请求
• 一旦收到 bare-minority = (N/2)的上界 - 1 个 reponse，取最大的作为自己的 LLE。这里 bare-minoity 在 2n+1 个副本的时候等于 n，注意和 bare majority 区分开来。注意这里只需要 n 个 reponse 即可，后面将详细证明为什么。

那什么样的节点是处于 recovered 状态呢 ？

1. 在 fast mode 有过 Op，且没有 crash 过的节点
2. 在 slow mode 下，且盘上有 LLE-MAP 的节点

一旦 LLE Map 恢复之后，就可以发起选举了，如果成为 leader，那么就可以从 follower 中恢复数据，反之变成 follower，则从 leader 恢复数据。到这里肯定会有一个疑问：

• 为什么需要 LLE Map ？

在 fast mode 模式下 crash 的节点，重启之后需要知道自己有哪些 log，这样才能参与选举，从而可以提高可用性。考虑一种情况，假设集群 5 个节点 ，挂了 3 个节点，那么只剩下 2 个节点了，此时集群正处于 slow mode，如果这个时候一个之前处于 fast-mode 的节点重启了，如果没有 LLE Map，这个在 fast mode crash 的节点重启，是没办法恢复的，因为这个时候只有 2 个节点，重启之后的节点并不知道自己有哪些 log，所以没办法进行投票，从而不能形成大多数，就没法选举，有了 LLE Map，这个重启的节点可以根据 max-among-minority algorithm 从 bare-minority 个节点中恢复 LLE，并恢复数据，这样集群恢复到了 3 个节点存活，从而可以选出 new leader，集群恢复可用。

4.3. Safety

Safety 证明实际上就是证明 fast mode 下的 crash recovery 不会出现 data loss；在证明 fast mode recovery 的正确性之前，首先做一些假设，假设这个恢复的节点为 N，其 log 是 D，其中 Cn 为 D 最后一条被 committed 的 log entry，其中 L 为 actual last-logged entry (LLE)，而 L' 为 通过 max-among-minority algorithm 恢复的 LLE，如果能证明 L' ≥ Cn，那么就不会出现丢失数据。先看个例子，如下图：

上图中 5 个节点，S1、S2、S3、S4、S5；其中 S1 是 leader

• S1 成功将 entry 1 复制给 S2、S3、S4、S5；由于复制给了超过 bare majority + 1（4个副本），所以这条 entry 可以 commit ，然后返回给 client
• S1 在复制 entry 2 的时候，S4、S5 由于网络隔离和 S1 失去联系，然后 S1 将 entry 2 成功复制给了 S2和S3、但是由于 S1 还未发现 S4，S5离线，所以处于 fast mode，此时加上 S1，小于 bare majority + 1 (4个副本) ，entry 2 还不能提交，Cn=1，L=2
• S3 crash and recover，S1 和 S2 down 了，S4、S5 网络隔离恢复，S3 执行 max-among-minority algorithm 获得 L'=1 ，L'包含了已经提交 log entry，不会造成数据丢失。

证明 L' ≥ Cn：

这里用反证法，假定经过 max-among-minority 之后，L' < Cn，那么只有可能是：

• bare-minority 个副本由于网络隔离后又恢复，或者 crash 之后再恢复；因为 max-among-minority 算法会从 bare-minority 个副本上获取 LLE Map 信息，然后取最大的，只有 2 个副本（假设5个副本）因为crash 或者隔离导致它们上面的 LLE Map 记录 LLE 才有可能小于 Cn；而在 fast mode 情况下，由于一个 entry 的提交是需要 bare majority + 1，也就是 4 个副本复制成功，那么必定和 bare mniority，也就是 2 个副本有交集，4+2 > 5，那么意味着要么 Cn 不可能提交，从而与假设矛盾；

实际上还有另外一种情况就是在 slow mode 下，但是在 slow mode 下，其恢复本身就有 safety 保证，这里就不在赘述。

4.3. Summary

首先看看 SAUCR 的状态转换，以及其可用性的情况。

如上图，下面对各种 state 进行分别描述：

（1）< bare minotiry 节点离线，集群处于 fast mode，可用

（2）= bare minority 节点离线，集群处于 slow mode，可用

（3）有节点恢复，又回到 < bare minority 节点离线，集群处于 fast mode，可用

（4）在 Available slow 状态下，出现任意数量的节点离线，集群都将处理不可用的状态

（5）恢复到 >= bare majority 个节点在线，进去 slow mode，可用

（6）当有 =bare majority 个节点同时离线，将会造成 Temporarily unavailable，为什么是临时的不可用，因为，其他节点加入或者恢复，集群还可以进入可用状态

（7）如果在 fast mode 下，> bare majority 个节点同时离线，那么集群将处于 Permanently unavailable，因为 recovery 至少收到 bare minority 个节点的 response，所以即使通过配置变更加节点或者 crash 节点 recovery 也都不好使了。一般这种时候需要人工介入。

5. Evaluation

5.1. Reliability

作者给出了一些 crash-testing，并统计了 SAUCR 在各种情况下，可用性和可靠性的数据，如下表，可以看出 SAUCR 在非 NSC 的猜想前提下，可用性和可靠性都没有降低；而且即使考虑 SC 的情况，也只是可用性降低了一些，但是数据可靠性并没有降低（这组数据感觉有点 ？？？）。

5.2. Performance

在看看性能，如下图：

6. Summary

通过全文的解读，发现 SAUCR 基于非同时性假设，实现了 Reliability 和 Performance 之间一个不错的平衡，总体上看，可用性没有降低，但是 reliability 呢 ？毕竟对于一些应用来，data loss 毕竟总是难以被接受，如果能有什么方法能间接的解决 SAUCR 在同时性错误发生的情况下 data loss 的问题，例如通过备用电池加上一些工程手段保证，节点 crash 之前数据落盘，那么 SAUCR 或许能够找到它的发挥余地，总体看来 SAUCR 也算是一个思路，学习和了解下，也可以加深对共识算法的理解。

Notes

于作者水平，难免有理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献中列表注明，但仍有可能有疏漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章供于学习交流，转载注明出处

参考文献

[1]. Fault-Tolerance, Fast and Slow: Exploiting Failure Asynchrony in Distributed Systems. https://www.usenix.org/system/files/osdi18-alagappan.pdf