Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS——MIT6-824

发表于

Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS

ABSTRACT

COPS的KV存储系统，并引出了一种新的一致性模型——具有收敛性冲突处理的因果一致性。

INTRODUCTION

对于分布式存储系统，论文从CAP转移到关注ALPS——即可用性、低延迟、分区容忍性和扩展性。论文介绍了一个叫COPS的KV存储系统，并实现了一种新的一致性模型causal+ consistency，收敛冲突处理的因果一致性。除此之外还有一个扩展版本——COPS-GT，提供了get事务来保证提供对于多个key的一致性视图，并且是无锁和非阻塞的。

  • 因果一致性：确保数据存储遵循操作之间的因果依赖关系；
  • 收敛冲突处理：确保副本永远不会发散，并且在所有节点上对相同key的冲突进行相同的处理；

两者结合，确保客户端看到因果正确，无冲突且始终在发展的数据存储。

ALPS SYSTEMS AND TRADE-OFFS

一个分布式系统主要关注以下几个特性：

  • Availability：所有操作不会被永久阻塞或者返回不可用的错误；
  • Low Latency：client能快速完成操作；
  • Partition Tolerance：在网络分区的情况，数据存储能继续提供服务；
  • High Scalability：能做到线性扩展；
  • Stronger Consistency：理想的数据存储最好能提供线性化；

由于CAP的缘故，具备可用性和分区容忍性的分布式系统无法实现强一致性。为了在ALPS系统的要求和易编程之间取得平衡，论文定义了一个中间一致性模型。

CAUSAL+ CONSISTENCY

对于具有收敛冲突处理的因果一致性来说，其抽象模型只有两种操作：put(key,val)和 get(key)=val，即读写。在COPS系统里，单个逻辑副本就是完整的本地集群的所有节点。

该模型定义了三条规则：

  • Execution Thread：如果a和b是单线程内的两个操作，a->b表示a发生在b之前；
  • Gets From：如果a是一个put操作，b是一个获取a写入值的get操作，则是a->b；
  • Transitivity：对于操作a、b、c来说，如果存在a->b和b->c，则一定有a->c；

下图就是这三条规则的一个样例：

Definition

论文将因果一致性定义为两个属性的组合：因果一致性和收敛性冲突处理。

所谓的因果一致性就是上图提到的一个操作顺序结果，如果client 2读取x的时候，先读取到4，再读取到1就会违反因果一致性。但如果两个操作a和b没有任何顺序关系，那么因果一致性就会认为这是一个并发操作，不会做任何的约束，提高系统性能。如果a和b都在同一个key上做put操作，就意味着发生冲突。冲突会带来两个问题：冲突的值可能不确定，即不同副本的值可能不一致；冲突可能产生需要特殊处理的特殊情况；

因此就需要收敛的冲突处理，冲突处理函数必须能在所有副本上以相同的方式进行处理，并且满足交换律和结合律的，即\(h(a,h(b,c))=h(c,h(b,a))\)，不同的副本以接收到顺序处理冲突，收敛处理的结果。

COPS可以自定义冲突收敛函数，默认使用last writer wins。

Causal+ vs. Other Consistency Models

这一章主要介绍各种一致性模型的对比，从约束能力来看：

1
2
Linearizability > Sequential > Causal+ > Causal > FIFO
																			 > Per-Key Sequential > Eventua

Causal+提供了比较适中的一致性模型，且能满足ALPS的系统要求。

Causal+ in COPS

COPS系统提供了两个抽象：其一是版本号，每个key都有一个版本号；另外就是依赖关系，如果b依赖a，那么在复制的时候，需要先复制a，才能再复制b；

Scalable Causality

有些类似的因果一致性系统使用的是日志交换的序列化，在扩展性方便表现不好。而COPS则是采用了划分key空间和编码依赖关系到key元数据的方式来提高扩展性。

SYSTEM DESIGN OF COPS

COPS是一个实现了causal+一致性的、能满足ALPS的分布式存储系统，论文提及了两个版本：一个是简单版的，支持causal+ 的一致性，另一个则是升级版的，支持get事务，能确保client请求keys的时候，存储系统能提供一个一致的相关values的快照，成为 COPS-GT。

Overview of COPS

如下图，COPS就是一个在若干个数据中心运行着的kv存储系统。每个数据中心都有一个本地的COPS集群，保存着完整的一份数据。Client只与本地的数据中心进行联系，并通过COPS的client库进行调用。

COPS系统主要由两个组件组成的：

  • Key-value store：提供了对keys的线性化操作
    • 每个key- value对都有对应的元数据。对于COPS，这个元数据是版本号；对于COPS-GT，则是有版本号和一系列的依赖‘
    • kv存储提供了三种额外的操作：get by version, put after和dep check这三种操作确保了client库和异步复制进程能够提供Casula+一致性和get事务；
    • 对于 COPS-GT，系统保存了kv对的一些老版本数据，提供get事务；
  • client库：主要提供读写操作，COPS的get， COPS-GT的get_trans，还有put。

另外，COPS为了在确保casual+一致性的时候，能降低资源和性能开销：

  • 避免检查所有值的依赖关系；
  • 做垃圾回收，减少存储多版本key和依赖关系元数据的空间开销；
  • 最多进行两次的get事务，降低延迟；

The COPS Key-Value Store

对于COPS，存储元组是<key: {value, version}>，存储的是最新版本的数据；

对于COPS-GT，存储元组是<key: {value, version, deps}>，deps就是一个链表，链表元素是<key, version>；

每个COPS集群都持有完整的一份kv存储数据，每个集群节点根据一致性哈希获得一个独立的keys空间。至于容灾，则是通过链式复制来提供的。在每个集群中，每个key都有一个主节点，主节点会复制到集群内的从节点；至于其他集群也有一个对应的主节点；

集群内的操作是线性化的，本地commit后，跨集群复制时会将数据放到一个队列上异步复制到其他集群的主节点。待其他集群检查完依赖关系后，就会提交该key；

Client Library and Interface

COPS的clientAPI主要包含四个步骤：

1
2
3
4
5
6
1. ctx id ← createContext()
2. bool ← deleteContext(ctx id)
3. bool ← put (key, value, ctx id)
4. value ← get (key, ctx id) [In COPS]
or
4. hvaluesi ← get trans (hkeysi, ctx id) [In COPS-GT]

与传统的kv系统API不同，这个client库会有一个针对COPS-GT的get_trans的API，还有就是所有的函数都需要一个context的参数，该参数可以记录每个client操作的因果关系；

  • COPS-GT Client Library

COPS-GT的client库中context存了一组<key, version, deps>，读取时，client会将该key和其依赖关系添加到当前的context里；写入时，client先取出最新版本key的依赖关系，重新计算新依赖D，待写入成功后，则将写入该项<key，返回的version，D>到context；

下图就是运行过程中的依赖关系变化图：

这种依赖关系的设计会嗲来两个问题：空间占用大和检查依赖关系的成本高。

论文的解决方法是：COPS-GT会在依赖关系被提交后进行垃圾回收，另外就是由于依赖关系具备传递性，一旦依赖项被提交，那么可以确定该依赖项的依赖项也被提交了，所以只需要检查最近依赖；

get_trans需要检查全部的依赖

  • COPS Client Library

COPS的client库需要更好的状态，因此读取时只需要将拿到的key和版本号添加到context就好，至于写入，则是先使用context作为最近的依赖项，返回数据后，则用返回的数据去副高context。

Writing Values in COPS and COPS-GT

所有对COPS的写入都分为两步：同步写入本地集群，异步复制到其他集群，并且都通过下面的API去完成：

1
<bool,vers> ← put_after (key, val, [deps], nearest, vers=∅)

写入本地集群

当client调用put接口时，首先需要计算最近的依赖关系，然后client库会去调用put_after接口，这里COPS不需要传入deps参数。然后该key对应的本地主节点会赋予该key一个版本号。put_after接口可以确保本地集群的commit是强一致性的，至于其他集群的提交在后面叙述。

主节点使用Lamport时间戳来为每次更新计算一个版本号，其中高位是版本号，低位是节点号，通过比较Lamport时间戳，并应用 last-writer-wins 来检查和解决冲突。Lamport时间戳提供了所有分布式事件的偏序关系，与COPS的因果一致性兼容。

复制到其他集群

本地写入提交后，主节点会调用put_after（此时vers参数需要设置为新得到的值）异步复制到其他集群的主节点，主节点进行依赖检查dep_check，一直阻塞直到依赖中的值都写入提交了，参会写入并提交该key值。依赖检查只需要nearest就好。

Reading Values in COPS

COPS的读取会通过下面的API完成，并且version会设置为默认的LATEST，并将得的数据按照前面说的添加到context里。COPS-GT可能需要获取非LATEST版本的值；

1
<value, version, deps> ← get_by_version (key, version=LATEST)

Get Transactions in COPS-GT

COPS-GT提供了get_trans接口，以事务的方式返回一对kv，满足因果一致性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# @param keys list of keys
# @param ctx_id context id
# @return values list of values

function get_trans(keys, ctx_id):
	# Get keys in parallel (first round)
	for k in keys
  	results[k] = get_by_version(k, LATEST)
    
  # Calculate causally correct versions (ccv)
  for k in keys
    ccv[k] = max(ccv[k], results[k].vers)
    for dep in results[k].deps
    	if dep.key in keys
    		ccv[dep.key] = max(ccv[dep.key], dep.vers)
          
  # Get needed ccvs in parallel (second round)
  for k in keys
    if ccv[k] > results[k].vers
    	results[k] = get_by_version(k, ccv[k])
      
  # Update the metadata stored in the context
  update_context(results, ctx_id)
      
  # Return only the values to the client
  return extract_values(results)

论文举了一个相册例子：A修改相册权限acl为“仅朋友可见”，然后修改相册说明desc，然后添加照片到相册album。

现在要读取A的相册，如果出现一个这样的顺序：先读取到旧的acl，检查权限，然后acl被修改，最后越权读到了desc和album。为了避免这种问题，使用get_trans就不会有这个问题：

  • 首先是第一轮并行调用get_by_version，拿到acl，desc和album的值，并获得相应的依赖；
  • 此时可能读到旧的acl、新的desc和album，然后计算ccv，根据依赖关系可以得知desc和album依赖的acl比读到的acl要更新；
  • 然后根据前面的计算，得到需要进行第二轮get_by_version的调用，此时获取指定版本的值；（同样是并行调用）；
  • 此时拿到的acl值就是最新的了；

GARBAGE, FAULTS, AND CONFLICTS

Garbage Collection Subsystem

随着key的更新和插入，系统的空间占用将会无限制增长。COPS的垃圾回收子系统能够删除无用的状态，将系统的空间维持在一个合适的大小。

  • Version Garbage Collection. 仅COPS-GT需要

存储：COPS-GT存储了每个key的多个版本，以便client调用get_by_version；

get_trans算法会限制完成一个事务需要的版本数，即在第二轮获取所需的旧版本数据，因此使用默认为5s的trans_time限制执行时间，若超时则进行重试。写入新版本的key后，COPS-GT只需要保留一段时间的旧版本数据，在此之后就不再使用旧版本来请求数据，并且GC可以降低删除。

  • Dependency Garbage Collection. 仅COPS-GT需要

存储：存储get事务需要的依赖

当COPS-GT的get事务不再需要这个依赖的时候，就可以进行GC回收，至于不需要则是指：kv被写入到所有集群后经过了trans_time。此时的回收主要是清楚value的依赖，并且设置一个never-depend的标志。

清除依赖需要通知其他集群，在其他集群的写提交后trans_time，就需要通知原集群，原集群删除后再通知其他集群也删除。

  • Client Metadata Garbage Collection. COPS和COPS-GT

存储：client存在context里的元数据，包括依赖关系和其他数据。

COPS清理的方式有两种：

  1. put_after作用于所有集群后，会对key标记为never- depend，并返回给client，client就可以在context中进行删除；
  2. COPS节点会从put_after中移除不需要的依赖，这里使用了一个global checkpoint time的概念，版本号比这个小的都移除；global checkpoint time的计算方式：首先是从pending中的put_after里找到最早的Lamport timestamp；然后联系其他集群的等价节点，一对一交换拿到最早的Lamport timestamp，所有数据中心都能知道key范围内最早的Lamport timestamp是什么了；最后数据中心会gossip自己负责的key range的最小时间戳，以找到任何一个节点观测到的最早Lamport timestamp。论文的实现是，每秒执行10次，并且对性能没有明显影响。

Fault Tolerance

Client Failures

Client出故障意味着不能发送请求，因此不需要做任何处理

Key-Value Node Failures

COPS使用了类似FAWN-KV的设计来做链式复制，从而实现节点容灾。在本地集群中，put_after则是直接作用于链的头节点，然后向后传导，在尾节点commit。读取时get_by_version则是直接读尾节点。跨集群传播，则是源集群尾节点将其传播到其他集群的头部节点，进行dep_check后同样沿着链条将值传播，尾节点commit。

Datacenter Failures

应对数据中心出故障，COPS能继续对外工作，但可能会有一些key不一致；

本地集群写入时出错：

  • 集群宕掉，若没有拷贝，数据丢失；
  • 网络分区，数据不会丢失，等分区修复则可；

其他集群写入出错，需要等待管理员解决：

  • 允许复制队列增长，直到故障修复；
  • 重配置，去掉失败数据中心；

数据中心出故障时，COPS-GT无法进行依赖回收，要等到重新配置去掉有问题的数据中心。

Conflict Detection

多线程并发写同一个key会导致冲突。

COPS使用的是前文提到过的last- write-win策略来解决冲突，last则是最新的写入版本号。

COPS也可以自定义冲突检查和解决策略，但需要考虑三个部分的内容：

  • 所有的写入都需要带上前面的版本元数据，即本地集群看到的最近版本；
  • 所有的写入都需要带上隐式依赖数据，在写入前进行依赖检查；
  • 检查出冲突后需要自定义一个收敛的冲突处理函数；

冲突检查：如果写入的key——new，带有了一个版本号prev，而此时可见的当前版本是curr，如果prev!=curr，则意味着发生冲突。

CONCLUSION

本文介绍了一种可扩展的分布式存储系统COPS，可以在不牺牲ALPS属性的情况下提供因果关系+一致性。COPS通过在每个集群的写入之前跟踪并显式检查是否满足因果关系来实现因果一致性。COPS-GT通过在COPS的基础上引入get事务，使client能够获得多个key的一致性视图； COPS-GT进行了优化，减少状态，最小化多轮协议并减少复制开销。