Abstract 摘要

文件存储系统在有潜在错误风险的机器上备份和复制，来提供可靠性和可扩展性。 但是很多都牺牲了强一致性来获取高吞吐量。 CRAQ是一个对象存储系统，改进了链式复制，将负载分配到每一个对象，既维持了强一致性，也提高了吞吐量。 如果系统能够接受，尤其是在系统动荡的情况下，它会提供noncommit的操作，可维持弱一致性。

1 Introduction 介绍

对象存储支持两个基础原语：read（或query）、write（或update），对象的命名空间会被分区并多次备份 只需要知道对特定对象的修改顺序，不需要是整个系统，对于一个对象的一致性维护成本比维护整个系统要低

基础链式复制

头结点负责写，尾结点负责读头结点的写操作链式传递，保证强一致性，尾结点负责向client发送确认单一的读结点会产生热点，导致性能下降多个chain可以通过一致性hash来形成聚簇，提供更好的负载均衡（具体实现我也不知道），但是在实际情况中还是因为object分布产生问题

CRAQ

在保证强一致性的前提下，所有结点都提供读操作在写竞争的情况下，为了低延迟读，提供最终一致性在短暂的分区产生时，会退化为只读读可以完全由本地集群处理，或者在最坏的情况下，需要在高写度期间在广域网中传输简洁的元数据信息

2 Basic System Model 基本系统模型

2.1 Interface and Consistency 接口和一致性模型

write(objID, v)：写V <- read(objId)：读强一致性：对于一个object的所有的读写都按照一定顺序，保证能够读到最后写入的值最终一致性：系统中对于一个object的写依然是按序传递给结点，最终一致性会导致在某些时候一些不同的节点会返回过期的数据。但是当所有的节点都接收了数据，就不可能再读到旧值了

2.2 Chain Replication 链式复制

头结点负责所有读，将读传递给后续结点，尾结点负责提交。 头结点会把TCP连接也传递下来，所以尾结点可以给用户反馈。 相比主从模型，CR具有更好的吞吐量，但是恢复能力较弱。 只从尾结点读会减少吞吐量，但是能够提供强一致性。

2.3 Chain Replication with Apportioned Queries 分散请求的链式复制

一个CRAQ结点可以储存多个版本的object，有一个单调递增的版本号，和一个值为clean或dirty的属性。所有版本在初始化的时候都是clean。当收到一个新的版本号，结点会在object后增加最新的版本号。 2.1 如果不是尾结点，将该版本标记为clean，向后传递 2.2 如果是尾结点，就设置为clean，相当于commited，然后将这个确认回传。结点收到了回传的ack，就将这个version标记为clean，然后删除前面所有的版本。如果结点收到一个读请求 4.1 该节点最后一个版本是clean，直接返回 4.2 如果是dirty，就会联系尾结点，询问最新的已提交版本，然后返回那个版本的值。这样不违反强一致性

只要结点在收到写提交确认后立刻删除旧版本信息，就可以隐式地判断一个节点是的状态。也就是如果一个结点只有一个状态，就是clean的，有多个就是dirty的。 在下面两个场景中，CRAQ的吞吐量优于CR：

Read-Mostly多数读负载：会被线性地分配到chain上面Write-Heavy大量写负载：会产生很多对于dirty数据的读，就会对尾结点发送确认消息，但肯定要比直接向尾结点请求整个object开销小

对于长的chain，可以尝试让尾结点只负责对于version的确认，不提供读服务

2.4 Consistency Model on CRAQ 一致性模型

对于读有三种不同一致性的模型

强一致性：就是之前描述的模型最终一致性：返回当前结点最新version的值。单个结点能够保持单调递增的读一致性有最大非一致性限制的最终一致性：允许返回未提交的最新version的值，但是只针对一些结点。如果chain可用，可能返回较新的值，如果chain分区了，会返回较旧的值

2.5 Failure Recovery in CRAQ 错误恢复

每个结点知道前驱和后继 头结点宕机了，他的后继成为头 尾结点宕机了，他的前驱成为尾 中间结点宕机了，前后相连 可以在任意位置加入新的机器

3 Scaling CRAQ 扩展

3.1 Chain Placement Strategies 放置策略

一般场景有这些需求

对于一个object的写一般都在一个数据中心一些object可能之和部分数据中心有关热门的object需要多备份一些

每个object有两个标识符 chain identifier：哪些节点保存了这个object object identifier：在chain里面object的唯一标识符

1 Implicit DataCenter & Global Chain Size

$$\{num\_datacenter,chain\_size\}$$ 到底哪些数据中心保存了chain没有被显示指定，会通过一致性hash进行计算

2 Explicit Datacenter & Global Chain Size

$$\{chain\_size,d{c}_1,d{c}_2,...,d{c}_n\}$$ 所有的datacenter都保存长度相等的chain。链头保存在数据中心$d{c}_1$中，链尾在$d{c}_n$中 用一致性hash来解决数据中心中哪些结点来保存该chain中的数据 如果$chain\_size$为0，那么表示数据中心所有结点都保存一份数据

3 Explicit Datacenter Chain Sizes

$$\{d{c}_1,chain\_siz{e}_1,...,d{c}_n,chain\_siz{e}_n\}$$ 每个数据中心中的chain长度都可以不同

在2、3模式中，可以将$d{c}_1$设置成master datacenter，如果发生了短暂的错误，那么只有master会接收到写操作。如果$d{c}_1$出错了，$d{c}_2$会接管成为master 对于key identifier的数量是没有限制的

3.2 CRAQ within a Datacenter

如何在一个datacenter放置多个chain 可以用一致性hash将不同的chain identifier映射到一个结点中 也可以随机分配，但是需要维护额外的metadata

3.3 CRAQ Across Multiple Datacenters

用户可以选择就近地读取数据 可以将chain的存储位置进行优化选取，这样可以优化读取时间 虽然主从备份是可以并行写的，但是链式备份支持流水线

3.4 Zookeeper Coordination Service

使用Zookeeper来保存元数据，还可以通知结点的加入和移除 在多个数据中心中部署Zookeeper会增加网络开销 可以通过层级Zookeeper来减少冗余，例如一个zk结点和外界通信，其他的维持本地数据

4 Extensions

4.1 Mini-Transactions on CRAQ

4.1.1 Single-Key Operations 单键操作

CRAQ已经支持这些原子性单键操作

Prepend/Append：在一个object的前面或后面追加Increment/Decrement：对于一个整数类型的加减Test-and-Set：满足条件下的赋值 对于前两个，头结点可以立即接受；或者将多个合并成一个batch，将会优于两阶段提交 对于TAS操作，头结点在判断之后有权驳回；头结点可以锁上一个数据，但是太影响性能了

4.1.2 Single-Chain Operations

实现抓取对所有要修改的object的锁，如果能够全部获取，就提交修改，不然就释放锁 多个拥有相同chain id的object共享同一个结点作为头部，就不需要两阶段提交了

4.1.3 Multi-Chain Operation

只需要在多个chain的头部实现优化的两阶段提交，但是要注意对性能的影响

4.2 Lowering Write Latency with Multicast

在chain的成员稳定之后，可以形成一个多播组，这个多播协议不需要按序和提供可靠性 写入的值可以直接通过多播传递给所有的结点，少部分metadata通过链式传递，用来确认是否所有结点都收到了消息，如果一个结点没有收到，也可以在收到commit信息后从前驱或者后继获得value 尾结点对于消息的commit确认也可以通过组播发送 如果一个结点未收到commit ack，也可以在下一次的读请求时向尾结点确认是否已经commit