背景及相关定义

分布式数据库遵守CAP理论，应对当今网络存储需求，现代数据库需要满足以下特性

Available
Low Latency
Partition-tolerance
high Scalability

简称：ALPS 系统，ALPS系统必须牺牲强一致性，但在这种情况下，因果一致性满足该限制。在因果一致性之外，本文定义 ==具有收敛冲突处理的一致性模型，称之为Causal +==，这是本论文首次定义该概念，之前已经出现过满足该定义的论文，本文在定义该术语之外，还实现了可扩展的因果一致性

Causal + 一致性的聚合冲突处理组件可确保副本永远不会出现分歧，并且对同一密钥的冲突更新在所有站点上得到相同的处理。当与因果一致性相结合时，此属性可确保客户端仅看到逐渐更新的密钥版本。相比之下，最终一致的系统可能会暴露无序的版本。

可扩展的因果一致性：COPS之前的系统，要求数据中心配置、机器数量等要求一致，而存储在COPS的数据可以分布在任意大小的数据中心，而且依赖项（或者事务）可以分布在数据中心的许多服务器上。

数据中心：每个数据中心，包括前端服务器和后端服务器，以及存储数据的数据库

简化KV 数据库的操作：Get(key) = value, Put(Key, Value)

Causal + consistency

==CAUSAL+ CONSISTENCY==：causal consistency with convergent conflict handling

定义潜在因果关系：$\rightsquigarrow$

三个潜在因果关系的规则

Execution Thread：同一线程中的两个操作a,b ，如果a先于b发生，则 $a \rightsquigarrow b$
Gets From: 如果a是put操作，然后b是返回被a写入的值的get函数，则 $a \rightsquigarrow b$
Transitivity：对于操作a,b,c,如果 $a \rightsquigarrow b$， $b \rightsquigarrow c$，则 $a \rightsquigarrow c$

这些规则在同一执行线程内的操作之间以及其执行线程通过数据存储交互的操作之间建立潜在的因果关系。在本论文的模型中，不允许直接使用线程通信，而是使用数据存储的方式进行通信

为什么需要Causal+ consistenct：

因为并发操作不遵守因果一致性, 两个不相关的操作对同一Key进行写入，就会导致冲突

收敛冲突处理要求在所有副本上使用处理函数 H 以相同的方式处理所有冲突的 put操作。

常见的两种处理方法：

last-writer-wins rule：[Thomas' write rule](https://dl.acm.org/doi/10.1145/320071.320076)
标记冲突，使用其他方式处理：例如Coda系统中人工交互；或者Bayou系统和Dynamo系统中编程处理

一致性分级

线性一致性 > 顺序一致性 > Causal+ 一致性 > 因果一致性 > FIFO一致性 >> 单独键顺序一致性（Per-key sequential consistency）> 最终一致性

Causal+ in COPS

在COPS系统中使用了两个抽象：dependencies和version，以此帮助推理因果+一致性

每个key都有自己的version: $key_{version}$

如果$x_i\rightsquigarrow y_j$, 则 $i < j$

一旦COPS中的副本返回密钥x_i 的版本i，Causal+ 一致性确保它将仅返回该版本或因果上较晚的版本（==冲突的处理因果上晚于冲突解决==）

因果+ 一致性的进步属性 progressing property ：COPS中的每个副本始终返回密钥的非递减版本

因果一致性规定，因果上先于给定操作的所有操作必须看起来在该操作之前发生。换句话说，如果 $x_i\rightsquigarrow y_j$，那么xi的写操作发生在yj之前。我们将这些前面的值称为依赖关系（dependencies）。

这些依赖关系本质上与写入的因果顺序相反。 COPS 通过仅在写入所有依赖项后才写入版本，在复制期间提供因果+一致性。

Scalable Causality

本文之前的系统研究设计初衷并不是为了提供Scalable causal consistency，他们都使用日志序列化和交换的形式。

逻辑副本上的所有操作都按序列化顺序写入单个日志，通常用版本向量标记。然后，不同的副本交换这些日志，使用版本向量建立潜在的因果关系并检测不同副本的操作之间的并发性

基于日志交换的序列化抑制了副本的可扩展性，因为它依赖于每个副本中的单个序列化点来建立排序。因此，键之间的因果依赖关系仅限于可以存储在一个节点上的一组键，或者单个节点（或复制状态机）必须为所有键提供提交顺序和日志跨集群的操作。

本文使用了一个不同的方法来获得可扩展性

每个数据中心中的节点负责密钥空间的不同分区，但系统可以跟踪并强制存储在不同节点上的密钥之间的依赖关系。 COPS 显式编码与每个密钥版本关联的元数据中的依赖关系。当远程复制密钥时，接收数据中心会在提交传入版本之前执行依赖性检查。

COPS 系统设计

COPS特点

对于COPS-GT，使用get 方法通过一致性快照返回值
使用COPS的Client 只与同一数据中心运行的本地COPS集群进行通信
COPS被设计运行在小数量的数据中心上
提交到COPS上的数据，在本地数据中心上执行是线性化的
当本地线性执行操作之后，再使用异步方式传输数据
在 COPS 中，系统存储每个密钥的最新版本号和值。在 COPS-GT 中，系统将每个键映射到版本条目列表，每个版本条目由 <version、value、deps> 组成。 deps由多个<key, version> 组成

系统组件

Key-value store
1. 每个键值对都有其相关的元数据。COPS中，元数据为版本号；在COPS-GT中，元数据是版本号和相关的依赖列表
2. 三个额外的操作；get_by_version put_after dep_check,这些操作能够启用 COPS 客户端库、支持因果+一致性、获取事务的异步复制过程
3. 针对COPS-GT，保留旧版本的KV键值对，方便支持事务
Client library：用于支持get get_trans put操作，通过客户端库 API 中的上下文（Context）参数维护有关客户端当前dependencies 项的状态。

在实现Causal Consistency 之外，本文还通过一系列的优化，做到了近似实现最终一致性系统所需要的开销（几乎是最小的开销）

（COPS）由于因果一致性需要检查依赖，本文使用一个机制避免检查所有值的依赖，通过利用因果依赖关系固有的图结构，只需要少量的此类检查。
（COPS-GT）使用垃圾回收机制减少每个key存储的相关多版本
（COPS-GT）保证COPS-GT 返回一个因果+一致的数值集合，同时，COPS-GT还是用一个算法，仅使用两个循环（two round）就实现了该事务，避免了其他算法可能形成的阻塞或长时间轮训。

Key-Value 存储的实现

每个 COPS 集群都维护自己的键值存储副本。为了实现可扩展性，COPS使用一致性哈希跨集群节点对键空间进行分区。为了实现分区容错性，每个key都使用链复制跨少量节点进行复制。
get和put操作可在集群中的节点之间线性化。操作在本地集群执行后立即返回客户端库；集群之间的操作异步发生。
COPS 中存储的每个密钥在每个集群中都有一个主节点
COPS 的一致性哈希为每个节点分配了几个不同的键范围的责任。在不同的数据中心中，键范围可能具有不同的大小和节点映射，但是给定节点需要与之通信的等效节点的总数与数据中心的数量成正比（即，节点之间的通信不是全部到所有的）位于不同的数据中心
当一个写操作完成时，主节点会将其放到复制队列中，异步发送消息到其他集群的主节点上（称之为等效节点，equivalent nodes）。这些节点依次等待，直到本地集群中满足值的依赖关系，然后再进行本地提交。这种依赖性检查机制确保不同节点的写入以因果一致的顺序发生，并且读取永远不会阻塞。

客户端库和接口

客户端库实现了两种不同于KV存储的接口实现

（COPS-GT）get_trans, 它在一次调用中返回多个键值对的一致视图
（COPS-GT）每个函数都适用上下文参数（Context argument），库在内部使用该参数来跟踪每个客户端操作之间的因果依赖关系。上下文定义了因果+“执行线程”。单个进程可能包含许多单独的执行线程，通过分离不同的执行线程，COPS 避免了由于混合它们而导致的错误依赖关系。
COPS-GT 中的客户端库将客户端的上下文存储在 <key、version、deps> 条目表中。

客户端使用 API 中的上下文 ID (ctx id) 引用其上下文。当客户端从数据存储中get(key)时，库会将此key及其因果依赖项添加到上下文中。当客户端put key时，库将放置的依赖项设置为当前上下文中每个key的最新版本。成功放入数据存储中会返回分配给写入值的版本号 v。然后，客户端库将这个新条目<key, v, D> 添加到上下文中。
（COPS-GT）因为上一个的特性，上下文包括之前在客户端会话中读取或写入的所有值，以及所有这些依赖项的依赖项
1. 这就导致了一个潜在的问题：开销的增加，COPS-GT使用垃圾回收机制，一旦依赖项提交到所有 COPS 副本，就会删除依赖项。
（COPS-GT）同时为了在复制期间减少依赖检查的开销，客户端库做了一些潜在的优化：只使用最近的依赖项，减少潜在的依赖开销
(COPS), COPS只需要了解最近的依赖项，因此它不会存储甚至检索其获取的任何值的依赖关系，COPS 客户端库只需要存储<key,version>条目

对于 get 操作，检索到的 <key,version> 将添加到上下文中。对于 put 操作，库使用当前上下文作为最近的依赖项，清除上下文，然后仅使用此 put 重新填充它。

写数据操作

COPS 中的所有写入首先进入客户端的本地集群，然后异步传播到远程集群。

COPS提供两个API完成着两个操作

本地线性执行
异步通信

写数据到本地

当一个客户端调用put(key,value,ctx_id),库会计算所需要的依赖集合
识别最近的依赖集
库在不带版本参数的情况下调用 put_after
1. COPS: 库只需要包含最近的，不包含 deps。
2. COPS-GT: 该库在调用后的 put 中包含 deps，因为依赖项必须与值一起存储
本地集群中key的主存储节点为key分配一个版本号并将其返回给客户端库。我们将每个客户限制为单一outstanding put；这个操作是有必要的, 因为后面的 put 必须知道早期 put 的版本号，这样它们可能依赖于它们

其他特点：

如果 y 依赖于 x，则 put(x) 必须在 put(y) 发出之前提交
主存储节点使用Lamport 时间戳来给每次更新分配一个独一无二的版本号，节点在版本号的高位使用Lamport 时间，在低位使用独一无二的节点标识符，Lamport 时间戳可以保证写的全局一致性。

集群间的写复制

本地写入提交后，主存储节点异步复制，使用 put_after 操作流写入不同集群中的等效节点
但接受提交操作的等效节点需确保该提交的依赖项已提交到同一集群后才能提交更新，如果不满足条件，则阻塞直到所需要的版本号提交（此处提交需要调用put_after，并根据COPS和COPS-GT的不同，需要携带不同的附加参数）
如果最近依赖项上的所有 dep 检查操作成功，则处理 put_after 请求的节点将提交写入的值，使其可供本地集群中的其他读取和写入使用。(这个顺序需要保证：如果任何 dep 检查操作使处理 put 的节点在重新发出后超时，则在发生故障时可能会发送到新节点。)

使用COPS 读数据

读只需要在本地集群读取即可，可以读取最新版本的数据，或者指定某个特定老版本的数据

在COPS-GT中实现事务

COPS-GT 客户端库提供了 get_trans 接口，因为使用单key值 get的接口读取一组依赖键无法确保因果+一致性（样例见论文第7页，由于time-to-check-to-time-to-use导致的竞争条件）

一个简单的解决方法是通过要求客户端按照因果依赖关系的相反顺序发出单键获取操作，但这种方法会导致错误
另一种方法是通过设计好的编程接口将允许客户端获得多个键的因果+一致视图。

实现这种保证的标准方法是在事务中读取和写入所有相关密钥；然而，这需要所有分组密钥有一个序列化点，COPS 避免了这种情况，以实现更大的可扩展性和简单性。

COPS 允许独立编写密钥（在元数据中具有显式依赖性），并提供 get_trans 操作来检索多个密钥的一致视图。

COPS客户端库分两轮实现get事务算法

# @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)

第一轮

使用n个并发get_by_version操作来获取本地集群数据，本地集群一定是有该数据的，但这些独立检索的数据可能并不能返回相同的version值，get_by_version会返回一个<value, version, deps >元组，deps 是一个<key, version>的列表，用于保存该key版本所需要的依赖key及依赖key的版本

如果客户端没有请求依赖键，或者如果请求了，则它检索到所有的依赖项的版本都是依赖项列表中的版本，则满足该结果的因果依赖项。返回该事务的get值

第二轮

如果有某个依赖项的值没有满足，则请求第二轮。请求的版本将是第一轮任何依赖项列表中看到的最新版本(第一轮中某个key的version 大于所需要的版本，则第二轮所发送的请求就应该是针对该版本的请求)。这些版本满足第一轮的所有因果依赖关系，因为它们是所需的版本。此外，由于依赖关系是可传递的，并且这些第二轮版本都被第一轮检索到的版本所依赖，因此它们不会引入任何需要满足的新依赖关系。该算法允许 get_trans 返回截至第一轮检索到的最新时间戳的时间的数据存储的一致视图。

仅当客户端必须读取比第一轮检索到的版本更新的版本时，才会发生第二轮。仅当 get 事务中涉及的密钥在第一轮期间更新时才会发生这种情况。因此，我们预计第二轮比赛的机会很少。

数据存储的因果+一致性为get事务算法的第二轮提供了两个重要的属性。

首先，获取版本请求将立即成功，因为请求的版本必须已存在于本地集群中。其次，新的按版本获取请求不会引入任何新的依赖项，因为由于传递性，这些依赖项在第一轮中已经已知

第二个属性说明了为什么获取事务算法在第二轮中指定显式版本，而不仅仅是获取最新版本：否则，面对并发写入，较新的版本可能会引入更新的依赖项，这可能会无限期地持续下去。

COPS-GT限制get_trans的执行时间trans_time（论文中设置为5s），由于该算法在本地执行，所以执行速度很快，如果超时，则客户端库将重启该调用，该情况只出现在集群出现多个节点崩溃的情况

垃圾回收、容错、冲突探测

垃圾回收

本文中提到了三种垃圾回收：

version 垃圾回收：COPS-GT only
dependency 垃圾回收： COPS-GT only
客户端元数据垃圾回收： COPS-GT and COPS

垃圾回收，在本文中以四个角度来思考垃圾回收：What，Why，When，Overhead，基本对应了：垃圾从哪里来？为什么要清理？何时清理？所需要的负载。

Version 垃圾回收

What：COPS-GT需要存储key的多个版本来回应get_by_version请求

Why：get_trans算法只需要两轮轮询，而且第二次轮询是第一次轮询的新版本，所以并不需要存储全部的版本数据。

When：当新数据被写入后，COPS-GT只需要保留旧版本的传输时间以及时钟偏差的小增量。 在此之后，版本调用将不再请求旧版本（可以结合get_trans 算法来思考为什么不再需要旧版本数据），并且垃圾收集器可以将其删除。

Overhead：空间开销受到传输时间内可以创建的旧版本数量的限制。该数字由单个节点可以承受的最大写入吞吐量决定。

Dependency 垃圾回收

What：依赖可以保证事务能够获取数据的一致性实图

Why：一旦不再需要与旧依赖项关联的版本来保证获取事务操作的正确性，COPS-GT 可以垃圾收集这些依赖项。

Example：

假设有$z_2$依赖于$x_2,y_2$。一个事务获取$x,y,z$,如果返回$z2$，则将会返回$x{\ge2},y_{\ge2}$,

因果一致性保证：x_2,y_2写入发生在z_2写入之前

因果+一致性保证：一旦x_2,y_2被写入，那么他们或更高版本将始终由get操作返回

因此，一旦z_2被写入所有数据中心可入，并且经过了trans_time时间后，获取z2的事务，将同时返回$x{\ge2},y_{\ge2}$，因此z_2的依赖可以被垃圾回收

z_2的依赖结构 deps[<x,2>,<y,2>],如果返回的x,y版本大于2，则下一次事务获取的z的版本也将大于2，此时并不需要再存储版本2的依赖项目。同时，版本2的z，并没有什么特殊意义，假设此时x,y的版本号为3，而z的版本号为2，此时调用<x,y,z>的事务，则获取z的时候，将等待第三版本的z写入后，才会完整的结束事务。

When：当所有数据中心提交上个的值之后，再经过trans_time，即可清除值的依赖。COPS和COPS-GT都会将其标记为never-depend, 为了清除依赖关系，每个远程数据中心都会在写入已提交且超时期限已过时通知原始数据中心。一旦所有数据中心都确认(类似于 2PC 协议)，原始数据中心就会清除自己的依赖关系，并通知其他数据中心也这样做。为了减少这部分开销，这部分通信可以附加在传输其他内容的过程中。

Overhead：trans_time + 往返时间

Notice：COPS定义在分区期间，具有多个版本的依赖不能被回收。

客户端元数据垃圾回收

What：COPS、COPS-GT 客户端库使用随所有操作传递的 ctx_id 来跟踪客户端会话（单线程执行）期间的所有操作(存放在客户端上)。在这两个系统中，自上次放置以来的每次获取都会添加另一个最近的依赖项。此外，在 COPS-GT 中，所有新值及其在 get trans 操作和所有 put 操作中返回的依赖项都会添加正常的依赖项。 如果客户端会话持续很长时间，则附加到更新的依赖项数量将会增加，从而增加 COPS 需要存储的依赖项元数据的大小。

Why：与上面的依赖关系跟踪一样，客户端只需要跟踪依赖关系，直到保证它们在任何地方都得到满足。

When：COPS 通过两种方式减小此客户端状态（上下文）的大小。

首先，如上所述，一旦 put_after 成功提交到所有数据中心，COPS 就会将该key版本标记为从不依赖，以表明客户端不需要表达对其的依赖。按版本获取的结果包含此标志，并且客户端库将立即从客户端上下文中的依赖项列表中删除从不依赖的项。 此外，这个过程是传递的：任何从不依赖的键所依赖的东西都必须被标记为从不依赖，因此它也可以从上下文中进行垃圾收集。

其次，COPS 存储节点从 put_after 操作中删除不必要的依赖项。当节点收到 put_after 时，它会检查依赖项列表中的每个项目，并删除版本号早于全局检查点时间的项目。 该检查点时间是整个系统所有节点都满足的最新 Lamport 时间戳(一个全局统一的上次事务提交的时间点)。 COPS 键值存储将此检查点时间返回给客户端库（例如，响应 put_after），允许库从上下文中清除这些在检查点之前的依赖项。

为了计算全局检查点时间，每个存储节点首先确定其主键范围内任何待处理放置的最旧的 Lamport 时间戳。（换句话说，它确定其最旧密钥的时间戳，但不能保证所有副本都满足该时间戳。）然后，它联系其他数据中心中的等效节点（处理相同key范围的那些节点）。节点成对交换其最小 Lamport 时间，记住任何副本中最旧的观察到的 Lamport 时钟。在此步骤结束时，所有数据中心都具有相同的信息：每个节点都知道其密钥范围内全局最旧的 Lamport 时间戳。 然后，数据中心内的节点围绕每个范围的最小值进行闲聊，以找到其中一个节点观察到的最小 Lamport 时间戳。在我们的实现中，这个定期过程每秒执行 10 次，并且对性能没有明显影响。

Fault Tolerance

主要讨论三种故障情况，不讨论人为、恶意的故障情况

客户端故障
Key-Value 存储节点故障
数据中心故障

客户端故障

COPS 的键值接口意味着每个客户端请求（通过库）都由数据存储独立且原子地处理。属外部故障，不需要COPS内部处理。COPS 的依赖性跟踪通过确保引用完整性等属性，可以更轻松地处理其他客户端的故障。

K-V存储节点故障（集群内部）

COPS 可以使用任何底层容错线性化键值存储。我们在独立的 FAWN-KV [5] 节点集群之上构建了我们的系统，这些节点在集群内使用链复制 [51] 来屏蔽节点故障。

每个数据项都存储在沿着一致性哈希环的 R 个连续节点的链中。将操作发送到相应链的头部后，沿着链传播，然后在尾部提交，然后尾部确认该操作，读取操作则直接发生在尾部

服务器发出的操作稍微复杂一些，因为它们是从不同的节点链发出并由不同的节点链处理的。

本地集群中的尾部将操作后的内容复制到每个远程数据中心的头部。然后，远程头将 dep 检查操作（本质上是读取操作）发送到本地集群中适当的尾部。一旦这些返回（如果操作没有返回，将触发超时，并且将重新发出 dep 检查）(有一步检查依赖的过程)，远程头部将值沿着（远程）链传播到远程尾部，远程尾部提交该值并确认操作返回到原始数据中心。

当存在异常节点时，由链上的节点接管存储内容，然后本地集群的尾部节点更新其相应的键范围最小值。

数据中心故障

某个数据中心故障，整体上照常运行，有细微的一点不同

源自故障数据中心但尚未复制出来的任何 put_after 操作都将丢失。 这是允许低延迟本地写入返回速度快于数据中心之间的传播延迟的不可避免的成本。 如果数据中心仅分区且未发生故障，则不会丢失任何写入操作。相反，它们只会被推迟到分区愈合为止。
活跃数据中心中的复制队列所需的存储将会增长。他们将无法将 put_after 操作发送到发生故障的数据中心，因此 COPS 将无法对这些依赖项进行垃圾收集。系统管理员有两个选择：如果分区可能很快就会修复，则允许队列增长，或者重新配置 COPS 以不再使用发生故障的数据中心。
在 COPS-GT 中，在数据中心发生故障时，依赖项垃圾收集无法继续，直到分区得到修复或重新配置系统以排除发生故障的数据中心。

冲突探测

当两个针对同一key不具有因果写入发生时，就会出现冲突。COPS默认使用last-writer-wins的机制来解决冲突（需要借助时间戳来获取全局顺序）

还有一部分程序只需要更简单的方法就可以完成冲突探测：

对于这些应用程序，COPS 可以配置检测冲突操作，然后调用一些特定于应用程序的聚合冲突处理程序。

我们使用COPS-DC来表示COPS的冲突检测，COPS-DC具有三个新的组件

所有 put 操作都带有先前版本元数据，该元数据指示写入时在本地集群上可见的密钥的最新先前版本（该先前版本可能为空）
所有 put 操作现在都隐式依赖于先前版本，这确保新版本只会在其先前版本之后写入。这种隐式依赖需要额外的 dep 检查操作，尽管它的开销较低并且始终在本地计算机上执行。
COPS-CD 有一个应用程序指定的收敛冲突处理程序，当检测到冲突时将调用该处理程序。
COPS-CD 遵循一个简单的过程来确定密钥的新 put 操作（以前的版本 prev）是否与密钥的当前可见版本 curr 冲突：

$prev \ne curr $ 当且仅当new和curr冲突时

假设A用户之前提交过一个写入prev（new的上一个写入）, 此时该key的可见版本号为curr，此时A重新提交一个版本号为new的写入
1. prev写入一定发生在new之前
2. $prev \ne curr$, 因为此时curr可见，而prev不可见
3. $curr > prev$, 根据因果+一致性的progressing 属性
4. $curr \nrightarrow new$ 由于prev是new的最近因果的上一个版本
5. $new \nrightarrow curr$ 因为curr发生在new的写入之前
6. 因此curr和此次写入冲突
7. 相反，如果new和curr冲突，则$curr \nrightarrow new$。根据定义，$prev \rightarrow new$，因此 curr$\ne$ prev 。

KTurnura / paper-notes

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