Distributed System Paper

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

Posted by keys961 on April 29, 2020

1. Overview

本文介绍一个KV存储系统COPS，其实现了集群级别的“带有收敛冲突处理的因果一致性”（Causal+），并有很好的扩展性。

此外基于COPS的COPS-GT，引入了get-事务，能获得多个键的一致性视图，不需要加锁/阻塞，最多只需两轮并行的内部数据中心请求。

“带有收敛冲突处理的因果一致性”分为2部分：

  • 因果一致：数据存储符合操作的因果依赖
  • 收敛的冲突处理：冲突操作下，副本永远不会发散（解决冲突的行为相同），且在所有副本上都会被相同地处理

有了上面这2个部分，客户端可以看到的是满足因果依赖、无冲突并一直在发展的集群存储。

COPS架构：

  • 有多个数据中心，每个数据中心包括一组客户端和一组服务端节点
  • 后台进行跨数据中心的复制，并满足Causal+一致性

img

2. ALPS系统

ALPS代表：

  • Availability（可用性）：所有的操作都会成功，不会有操作永远阻塞或返回一个不可用的错误
  • Low Latency（低延迟）：客户端操作响应快
  • Partition Tolerance（网络分区容错）：数据中心之间发生网络分区，依旧可用
  • Scalability（可扩展性）：添加$N$个系统资源，能带来$O(N)$的吞吐和存储能力的增长

由于CAP的缘故，为了达到ALPS的目标，一致性（C，即强一致性）被牺牲，取而代之的是Causal+ 一致性。

3. Causal+ 一致性

3.1. 模型抽象

操作：只有2个，即

  • put(k, v)
  • get(k) = v

逻辑副本：值存储和访问的地方，在COPS中，一个逻辑副本对应一个本地集群的所有节点

潜在的因果关系：用$\leadsto$表示，规则如下

  • 线程内规则：若一个线程先后有$a$，$b$两个操作，则$a \leadsto b$
  • 读取规则：若$a$是put操作，$b$是get操作且读到$a$写的值，则$a \leadsto b$
  • 传递规则：若$a \leadsto b$, $b \leadsto c$，则$a \leadsto c$

3.2. Causal+ 定义

a) 因果一致

get操作读到的值，和之前$\leadsto$顺序的操作得到的结果，两者一致。

如下图所示，箭头代表了$\leadsto$关系，Client 3的get(x) = 4操作值和之前的$\leadsto$顺序操作得到的值一致，满足因果一致：

2.png

但是$\leadsto$是一个偏序关系，可能出现$a \not \leadsto b$且$b \not \leadsto a$，即$a$和$b$是并发操作。若并发操作作用于相同的键，则它们是冲突的，这会带来一些问题：

  • 得到的副本可能是发散的，即冲突操作得到的值不能确定
  • 带来一些额外的异常，需要特殊处理

因此就需要“+”的部分，即收敛的冲突处理。

b) 收敛冲突处理

所有的冲突写操作，都会以相同的行为（解决冲突），作用于所有的副本。

这个冲突解决函数记为$h$，必须满足交换率和结合律，即$h(a, h(b, c)) = h(c, h(b, a))$。这保证了冲突操作不论顺序如何，都可以得到一个相同的值，即达成收敛。

冲突函数由很多种，常用的如last-writer-wins（即取最后一个操作值），也可以自定义该函数（如Bayou和Dynamo）。

COPS可自定义冲突函数，不过默认是last-writer-wins。

3.3. Causal+ 与其它一致性模型的对比

约束对比如下图所示，Causal+提供了一个较为适中的一致性约束：

1.png

  • 线性化：保持全局且实时的顺序

  • 串行化：保持全局的顺序

  • 因果一致：保持依赖（happens-before）操作的偏序

  • FIFO一致：保持单线程依赖操作的偏序

  • Per-key串行化：对于单个key保持全局的顺序

  • 最终一致：副本最终会收敛于某个值

前两个不能达成ALPS。

3.4. Causal+ in COPS

COPS使用两个抽象：

  • version：每个key有该字段。当COPS返回一个键key，key.version = i，那么Causal+确保之后的返回值，版本号一定等于或大于（因果序下）i

    因此Causal+有progressing property

  • dependency：“$a \leadsto b$”等价于“$b$依赖于$a$”，COPS为了保证Causal+，只有在某个操作的依赖操作复制完成后，才会复制本操作

3.5. 因果一致下的扩展

COPS使用多种方式提高扩展性，如：

  • 每个数据中心的节点负责键空间的不同分区，但能追踪其它节点上的键的因果关系
  • 将依赖信息直接编码到键的元数据中，复制时，接收方就可以在提交前进行检查

4. COPS的系统设计

4.1. COPS概览

COPS可以跨数据中心运行，架构图如下：

1.png

对于每个数据中心，包含：

  • 数据节点：存储K-V数据
    • 整个集群存储数据完整副本
    • 集群内，每个节点存储数据的一个分区
    • 集群内，操作都是线性化（因为内部不涉及复制，延迟很低）
    • 数据复制是跨集群（数据中心）的，且异步进行
  • 客户端：
    • 使用客户端库直接和数据节点交互，暴露两个接口：get（COPS）/get_trans（COPS-GT）和put
    • 只会和本集群交互，不会和其它集群交互

而对于COPS-GT，数据节点还需要添加下面的功能：

  • 键值对的元数据除了版本号外，还需要一个依赖列表（其它键和对应的版本号）
  • 额外暴露3个接口：get_by_version, put_after, dep_check
  • 需要保存旧版本的数据，以提供get-transaction的能力

此外，为了达到可扩展性，Causal+需要的开销要和最终一致类似：

  • 降低检查因果依赖的检查开销
  • （COSP-GT）利用GC回收旧版本数据，降低空间开销
  • （COSP-GT）get_trans需要很快就能返回一个满足因果序的结果集，只需要至多两次的get_by_version

4.2. COPS数据存储

a. 格式

对于COPS：存储{key: (val, version)}的映射，其中version是最新的；

对于COPS-GT：存储{key: [(val, version, deps)]的映射，映射的值是一个列表，包含不同版本的值和依赖，而依赖deps是一个包含其它键的(key, version)列表（即deps = [(other_key, version), ...]）

b. 分区与复制

使用一致性散列对数据进行分区，并根据散列环顺序复制到其它节点上（数量很小）。

即每个集群中，每个键都有一个主节点，主节点会复制到集群内的从节点上

而其它集群中，集群也有一个对应的主节点，该键的主节点集合被称为等价节点，它的个数和集群个数成正比

集群内的操作是线性化的，但是跨集群复制是异步的。

当本地集群的写入操作完成后，主节点会将数据放到复制队列，异步复制到其它等效节点上。其它等效节点收到数据后进行依赖检查，保证写入维持因果序，且不阻塞读取。

4.3. 客户端库与接口

客户端提供下面的接口：

1.png

和其它K-V系统不同，COPS API有下面的变化：

  • 对于COPS-GT，提供get_trans接口，返回多键值对的（因果）一致性视图
  • 所有API都包含ctx参数，代表一个线程的执行上下文，它被用于跟踪不同客户端的因果依赖

关于上下文的内容，COPS-GT和COPS不太一样，见下面所述。

a) COPS-GT库

对于COPS-GT，上下文维护了一个(key, version, deps)表：

  • 读取时，客户端将读取到的键和对应的依赖添加到上下文中
  • 写入时：
    • 客户端先从对应键最近的一项取出依赖，计算出新的依赖，然后发送给服务端
    • 成功后，返回版本号，然后将新的版本号和新的依赖，连同键一起，添加到上下文中

而上下文维护的依赖，包含最近依赖和所有依赖，它会在客户端和服务端保存，如下图所示：

1.png

关于依赖维护和检查，有下面2个问题：

  • 减少空间占用

    COPS-GT的GC可回收空间，一旦数据被所有集群的副本提交，依赖就可以被删除。

  • 降低依赖检查开销

    只需检查最近依赖，不需要全部检查，因为根据传递性，若依赖项被提交，那么依赖项的依赖项肯定也被提交了。这个最近依赖需要客户端发送请求前计算完成。

    get_trans接口需要提供全部的依赖，所以上下文需要存全部依赖。

b) COPS库

它需要的状态就相对少一些，它只需要知道最近的依赖。

而实际上，它不需要存依赖，因为获取到的值比其它所有依赖更近。因此上下文只存储(key, version)表，它就代表了最近依赖：

  • 读取时，获得到的键和版本号被添加到上下文中
  • 写入时，使用当前上下文作为最近的依赖，然后清除上下文，仅用本次的写入结果来填充上下文

4.4. COPS/COPS-GT的写操作

写入分为两步：

  • 写入本地集群（同步）
  • 复制到其它集群（异步）

这两步最后都会使用下面这个接口：

1.png

a) 写入本地集群

  1. 客户端计算完整依赖deps，并从中抽取得到最近的依赖nearest
  2. 客户端调用put_after，vers参数设为空
    • 对于COPS-GT，需要传入deps和nearest参数
    • 对于COPS，只需要传入nearest参数
  3. 本地集群中，key的主节点设置版本号并返回给客户端

一些细节需要说明：

put_after的保证

put_after保证，当依赖列表（即deps和nearest）项被写入后，val才能被所有集群提交：

  • 对于本地集群，直接保证，因为本地集群提供强一致性
  • 对于其它集群，后面会叙述

版本号

COPS的版本号是Lamport时间戳（见文章3.1.节）：

  • 高位是版本号
  • 低位是节点号

通过比较Lamport时间戳，并应用last-writers-wins冲突解决策略，COPS能得到每个键的写入操作顺序，并检测和解决冲突。

Lamport时间戳维持了因果顺序，这正是$\leadsto$关系，所以使用它就足够了，不需要使用向量时间戳。

Lamport时间戳维持了因果顺序，即$a \leadsto b$，那么时间戳必有$L(a) \lt L(b)$。（反过来不能推导）

b) 复制到其它集群

本地集群写入完成后：

  1. 主节点将数据异步复制到其它集群的等价节点，这会调用put_after，并设vers为key的版本号，其它参数和a)一样
  2. 其它节点收到数据后，调用dep_check检查依赖：查找本地存储，检查依赖中的值是否已经写入
    • 若全部写入，则返回true，后续写入并提交key数据
    • 若没有，则阻塞，直到依赖全部被写入

依赖检查只需检查nearest即可。此外，若依赖检查阻塞超时，则会重试（若出错则会换一个节点重试 ）。

4.5. COPS的读操作

COPS读操作最后会调用get_by_version函数：

1.png

COPS中，版本号都会填LATEST，以获取最新的数据（COPS-GT会获取旧数据）。获得数据后，会按照4.3.a)和4.3.b)规则，修改上下文（添加(key, version[ ,deps])项到上下文）。

4.6. COPS-GT的Get-Transaction

COPS-GT提供get_trans接口，以一个事务的方式，返回一组键值对，并满足因果一致性。它只需要2轮get_by_version就可以实现，流程如下：

2.png

一个例子：

  • A修改相册权限acl为“朋友可见”，然后修改相册说明desc，然后添加相片到相册album

现在要读取A的相册，则需要获取acl, desc和album，并要满足先后顺序。

一种错误的方式是按顺序读取这3个值：先读取acl，然后检查权限，最后读取desc和album。可能出现的情况是：先读到了旧的acl，但是之后acl马上被修改，最后越权读到了desc和album。

而使用get_trans，就不会出现这个问题：

  • 首先和之前一样，获得acl, desc和album的值，不过还获取到对应的依赖（第一轮get_by_version）

  • 读到的acl可能是旧的，desc和album是新的，通过计算ccv，根据依赖，能发现acl版本是旧的

    这里ccv[dep.key] = max(ccv[dep.key], dep.vers)就能达到这个功能，并告知客户端需要获取依赖所需的新值

  • 通过ccv的计算，得到需要再次获取的键，以获得依赖所需版本的新值（第二轮get_by_version，vers = ccv[key]）

  • 这样，acl值就是新的了，后面的逻辑检查acl，就不会出现越权访问的问题了

5. 垃圾、错误、冲突处理

5.1. 垃圾回收

COPS和COPS-GT客户端存储上下文数据，COPS-GT服务端还会存储多版本的键和依赖。这些数据量会增长。因此需要垃圾回收机制，删除一些不需要的状态。

a) 版本信息回收（COPS-GT）

COPS-GT会存旧版本数据，用于响应get_by_version

但不能无限存储旧数据，COPS-GT使用参数trans_time：

  • 服务端只会保留旧数据一段时间
  • 由于get_trans第二轮需要获取旧数据，因此它必须限制执行时间，即trans_time，若超时则会重试get_trans

b) 依赖回收（COPS-GT）

COPS-GT会存因果依赖关系，用于响应get_by_version，以获取一个多键的满足因果一致约束的试图。

但依赖也不能无限存储，COPS-GT依旧使用了参数trans_time，当数据被所有集群提交后，过了trans_time

  • 对应的依赖也会被清除

  • 数据会被标记never-depend，供客户端清除上下文中的依赖

清除依赖需要同步到其它集群，流程是：

  • 其它的集群写提交后，等待trans_time，然后告知原集群
  • 原集群确认后，删除依赖，并通知其它集群也删除依赖

c) 客户端元数据回收（COPS + COPS-GT）

客户端会将元数据存在上下文中，维护因果依赖关系以及其它数据。

不过有些元数据不需要存储，因为如4.3.a)图所示，检查依赖不需要所有的依赖关系，那些不需要的可以清除。

COPS使用两种方式：

  • put_after作用于所有集群后，会标记该键对应版本为never-depend，并告诉客户端，客户端就可以在上下文中删除该项（正确性由因果关系的传递性保证），而get_by_version返回结果也包含这个标记

  • COPS存储节点会从put_after移除不必要的依赖，移除的是版本小于“global checkpoint time”的依赖

    global checkpoint time的获得如下:

    • 节点从未完成的put_after中，找到最小的Lamport时间戳
    • 节点联系不同集群的等价节点，一对一对地交换并得到一个最小的Lamport时间戳
    • 节点把自己所负责的key range的最小时间戳gossip给集群内所有节点，从而获得整个数据范围的最小时间戳

5.2. 容错

a) 客户端出错

不需要管任何事情，因为它只代表停止发送请求。

b) 存储节点出错

COPS使用链式复制来容错，它参考了FAWN-KV。

本地集群里：

  • put_after：先写入主节点（即链头），任何沿着一致性散列环顺序，将数据复制/传播给从节点，并到链尾结束，此时本集群的写入提交完毕；

  • get_by_version：读取链尾节点

跨集群复制：

  • put_after：本地集群提交完成后，由尾节点发送复制请求到其它集群的头节点
  • dep_check：
    • 其它集群的头节点收到put_after后，向该集群的尾节点发送dep_check（因为它是读操作）
    • 一旦检查完成，头节点沿散列环顺序复制/传播到从节点，直到链尾被提交，然后响应本地集群（源集群）

依赖回收也遵循类似的方式；版本回收只在节点单独进行；计算global checkpoint time所需的数据也是从链尾节点获得。

c) 数据中心出错

数据中心出错，或者发生分区，COPS依旧可以工作，只会带来少量的数据不一致：

  • 写入时出错在本地集群
    • 数据中心宕掉：由于数据没拷贝，数据丢失
    • 数据中心间网络分区：数据会暂时不一致，但不会丢失，待网络恢复后恢复正常
  • 写入时出错在其它集群/网络分区，导致数据无法复制，也无法进行垃圾回收，这时需要管理员介入：
    • 等待至系统恢复正常
    • 将出错的目标集群从配置中移除

5.3. 冲突检测

不同线程并发写同一个key会造成冲突。

COPS默认使用 last-writer-wins 策略，last 决定于写入的版本号（即Lamport时间戳）。这种策略下，它会自动检测并解决冲突。

COPS也可以自定义冲突检测和冲突解决策略，这里需要加3个部分：

  1. 所有的写入请求必须携带它们以前版本的元数据（表示在写入时，在本地集群上可见的key最新的旧版本）

  2. 所有的写入请求由于1，带有隐式依赖数据，写入前需要额外的dep_check
  3. 检测出冲突后，需要自定义一个收敛的冲突处理函数

冲突检测（额外的依赖检查）流程也很简单：若当前写入的新值为new，携带的前一版本是prev，当前可见值的版本为cur，有：prev != cur$\Leftrightarrow$ new和cur发生冲突。

简单的说明：

  • 正向：若prev != cur，根据Causal+ progressing特性，一定有cur > prev，而prev是new的最新旧版本，所以肯定有cur$\not\leadsto$new；而cur的写入肯定比new早，所以肯定有new$\not\leadsto$cur，即cur和new冲突
  • 反向：若cur与new冲突，则有cur$\not\leadsto$new，此外按定义prev$\leadsto$new，可以推定必有prev != cur

6. 总结

CPOS主要的重点和创新点在于：

  • 客户端和服务端保存Lamport时间戳（以及基于时间戳构建的因果依赖图），只需要至多两轮查询，就能获取一个多键且满足因果约束的视图，从而极大提高了扩展性
  • 利用因果依赖的传递性，降低了依赖检查的开销，并能即使回收资源
  • 默认使用last-write-wins解决冲突且结果收敛，高效易实现；而也可以自定义冲突解决方案，冲突的检测方案也很简单（也基于因果传递以及Lamport时间戳的特性）
CATALOG
    FEATURED TAGS
    Algorithm Java Network Distributed System Stream Processing Operating System Paper Linux Redis etcd Kubernetes C++