CRAQ论文笔记

Object Storage on CRAQ（使用分配查询的链式复制）

High-throughput chain replication for read-mostly workloads（对于读高负载的高吞吐链式复制） 论文地址：https://pdos.csail.mit.edu/6.824/papers/craq.pdf

一、介绍

CRAQ的目标是在提供高读吞吐时同时还提供强一致性的保证，同时在某些未提交操作下，提供弱一致性的保证。讨论跨数据中心的地域复制优化、多对象更新、对大对象的多播优化更新

二、基本系统模型

2.1 接口和一致性模型

对象存储系统提供两个操作原语 write(objID, V): 写操作存储与objID相关的value值V←read(objID): 读操作获取与objID相关的值 一致性 强一致性保证对一个对象的读写都是按顺序进行，并且总是看到最新的值最终一致性意味着单个对象写操作会被顺序应用在所有节点，但是对不同节点的最终一致读可能返回混乱的数据在某些不一致的时段（例如在写被实施到所有节点以前）。一旦所有副本接受写操作，读取操作将不会获取到更旧的版本数据。如果一个客户端与某个节点维持会话，那么它总是可以看到单调的读一致。

2.2 链式复制（Chain Replication -> CR）

       链式复制是一种复制数据的方法，它跨越多个提供强一致性存储接口的节点。节点形成长度为C的链，写请求只能由头节点处理，读请求由尾部节点处理。当客户端发送一个写请求时，头节点接收并处理完成以后传播到后继节点，然后到达尾部节点，尾部节点处理完成后再返回ACK处理成功的消息给前驱节点，依次到达头部节点，头部节点返回处理成功给客户端。当客户端发送一个读请求，尾部节点接收并返回数据。

2.3 分配查询的链式复制（Chain Replication with Apportioned Queries -> CRAQ）

       受高读负载场景的启发，CRAQ寻求一个通过允许任意节点处理读请求来提高读吞吐量，并且还提供强一致性的保证。

以下是CRAQ的主要扩展

在CRAQ中的节点可以存储对象的不同版本，每个对象都包括单调自增的版本号和额外的版本的属性，版本是 clean 或者 dirty，所有的版本最初标记是clean。当一个节点接收到一个对象的新版本时，此节点增加最新版本到它的版本列表当中。 如果此节点不是尾节点，节点标记版本为dirty并且传播到后继节点如果此节点是尾节点，节点标记版本为clean，同时我们称此对象版本为已提交。尾节点然后可以通过反向传播通知其它节点ACK提交信息。 当ACK提交信息到达某个节点，此节点标记对象版本为clean，然后此节点就可以删除这个对象以前的版本。当一个节点接收到某对象的读请求： 如果请求对象的最新版本是clean，则返回它的值。否则，如果对象最新版本是dirty，此节点联系尾节点查询对象的最新提交版本。节点然后返回对象的最新版本。按结构，节点保证存储此对象的版本。我们注意到尽管尾部可以提交一个新版本在它返回版本查询请求和内部节点发送一个响应给客户端之间，这样也不和我们的强一致性定义冲突（读操作相对尾节点是序列化的）。 CRAQ的吞吐量高于CR，在两个不同场景 读负载较高的场景下，多数的读请求都发生在非尾部节点，因此在此场景下吞吐量是线性增加的。写负载较高场景下，多数读请求都是请求dirty的版本对象，因此需要向尾部查询版本。我们认为这些比起尾部节点接收全查询的负担要小很多，因此尾部节点可以在饱和以前以更高的速度处理查询请求。总的来说，CRAQ读吞吐量仍然要比CR要高。

2.4 CRAQ中的一致性模型

CRAQ支持三种一致性模型：

强一致性：查询的所有对象保证是最新的值最终一致性：对一个对象的读取可能会读取到旧的值，因此这不能满足单调一致的读取（但是在跟单个节点保持会话是可以的）含有最大界限不一致的最终一致性：查询操作得到的值的一致性可能会有某种限度，一种是基于时钟，一种是基于版本