Riak中CRDT的模糊指南(2013)

Riak1.4包括计数器。这是里亚克打破常规的一次突破。我们总是说：“你的数据对Riak来说是不透明的”，但反驳说这不是真的。Riak知道您针对Counter Key存储的内容，以及如何递增和递减。你用计数器API告诉Riakthis。您永远不会获取、变异和放置计数器，您只需说：递增5或递减100。您从不发送avlock，最重要的是，Riak知道如何将并发写入合并到计数器。你永远不会看到计数器的兄弟姐妹，你总是看到一个单一的值。不会丢失任何写入，最终，计数器将反映所有写入并达到一致的值。

计数器是可以的，但是您不能仅仅在计数器上构建很多应用程序。对于Riak2.0，我们添加了一些更多的数据类型。我们相信，通过添加这些数据类型，您可以更加简单地对许多应用程序的数据存储需求进行建模，而不必再编写兄弟合并函数。

当我们在过去讨论向Riak添加数据类型时，我们谈到了CRDT。CRDT代表(不同的)无冲突复制数据类型、收敛复制数据类型、交换复制数据类型等。关键的、重复的短语表明，我们正在处理复制的数据类型。

复制对于Riak来说是正常的。它是N值定义的。数据类型在计算中相当常见。集合、袋子、列表、寄存器、地图、计数器…。等等。这样我们就只剩下C来处理了。

15年前，卡洛斯·巴奎罗(Carlos Baquero)和弗朗西索·穆拉(Franciso Moura)提出了基于状态(或收敛CRDT)的CRDT，作为一种称为连接半格的东西的应用：偏序集合的三元组、最小元素(底层呵呵)和一个产生最小上界的函数。此函数必须是幂等、结合和可交换的，并且当应用于两个集合时，返回一个合并的或至少上界的集合，该集合也是偏序集合的实例。

Riak是一个最终一致的系统。它非常倾向于CAP频谱的AP端。我们通过向备用节点执行草率仲裁写入之类的操作来实现此可用性。但是，即使没有分区和许多节点，交叉或并发写入也可能导致冲突。传统上，Riak保留所有值并将它们呈现给用户进行解析。客户端应用程序必须具有解决冲突的确定性方法。它可能是选择最高的时间戳，或者联合列表中的所有值，或者执行更复杂的操作。无论它做什么，它都是临时的，并且是专门为手头的数据模型和应用程序创建的。但是它必须看起来就像JOIN半格的LUB函数：它必须是幂等的、可交换的和结合的。

在Riak中，没有冲突的C是一种谎言。仍然存在冲突，只是解决方案是数据类型设计的一部分。在所有以上的C中，Convergent对我们来说才是最重要的。我们为Riak创建的数据类型在写入和读取时在服务器上自动收敛。如果客户端应用程序可以使用我们提供的数据类型对其数据进行建模，它们将永远不会看到兄弟关系值，也不需要编写特殊的自定义合并函数。

如果您在Riak中存储数据，并且将ALLOW_MULT设置为TRUE，那么您需要处理冲突的写入。如果您必须在代码中处理它，则必须简化数据模型或编写复杂的合并函数。

“发电机报”[2]中的经典例子是亚马逊购物车。单个用户向购物车添加两个项目，这两个项目都添加了不同分区的服务器。现在有两个购物车，一个装有物品A，另一个装有物品B。合并逻辑很简单：联合购物车以获得单个正确的值。但是去掉的又是什么呢？如果物品A是由A添加的而还没有看到，或者是从第二车和第一车中移走而没有意识到，你怎么能说它不在第二车中呢？

也许您的应用程序稍微复杂一些，您需要添加购物车中每件商品的数量。现在，您的合并函数必须决定何时在一个同级中显示6个“发刷”实例，在另一个同级中显示4个实例，如果用户添加了6个，然后删除了2个，或者添加了4个，然后又添加了2个。也许你开始添加墓碑了。或记录操作(如StateBox。)。但很快就变得复杂起来。如果您需要记录更多信息，或者需要改进您的数据模型，那么您的合并功能必须扩展、调整和处理不同版本的数据，该怎么办呢？它很快就会变得非常复杂。

而且每个新的数据模型都需要新的即席合并功能，当您要在Riak中存储一些其他数据时，比如用户配置文件，您需要从头开始构建您的数据模型和合并逻辑。

当用编程语言建模应用程序的领域时，开发人员习惯于从一些原始数据类型(如集合、映射、寄存器、整数、布尔值等)组成状态。Riak中的数据类型使开发人员恢复了这种能力和表现力，并减轻了他们设计和测试确定性合并函数的负担。关键是数据对于Riak来说不再是不透明的。当您使用数据类型时，API Riak“知道”您存储的是什么类型的数据，并且能够为您执行语义合并。Riak已经检测到了冲突，它也能够利用数据类型来处理冲突。

读取数据类型值时，您将只看到单个值。该值最终仍然是一致的，但它将是正确的，因为它可以被赋予数据库中的熵量，并且当系统处于静止状态时，所有的值都将收敛到单一的、确定的、正确的值。

我们有一些数据类型可以根据Riak中的键存储，我们称之为顶级类型。

集合：它们是事物的集合。在Riak中，我们希望您存储二进制文件，这就是我们在Erlang中编码文本字符串的方式。你存储在集合中的东西可能是团队或部门的成员，社交网络上的追随者，也可能是现实世界收藏中的物品。

地图。映射是将数据类型组合成更丰富、更复杂结构的方法。映射是字段的集合。字段是名称和数据类型对。这样我们就不必处理合并不同类型的字段。如果将两个同名但类型不同的字段添加到地图中，则它们是两个不同的字段。您只能在地图中存储数据类型。

您可以将任何顶级类型存储在Map的字段中，包括Map。我们还增加了：

这些数据类型中的每一种的语义都不同于它们的常规线性对应类型。虽然我们认为我们选择的语义是最直观、最有用的，也是最不令人惊讶的。

因为我们将数据类型存储在Riak中(甚至在riak_Objects中)，所以最终一致性的所有权衡都适用(当然，第二次解析除外)。这意味着计数器不用于创建唯一的有序ID。而且Set和Map没有Redis对应物的原子和阻塞操作。

柜台没有任何变化。它们仍然不是幂等的。如果Riak为计数器操作返回错误，则可能只是部分失败，重试可能导致重复计数。但是，将元素添加到集合或将字段添加到映射是幂等的。

我们为Set和Map选择的语义是“add wins”。本文也将此称为“观察到的移除”，但这是Add如何取胜的实现细节(我将在下面介绍它)。

当集合上的任何一对操作是并发的，其中一对添加元素，而另一对删除元素时，添加操作获胜。如果删除操作紧跟在添加操作之后，则删除操作有效。不同元素上的并发操作的工作方式与您的预期不谋而合。

地图直接从集合中借用其行为。除了每次更新字段的内容(比如，在“Like”字段中增加计数器，或者在“Folders”字段中添加好友)，这将被视为“添加”该字段。这样，同时删除字段和更新字段将使更新获胜。再加一次赢。

难以回答的问题是，当字段同时更新和删除时，它的值应该是什么。答案是更新获胜，字段保留，它的值是所有幸存的副本合并后的值。

假设Map字段中的计数器在副本A处递增到5，并复制到B和C。同时，计数器字段从A中移除并在C处递增3，合并值将为8。也就是说，在A处移除不会逆转A之前的所有操作。

这个语义有一些令人惊讶和不完善的地方。如果AHAD在从C分区之后但在删除计数器字段之前将计数器递增2，则更新将丢失。只有B和C看到的A的值将保持不变。删除是很棘手的。

从撤军中还有另一个奇怪的优势，可能也会令人望而生畏。想象一下，副本A同时协调从地图中删除集合字段，而副本B协调删除同一集合中的所有元素。根据上面的规则，字段updatescount为“add”(对于add wins语义)，因此该字段仍然保留在Map中，尽管它是一个空集。

这些仅映射类型具有简单的语义。寄存器是Last WriteWins，使用处理写入的节点上的时间戳。因此，所有关于时钟同步的声明都适用。旗帜开始关闭，您可以将其打开。对于WINS上的任何一对并发的、冲突的操作(ON|OFF)。同样，同样的添加赢得了语义。

稍后将详细介绍这一点，但是所有的加法操作(即除了集合成员和映射字段删除之外的所有操作)都可以通过简单地向Riak发送操作来执行。不是通常的GET、MODIFY、UPDATECYCLE。这种“远程操作”是在Riak1.4中引入的，带有计数器，并扩展到新的数据类型。

仍然有两个接口，PB和HTTP。在撰写本文时，http API尚未完成，因此我将讨论PBAPI。假设会有平价。

API允许您指定要在Riak中复制副本的数据类型上执行的操作。对于计数器，您只能发送带有金额的单个操作“增量”(如果是减量，则为负数)。

您可以发送一份操作清单。该列表可以同时包含添加元素X和删除元素Y操作。如果您要删除元素，我们强烈建议您首先获取集合及其上下文，然后将上下文与删除操作一起发送。

所有操作都在协调副本处自动执行。如果列表中的任何操作失败(只有删除可以失败！)。则不会应用任何操作。

您可以发送一份操作清单。这些操作要么是现场操作，要么是现场更新操作。外业操作在地图中添加或删除字段。我发现将Map看作是(JSONlike？)。文件。现场操作会更改地图的模式。

字段更新操作作用于存储在地图中的数据。您可以将任意数量的操作分批发送到一起。您可以混合使用FieldOperations和Field Update Operations。

例如，如果您将“游戏状态”建模为特定用户和游戏的“地图”。您可以在用户开始游戏时发送操作，创建地图，添加点数和生命值计数器字段，解锁成就集，以及包含两套(盔甲和武器)和生命值计数器的库存地图。

随着游戏的进行，更新多个计数器、从集合中添加和删除元素等操作可以作为批处理发送，这些批处理在协调复制品处自动执行。这并不意味着您可以强制执行映射中的值之间的协不变量。

对于Map，强烈建议您使用任何一批包含Field或SetElement Remove的操作发送上下文文本，无论Map中嵌套得有多深。

如果您只更新映射中的字段，则不需要首先获取，也不需要上下文，您只需发送操作即可。

您不需要显式创建字段。更新协调复制品中不存在的字段将创建并更新该字段。例如，在Map at Key Game1的Field<；<；“gold”>；中的计数器上加10，如果该字段不存在，则会创建该字段，然后递增10。

我们不允许您从不在那里的集合/地图中删除某些内容。由于不能保证协调您的删除操作的副本包含您想要删除的值(想象一个空的后备以接受请求)，上下文用您看到的值“播种”处理副本。如果您没有发送上下文，并且副本没有您想要删除的值，则操作会失败，并出现“Predition Failure”错误。删除元素或字段的前提条件是它存在。

第二个原因更为微妙，需要一些实现细节(稍后我将介绍)才能真正理解。在这一点上，只要说没有删除的上下文就足够了，您可能会删除比计划更多的内容。“添加成功”语义基于“观察到的删除”，这意味着只删除您看到的内容。上下文告诉处理操作的副本您所看到的内容。如果要删除的元素的“Add”在您发送Remove之后由副本处理或看到，并且没有上下文，则Remove将赢得并发Add的支持。有时您可能需要这样做，但一般情况下，请使用上下文for removes。

上下文是集合或映射的紧凑二进制编码。我们希望在将来的版本中进一步简化它。

主要成本是数据类型占用空间。合并功能有一些计算性开销，这些功能将在您的Riak服务器上执行，而不是在您的客户端应用程序中执行。我们还需要测量这一点。

我们存储的数据类型是riak_Objects。因此，他们可以很好地处理Riak的所有系统，如AAE、企业多数据中心复制、读取修复等。因此，我们马上就有了Riak_Object的开销。

数据类型本身至少和它们包含的内容一样大，再加上一个版本向量，再加上一些圆点(见下文)。我们试图用有效的二进制表示来保持它们小(我们会在这方面不断改进)，但它们比人们最初想象的要大。

IRL：一个版本向量，每个参与者有两个整数，它协调了一个增量。每个参与者为8个字节。至少需要N-Val演员。

IRL：每个成员的成员大小之和加上一个版本向量和小数版本向量(最多为集合向量的大小，通常为一对{参与者，计数})。版本向量的大小取决于N-val、MDC、集群流失等。同样，每个参与者8个字节，尽管我们只存储每个参与者一次。

期望值：键的大小之和加上值的大小之和。

IRL：每个键都是一对{name，int}，其中int映射到实现字段数据类型的模块。每个成员也有十进制时钟(与集合一样)。

您现在已经足够了解Riak的数据类型了。如果你真的想知道香肠是怎么做的，那就往下看。

在这一点上值得记住的是，Vnode是Riak中的并发单位。每当我说Actor时，我指的是Vnode和Vnode ID。Riak中的正确性取决于单个演员的连续操作。

计数器是称为PN计数器的CRDT，其中P为正，N为负。它是{参与者，正，负}的三元组的列表，其中值是所有正的和与所有负的和之间的差值。参与者只能更新列表中自己的条目。当两个计数器合并时，我们取每个参与者的正值和负值的最大值。当参与者只在一个计数器中时，我们只将其值保留在合并的计数器中。

标志在逻辑上等同于只能包含一个元素的集合。元素的存在或不存在分别等同于标志是否打开或关闭。同样的“添加WINS”/“观察到的删除”行为也适用，除了我们称之为“观察到的禁用”的标志。对于用户来说，标志看起来像布尔值。

寄存器是一对{值，时间戳}。它们在最高的时间戳上汇聚。就像卡桑德拉的价值一样。它们需要精确同步的时钟。当两个寄存器合并时，具有最高时间戳的对是合并值。

任何收敛的或基于状态的CRDT的关键部分是它的合并功能。合并函数是JOIN-Semi-Lattice的Lub，它定义了数据类型的语义，以及客户可能不得不编写的所有临时冲突解决方案的泛化。

对于两个集合中的任何元素，优化OR集合[3]的合并函数都非常简单：它们都在集合中。当一个元素只在要合并的两个集合中的一个集合中时，困难就出现了。

当两个副本合并时，其中一个在其集合中包含一个元素，而另一个没有，为什么它会在那里？它可以是：

元素已添加到一个复本，而另一个复本尚未看到它。

我们需要知道为什么一个元素只在一个集合中才能得到正确的合并值。一如既往，在这些事情上，因果关系导致了这一结果。合乎情理的是，如果该元素曾经在集合A中，但不再存在，那么它将被移除。我们可以存储移动物品的墓碑值，但这意味着我们的集合永远不会变小。有一个成员的集合曾经有100个成员，其大小将与有100个成员的集合的大小相同。

相反，我们所做的是将一个版本矢量附加到集合中，并且每次将元素添加到集合中时，我们都会为添加该元素的副本递增版本矢量中的条目。我们还存储了对元素(从现在开始我将称之为Dot[4])的增量所产生的{actioner，count}对。如果已经有一个与元素相关联的点，我们也会保留它。我们最终得到的结果如下[{actor1，count}=dot1，{actor2，count}=do2，…]。，它是一个版本向量，但它是一个最小时钟，在添加元素时只存储点或事件。请注意，附加到整个集合的版本向量将始终控制所有元素的所有最小时钟。

当从集合中删除一个元素时，我们只需删除该元素及其最小时钟。

现在，当合并发生时，我们比较这两个集合。我们获取集合A中的所有元素和不在集合B中的所有元素，并将它们的最小时钟与集合B的集合版本向量进行比较。每个最小时钟占主导地位的元素都已从集合B中移除，并且不会进入合并的集合。作为一种轻微的优化，我们还从由集合B‘sclock支配的最小时钟中丢弃了任何点。这使最小时钟保持最小。您可以将其视为从集合B的集合版本向量中减去最小时钟，如果留下任何点，则元素在合并的集合中，剩余的点作为新的最小时钟。

我们以另一种方式重复该过程，将不在集合A中的所有集合B的元素与集合A的集合版本向量进行比较。

我们保留两个集合中的所有元素，合并它们的最小时钟。最后，我们将两个集合版本向量合并，以保证集合版本向量始终支配所有最小时钟的属性。

集合被实现为版本向量和来自元素->；最小时钟的映射字典。

就实现而言，Map就像上面描述的集合一样。它们使用相同的Map版本矢量和每个条目的最小时钟来决定如何处理仅位于amerge一侧的Field。

当然，主要区别在于当一个元素同时位于两个Map中时：我们调用数据类型的合并函数来获得单个收敛的值。从概念上讲，合并两个映射等同于合并两组字段，然后对所有公共字段值调用Merge。

[4]点状版本矢量：乐观复制的逻辑时钟努诺·普雷奎萨、卡洛斯·巴奎罗、保罗·塞尔吉奥·阿尔梅达、维克多·方特、里卡多·贡萨尔维斯·http://arxiv.org/abs/1011.5808