COPS 论文阅读
本文最后更新于：3 年前
背景
考虑这么一个问题：对于大型网站的异地复制，公司存在多个数据中心，每个数据中心拥有全量数据，读均为本地读。那么写应该怎么实现？一致性应该如何取舍？
对于以上背景，Spanner 和 Facebook/Memcached 已经给出了他们自己的解决方案：
- Spanner：
- 线性一致性。
- 通过 Paxos 和 2PC 实现分布式写事务。
- 写入需要等待 quorum 的数据中心返回 ack，性能较低。
- 读取从本地数据中心读，可能需要等待，性能较高。
- Facebook/Memcached：
- 最终一致性。
- 写入需要主数据中心返回 ack，性能一般。
- 读取从本地数据中心的缓存中读，性能极快。
基于以上背景，本论文在性能和一致性之间找出了一个 trade-off，给出了一种中间状态的一致性：因果一致性，其相比线性一致性更弱但相比最终一致性更强。因此，其性能也会处于中间的状态。
有关因果一致性的定义，建议先阅读此 博客。
以下简单介绍其实现。
介绍
概述
COPS（订单保留服务器集群）是一种地理复制的键值存储系统，可保证因果一致性。它包含两个软件组件：客户端库和键值存储。
涉及的每个数据中心都有一个本地 COPS 集群，该集群维护其整个数据集的副本。COPS 客户端是使用客户端库与键值存储交互的应用程序。客户端仅与在同一数据中心运行的本地 COPS 集群交互。
COPS 跨集群中的节点对存储的数据进行分片，每个键属于每个集群中的一个主节点。此主节点接收键的写入。写入完成后，本地集群中的主节点将其复制到其他集群中的主节点。
每个键也有版本，代表该键的不同值。COPS 保证一旦副本返回了密钥的版本，副本将只返回该版本或后续请求中的因果更新版本。
定义因果关系
更正式地，该论文提到了作者用来定义操作之间潜在因果关系的三个规则，表示为->：
- 执行线程：如果 a 和 b 是单个执行线程中的两个操作，则 a -> b 如果操作 a 在操作 b 之前发生。
- 从获取：如果 a 是 put 操作，b 是 get 操作，返回 a 写入的值，则 a -> b。
- 传递性：对于操作 a、b 和 c，如果 a ->b 和 b -> c，则 a -> c
图 2 中的执行说明了这些规则。
此外，因果一致性不排序并发操作。如果我们不能判断一个操作在另一个之前发生，我们就说两个操作是并发的。一个系统可以以任何顺序复制两个不相关的 put 操作，但是当 put 对同一个键有并发操作时，我们说它们是冲突的。
对于某些并发场景，最后写入者胜的规则能够保证集群对某一个值最终达成共识。然而应对某些冲突写入的场景，类似于 append 函数，原子计数器等场景，都需要更细致的考虑。
上下文
每个客户端维护一个上下文来表示其操作的顺序。将此上下文视为包含项目的列表。每次操作后，客户端都会向其上下文中添加一个项目。这些项目在列表中的顺序捕获了版本之间的依赖关系。使用此上下文，客户端可以计算版本的依赖关系。
LP 提供全局顺序
使用 Lamport Timestamp in higher bits + unique ID For Data Center in lower bits 来支持所有操作的全序顺序。
通过结合逻辑时钟和 Wall Clock，即使不同数据中心的时间有较大误差，我们依然可以为所有操作给出一个全序排序。
时钟实现如下所示：
1 | |
写入
当客户端调用 put key 时，库会根据其上下文计算该 key 的依赖关系，并将该信息发送到本地主存储节点。在 COPS 集群写入所有计算的依赖项之前，此存储节点不会提交密钥的值。提交该值后，主存储节点使用 Lamport 时间戳为其分配一个唯一的版本号，并立即将该编号返回给客户端。通过不等待复制完成，COPS 消除了具有更强一致性保证的系统产生的大部分延迟。
主存储节点在本地提交写入后，将写入异步复制到其他集群。节点在复制它时包含有关写入依赖项的信息。当另一个集群中的节点收到此写入时，该节点会检查其集群中的本地节点是否满足所有依赖项。接收节点通过向负责这些依赖关系的本地节点发出依赖关系检查请求来做到这一点。如果本地节点没有写入依赖值，它会阻塞请求，直到写入该值。否则，它会立即响应。
总之，COPS 通过计算写入的依赖关系来保证因果一致性，并且在集群提交所有依赖关系之前不会在集群中提交写入。
读取
COPS 也满足本地集群中的读取。COPS 客户端可以指定他们是要读取密钥的最新版本还是特定的旧版本。当客户端库接收的读取响应，它增加了操作的情况下捕捉到潜在的因果关系。
限制
虽然因果一致性是一个流行的研究思想，但它有一些局限性。两个主要是：
- 它无法捕获外部因果依赖性。一个典型的例子是一个电话：如果我做动作 A，打电话给我在另一个大陆的朋友告诉她关于 A 的事情，然后她做了动作 B，系统将无法捕捉到 A 和 B 之间的因果关系。针对此问题，Lamport 早已经给出了答案：只能通过强同步的物理时钟来实现，具体可以参考本人另一篇 博客。
- 管理冲突可能很困难，尤其是当
最后写入者胜规则不够用时。
总结
简单学习一下因果一致性，虽然讲义中提到它在实际系统中应用不多，但个人感觉这是一个很有意义的方向。在未来，对于不追求数据线性一致性的场景，很可能跨数据中心的同步范式都会参考因果一致性而不是最终一致性。虽然牺牲了一点性能，但前者相比后者保证了一定程度的 safety，这是非常可贵的。