链式复制架构：高吞吐量与可用性

Sep 28, 2023 20:00 · 5942 words · 12 minute read Architecture Distributed System

来自康奈尔大学的论文 Chain Replication for Supporting High Throughput and Availability

Mind Mapping

1. 介绍

两种存储系统代表：

  • 文件系统：幂等地访问单个文件
  • 数据库：线性地访问多个对象

存储服务介于文件系统和数据库之间：

  • 存储对象
  • 支持查询操作，返回对象的值
  • 支持更新操作，原子地变更单个对象的状态

构建大规模存储服务的挑战：

  • 高可用
  • 高吞吐量
  • 故障容忍
  • 一致性保证

强一致性保证通常与高吞吐量和高可用是矛盾的（CAP）。GFS 不愿牺牲吞吐量和可用性舍弃了强一致性；而本文的主角链式复制，协调故障停机的服务器，同时支持高吞吐量、可用性和强一致性。

2. 存储服务接口

存储服务客户端查询和更新操作的请求：

  • query(objId, opts)
  • update(objId, newVal, opts)

客户端可以在更新前先查询一把看看当前的值是否已被更新过（幂等）。

链式复制架构中，每次瞬时中断的持续时间远短于移除故障主机或添加新主机所需的时间。因此客户端的请求在面临集群故障、恢复和重新配置时，中断的可能性被最小化。大多数复制管理协议要么会阻塞一些操作要么牺牲一致性保证。

给客户端一个对象状态的视图还有应答查询和更新时状态的转换来指定存储服务的功能。

Figure 1

如图用两种变量定义 objID 状态：

  1. HistobjID 是已作用于 objID 的更新序列
  2. PendingobjID 是未处理的请求集合

图中列出了可能的状态过渡：

  1. 事务 T1 断言一个到来的客户端请求被添加至 PendingobjID
  2. 事务 T2 指示某些待处理的请求被忽略了——这种过渡不会很频繁
  3. 事务 T3 给出一个高级别的请求处理视图：请求 r 首先从 PendingobjID 集合中移除；然后追加更新至 HistobjID。

3. 链式复制协议

假设服务器宕机了：

  • 每台服务器因故障停止工作
  • 服务器的宕机状态可被探测到

当一个对象被复制到 t 个服务器，不影响可用性最多允许 t - 1 个服务器故障。因此该对象的可用性被提升至 1 - 所有托管着它的服务器都发生故障的概率。

在链式复制中，服务器们复制给定的对象 objID 按线性顺序排列形成链。

Figure 2

链内第一台服务器叫做链头（head），最后一台服务器叫做链尾（tail），请求处理的实现大致如下：

  • 回复（reply）

    每条请求的应答生成并由链尾发送。

  • 查询处理

    每条查询请求被直接发送到链尾，并在链尾读出已存储的 objID 的副本。

    查询请求只涉及一台服务器，意味着查询是相对低开销的操作。

  • 更新处理

    每条更新请求被直接发送到链头，并在链头使用 objID 的副本处理，然后状态变更沿着一条可靠的 FIFO 链转发到下一个节点，直到请求由链尾处理。

    处理更新请求时，t 个服务器中有 t - 1 是冗余的，对应答没有任何贡献；不过它们增强了容错能力。链式复制中避免了在 t - 1 台服务器上重复计算，只要链头计算一次，随后沿着链向后转发，因此每个副本只要执行一次写入。

强一致性就是这么来的，查询和更新请求都在单台服务器上串行处理；而且每条请求的开销很小，因为只有一台服务器处理查询（链尾）。

3.1 协议细节

用链式复制架构来实现图 1 中的规范：

  • HistobjID 被定义为 HistTobjID，HistobjID 的值存储在链尾 T。
  • PendingobjID 被定义为链中任意服务器收到的客户端请求集合，并且这些请求还未被链尾处理。

影响 HistobjID 和 PendingobjID 的服务器状态过渡：

  1. 链中的服务器收到来自客户端的请求（影响 PendingobjID）
  2. 链尾处理客户端请求（影响 HistobjID）

由于其他的服务器状态转换相当于无操作（no-op），因此可以证明过渡 1 2 与 T1 到 T3 一致。

  • 客户端请求来到链式服务器

    客户端向链头发送更新请求，向链尾发送查询请求。将请求 r 添加至 PendingobjID，与 T1 一致。

  • 请求由链尾处理

    从 PendingobjID 删除请求 r，是 T3 的第一步。队尾 T 处理该请求使用的是副本 HistTobjID，实现了 HistobjID，而这正是 T3 剩余步骤所规定的。

应对服务器故障

在检测到链中的服务器故障后，要重新配置服务器链来移除故障的服务器。为此，我们部署一个叫做 master 的服务，用于：

  • 探测服务器故障
  • 从“链表”中剔除故障服务器，通知链中的每个服务器它的前一个节点或后继节点
  • 通知客户端哪两台服务器是链头和链尾

理想很美好现实很骨感，master 是有可能出现单点故障的，链式复制的原型在多个主机上部署了 master 副本进程，使用 Paxos 来协同这些副本。

master 将故障分为三种情况：

  1. 链头故障
  2. 链尾故障
  3. 链中其他服务器故障

对每种场景的处理取决于更新如何在链中传播。

将链头标记为 H，下一个节点标记为 H + 1，而链尾则标记为 T。

定义 HistiobjID ≤ HistjobjID 来维持是否服务器 i 的请求序列 HistiobjID 是服务器 j 的请求序列 HistjobjID 的前缀。

因为更新通过可靠的 FIFO 链接在链内的节点之间发送，每台服务器接收到的更新序列是它继任节点接收到的序列的前缀。

  • 链头故障

    master 将链头 H 剔除，并将 H + 1 作为新的链头。因为不太可能所有服务器全都坏了，也就可以认为继任者一定存在。

    删除 H 也就是变更了复制链，算是一种转换，必须要么是一个无操作（no-op）要么遵循图 1 的 T1 T2 T3。

    • PendingobjID 被定义为链中任意服务器收到的请求，该请求还未被链尾处理。
    • 从 PendingobjID 删除 H 收到的还未被转发到下一个节点的请求。

  • 链尾故障

    将链尾 T 从链中剔除，将 T - 1 作为新的链尾。

    这个变更同时动了 PendingobjID 和 HistobjID，这么做与重复 T3 过渡一致：PendingobjID 减小因为 HistTobjID ≤ HistT-objID(T- < T)，所以将链尾从 T 变更为 T- 潜在地增加了由链尾完成的请求集，根据定义减少了 PendingobjID 集合中的请求。另外，因为 T3 要求，那些由 T- 完成但是 T 还未完成的请求现在出现在 HistobjID 集合中因为链尾是 T-，HistobjID 被定义为 HistT-objID。

  • 链中其他服务器故障

    通过删除链中的 S 服务器来处理该服务器故障。

    master 先通知 S 的下一台服务器 S+ 新的服务器链配置，然后通知 S 的上一台服务器 S-。但是这样会使得更新传播不变性失效，要确保 S 在故障前收到的更新请求仍沿链传递。执行转发的是 S-，但现在需要簿记和协调。

    如果 i < j，那么 HistiobjID = HistjobjID ⊕ Senti

  • 扩展链

    虽然可以从链中移除故障的服务器，但随着链变短，容错的余地也减少了，如果很多服务器都坏掉，可用性最终可能受到影响。解决方案就是添加新服务器，维持链长。

    理论可以在链的任意位置添加新服务器。实际上，在链尾追加一台服务器 T+ 看上去最简单。

    • T 被通知到不再是链尾，将收到的客户端的查询请求传递至新的链尾 T+
    • master 被通知到 T+ 是新的链尾
    • 客户端被通知到查询请求应该被直接发到 T+

4 主备协议

链式复制也是主备的一种，用状态机管理副本。

主机（primary）：

  • 对客户端请求排序（从而确保强一致性）
  • 分发客户端请求或更新至其他服务器（备机）
  • 等待所有非故障备机的确认
  • 给客户端回复

如果主机挂了，备机之一会被提升为主机。

相比链式复制，主备架构在应答查询前，必须同步等待所有备份的更新确认。两种架构，更新请求必须传播至所有副本，都则副本会分叉。链式复制串行地传播，导致其延迟高于主备架构，后者将请求并行分发至副本。

链式复制架构要考虑三种情况，链头故障、中间故障和链尾故障。

  • 链头故障：

    不会中断查询处理。在主节点向新的链头节点及其后继广播消息，然后通过广播通知客户端新的链头节点前，更新将不可用。

  • 中间故障：

    也不会中断查询。更新可能会延迟，但更新请求不会丢失，只要整个链中已接受到请求的服务器仍在运行，就不会服务中断。链中间的服务器故障可能导致更新请求处理延迟。

  • 链尾故障：

    在主服务器向新的链尾节点广播消息然后通知客户端新的链尾节点前，查询和更新都不可用。

在主备架构中要考虑两种情况：主机故障和备机故障。每种情况都会对查询和更新请求产生相同的影响。

  • 主机（Primary）故障：

    服务中断将经历 5 条消息延迟：主节点（master）检测到故障并向所有备机广播一条消息，请求每个备机已处理的更新数量，并告诉它们暂停处理请求。每个备机都回复主节点。然后主节点将新的主机（primary）广播给所有备机，**新主机（primary）**是已处理更新数量最多的那个，并且必须将缺失的更新转发给备机。最后，主节点通知所有客户端新主机（primary）。

  • 备机故障

    不会中断查询处理，但是更新请求则不然，因为主节点（master）会向主机发送消息指示故障的备机不会应答确认，后续主机不应该向那个有问题的备机发送请求，服务中断将经历 1 条消息延迟。

所以，链式复制架构最坏情况的服务停滞时间永远比主备架构的最坏情况都要短；而且链式复制架构最佳情况下的服务停滞时间比主备架构同样最佳情况下的要短。如果停机时间是设计存储服务时的主要考虑因素，在链式复制和主备架构之间选择就要先了解各种服务器故障的可能性。

5. 模拟实验

为了更好地理解链式复制的吞吐量和可用性，我们在模拟网络中进行了一系列实验，主要关注处理和通信的内在延迟，所以模拟了一个无限带宽但每条消息延迟 1ms 的网络。

5.1 单链，无故障

副本因子 t 为 2、3 和 10。我们比较了 4 种不同的副本管理方式的吞吐量：

  • chain：链式复制
  • p/b：主备
  • weak-chain：略微改动链式复制架构，查询请求会随机去往服务器
  • weak-p/b：略微改动主备架构，查询请求会随机去往服务器

注意，weak-chain 和 weak-p/b 并不保证强一致性。

我们将服务器的查询延迟固定在 5ms，更新延迟固定在 50ms。假设每次更新都要进行一些磁盘 IO，将对象的变化转发到存储副本的开销比在每个副本上重新处理更新要更小；预计单个副本处理一个对象变化消息的延迟将会是 20ms。

所以一条 3 服务器的链，执行更新的总延迟是 94ms：

  1. 客户端向链头发送消息 1ms
  2. 链头节点的更新延迟 50ms
  3. 在另外两个节点上增量处理更新各需要 20ms * 2
  4. 还有额外 3ms（1ms * 3）的转发延迟

然而查询延迟只有 7ms。

在图 4 中我们将总吞吐量作为更新请求占比的函数绘图，t = 2 3 和 10。有 25 个客户端，每个都按给定的比例发送查询和更新请求。所以客户端最多可以并发 25 个请求。

Figure 4

链式复制架构（chain）在所有副本因子（t）和更新占比中，性能都等于或优于主备架构。意外的是链式复制的弱变体，当更新请求超过 15% 时，它们的性能反而比强一致性的链式复制更差：

  • 在查询密集型负载下性能优于链式复制架构，是因为它们将查询负载分发到所有服务器上，与副本因数成正比。
  • 随着更新的占比变大，普通的链式复制超越其变体，是因为所有的更新都在链头完成。

因为 weak-chain 和 weak-p/b 没有实现强一致性，所以这些方案很少被优先选择。

5.2 多链，无故障

如果每个对象都由单独的链来管理，而且对象本身很大，那么添加一个新副本可能会因为需要将对象的状态转移到新副本所需的时间导致很大的延迟。如果对象很小，则大型的存储服务涉及许多对象。系统中的每个服务器可能会承载多条链——处理器和通信频道的复用开销可能过大。此外，单个节点故障现在会影响到多条链。

一组对象可以被组合至一个卷中，而这个卷本身在链式复制中可以被看作一个对象，所以设计者在决定对象大小时有很大的自由度。

下一组实验，我们假设：

  • 卷的数量为一个常量
  • 有一个哈希函数将每个对象映射到一个卷，从而映射到一条唯一的链
  • 每条链由从存储服务的服务器中选出的主机组成

Figure 5

图 5：每个客户端的平均请求吞吐量是不同更新比例的函数

我们的实验中有 25 个不同的客户端，每个客户端随机提交查询和更新请求，均匀分布至链上。客户端尽可能快地发送请求，但每次只能发送一个。

为了与 GFS 的实验相比较，我们假设 5000 个卷每个三副本，并且改变服务器的数量。我们发现链式复制，weak-chain、主备和 weak-p/b 之间几乎没有差异，图 5 展示了每个客户端的平均请求吞吐量（链式复制）作为服务数量的函数，在不同比例的更新请求下的情况。

5.3 故障对吞吐量的影响

在链式复制架构中，每台服务器故障会导致启动三步处理：

  1. 主节点检测到服务器故障需要一些时间（在实验中保守假设为 10 秒）。
  2. 有问题的服务器从链中剔除。
  3. 主节点向该链添加一台新的服务器并启动数据恢复处理，这个过程所需的时间与故障服务器上存储的数据还有可用网络带宽成正比。

我们假设一个存储服务有以下特征（参考自 GFS 的报告）：

参数 值
服务器数量（N） 24
卷数量 5000
链长（t） 3
最大网络带宽 6.25 Mb/s
服务器重启时间 10min

Figure 6

图 6：一到两个节点故障时查询和更新吞吐量

每个实验持续两小时，在实验开始后 30 分钟，模拟一到两台服务器故障。图 6（a）展示了在试验开始 30 分钟后单台服务器 F 故障的情况下，吞吐量骤降，因为主节点花了 10 多秒探测到服务器故障然后从链中将其剔除。从链中剔除故障的服务器后，服务得以维系，速率稍低是因为服务器少了，而且数据恢复也会占用一部分资源。十分钟后故障的服务器上线，并且开始恢复数据。

我们预期在所有数据卷恢复后，查询吞吐量会和实验开始时相同。现实情况很微妙，因为卷不再均匀分布在服务器之间，特别是故障的服务器 F 将成为它参与的每条链的链尾，因此服务器的负载均衡得不是很好，聚合查询的吞吐量会变低。

在服务器发生故障时，更新吞吐量会降到 0，然后一旦主节点从所有链中删除故障的节点，吞吐量甚至会比开始时还好一点，因为服务器故障导致链的长度变短了（从 3 变成了 2）。

两台服务器故障也差不多。

5.4 大规模副本数和数据量

随着服务器数量的增加，故障的总体概率也会增加。如果有太多服务器故障了，那么卷可能会不可用，取决于卷是如何放置在服务器上的（拓扑），这决定了数据恢复时的并行度。

三种拓扑：

  • 环形（ring）：副本放在连续成环的服务器上，由卷标志符的一致性哈希确定。
  • rndpar：卷的副本随机落在服务器上。这是 GFS 使用的策略。
  • rndseq：卷的副本随机落在服务器上（如 rndpar），但并行数据恢复的最大数量受 t 限制（如 ring）

要理解并行数据恢复的优势，想象一台故障的服务器 F 参与了链 C1、C2…Cn。对于每条链 Ci 来说，数据恢复需要一个源来获取卷数据和一台新主机来成为链中的一环。如果节点足够多而且没有限制卷的拓扑，很容易确保新节点是不相交的。并且因为卷的随机放置，数据源也可能是不连续的，链 C1、C2…Cn 的数据恢复可以并行。存在较短的窗口，期间的少量并发故障将导致某些卷不可用。

我们将任意对象的平均不可用时间（MTBU）量化为服务器数量和卷放置策略的函数。假设每台服务器的平均故障间隔时间为 24 小时，随着存储系统中服务器数量的增加，卷的数量也会增长。在我们的实验中，每台服务器开始时存储 100 个卷。

假设将一台服务器的所有数据复制到另一台要 4 小时，与 GFS 实验一样，通过网络并行恢复数据的最大数量限制为服务器数量的 40%，最小传输时间设置为 10 秒（复制单个 GFS 对象所需的时间，64KB）。

Figure 7

图 7 显示环形拓扑的 MTBU 近似 Zipfian 分布。因此为了维持特定的 MTBU，链长度似乎与服务器数量呈对数关系。图 7（b）展示了 rndseq 的 MTBU。当 t > 1 时，rndseq 的 MTBU 比环形拓扑更低。与环形相比，随机放置的性能较差是因为有更多台服务器存储链的副本，因此因故障丢失链的风险更大。

但是如果服务器足够多，随机放置就可以提供额外的并行恢复机会。图 7（c）展示了 rndpar 的 MTBU，少量服务器时，rndpar 与 rndseq 性能相同，但随着服务器数量增加，并行恢复的概率也在不断增加，从而提高了 MTBU，最终 rndpar 的性能超越了 rndseq，也超过了 ring。