MIT 6.824 - Chain Replication for Supporting High Throughput and Availability

Posted on Word count in article: 10k Reading time ≈ 17 mins.

介绍

一个存储系统一般来说会实现一些接口使得客户端能够存储，获取，或者修改数据。文件系统和数据库系统是最广为人知的例子。对于文件系统来说，对单个文件的操作（读和写）是原子的；对于数据库系统来说，每个操作（事务）可能会访问多个对象，并且是可串行化的。

本文关注的存储系统介于文件系统和数据库系统之间。特别的，本文关注的存储系统，在这之后称之为存储服务，有以下功能：

  • 存储对象
  • 支持查询操作，能够返回单个对象的衍生数据
  • 支持更新操作，能原子的基于单个对象之前的状态根据某些预编程的计算（可能是非确定性的）来修改对象的状态

文件系统的写操作是上述存储服务的更新操作的一个特例，而上述存储服务的更新操作又是数据库事务的一个特例。

越来越多的在线零售商（例如 Amazon.com），搜索引擎（例如 Google 和 FAST），以及很多信息密集型服务通过将大型存储系统使用网络互联来提供服务。相对于文件系统和数据库系统来说，存储系统对于这些应用来说是较为适合的方案，因为数据库系统成本和代价过大，而文件系统则缺少丰富的操作语义。

构建大型存储服务的一个挑战是如何伴随着异常和配置更改（异常组件能被检测到并被替换）的同时维持系统的高可用和高吞吐。

一致性保证对于存储服务来说同样很重要。即使不重要，如果有了强一致性的保证，则能简化基于存储服务的应用程序构建，强一致性保证了：

  1. 对单个对象的读写操作会按照某个顺序执行
  2. 读操作一定能读取到之前的更新操作的结果

强一致性保证经常被认为和高吞吐、高可用是冲突的。系统设计者一般不会牺牲系统的吞吐或者可用性，而是牺牲强一致性保证。The Google File System（GFS）就体现了这样的思想。实际上，大型存储服务的强一致性保证和高吞吐、高可用并不是冲突的。本文介绍的 chain replication 方式在对 fail-stop 类型异常容错的同时，能同时支持高吞吐，高可用和强一致性。

存储服务接口

客户端会向存储系统发起查询和更新操作的请求。虽然能做到每一个到达存储服务的请求都能保证被执行，不过在论文 End-to-end arguments in system design 中提到这样做意义不大。存储服务可以简单的只处理能到达的请求，并在请求完成时响应客户端，这样就不用区分对待请求丢失和响应丢失这两种情况：客户端可以在一段时间没有收到响应后重新发起请求。

本文描述了两种接口：

  • query(objId, opts) 会返回 objId 对应的对象的衍生数据；opts 指定了需要返回对象中的哪部分数据。objId 所对应对象的值不会被修改。
  • update(objId, newVal, opts) 的返回值取决于 opts，一般来说，返回值 V 会基于 objId 对应的对象的当前值和（或）新值 newVal 根据某些预编程的非确定性计算求得；V 会成为 objId 对应的对象的新值。

查询操作是幂等的，但是更新操作不一定幂等。当客户端重新发起某个非确定性的更新操作时，必须确保上一次的请求并没有被执行。例如，客户端在重新发起更新操作前可以先执行一个查询操作，来确认该对象的值是否已经被更新。

如果某个请求没有响应，那么并不能区分是因为客户端的请求在到达存储服务前丢失还是客户端的请求被存储服务所忽略。这样当存储服务经历短暂的异常而丢弃了客户端的请求时，客户端可以简单的重新发起请求，而无需对这一异常场景单独处理。当然出于客户端性能的考虑，会尽可能降低系统异常的频率和持续时间。

在链式复制（chain replication）模式下，系统异常的时间远小于移除一个异常的节点或者增加一个新节点的时间。所以，遇到系统异常，恢复和其他配置变更时，对客户端请求的影响能降低到最小。而其他大多数的副本管理协议（replica-management protocols）要么会阻塞某些操作，要么在异常后或者配置变更期间牺牲一致性保证。

通过客户端视角下对象的状态以及查询和更新操作下客户端状态的转换，本文定义了所描述的存储系统的功能。下图通过伪代码的方式描述了该存储系统的功能：

alt

上图通过两个变量定义了 objIDobjID 所对应对象的状态：HistobjIDHist_{objID} 表示 objIDobjID 所对应对象已执行的更新操作，PendingobjIDPending_{objID} 表示待处理的请求。

上图也同时列出了可能的状态转换。T1 声明了新到达的请求会被添加到 PendingobjIDPending_{objID}。T2 声明了 PendingobjIDPending_{objID} 中的请求被系统忽略时会从 PendingobjIDPending_{objID} 中移除，不过这种情况不会频繁发生。T3 展示了高层次的请求处理过程：首先请求 r 会从 PendingobjIDPending_{objID} 中移除；然后查询操作会生成相应的响应，而更新操作在生成响应之外还会将请求 r 添加到 HistobjIDHist_{objID} 中。

链式复制协议

本文描述的服务器假定具有 fail-stop 特性：

  • 每台服务器发生异常时会停机，而不是继续执行错误的状态转换
  • 服务器的异常能够被系统检测

对于有 t 个副本的对象来说，可以容忍 t - 1 个副本异常而不影响可用性。所以存储对象的可用性就取决于所有持有该对象副本的服务器都发生了异常的概率。因此，本文假定最多有 t - 1 个服务器会同时发生异常。

alt

如上图所示，在链式复制模式下，各节点以一条链的形式来复制对象。链中的第一个节点被称为头节点，最后一个节点被称为尾节点，系统以如下的方式处理请求：

  • 生成响应：每个请求的响应都只由尾节点生成并发送给客户端。
  • 查询处理：每个查询请求都只由尾节点处理，并根据 objIDobjID 查询尾节点本地的数据。
  • 更新处理：每个更新请求都交由头节点处理。首先头节点根据 objIDobjID 更新本地的数据，然后将更新请求以 FIFO 的顺序交由后继节点处理，以此类推，一直传递到尾节点处理。

在上述流程下，系统能保证强一致性，因为查询操作只由尾节点处理，而直到尾节点处理更新操作前，该更新结果都不会暴露给客户端，一旦尾节点更新完成，则后续的查询操作就能读到最新的请求。另外，各节点间 FIFO 的请求传递顺序也保证了某个对象更新的全局顺序性。

因为查询操作只涉及单个节点，所以查询操作是一个轻量级的操作。对于更新操作来说，前 t - 1 个节点的更新操作和最后一个节点生成响应没有直接关联，属于冗余操作，不过也正是这种冗余操作提高了系统的容错性。

如果更新操作不是单纯的直接写入而是需要涉及一系列计算，则该计算只会在头节点计算一次，后续节点的更新可以直接复用头节点计算的结果然后直接写入。这也表明系统可以接受非确定性的更新请求，因为非确定性计算只会在头节点计算一次。

协议细节

客户端不会直接操作 HistobjIDHist_{objID} 和 PendingobjIDPending_{objID}，所以可以以适合的方式来实现它们。当使用链式复制来实现 Fugure 1 中的规范时：

  • 使用 HistobjIDTHist_{objID}^T 来表示 HistobjIDHist_{objID}，表示尾节点所存储的 HistobjIDHist_{objID}。
  • PendingobjIDPending_{objID} 表示链中任一节点收到但还未被尾节点处理的客户端请求集合。

根据规范描述的如何实现 HistobjIDHist_{objID} 和 PendingobjIDPending_{objID}（假设此时不会发生异常），可以发现唯一能影响 HistobjIDHist_{objID} 和 PendingobjIDPending_{objID} 的系统状态转换为：

  1. 链中的某个节点收到了来自客户端的请求（影响 PendingobjIDPending_{objID}）
  2. 尾节点处理客户端请求（影响 HistobjIDHist_{objID}），这里应该是处理更新请求

由于这里假设此时系统不会发生异常，所以上述两种情况已经能够覆盖 Fiture 1 中的状态转换。然后具体来看这两种情况：

  • 链收到来自客户端的请求：客户端将请求发送给头节点（更新）或者尾节点（查询）。在请求未被尾节点处理前，请求 r 会被先添加到 PendingobjIDPending_{objID} 中，并符合 T1 的转换。
  • 尾节点处理请求：处理请求时会先从 PendingobjIDPending_{objID} 中移除请求 r，也就是 T3 的第一步。尾节点处理完后会将请求 r 添加到 HistobjIDHist_{objID} 中，而在本文的定义下为 HistobjIDTHist_{objID}^T。

处理节点异常

如果发现链中某个节点异常（根据 fail-stop 的假设，所有该种类型的异常都能被监测到），则链需要更新配置来剔除异常的节点。针对此，需要引入一个主节点来处理：

  • 监测节点异常
  • 通知链中的每个节点在删除异常节点后的新链中的前继和后继节点
  • 通知客户端新链中的头节点和尾节点

在本文接下来的内容中，本文假设主节点是个永远不会发生异常的单进程。这虽然简化了描述但显然不是一个现实的假设；在作者的原型实现中，主节点有多个副本，并使用 Paxos 协议来协调各节点，所以对外来说整个系统就有了一个不会发生异常的主节点。

主节点能监测三种类型的异常：

  1. 头节点异常
  2. 尾节点异常
  3. 中间节点异常

这三种异常的处理方式取决于更新操作如何在链中传递。

记链的头节点为 H，则下一个节点为 H + 1，以此类推。再记尾节点为 T，定义下述关系表示节点 i 的 HistobjIDiHist_{objID}^i 是节点 j 的 HistobjIDjHist_{objID}^j 的前缀：

HistobjIDi⪯HistobjIDjHist_{objID}^i \preceq Hist_{objID}^j

因为更新操作以 FIFO 的顺序从一个节点传给下一个节点，所以每个节点收到的更新序列是前一个节点收到的更新序列的前缀。所以有：

  • Update Propagation Invariant：对于满足 i≤ji \leq j 的节点 i 和 j（即 i 在链中是 j 的前继节点），有 HistobjIDj⪯HistobjIDiHist_{objID}^j \preceq Hist_{objID}^i。
头节点异常

头节点异常时，系统会从链中移除头节点，并将头节点的下一个节点作为新的头节点。因为系统最多容忍 t - 1 个节点异常，所以必然存在一个新的头节点。

由于删除头节点属于系统转换，所以需要证明这等同于一个空操作或者满足 Figure 1 中的 T1，T2 和（或）T3。修改链中的节点可能会改变 PendingobjIDPending_{objID} 的值，因为 PendingobjIDPending_{objID} 表示链中任一节点收到但未被尾节点处理的请求，所以从链中删除头节点 H 会一并删除 PendingobjIDPending_{objID} 中被 H 接收但还没有传递给下一个节点的请求。而从 PendingobjIDPending_{objID} 中删除请求符合 Figure 1 中的 T2，所以从链中删除头节点 H 符合 Figure 1 中的规范。

尾节点异常

尾节点异常时，系统会从链中移除尾节点 TT，并将尾节点的前一个节点 T−T^- 作为新的尾节点。和前面描述的一样，因为系统最多容忍 t - 1 个节点异常，所以必然存在一个新的尾节点。

删除尾节点会同时影响 PendingobjIDPending_{objID} 和 HistobjIDHist_{objID}，不过也能满足 T3：因为 HistobjIDT⪯HistobjIDT−Hist_{objID}^T \preceq Hist_{objID}^{T^-}（根据 Update Propagation Invariant 可得，因为 T−<TT^- \lt T），对于新的尾节点来说，它未处理的请求相比于旧的尾节点少，所以 PendingobjIDPending_{objID} 序列的大小会减少。另外，根据 T3 的要求，已完成的请求需要追加到 HistobjIDHist_{objID} 中，在更新了尾节点后，某些未被 TT 完成的请求可能已被 T−T^- 完成，所以此时以 HistobjIDT−Hist_{objID}^{T^-} 来表示 HistobjIDHist_{objID}。

中间节点异常

中间节点 SS 异常时，系统会从链中移除节点 SS。主节点会首先通知 SS 的后继节点 S+S^+ 和 SS 的前继节点 S−S^-，告诉它们新的前继和后继节点。不过这有可能会违反 Update Propagation Invariant，因为 SS 收到的某些请求可能还没有转发给 S+S^+（这些请求必然在任一 SS 节点前面的节点 i 的 HistobjIDiHist_{objID}^i 中）。最适合将这些请求发送给 S+S^+ 的就是 S−S^-，不过需要些额外的协作。

记 UU 表示一个请求集合，<U<_U 表示该集合中所有请求的顺序。如果下述条件满足，则认为请求序列 Mr‾\overline{\vphantom{M}r} 和 (U,<U)(U, <_U) 一致：

  1. Mr‾\overline{\vphantom{M}r} 中的所有请求都在 UU 中
  2. Mr‾\overline{\vphantom{M}r} 中的所有请求以符合 <U<_U 的顺序升序排序

最后，对于和 (U,<U)(U, <_U) 一致的请求序列 Mr‾\overline{\vphantom{M}r} 和 Mr′‾\overline{\vphantom{M}r^{'}}，记 Mr‾⊕Mr′‾\overline{\vphantom{M}r} \oplus \overline{\vphantom{M}r^{'}} 表示以出现在 Mr‾\overline{\vphantom{M}r} 中或者 Mr′‾\overline{\vphantom{M}r^{'}} 中的请求组成的请求序列，所以 Mr‾⊕Mr′‾\overline{\vphantom{M}r} \oplus \overline{\vphantom{M}r^{'}} 也和 (U,<U)(U, <_U) 一致（所以 Mr‾⊕Mr′‾\overline{\vphantom{M}r} \oplus \overline{\vphantom{M}r^{'}} 中的请求以符合 <U<_U 的顺序升序排序）。

当节点 S−S^- 的后继节点指向节点 S+S^+ 时，首先将 HistobjIDS−Hist_{objID}^{S^-} 中存在但是可能没有发送给节点 S+S^+ 的请求通过 FIFO 通道发送给节点 S+S^+；只有当这些请求都发送给了节点 S+S^+ 之后，节点 S−S^- 才能将新来的请求发送给节点 S+S^+。这样就保证了 Update Propagation Invariant。

每个节点 i 维护了一个已转发给后继节点但可能还没有被尾节点处理的请求列表，记 SentiSent_i。对 SentiSent_i 的增删非常简单：每当节点 i 将某个请求 r 转发给后继节点时，就将 r 加入 SentiSent_i；当尾节点处理完某个请求 r 时，它就会给前继节点发送一个 ack(r) 请求，表示请求 r 已处理完毕。当前继节点收到 ack(r) 请求时，就将 r 从 SentiSent_i 中移除，并同样给它的前继节点发送一个 ack(r) 请求。

如果尾节点收到了一个请求，那么这个请求必然被所有的前继节点收到，因此有：

  • Inprocess Request Invariant：如果 i≤ji \le j，则 HistobjIDi=HistobjIDj⊕SentiHist_{objID}^i = Hist_{objID}^j \oplus Sent_i。

所以，当主节点通知节点 S−S^- 新的后继节点是 S+S^+ 时，首先节点 S−S^- 将 SentS−Sent_{S^-} 中的请求发送给节点 S+S^+，而已经存在于 HistobjIDS+Hist_{objID}^{S^+} 中的请求则无需发送，这就保证了 Update Propagation Invariant。

alt

上图描述了中间节点发生异常时的流程。主节点发送消息1告诉节点 S+S^+ 新的前继节点，节点 S+S^+ 收到消息后发送消息2告知主节点已确认收到配置变更消息，同时也告知了主节点最后收到的更新消息序列号 sn；然后主节点发送消息3给节点 S−S^- 新的后继节点以及节点 S+S^+ 最后收到的更新消息序列号 sn，节点 S−S^- 就能计算出需要将哪些更新请求发送给节点 S+S^+；最后消息4就是节点 S−S^- 发送给节点 S+S^+ 的更新请求。

扩展链

系统会将异常的节点从链中移除。不过链越短则能容忍的节点异常也就越少，最终由于节点数过少从而影响了对象存储的可用性。解决方法就是当链的长度减少到一定程度时，向链中增加新的节点。鉴于节点异常的概率不是很高，以及往链中添加一个节点不需要太长时间，链的长度基本能维持在期望的 t 个节点的水平（因此 t - 1 个节点都发生了异常才会造成可用性问题）。

理论上可以往链的任意位置插入一个新节点。不过，往链的结尾插入一个新的节点 T+T^+ 是最简单的。对于一个新的尾节点 T+T^+，它的 SentT+Sent_{T^+} 永远是个空列表，所以初始化 SentT+Sent_{T^+} 很简单。剩下的就是要初始化 HistobjIDT+Hist_{objID}^{T^+} 来满足 Update Propagation Invariant。

可以让当前的尾节点 TT 发送自己的 HistobjIDTHist_{objID}^T 给节点 T+T^+ 来完成 HistobjIDT+Hist_{objID}^{T^+} 的初始化。这个过程（如果数据太大可能会需要一段时间）可以和节点 TT 处理来自客户端的查询请求和来自前继节点的更新请求并行执行，只要每一个更新请求都追加到列表 SentTSent_T 中。因为整个过程中满足 HistobjIDT+⪯HistobjIDTHist_{objID}^{T^+} \preceq Hist_{objID}^T，所以也满足 Update Propagation Invariant。因此，只要满足 HistobjIDT=HistobjIDT+⊕SentTHist_{objID}^T = Hist_{objID}^{T^+} \oplus Sent_T，则也满足 Inprocess Request Invariant，节点 T+T^+ 就可以成为新的尾节点：

  • 节点 TT 被通知不再是尾节点。节点 TT 就可以丢弃来自客户端的查询请求，不过更合适的策略是将这些查询请求转发给新的尾节点 T+T^+。
  • 节点 TT 将 SentTSent_T 中的请求按序发送给节点 T+T^+。
  • 主节点被通知新的尾节点是节点 T+T^+。
  • 所有客户端被通知新的查询请求需要发送给节点 T+T^+。

主从复制协议

链式复制也是主从复制协议的一种，而主从复制协议本身也是复制状态机的一种。在主从复制协议下，系统会指定一个节点为主节点，并且：

  • 主节点强制按序执行客户端请求（因此保证了强一致性）
  • 主节点按序将客户端请求或结果更新发送给从节点
  • 主节点会等待所有非异常从节点的请求确认
  • 主节点收到从节点的请求确认后，再响应客户端

如果主节点发生异常，某个从节点会被提升为主节点。

在链式复制模式下，保证请求的顺序性的主节点的角色由两个节点承担。头节点负责处理更新请求，尾节点负责处理查询请求。这种分工一方面拆分了任务，另一方面降低了处理查询请求的延迟和负载，因为只会有一个节点处理查询请求（对单个对象来说），而且这个查询请求不会依赖链中的其他操作。而在主从复制模式下，主节点必须先收到从节点之前更新请求的确认，才能响应客户端的查询请求。

不管是链式复制还是主从复制，更新请求都需要发送给所有的节点，否则副本间可能会出现数据不一致。链式复制以串行的方式分发更新请求，相比于主从复制的并行更新有着更高的延迟。在并行更新下，整个过程的时间就取决于最慢的从节点更新完成的时间；在串行更新下，整个过程的时间等同于所有节点更新完成的时间之和。

当系统发生异常时，其中一个关注的点是客户端感知到的系统异常会持续多久，在这期间系统检测到了异常并需要重新调整集群配置；另一个关注点是由于节点异常所带来的延迟增长。

当某个节点发生异常到这个异常被监测到的时间是主要耗时的地方，不过这个时间对于链式复制和主从复制来说都是一样的。所以，剩下的就是要比较两种方式下异常恢复所需要的时间；相比于 CPU 计算延迟，消息延迟在异常恢复时间中被认为是占据主导地位。

对于链式复制，有三种异常需要考虑：头节点异常，中间节点异常，尾节点异常：

  • 头节点异常：客户端的查询请求不受影响。更新请求暂不可用，整体恢复时间受限于两个消息的处理，一个是主节点广播通知新的头节点和它的后继节点；二是主节点广播通知客户端新的头节点。
  • 中间节点异常：客户端的查询请求不受影响。更新请求可能会延迟不过不会丢失，异常节点后的节点还能正常处理已收到的更新请求，而异常节点前的更新请求可能会延迟。整个过程的延迟取决于 Figure 3 中的四个消息的处理时间。
  • 尾节点异常：客户端的查询和更新请求都不可用。整个过程的延迟取决于两个消息的处理，一个是主节点通知新的尾节点，另一个是主节点通知所有客户端新的尾节点。

在主从复制模式下，需要考虑两种异常：主节点异常和从节点异常。查询请求和更新请求需要处理的情况都一样：

  • 主节点异常：整个过程的延迟取决于5个消息的处理。系统监测到主节点发生异常，然后广播通知所有的从节点，要求各从节点返回已处理的更新请求数量并告知从节点暂停处理请求。每个从节点发送响应给系统。系统收到所有的响应后，选举一个新的主节点，并将主节点的信息广播给所有的从节点。只有处理了最多数量的更新请求的从节点才有可能被选为主节点，之后新的主节点需要给其他从节点补发缺失的更新请求。最后，系统再通知所有客户端新的主节点信息。
  • 从节点异常：客户端的查询请求不受影响，只要当前没有进行中的更新请求。如果有进行中的更新请求，则整个过程的延迟取决于一个消息的处理，系统需要通知主节点某个从节点异常，主节点就知道无须等待这个异常的节点对更新请求的确认。

所以异常情况下，链式复制的最差情况（尾节点异常）不会比主从复制的最差情况（主节点异常）还差；而链式复制的最好情况（中间节点异常）则好于主从复制的最好情况（从节点异常）。如果系统异常时的持续时间是设计存储服务的首要设计目标，那么需要结合请求的类型（查询请求多还是更新请求多）以及不同系统异常发生的概率来决定选择链式复制还是主从复制。

参考