论文地址： 收敛和交换复制数据类型的综合研究——Shapiro等人。2011年

    它继续以一种原则性的方式尽可能避免协调开销的主题。正如我们昨天看到的，一致性、故障容忍度、延迟容忍度和性能之间存在权衡。让我们不要将最终一致性方法的系列与定义不明确的“近似”一致性混淆，尽管：

    [最终一致性]表现良好（因为一致性瓶颈已经转移到关键路径之外），并且较弱的一致性被认为是某些类应用程序可以接受的。然而，和解通常是复杂的。关于如何设计一个正确的乐观系统，几乎没有什么理论指导，特别的方法已经证明是脆弱和容易出错的。

    本文介绍了CRDT的概念，这是一种“简单、理论上合理的最终一致性方法”，让我们在这里补充一下我们这个时代迫切需要解决的分布式系统问题：“CRDT代表什么？“在过去的几周中，我们看到复制有两种基本方法：可以在主服务器上执行操作并复制结果状态，也可以复制操作本身。如果要复制状态，那么给定一些状态的聚合规则，就可以创建聚合复制数据类型。如果您正在复制操作，那么给定精心设计的用于交换的操作，您可以创建可交换的复制数据类型。方便地说，“收敛”和“交换”都是从C开始的，所以我们可以调用这两个crdt。在这两种情况下，更高一级的目标是通过确保独立采取的行动不会相互冲突（从而可以在稍后的时间点组成）来避免协调的需要。因此，我们也可以称它们为无冲突复制数据类型。

    可以这样想：早期的语言为我们提供了set、list、map等的标准数据类型实现。然后我们看到了集合和相关数据类型的并发版本的引入。使用CRDTs，我们看到了分布式集合和相关数据类型的诞生。最终，任何自尊心强的语言/框架都会附带一个分布式集合库——Riak 已经支持CRDTs，Jonas至少在github中有一个Akka CRDT库。当你通读这篇文章的时候，你会很容易想到“哦，这些是很容易实现的”，但是请注意关于垃圾收集的一节——有点像我们在Edelweiss中看到的那样，使生产实现的状态不是无限的，这会使事情变得更加困难。

    由于CRDT在设计上并不使用一致性，因此这种方法有很强的局限性；尽管如此，一些有趣的、非琐碎的CRDT还是存在的。

    假设一个对象（例如一个集合）的一些副本是分布式的。我们希望它们最终收敛到相同的状态，或者更准确地说，我们希望对象上的所有查询操作在每个副本上返回相同的结果。对于任何两个副本i和j，这都需要安全和活跃的条件：

    • 安全性：如果i和j的因果关系相同，那么i和j的抽象状态是等价的。
    • 活跃度：如果某个事件e在i的因果史中，那么它最终将在j的因果史中。
    • 如果我们对任何i和j都有这种成对的最终收敛，那么这意味着只要所有副本最终接收到所有更新，副本对象的任何非空子集都将收敛。

    基于状态的CRDTs
    术语看起来很吓人，但核心思想实际上非常简单。如果你理解max（x，y），你就能理解基于状态的CRDTs是如何工作的。假设我们的状态是一个简单的整数值。给定两个值4和6，则最大值为6。我们也可以将6描述为两个值中的最小上界：最小值，即4和6都小于它。当然，我们要组合的状态值并不总是整数，但是只要我们可以在状态上定义一个有意义的最小上界（LUB）函数，我们就可以创建一个CRDT。你可能会听到术语join半格被抛出。这仅仅意味着一组值，上面定义了一个基于LUB的偏序函数。（例如整数集和max）。

    取一个值来自这样一个半格的对象，并将状态值的合并操作定义为其最小上界函数。如果这样一个对象的值变得更大（由最小上界函数定义）——单调半格，那么该类型就是CRDT。这种类型的复制品最终会收敛。

    基于操作的CRDTs
    对于基于操作的对象，我们假设一个传递通道（如TCP），它可以按照数据类型指定的传递顺序（如因果传递）传递更新。本订单未涵盖的操作称为同时操作。如果所有这些并发操作交换，那么所有与传递顺序一致的执行顺序都是等价的，并且所有副本都将收敛到相同的状态。例如，加减法通勤（+7，-5给出的结果与-5，+7相同）。

    有趣的是，总是可以使用基于操作的方法模拟基于状态的对象，反之亦然。

    示例CRDTs
    从表面上看，这可能有点让人不安。聪明的是，如果这些规则是我们必须处理的全部，那么我们如何设计数据类型，这些数据类型既能遵守约束，又能做有意义的事情呢？因为如果我们能做到这一点，我们就能得到所有好的收敛性质。对一个拿着锤子的人来说，一切都像钉子。我们有锤子，是时候找钉子了…

    从简单的计数器开始，基于操作的计数器是简单的，因为加法和减法通勤。不过，基于状态的计数器强调了在设计CRDTs时出现的一些有趣的问题。让我们从一个只递增的计数器开始：如果两个独立的副本都递增计数器（从0到1），然后我们与max合并，我们将得到1，而不是期望的2。因此，让我们保持一个更复杂的状态结构，以一个向量时钟为模型，每个副本在向量中有一个条目，给定副本的增量会增加其在向量中的计数器。现在merge可以取每个条目的最大值，计数器值是所有条目的总和…

    用前面的表示来支持减量并不容易，因为这个操作会破坏半格的单调性。此外，由于merge是一个max操作，因此减量不会有任何影响。

    但是…我们可以通过保留两个计数器来解决这个问题，一个用于递增数，另一个用于递减数。（作者称之为PN计数器）。有一个非负的计数器（例如，计算一些资产的剩余数量）是困难的，因为“非负”是一个全局不变量，你不能在本地计算。您可以在每个复制副本上本地强制执行该规则（减少量不能超过增加量），这当然可以确保全局属性，但可能限制性太强。

    可悲的是，剩下的选择是同步。这可能只是偶尔的，例如，在托管交易中，提前保留发起一定数量减量的权利。

    既然您已经了解了设计CRDTs所涉及的内容，那么让我们来了解一下本文中定义的其他CRDTs：

    • 最后一个写入程序赢得寄存器（寄存器是可以存储对象或值的单元格）–合并基于时间戳
    • 多值寄存器-基于版本向量合并
    • 仅增长集（支持添加和查找）。这对于更高类型的应用来说是一个有用的构建块。
    • 一种2P集合（两阶段集合），其中一个项目可以添加或删除，但以后再也不会添加。
    • 一个U集（唯一集）。假设“要添加的每个元素都是唯一的”，2P集的简化变体。这让我在最初的几次阅读中感到困惑，因为根据定义，集合中的每个元素都是唯一的！作者在这里似乎捕捉到的是，要添加的元素并不是从一些先验的已知固定值集中提取的，而是在添加点“创建”的，这样就永远不能再创建同一个元素，也不能在另一个副本上独立创建它。例如，假设从所有uuid的集合中提取值，副本生成uuid，然后将其添加到U-set…
    • 最后一个Writer Wins元素集，它保留一个add集和一个remove集，并带有带时间戳的条目
    • 一种PN集合，它为每个元素保留一个计数器（具有一个有趣的特性，即计数器可以变为负数，在这种情况下，添加元素不会使其成为集合成员……）。
    • 观察到的移除集：

    • 前面的集合结构有实际的应用，但有些违反直觉。在2P集合中，删除的元素永远不能再添加；在LWW集合中，并发更新的结果取决于时间戳如何分配的不透明细节。我们在这里提出观察到的移除集（或集合），它支持添加和移除元素，并且很容易理解。一个加和除序列的结果只取决于它的因果历史，并且符合集合的序列规格。在同时添加和删除同一个元素的情况下，add具有优先权（与2P Set相反）。

    • 2P2P图（顶点和边的两个2P集的组合）。

    • 仅添加单调DAG（仅当边的方向与现有路径相同时，才可以添加边）。
    • 添加和删除部分顺序数据类型
    • 支持协同文本编辑的两种数据类型。

    又是购物车
    在周一的论文中，阿尔瓦罗等人。向我们展示了如何使用Bloom中的CALM分析来减少购物车中所需的协调量。夏皮罗等人。通过使用CRDTs对购物车建模来实现同样的技巧。

    我们将购物车数据类型定义为从ISBN编号（表示图书版本的唯一编号）到表示用户要购买的图书单位数的整数的映射。前面提出的任何集合抽象都很容易扩展到地图；我们选择扩展或集合，因为它可以最小化异常。元素是（键，值）对；具体来说，键是图书ISBN（唯一的产品标识符），值是多个副本。

    再往前走一步，我们可以为书店的购物车做模型：

    我们的电子商务书店维护以下信息。每个用户帐户都有一个单独的或购物车。假设帐户是唯一标识的，那么从用户到或购物车的映射可以通过一个U-Map来维护，这个U-Map以一种显而易见的方式派生自U-Set。购物车在首次创建帐户时创建，从系统中删除时删除。

    在Amazon与Dynamo一起使用的多版本方法中，在并发更新失败的情况下，可能会发生版本分支。添加的项目不会丢失，但删除的项目可能会重新出现。

    这种（基于CRDT的）设计仍然很简单，并且不会导致Dynamo报告的删除异常，也不承担Dynamo的MV寄存器方法所需的版本向量的成本。

    关于CRDTs与CALM的一点注记
    阿尔瓦罗等人所谓的CALM方法通过实施单调逻辑来确保最终的一致性。这有点类似于我们对于CvRDTs的规则，即每个更新或合并操作都在单调半格中向前移动。他们的Bloom领域专用语言附带了一个静态分析工具，可以分析程序流程并识别需要同步的非单调点。这种方法鼓励程序员编写单调的程序，并使他们意识到同步需求。单调逻辑比我们的单调半格更具限制性。因此，Bloom不支持不同步移除。