如何计算google.com页面点击量？ 以及如何存储非常受用户喜欢的计数器？ 本文建议考虑使用CRDT（无冲突的复制数据类型，在俄语中大致翻译为无冲突的复制数据类型）来解决这些问题，在更一般的情况下，是使用具有多个主节点的分布式系统中的副本同步任务。

1.简介

长期以来，我们习惯于使用诸如日历之类的应用程序或诸如Evernote之类的便笺服务。 它们的结合是，它们使您可以脱机工作，从多个设备同时到多个人（在同一数据上）。 每个这样的应用程序的开发人员面临的挑战是如何确保在多个设备上同时更改的数据的“最流畅”同步。 理想情况下，根本不需要用户参与即可解决合并冲突。

在上一篇文章中，我们已经考虑了一种解决此类问题的方法-操作转换，还将描述一种既有优点又有缺点的非常相似的方法（例如，尚未发明CRDT for JSON。Upd ：感谢msvn的链接，这里这是研究文章作者关于CRDT中JSON的实现的项目）

2.强大的最终一致性

最近，在最终一致性领域已经进行了很多工作，并进行了大量研究。 以我的观点，现在有一个趋势，即从强一致性转向各种一致性选项，研究在哪种情况/系统中应用哪种一致性更有利可图，以重新考虑现有定义。 例如，当某些作品的作者谈论一致性，最终具有某些其他属性的一致性，而其他作者为此使用某些术语时，这会引起混乱。

其中一篇文章的作者提出的问题批评了最终一致性的当前定义：据此，如果您的系统始终对所有请求都回答“ 42”，那么一切正常，最终是一致的。

在不违背本文正确性的前提下，我跟随原始文章的作者，使用以下术语（请注意，这些不是严格的定义，是不同的）：

• 强一致性（SC）：所有写入操作均严格排序，任何副本上的读取请求均返回相同的最后记录结果。 需要实时共识来解决冲突（以及随之而来的后果），并且可以承受下降到n / 2-1个节点的风险。
• 最终一致性（EC）：在本地更新数据，然后进一步发送更新。 在不同的副本上进行读取可以返回陈旧的数据。 如果发生冲突，我们要么回滚，要么以某种方式决定要做什么。 T.O. 仍然需要达成共识，但不再是实时的 。
• 强大的最终一致性（SEC）：EC +用于解决冲突，副本具有预定义的算法。 T.O. 不需要共识 ；它可以承受n-1个节点的下降。

请注意，SEC（照原样）解决了CAP定理的问题：满足了所有三个属性。

因此，我们准备捐赠SC，并希望为我们潜在不稳定的分布式系统提供一组特定的基本数据类型，这些数据类型将自动为我们解决写入冲突（不需要用户交互或请求仲裁者）

3.关于喜欢和点击的任务

毫无疑问，有几种算法可以解决此类问题。 CRDT提供了一种相当优雅和简便的方法。

Google.com命中数：

google.com每秒大约处理来自世界各地的150,000个请求。 显然，计数器需要异步更新。 队列部分地解决了这个问题-例如，如果我们提供一个外部API来获取此值，那么我们将必须进行复制，以免将存储库置于读取请求中。 如果已经存在复制，也许没有全局队列？

计算用户点赞次数：

该任务与上一个任务非常相似，只是现在您需要计算唯一点击数。

4.术语

为了更全面地了解本文，您需要了解以下术语：

1. 幂等
   说多次应用操作不会改变结果。
   示例-GET操作或零加法： $$$f（x）= x + 0$
   
2. 可交换性
   $$$f（x，y）= f（y，x）$
   
3. 偏序
   自反性+传递性+反对称
   
4. 半格
   部分排序的集合具有准确的上（下）面
   
5. 版本向量
   维向量等于节点数，并且每个节点在发生特定事件时会在向量中增加其值。 在同步期间，将使用此向量传输数据，这将引入顺序关系，从而使您可以确定哪个副本具有旧/新数据。

5.同步模型

基于州：

也称为被动同步，它形成了聚合复制数据类型-CvRDT。
它用于NFS，AFS，Coda等文件系统以及KV存储Riak，Dynamo中
在这种情况下，副本直接交换状态，接收副本将接收到的状态与其当前状态合并。


要使用此同步执行副本的收敛，必须：

• 数据形成半格
• 合并功能产生了确切的上限
• 复制品形成了一个连通图。

一个例子：

• 数据集：自然数 $$$\ mathbb {N}$
• 最低要求： $$$-\ infty$
• $$$合并（x，y）=最大值（x，y）$

这些要求为我们提供了一个交换和幂等合并函数，该函数在给定数据集上单调增长 ：


这样可以确保副本早晚收敛，并且使您不必担心数据传输协议- 我们可能会丢失具有新状态的消息，将它们发送几次，甚至可以以任何顺序发送 。

基于操作：

也称为主动同步，它形成交换复制数据类型-CmRDT。
用于协作系统，如Bayou，Rover，IceCube，Telex。

在这种情况下，副本交换状态更新操作。 更新数据时，原始副本：

• 调用generate（）方法，该方法返回effector（）方法以在其余副本上执行。 换句话说，效果器（）是用于更改其余副本状态的闭包。
• 将效应器应用于本地状态
• 将效应器发送到所有其他副本

要执行副本的收敛，必须满足以下条件：

• 可靠的传送协议
• 如果效应器按照输入的顺序（对于给定类型）交付给所有副本，则同时效应器是可交换的， 或者
• 如果效应器在不考虑顺序的情况下交付给所有副本，则所有效应器都是可交换的。
• 如果效应子可以多次传递，则它必须是幂等的
• 一些实现使用队列（Kafka）作为传递协议的一部分。

基于增量的：

考虑到基于状态/操作，很容易注意到，如果更新仅更改部分状态，则发送整个状态是没有意义的；如果大量更改影响一个状态（例如，计数器），则可以发送一个汇总更改，而不是所有操作变化。

增量同步结合了这两种方法，并发出增量变量，这些变量会根据最新的同步日期更新状态。 在初始同步时，有必要完全发送状态，并且在此类情况下，某些实现在构造增量变量时已经考虑了其余副本的状态。

如果允许延迟，则下一个优化方法是压缩基于op的日志。

基于纯操作：

在基于op的同步中创建opector会有延迟。 在某些系统中，这可能是不可接受的，然后您必须发送原始更改，但要付出复杂的协议和额外的元数据量的代价。

标准使用方法：

• 如果要立即在系统中发送更新，则基于状态将是一个糟糕的选择，因为发送整个状态比仅进行更新操作要昂贵。 基于增量的效果更好，但是在这种特殊情况下，与基于状态的差异很小。
• 如果您需要在失败后同步副本 ，那么基于状态和基于增量的是最佳选择。 如果必须使用基于op的选项，则选项为：
  
  1）从失败时刻开始滚动所有错过的操作
  2）副本之一的完整副本，并回滚丢失的操作
• 如上所述，基于op的更新要求准确地交付给每个副本一次。 如果效应子是幂等的，则仅可以省略一次交货要求。 在实践中，实施第一种方法要比第二种方法容易得多。

基于Op和基于State之间的关系：

可以互相模拟两种方法，因此将来我们将在不参考任何特定同步模型的情况下考虑CRDT。

6. CRDT

6.1柜台

支持两个操作的整数：inc和dec。 例如，考虑基于op的同步和基于状态的同步的可能实现：

基于操作数的计数器：

显然，仅发送更新即可。 inc的示例：

function generator() { return function (counter) { counter += 1 } } 

基于状态的计数器：

由于不清楚合并功能的外观，因此实现不再那么明显。

考虑以下选项：

单调递增计数器（仅递增计数器，G计数器）：

数据将被存储为尺寸等于节点数的矢量（版本矢量），并且每个副本将使用其id增大位置值。

合并函数将在相应位置取最大值，最终值为向量中所有元素的总和

$$

$$\ begin {align} inc（）＆：V [id（）] = V [id（）] + 1 \\ value（）＆：\ sum_ {i = 0} ^ {n} V [i] \\合并（C_1，C_2）＆：[1..n]中的i \结果[i] =最大值（C_1.V [i]，C_2.V [i]）\结束{align}$$

您也可以使用G套件（见下文）

应用范围：

• 计算点击次数/点击数（原文如此！）

带减量支持的计数器（PN计数器）

我们启动两个G计数器-一个用于递增操作，第二个-用于递减

应用范围：

• p2p网络（例如Skype）中已登录的用户数

非负计数器

尚不存在简单的实现。 在评论中提出您的想法，进行讨论。

6.2注册

具有两种操作的存储单元-分配（写）和值（读）。
问题是分配不是可交换的。 有两种方法可以解决此问题：

最后写胜寄存器（LWW寄存器）：

我们通过为每个操作生成唯一ID（例如时间戳）来输入完整订单。

同步的一个示例是对（值，id）的交换：


应用范围：

• 卡桑德拉中的列
• NFS-全部或部分文件

用多个值注册（多值寄存器，MV寄存器）：

该方法类似于G计数器-我们存储集合（值，版本向量）。 寄存器值-合并时的所有值-向量中每个值的LWW分别。


应用范围：

• 在亚马逊的篮子。 与此相关联的是一个众所周知的错误，当从购物篮中删除一个项目后，它再次出现在那里。 原因是尽管寄存器存储了一组值，但它不是一组值（请参见下图）。 顺便说一句，亚马逊甚至都不认为这是一个错误-实际上，它可以增加销量。
• 子 在更一般的情况下，我们将选择实际（注意-没有冲突！）值的问题转移给应用程序。

亚马逊错误的解释：

6.3手

该集合是构造容器，地图和图形的基本类型，并支持操作-添加和rmv，这是不可交换的。

考虑一下基于op的集合的朴素实现，其中add和rmv在到达时执行（add同时到达1和2个副本，然后rmv到达1）


如您所见，副本最终分散了。 考虑构造无冲突集的各种选项：

生长套装（G-套装）：

最简单的解决方案是防止项目被删除。 剩下的就是加法运算，它是可交换的。 合并功能是集合的并集。

两相装置（2P装置）：

我们允许您删除，但删除后无法再次添加。 为了实现，我们设置了单独的一组远程G-set元素（这样的集合称为逻辑删除集）
基于状态的示例：

$$

$$\开始{align}查找（e）＆：e \在A \ land e \ notin R \\加（e）＆：A = A \ cup \ {e \} \\ rmv（e）＆：R = R \ cup \ {e \} \\合并（S_1，S_2）＆：\\ Res＆ult.A = S_1.A \ cup S_2.A \\ Res＆ult.R = S_1.R \ cup S_2.R \ end {align}$$

LWW元素集：

实现无冲突集的另一种方法是引入一个完整的顺序，一种选择是为每个元素生成唯一的时间戳。

我们得到两个集合-add-set和remove-set，当调用add（）时，添加（element，unique_id（）），检查集合中是否有元素-查看时间戳更大的位置-在remove-set或add-set中

PN集：

集合顺序的变化-我们为每个元素启动一个计数器，添加它时我们增加它，删除它时我们就减少它。 如果元素的计数器为正，则该元素在集合中。

注意有趣的效果-在第三个副本中，添加元素不会导致其外观。

观察删除集，或集，加赢集：

在这种类型中，添加优先于删除。 实现示例：为每个新添加的元素分配一个唯一的标签（相对于该元素，而不是整个集合）。 Rmv从集合中删除一个元素，并将所有可见对（元素，标签）发送到副本以进行删除。

赢双赢组合：

与上一个相似，但同时添加/ rmv rmv wins。

6.4图

这种类型是建立在许多基础上的。 问题是这样的：如果同时执行addEdge（u，v）和removeVertex（u）-我该怎么办？ 以下选项是可能的：

• RemoveVertex优先级，所有与此顶点相关的边都将被删除
• AddEdge优先级，恢复已删除的顶点
• 我们延迟执行removeVertex，直到同时执行所有addEdge。

最简单的选择是第一个，对于其实现（2P2P-Graph），它足以获得两个2P-Set，一个用于顶点，第二个用于边缘

6.5地图

文字映射：

要解决的两个问题：

• 如何同时执行推入操作？ 与计数器类似，您可以选择LWW或MV语义
• 与同步投放/ rmv怎么办？ 与集合类似，您可以将put-wins或rmv-wins或last-put-wins语义使用。

CRDT映射（CRDT的映射）：

一个更有趣的情况，因为 允许您构建嵌套映射。 我们不考虑更改嵌套类型的情况-这应由嵌套的CRDT本身决定。

递归重置地图删除

删除操作将类型值“重置”到某个起始状态。 例如，对于计数器，这是零值。

考虑一个例子-一般的购物清单。 其中一个用户添加面粉，第二个​​用户进行检出（这导致对所有元素的删除操作的调用）。 结果，一份面粉仍保留在列表中，这似乎是合乎逻辑的。


移除胜出地图

rmv操作优先。

示例：在一个在线游戏中，一个爱丽丝玩家拥有10个硬币和一把锤子。 然后，同时发生两个事件：在副本A上，她产生了一个指甲；在副本B上，她的角色被删除，同时删除了所有对象：



请注意，当使用递归删除时，最终会保留指甲，这在删除字符时不是正确的状态。

更新胜图

更新优先，或者取消先前的操作以删除同时的rmv。

示例：在在线游戏中，副本B上的Alice角色由于不活动而被删除，但是活动同时在副本A上发生。 显然，删除操作必须取消。


使用这种实现时，有一个有趣的效果-假设我们有两个副本A和B，并且它们通过某个键k存储该集合。 然后，如果A删除键k的值，而B删除该集的所有元素，那么最终副本将保留带有键k的空集。

请注意，单纯的实现将无法正常工作-您不能简单地撤消所有先前的删除操作。 在下面的示例中，使用这种方法，最终状态将是初始状态，这是不正确的：

清单

这种类型的问题是，在本地插入/删除操作之后，不同副本上的项目索引将不同。 为了解决此问题，应用了操作转换方法-应用获得的更改时，应考虑原始副本中元素的索引。

7. Riak

例如，考虑一下Riak中的CRDT：

• 计数器：PN计数器
• 设置：或设置
• 地图：CRDT更新胜出地图
• （布尔值）标志：或设置最多1个元素
• 寄存器：对（值，时间戳）

8.谁使用CRDT

Wiki部分包含了很好的示例。

9.参考

• 关键CRDT商店
• 无冲突的复制JSON数据类型
• 对收敛和交换复制数据类型的全面研究
• 收敛和交换复制数据类型
• 无冲突的复制数据类型
• Riak CRDT的模糊指南
• CRDT：一个更新（或只是一个PUT）
• 无冲突的复制数据类型：概述
• 强大的最终一致性和无冲突的复制数据类型
• 最终一致的数据结构