Object Storage on CRAQ——MIT6.824

发表于

Object Storage on CRAQ

Abstract

该论文描述了一种CRAQ(Chain Replication with Apportioned Queries)的对象存储设计，通过链式备份，能够在保证读取吞吐率的同时维持强一致性。

Introduction

对象存储是许多在线服务所需要的，其数据会以一个实体单元来呈现。对象存储支持两种基本原语：读和写。后续，有人开始提出用链式备份的方法来做对象存储，基本思路是将所有存储对象的节点组织在一条链中，其中尾部提供读取请求，而头部则处理所有的写入请求。然后在客户端得到确认之前，写操作会沿着链向后传播。

但这种思路会有不少局限，比如因为所有的读取都会走到同一个节点。该论文就提出了一种CRAQ的设计，实现了一个能够提供强一致性，并且写入低延迟和高吞吐的对象存储。

主要的设计如下：

  1. CARQ所有节点都会处理读请求；
  2. 除了强一致性，CARQ也能为了低延迟对读操作支持最终一致性；
  3. 利用负载均衡特性，提出了一种广域的系统设计，用于跨地理分布的集群来构建CRAQ链，同时保留强大的局部性；

Basic System Model

这一章介绍链式复制模型的主要概念。

Interface and Consistency Model

一个对象存储系统主要提供两个基本原语：

  • write(objID, V);
  • V <—— read(objID);

另外，论文提及了系统实现的两种一致性类型。

  • 强一致性：对于一个对象的读写操作会以某个顺序执行，并且读取对象时会看到最近的写入值；
  • 最终一致性：对于不同的节点的读取可能会返回过时的数据；

Chain Replication

Chain Replication（CR）是一种在多节点之间备份数据，提供强一致性存储接口的方法。

简单来说就是，节点组成一个链表，所有的写请求由链表头部接收，然后向后传导，直到到达尾部节点（此时视为committed）。然后尾部节点将会将响应返回到头部，由头部响应成功（因为实际实现使用的是TCP）。

读请求则是由尾部节点接收。

Chain Replication with Apportioned Queries

对于读取请求比较多的场景，CARQ会通过本地读取来尝试提高读取吞吐量。具体设计如下：

  1. CARQ的节点会存储对象的多个版本，并且会标示每个版本是dirty还是clean；
  2. 当一个节点得到新版本的写入，会追加到版本列表中；
    1. 如果节点不是尾节点，则标示该版本是dirty的；
    2. 如果是尾节点，则直接标示为clean，然后通过链条去答应通知前面的节点；
  3. 前面的节点收到响应后，得知某个版本的节点可以修改为clean；
  4. 如果一个节点得到了对象的读取请求；
    1. 如果对象最后一个节点是clean的，则马上响应；
    2. 否则，节点会联系尾节点，询问尾部节点最后一个committed版本。

具体效果如图所示：

Consistency Models on CRAQ

CRAQ提供了三种一致性模型：

  • 强一致性（默认的）：如上述所示；
  • 最终一致性：允许读取时返回本地已知的最新的对象版本；
  • 最大界限的最终一致性：允许读取请求返回最新的写入对象，即便该对象还没有commit。但会提供一个限制，比如基于特定时间内存的写入，或者某个绝对的版本；

Failure Recovery in CRAQ

双向链表的模式，即一个节点可以知道其后继节点和前驱节点，保证在节点失败时，由其周围的节点去接手。

Scaling CRAQ

在本节中，我们讨论应用程序如何在CRAQ中指定单个数据中心内和多个数据中心内的部署方案

Chain Placement Strategies

一个分布式应用需要面临很多问题，比如对象的大多数写入可能位于同一个数据中心，一些对象只与数据中心的子集有关，重要的对象可能需要不同的副本策略。

CARQ提供了更加灵活的链式配置策略，对于对象来说，使用的是链表ID和key ID结合的两层命名结构，另外就是配置的策略：

  • Implicit Datacenters & Global Chain Size: {num_datacenters, chain_size}

简单来说，就是定一个存储链的数据中心数量，通过对数据中心ID作一致性哈希来明确标识唯一的数据中心；

  • Explicit Datacenters & Global Chain Size: {chain_size, dc1, dc2, ..., dcN}

这个方法是每个数据中心都适用相同大小的链表去存储备份，链表头部位于dc1的节点，链表尾部则在dc2的其中一个节点，以此类推；

  • Explicit Datacenter Chain Sizes: {dc1, chain_size1, ..., dcN, chain_sizeN}

与上面的方法类似，但每个数据中心的链表大小不同；

CRAQ Across Multiple Datacenters

CRAQ本地读取的方法降低了延迟，client也可以灵活选择距离更近的节点。

另一方面，通过链优化，应用程序可以选择组成链的数据中心顺序来最大程度降低写入延迟，确保单个链在每个方向上仅仅需要跨越数据中心的网络边界一次。随着节点增加，很可能写延迟也会明显增加，但相比主备的方法，流水线的写操作可以极大地写入吞吐量。

ZooKeeper Coordination Service

CARQ使用zookeeper来追溯成员身份，并存储链元数据。另外就是当添加或者删除节点时，可以确保CARQ节点能够收到通知。

由于不了解数据中心原始的拓扑结构，因此Zookeeper节点之间的协调消息会在广域网上多次传输。为了消除跨数据中心ZooKeeper冗余的通讯，一个方法是可以构建一个Zookeeper实例的层次结构：每个数据中心可以包含其自己的本地ZooKeeper实例（由多个节点组成），并具有一个参与全局ZooKeeper实例的代表。另一个方法是，修改ZooKeeper本身以使节点知道网络拓扑。

Extensions

本章主要讲述了CARQ的一些拓展点

Mini-Transactions on CRAQ

对于某些应用来说，简单的对象存储读写可能比较局限。有些应用可能需要支持批量操作，有些可能需要有权限控制。因此CARQ提供了拓展功能来支持事务操作。

Single-Key Operations

CRAQ支持几种单key操作：

  • Prepend/Append: 在一个对象的当前值上追加data；
  • Increment/Decrement: 递增或者递减一个key的对象；
  • Test-and-Set: 只有在当前版本与指定版本匹配时才会更新对象；

对于前面两种操作来说，可以直接对链表的头节点进行apply，而不用管它的节点是clean还是dirty，应用完之后向后传播就行。

而对于Test-and-Set操作来说，CARQ并不会锁住对象，而是版本不匹配的时候直接返回。

Single-Chain Operations

Sinfonia最近提出的mini-transactions可以支持对单个链的多个key进行事务操作。它使用了乐观的两阶段提交协议，在prepare阶段会尝试在每个指定的内存地址上获取一个锁。如果可以锁定所有的地址，则协议提交。否则会释放所有的锁并进行充实。在CRAQ中，由于可以指定多个对象存储在同一个链表中，因此这里的两阶段提交减少到单个的交互，即使用单个头部节点则可以接受访问。

Multi-Chain Operations

对于多链参与多对象更新，优化的两阶段协议提交只需要用多个链表头部节点实现即可，链表锁住所有参与事务的keys，直到满足提交条件。

当然这个方法没办法pipeline实现，在一定程度上会影响吞吐量。

Lowering Write Latency with Multicast

CARQ使用多播协议来提高写入性能，由于链的成员资格在节点成员资格改变时是相对文婷的，因此可以为每个链创建一个多播组。然后，不是在整个链上串行传播完整的写入，而是将真实值多播到整个链表，然后紧紧在链上传播少量的元数据信息，以确保所有的副本都在尾部之前收到写操作。

如果存在节点由于某种原因未接收到多播，则该节点可以在接收到写入提交消息之后，然后进一步传播提交消息之前，从其前任中获取对象。

另外，当尾部节点接收到传播的写请求时，可以将多播确认消息发送到多播组，而不是将其沿链向后传播。这样既减少了节点对象在写入后重新进入清洁状态所花费的时间，又减少了客户端感知的写入延迟。如果链中的某个节点未收到确认，则当下一个读取操作要求它查询尾部时，它将重新进入clean。

Management and Implementation

Integrating ZooKeeper

CRAQ使用zookeeper的文件结构来维持数据中心中节点列表的成员资格。

在初始化时，一个CRAQ节点会创建一个临时文件(/nodes/dc_name/node_id)，dc_name就是数据中心的唯一名称，no de_id就是数据中节点的唯一ID。文件内容则是包含了节点的ip地址和端口号。

CRAQ可以查询/nodes/dc_name，来判断数据中的成员资格，通过添加一个watch到/nodes/dc_name，就可以被通知到节点的添加或者删除。

/chains/chain_id则是在CRAQ节点收到创建新链表的请求时，会创建一个文件，chain_id是一个160位的唯一标识符，文件内容时链表的配置策略。而节点通过监控链表文件，从而保证在链表元数据改变时得到通知。

Chain Node Functionality

节点在加入系统时会生成一个随机标识符每个数据中心内会使用该标识符作为one-hop DHT。节点之间或者节点与客户端之间的RPC通信都是通过TCP连接进行的。每个节点及其链的前任，后继和尾部维护着一组连接的TCP连接。请求通过这些连接进行管道传输和循环轮询。

对于跨多个数据中心的链，一个数据中心的最后一个节点保持与其后继数据中心的第一个节点的连接。当外部数据中心中的节点列表发生更改时，订阅更改的节点可以从其本地ZooKeeper中接收通知。

Handling Memberships Changes

对于正常的写传播，CRAQ节点遵循前面的协议。在恢复过程中，有时需要第二种传播方式，即反向传播。例如链表节点可能会在完成向后传播到头部节点之前失败。由于这些可能的故障状况，当新节点加入系统时，新节点会从其前任节点接收传播消息，并从其后继节点接收反向传播消息，以确保其正确性。新节点拒绝客户端对特定对象的读取请求，直到其与后继对象达成协议为止。

无论是节点添加或者删除，变更的节点对应的后继者或者前驱节点都需要传播足够的信息以确保链表的一致性。