本文将介绍CRAQ(Chain Replication with Apportioned Queries)分布式对象存储系统，该系统主要解决大量读负载的分布式系统中的强一致性与高吞吐量之间的权衡问题。

论文参考：《Object Storage on CRAQ —— High-throughput chain replication for read-mostly workloads》

  在当今云计算时代，分布式存储系统扮演着至关重要的角色。CRAQ(Chain Replication with Apportioned Queries)作为一种创新的分布式存储系统，完美地平衡了一致性与性能的需求。它在保持强一致性的同时，通过独特的设计解决了传统链式复制中的性能瓶颈问题。

  在传统的分布式存储系统中，我们经常面临一个两难的选择：是追求强一致性，还是追求高性能？许多商业系统如Google、Amazon、Facebook等，都选择牺牲强一致性来换取更好的性能和可用性。然而，CRAQ提供了一个优雅的解决方案，它证明了我们不必在这两者之间做出非此即彼的选择。

  CRAQ的最大亮点在于它的”分散查询”机制。不同于传统链式复制中所有读请求都必须由链尾节点处理的方式，CRAQ允许在链上的任意节点进行读操作。这个看似简单的改变，带来了革命性的性能提升：在读操作为主的场景下，性能可以提升数倍，同时还保持了强一致性的保证。这种创新设计使CRAQ特别适合现代互联网应用的需求，尤其是那些读操作远多于写操作的场景，如内容分发、社交媒体等应用。

系统模型

首先来看看对象存储系统的接口和一致性模型：
接口：

  • write(objID, V)：写操作将值V存储到对象标识符objID。
  • read(objID)：读操作从objID检索值V。

一致性模型：

  • 强一致性：保证所有读写操作按顺序执行，读操作总能获取最新写入的值。
  • 最终一致性：写操作按顺序应用于所有节点，但在传播完成前，读操作可能返回旧数据。一旦所有副本更新完成，读操作不会返回旧版本；若客户端与同一节点保持会话，还需能保证单调读一致性（但跨节点会话不适用）。

链式复制（Chain Replication, CR）

  链式复制（Chain Replication, CR）是一种用于分布式系统的数据复制方法，能够提供强一致性的存储接口。其核心思想是将多个节点按照顺序组织成一条链，写操作从链头开始，逐步传播至链尾，而读操作则全部由链尾处理，以确保数据的一致性。

  在写操作中，客户端的写请求首先被链头节点接收，然后写数据依次向链中的下一个节点传播。当写操作到达链尾并被应用到所有副本后，该写操作才被视为提交完成。此时，链尾会向链头发送确认消息，链头再将确认结果返回给客户端。通过这种方式，CR 确保了所有写操作按顺序传播并最终一致。如下图，是一个拥有四个节点的链：
四个节点的链
  在读操作中，所有客户端的读请求都由链尾节点处理。由于写操作只有在到达链尾并提交后才算完成，因此链尾节点返回的数据始终是最新的、已提交的值。这种设计保证了强一致性，因为所有读操作都能看到全局有序的最新数据。

  CR 的一个显著优点是其高效的写操作性能。通过流水线机制，多个并发写请求可以同时在不同节点上传播，从而分摊了传输成本，提高了整体吞吐量。此外，由于其拓扑结构简单，当某个节点发生故障时，只需调整前后节点的连接即可快速恢复，无需复杂的领导者选举或共识协议。

  然而，CR 也存在一定的局限性。由于所有读请求都集中在链尾节点，其读吞吐量受限于单一节点的处理能力，无法通过增加节点数来扩展读性能。此外，随着链长度增加，写操作需要经过更多节点传播到尾部，这可能导致写延迟上升。

CRAQ通过多节点处理读取流量来优化读吞吐量

  CRAQ（Chain Replication with Apportioned Queries）针对以读为主的工作负载场景，通过允许链中任意节点处理读请求来提高读取吞吐量，同时仍然保证强一致性。为了保证这一点，CRAQ：

  1. 多版本存储与状态标记：每个节点可以存储对象的多个版本，每个版本包含一个单调递增的版本号，并标记为“干净（clean）”或“脏（dirty）”状态。新版本初始标记为clean，只有当写操作在链尾提交后，版本才会被标记为clean。
  2. 写操作传播流程：
    • 当节点接收到写操作时，会将该对象的新版本添加到本地存储中。
    • 如果该节点不是链尾，则将新版本标记为脏，并将写操作传递给下一个节点。
    • 如果该节点是链尾，则将新版本标记为干净，并反向通知其他节点数据已经提交（committed）。
    • 当节点收到链尾的提交确认消息时，会将对应版本标记为干净，并删除所有旧版本。
  3. 读操作传播流程：
    • 如果节点存储的最新版本是干净的，则直接返回该值。如下图所示：
      读干净节点
    • 如果最新版本是脏的，节点会向链尾发送“版本查询请求”，获取链尾已提交的最新版本号，并返回对应的对象值。如下图所示：
      读脏节点

对象的“脏”或“干净”状态也可以通过隐式方式确定。如果节点只存储一个版本，则该版本为干净；如果存储多个版本，则最新版本为脏，需要从链尾获取正确的顺序版本。

  在 CRAQ 的操作中，当写请求从链头传播到链尾时，链中的节点会根据写入状态动态调整其数据状态。例如，当写操作传播到中间节点时，这些节点会暂时处于脏状态，并存储多个版本。如果此时有读请求到达这些脏节点，它们会向链尾查询已提交的最新版本号，然后返回对应的数据值。这种机制确保了即使在写操作传播过程中，所有节点仍然能够返回一致的数据。

CRAQ 相较于 CR 的性能提升体现在以下两种场景中：

  • 以读为主的工作负载：大部分读请求由非链尾节点（C-1 个）处理，吞吐量随链长度线性扩展。
  • 以写为主的工作负载：大部分读请求需通过非链尾节点查询版本，但这些查询比完整读取轻量，因此链尾能以更高速率处理查询，从而提高整体吞吐量。

此外，对于长链和持续写多的场景，可以进一步优化，让链尾仅处理版本查询而非完整读取，以提升读取性能。

CRAQ的一致性模型

CRAQ 支持的三种读取一致性模型，以满足不同应用对一致性的需求：

  1. 强一致性（Strong Consistency）：默认模式，保证所有读取操作返回最新提交的写入值。
  2. 最终一致性（Eventual Consistency）：允许节点返回其已知的最新版本，但不同节点可能返回不一致的版本，无法保证单调读一致性（但单节点会话内可保持）。
  3. 最大边界不一致的最终一致性（Eventual Consistency with Maximum-Bounded Inconsistency）：允许读取未提交的新版本，但限制不一致范围（基于时间或版本号）。

CRAQ故障处理

  CRAQ 的故障恢复机制与 CR 类似，每个节点需了解其前驱、后继以及链头和链尾的位置。当链头或链尾故障时，其直接后继或前驱节点分别接替其角色；中间节点的加入或故障则像双向链表一样在两节点间调整。CRAQ 支持节点在链中任意位置加入，并能在恢复过程中正确处理故障。

CRAQ扩展

  接下来介绍一些CRAQ在单数据中心和多数据中心下的链布局方案，以及CRAQ如何在ZooKeeper中存储元数据和成员信息。

CRAQ链安置策略

链标识符与键标识符：CRAQ 采用了链标识符和键标识符的两级命名层次结构，其中链标识符决定了哪些节点将存储该链的所有键，而键标识符则为每个链内的对象提供唯一命名。这种设计使得系统能够灵活应对不同的工作负载和数据存储需求。

CRAQ提供了几种主要的链安置策略：

  1. 隐式数据中心与全局链大小：在这种方式下，用户只需定义存储链的数据中心数量，而不需明确指定具体的数据中心。系统通过一致性哈希算法，结合唯一的数据中心标识符，自动确定哪些数据中心将存储该链。
    {num_datacenters, chain_size}
  2. 显式数据中心与全局链大小：在此方法中，每个数据中心使用相同的链大小来存储副本，链头位于第一个数据中心（dc1），而链尾则位于最后一个数据中心（dcN）。这种配置允许用户提供一个有序的数据中心列表，通过一致性哈希确定每个数据中心内部的存储节点。此外，这种方法还允许将链大小设置为零，表示该链应使用每个数据中心内的所有节点。
    {chain_size, dc1, dc2, . . . , dcN}
  3. 显式数据中心链大小：这种方式允许为每个数据中心单独指定链大小，从而实现负载均衡的非均匀性。这种灵活性使得系统能够根据不同的数据中心需求进行优化。
    {dc1, chain_size1, . . . , dcN, chain_sizeN}

  在方法 2 和 3 中，可以将某个数据中心设定为主数据中心，这意味着在短暂故障期间，写操作仅会被该主数据中心接受。如果主数据中心失效，其他数据中心可以接管写操作，确保系统的持续可用性。如果没有定义主数据中心，则在分区情况下，写操作仅会在包含大多数节点的分区中继续进行，否则该分区将变为只读状态。

  此外，CRAQ 还支持更复杂的链配置方法，例如可以指定一个备用的数据中心，仅在其他数据中心失效时参与链操作。用户还可以定义一组可替代的数据中心（如“East coast”），其中任何一个都可以填补方法 2 中有序列表中的一个位置。值得注意的是，CRAQ 不限制可以写入单个链的键标识符数量，这使得系统能够根据应用需求实现高度灵活的链配置，从而适应不同场景下的数据存储和访问需求。

单数据中心下的CRAQ

  CRAQ 当前的实现采用一致性哈希（consistent hashing）将多个链分布在数据中心内，这种方法将多个链标识符映射到单个链头节点。这种做法与越来越多的基于数据中心的对象存储系统相似。另一种方法是由 GFS 和 CR 提出的，即使用成员管理服务作为目录服务，随机分配和存储链的成员资格，这样每个链可以包含一些随机的服务器节点。这种方法提高了并行系统恢复的潜力，但也增加了中心化和状态管理的复杂性。虽然 CRAQ 也可以采用这种替代的组织设计，但这需要在协调服务中存储更多的元数据。

多数据中心下的CRAQ

  CRAQ 在跨多个数据中心时的设计显著提高了读取延迟。当客户端可以选择靠近的节点进行读取时，只要链处于干净状态，节点就能直接返回本地副本，无需发送广域请求。这与传统链复制（CR）不同，后者要求所有读取由可能距离较远的链尾节点处理。

  CRAQ 还允许根据数据中心选择链头和链尾节点，以利用对象的引用局部性。例如，Yahoo! 的 PNUTS 数据库设计基于其数据中心中观察到的高写入局部性。这使得应用能够优化广域链的选择，从而减少写入延迟和网络成本。

  通过优化数据中心的顺序，应用可以减少写入延迟，并确保单个链在每个方向上仅跨越数据中心的网络边界一次。尽管随着更多数据中心的加入，广域链接上的写操作延迟会增加，但 CRAQ 允许写操作沿链进行流水线处理，从而显著提高写入吞吐量。这使得 CRAQ 在处理大量写请求时表现优异，适用于需要高效读写的分布式存储场景。

CRAQ与ZooKeeper

ZooKeeper见：ZooKeeper

  CRAQ 采用 ZooKeeper 作为其协调服务，以构建一个容错的分布式应用程序协调机制。ZooKeeper 提供了一种高性能、分布式的方法来跟踪组成员资格，并存储链的元数据。通过使用 ZooKeeper，CRAQ 节点能够在节点添加或移除时接收到通知，同时也可以在感兴趣的元数据发生变化时获得更新。

  ZooKeeper 提供类似于文件系统的分层命名空间，其状态存储在内存中，并通过日志备份到每个 ZooKeeper 实例中。这种设计确保了高可靠性和可扩展性。ZooKeeper 使用类似于两阶段提交的原子广播协议来达成一致性，优化了读取操作，特别是在读多写少的工作负载下表现良好。尽管 ZooKeeper 在单个数据中心内提高了读取可扩展性，但它并未针对多数据中心环境进行优化。在多个数据中心之间传递协调消息时，由于缺乏拓扑知识，这些消息可能会多次通过广域网传输，从而影响性能。

  为了解决跨数据中心的冗余通信问题，可以构建一个 ZooKeeper 实例的层次结构，每个数据中心包含自己的本地 ZooKeeper 实例，并有一个代表参与全局实例。此外，还可以考虑修改 ZooKeeper，使其能够识别网络拓扑。

CRAQ使用ZooKeeper

  CRAQ系统需要一个组成员服务的功能，因此采用ZooKeeper的文件结构来维护每个数据中心的节点列表。CRAQ节点在初始化时会在ZooKeeper中创建一个临时文件，路径为/nodes/dc_name/node_id，其中dc_name是数据中心的唯一名称，node_id是节点在数据中心内的唯一标识。该文件的内容包含节点的IP地址和端口号。

  CRAQ节点可以查询/nodes/dc_name以获取数据中心的成员列表，而不需要定期检查变化，因为ZooKeeper允许进程在文件上创建监视器。当CRAQ节点创建了一个临时文件以通知其他节点加入系统后，会在/nodes/dc_name的子节点列表上创建watch，以确保在节点添加或移除时收到通知。

  当CRAQ节点接收到创建新链的请求时，会在/chains/chain_id路径下创建一个文件，chain_id是链的160位唯一标识符。该文件包含链的配置策略信息，但不包括当前节点列表。参与链的任何节点都会查询链文件并在其上设置watch，以便在链元数据发生变化时得到通知。

  虽然这种方法要求节点跟踪整个数据中心的CRAQ节点列表，但选择这种方法是因为假设链的数量通常比系统中的节点数量多一个数量级，或者链的动态性可能大大超过节点的加入或离开。如果情况允许，可以通过将每个节点仅跟踪一部分数据中心节点来提高当前方法的可扩展性，即根据node_id前缀将节点列表划分到/nodes/dc_name/下的不同目录中，让节点仅监控自己的和附近的前缀。此外，团队通过构建温和风格的包装函数成功将ZooKeeper的异步API集成到代码库中，这大大简化了代码复杂性。

CRAQ扩展

小型事务（Mini-Transactions）

  在分布式对象存储中，传统的全对象读写接口可能对某些应用造成限制。例如，BitTorrent 跟踪器或其他目录服务需要支持列表的添加或删除，分析服务可能希望存储计数器，或者某些应用可能希望提供对特定对象的条件访问。这些功能在仅使用纯粹的对象存储接口时难以实现。然而，CRAQ 提供了关键扩展，以支持事务操作，从而满足这些需求。

单键操作

CRAQ 支持几种单键操作，这些操作的实现相对简单。主要操作包括：

  1. 前置/后置添加（Prepend/Append）：在对象当前值的开头或结尾添加数据。
  2. 递增/递减（Increment/Decrement）：对键的对象进行加或减，视为整数值。
  3. Test-and-Set：仅在键的当前版本号等于指定版本号时更新对象。

  对于前置/后置和递增/递减操作，链头节点可以直接对最新版本的对象应用这些操作，即使该版本是脏的，然后将完整的替换写入传播下去。此外，如果这些操作频繁，链头还可以缓冲请求并批量更新，这比传统的两阶段提交协议要高效得多。

  在Test-and-Set操作中，链头会检查其最近提交的版本号是否与指定的版本号匹配。如果没有未提交的版本，链头接受该操作并向下传播更新；如果有未提交的写入，则拒绝该操作。虽然可以通过“锁定”对象来避免写入，但由于这种情况很少发生且会显著影响性能，因此选择CRAQ不实施此方案。

单链操作

  CRAQ系统中的单链操作设计巧妙地解决了多对象事务处理的问题。CRAQ的链式拓扑结构在支持迷你事务方面具有独特优势。系统允许将经常一起出现在多对象事务中的对象存储在同一条链上，从而保持数据的局部性。共享相同chainid的对象会被分配到同一个头节点，这样就将传统的两阶段提交简化为单一交互，因为只涉及一个头节点。

  CRAQ的另一个显著特点是，只涉及单链的迷你事务可以仅通过单个头节点来调解访问，因为头节点控制着链上所有键的写入访问权限。唯一的权衡是，如果头节点需要等待事务中的键变为clean状态，写入吞吐量可能会受到影响。

多链操作

  当涉及多个链的对象更新时，乐观两阶段协议只需要在链头节点之间实现，而不需要涉及所有节点。链头节点可以锁定迷你事务中涉及的所有键，直到事务完全提交。不过，开发人员在使用大规模锁定和迷你事务时需要谨慎，因为这会降低CRAQ的写入吞吐量。原因是对同一对象的写入不能再进行流水线处理，而流水线处理恰恰是链式复制的主要优势之一。

多播（Multicast）—— 降低写延迟

  CRAQ系统通过利用多播协议来提升写入性能，特别是在处理大型更新或长链时效果显著。在数据中心内部，通常采用网络层多播协议，而在广域网链中则更适合使用应用层多播协议。这些多播协议不需要保证顺序性或可靠性。

  系统的创新之处在于改变了传统的写入传播方式。不再是沿着链条串行传播完整的写入内容，而是将实际值多播给整个链上的所有节点。只需要一个小型元数据消息沿链传播，以确保所有副本在多播消息到达尾节点之前都收到了写入。如果某个节点因故未收到多播消息，它可以在收到写入提交消息后、传播提交消息之前从其前驱节点获取对象。

  此外，当尾节点收到传播的写入请求时，可以向多播组发送确认消息，而不是沿链反向传播。这种方式不仅减少了节点对象在写入后重新进入clean状态所需的时间，还降低了客户端感知到的写入延迟。同样，多播确认也不需要保证顺序性或可靠性，因为如果链中的节点没有收到确认，它会在下一次读取操作需要查询尾节点时重新进入clean状态。

CRAQ具体实现

CRAQ的链节点程序

  CRAQ的链节点程序实现了大部分功能，能够根据运行时配置设置作为链复制节点或CRAQ节点工作。节点在加入系统时生成随机标识符，并在每个数据中心内使用这些标识符组织成一跳DHT。链的前驱和后继节点在DHT环中定义。每个链由160位标识符命名，链的DHT后继节点被选为该数据中心的第一个节点，其后继节点则构成数据中心的子链。

  所有节点之间以及节点与客户端之间的RPC通信通过TCP连接进行，且关闭了Nagle算法。每个节点维护与其链的前驱、后继和尾节点的TCP连接池，请求通过这些连接进行流水线处理。

  对于跨多个数据中心的链，某个数据中心的最后一个节点与其后继数据中心的第一个节点保持连接。任何与外部数据中心的节点保持连接的节点也必须在外部数据中心的节点列表上设置watch。当外部数据中心的节点列表发生变化时，订阅变化的节点只会从其本地ZooKeeper实例接收通知，从而避免额外的跨数据中心流量。

CRAQ中的成员关系的改变（反向传播）

  CRAQ节点在正常写入传播时遵循特定协议，但在恢复过程中，有时需要进行反向传播以维护一致性，特别是在节点添加和故障情况下。例如，当新节点作为现有链的头节点加入时，原链头需要向后传播其状态。为了应对后续故障，系统需要保持稳健性，以防止故障导致更远的反向传播产生。

  当新节点加入时，它会从前驱和后继接收传播消息，以确保其正确性。在此过程中，新节点在与后继达成一致之前拒绝客户的读取请求。反向传播消息包含节点对象的完整状态，而不仅仅是最新版本，这样新加入的节点可以响应未来的确认消息。

对于节点添加情况：

  1. 新节点是前驱：
    • 当新节点A作为N的前驱加入时，原节点N需要向A反向传播所有对象。这意味着N将其当前持有的所有对象状态发送给A，以确保A能够获得最新的数据。
    • 在此过程中，N还需根据情况更新链的头尾：如果A成为新的头节点，N可能需要调整其角色，确保链的完整性和一致性。
  2. 新节点是后继：
    • 如果新节点A作为N的后继加入，N会将链中的所有对象传播给A。这一过程确保A能获取到链中最新的数据。
    • 在传播过程中，N还需进行必要的对象版本一致性检查，以确保A与链中其他节点的数据保持一致。这可能涉及到对比版本号或状态，以决定哪些对象需要被更新。

对于节点删除情况：

  1. 被删除的节点是后继：
    • 当后继节点D被删除时，原节点N需要将链中的所有对象传播给新的后继节点。这个过程确保新的后继能够接收到D未完成的写入操作。
    • N在传播时会尽量减少数据传输，仅传送那些新的、未知的对象版本，以提高效率。
  2. 被删除的节点是前驱：
    • 如果被删除的节点D是N的前驱，N需要向新的前驱节点反向传播所需的对象。这是因为D可能在被删除之前未能完成与其前驱的确认或传播。
    • 在此情况下，N还需根据情况更新链的头尾：如果D是链的头节点，N将承担起头节点的职责；如果N是链的尾节点，则需要放弃尾节点职责，并将所有对象传播给新的后继。

在其他情况下，无需采取任何行动。整个过程确保了在链中添加或删除节点时的一致性和有效性。

总结

  CRAQ（Chain Replication with Asynchronous Queue）是一种高效的数据一致性协议，旨在提高数据中心内节点的可靠性和性能。通过使用ZooKeeper进行节点管理和状态监控，CRAQ确保了节点的动态加入和离开不会影响系统的稳定性。在节点之间的通信中，CRAQ采用了反向传播和正常传播机制，以保证数据的一致性和完整性。整体设计考虑了节点的动态变化，使其适用于管理型数据中心环境。