本期论文地址： 一致性、可用性和可收敛性 Mahajan et al. 2014 和 不满足于最终，可扩展的因果一致性，适用于具有cop的广域存储 – LLoyd et al. 2011

    我之前的文章只关注主要结果，包括：

    在一个总是可用的单向收敛系统中不能提供比实时因果一致性（RTC）强的一致性，而在一个总是可用的单向收敛系统中可以提供RTC。

    今天，我想深入了解一下RTC（以及可用性和收敛性）在上面的声明中的真正含义。然后在第二部分中，我们将看一看“COPS”论文，它介绍并激励因果+一致性模型，并在COPS key-value存储中体现。

    第一部分：CAC
    等等，我还以为是CAP，不是CAC！为什么Mahajan等人。关注一致性、可用性和收敛性，而不是一致性、可用性和分区容忍度？

    CAP（一致性、可用性、分区弹性）公式将属性（一致性和可用性）与系统模型（网络可靠性假设）混合在一起。在我们的公式中，我们将模型与属性分离，以便我们可以分别考虑在省略和拜占庭失效模型下可实现的属性的边界。此外，CAP没有显式地考虑收敛性，因为线性化能力和序列一致性嵌入了收敛性要求。当我们研究弱语义如因果一致性时，我们发现我们必须显式地考虑收敛性。

    “收敛”问题经常在讨论CAP的文章中被提及，因为在没有CAP的情况下，你可以通过一些不太理想的方案来获得一致性，比如事先同意一个固定值，而从不改变它。所以一个包含收敛性的模型告诉我们一些重要的东西，我们在现实系统中实际关心。

    非正式地，聚合指的是实现确保一个节点发出的写入被其他节点观察到的能力。收敛性可以通过描述一组环境条件（网络、本地时钟等）来正式定义，在这些环境条件下，节点可以观察彼此的写入…一个简单的收敛性是最终的一致性。一个常见的定义要求，如果系统停止接受写操作，并且发生了足够的通信，那么系统将达到这样的状态：对于任何对象o，对o的读取将在所有节点返回相同的值。此公式定义了弱收敛性；例如，它对某些节点与其他节点的分区间隔没有任何承诺。

    对于最大活性，我们希望连接节点的任何子集都收敛于一个公共状态。作者定义了任意一对节点A和B之间的单向收敛，这允许通过两步单向通信来收敛。首先A向B发送更新，然后B向A发送更新。

    非正式地说，如果一致性是我们都同意的性质，那么收敛性就是我们都同意的事实上是一种可取和有用的状态的性质。

    可用性如何？

    可用性，非正式地，是指实现确保读写操作完成的能力。实现的可用性是通过描述所有已发布操作完成的环境条件（网络、本地时钟等）来定义的。如果对于任何工作负载，不管丢失了哪些消息，哪些节点可以通信，都可以完成所有读写操作，那么实现总是可用的。

    最后，我们将注意力转向一致性，特别是，如果实时因果一致性是我们所能做的最好的，那么这到底是什么？


    给定一组节点和一组可变数据项，则执行由一组读和写事件组成。写入事件包括执行写入的节点的nodeId、正在写入的数据项的objId、正在写入的值、写入操作的开始时间和写入操作的结束时间。（想想key-value存储）。在这里看到开始时间和结束时间看起来有点奇怪，但这些是建模实时因果一致性的“实时”方面所必需的。记住，这是一个模型，所以我们可以假设一个对所有节点都可见的绝对全局时间，即使我们在实际实现中无法做到这一点（参见Google的spanner和它为一个非常接近的现实系统引入的TrueTime API…）作为一个社区，在设计分布式算法时，我们不应该再依赖于松散同步的时钟和弱时间api。

    读取事件包括执行读取的节点的nodeId、正在读取的数据项的objId、writeList（生成读取返回值的所有写入操作的列表）以及开始时间和结束时间。允许读取返回多个结果，以便处理逻辑并发更新，而不必担心模型中的冲突解决。

    给定这个模型，我们可以开始对一致性进行推理。特别是，一致性模型“接受”（允许）某些执行，而不是其他执行。如果C-strong接受的执行集是C-strong接受的执行集的子集，则一致性语义C-strong比一致性语义C-strong强。如果根据这个定义，两个模型都不强，那么它们是不可比拟的。

    因果一致性允许什么样的执行？取每个事件并使它们成为有向无环图中的节点，其中从事件a到事件b的边表示a先于或“发生在”b。因此，此图对整个事件集施加部分顺序。对于因果一致性，我们在此图表上放置了两个要求：

    给定在同一个节点上发生的任何两个操作a和b，则a在b之前如果且仅当a的开始时间早于b的开始时间。
    read返回前面最新的并发写操作。读取的返回值编码在其writeList中。因此，这个writeList必须包含读之前的每个write w，并且不能被读之前的另一个write覆盖。
    实时因果一致性增加了第三个要求：

    时间不能倒流。如果事件a的结束时间早于事件b的开始时间，则b不能早于a（这与我们对“happens before”的常识定义相匹配）。
    ……大多数声称实现因果一致性的系统实际上实现了更强的语义（例如RTC）。劳埃德等人在[我们今天的第二篇论文]明确指出，他们的系统的因果和每对象顺序语义比因果一致性强。特别是，这些语义强制执行因果一致性的变化，其中对每个键的写入都是完全有序的。

    第二部分：COPS
    在“不要满足于最终”，劳埃德等人引入了偶然+一致性的概念，并证明了它可以在其COPS系统（保序系统集群）中有效地实现。为了与今天的主题保持一致，我将主要关注因果关系+方面，并让您参考这篇文章，了解COPS是如何构建的。

    分布式存储系统有多个目标，有时是相互竞争的：可用性、低延迟和分区容限，以提供“永不停机”的用户体验；可扩展性，以适应不断增长的负载和存储需求；以及一个足够强大的一致性模型来简化编程并为用户提供他们期望的系统行为。

    前四个属性被描述为“ALPS”属性：可用性、低延迟、分区容忍度和可伸缩性。

    • 可用性：所有操作均已成功完成，任何操作都不能无限期阻止或返回一个错误，指示数据不可用。
    • 低延迟：目标响应时间大约为几毫秒
    • 分区公差：数据存储继续在网络分区下运行
    • 可伸缩性：数据存储呈线性扩展

    考虑到ALPS系统必须牺牲强一致性（即线性化能力），我们寻求在这些约束条件下所能达到的最强一致性模型。更强的一致性是可取的，因为它使系统更容易让程序员进行推理。在本文中，我们考虑了收敛冲突处理的因果一致性，我们称之为因果+一致性。

    我们在上面提到的因果一致性。注意，如果a不在b之前，b不在a之前，那么a和b是并发的。因果一致性不会对并发操作施加任何顺序。

    通常，这允许在实现中提高效率：两个不相关的put操作可以按任何顺序复制，避免了它们之间需要序列化点。但是，如果a和b都放在同一个键上，则它们处于冲突中。

    如果每个节点都可以自由地以自己的方式解决冲突，那么副本就可能永远分离。因此，因果+一致性的收敛冲突处理增加了所有冲突更新在所有副本上以相同方式处理的要求。对于COPS，默认策略是使用last writer wins和基于Lamport时钟的实现：

    主存储节点使用Lamport时间戳为每个更新分配唯一的版本号。节点将版本号的高阶位设置为其Lamport时钟，将低阶位设置为其唯一的节点标识符。Lamport时间戳允许COPS对每个密钥的所有写操作派生一个全局顺序。此顺序隐式实现最后一个writer wins收敛冲突处理策略。

    一旦一个副本返回了一个给定版本的key，那么因果+一致性将确保它只返回该版本或因果关系更高的版本。因此，返回的版本号单调地增加，这被称为progressing属性。

    COPS的实现本身假设少量COPS集群（每个集群都完全包含在一个数据中心内）连接在一起，形成一个单独的数据存储。

    每个本地COPS集群都被设置为一个可线性化（强一致）的键值存储。可线性化系统可以通过将键空间划分为N个可线性化分区来实现。

    COPS集群之间的复制是异步进行的。COPS中一个有趣的设计点是支持get事务的扩展。如果存储区只支持单个密钥获取操作，那么即使该存储区是因果+一致的，也无法读取因果+一致的依赖密钥集。在这样的模型中，项值的顺序没有规范的正确顺序。

    …一个更好的编程接口将允许客户端获得多个key的因果+一致视图。实现这种保证的标准方法是读取和写入事务中的所有相关键；然而，这需要对所有分组键使用一个序列化点，而COPS为了获得更大的可伸缩性和简单性而避免了这一点。相反，COPS允许独立地编写key（在元数据中有显式的依赖关系），并提供get-trans操作来检索多个key的一致视图。

    实现分两轮进行：首先获取每个请求key的最新版本，以及它们所依赖的key的“依赖列表”。如果最初请求的任何键也出现在依赖项列表中，则会进行检查以确保检索到的版本至少与列表中的版本相同。如果其中一个检查失败，则会使用任何依赖项列表中看到的最新版本按版本获取有问题的key。