什么是分布式系统中的CRDT？

Question

我是分布式系统的新手，我想了解CRDT的概念。 我意识到，它有三个符号：

Conflict-free Replicated Data Type 
Convergent Replicated Data Type 
Commutative Replicated Data Type 

谁能给我们在分布式系统中使用CRDT的例子吗？ 非常感谢。

Answer 1

CRDTs的灵感来自Marc Shapiro的工作。在分布式计算中，无冲突复制数据类型（简称CRDT）是一种专门设计的数据结构，用于实现强大的最终一致性（SEC）和单调性（无回滚）。确保证交会有两条备选路线：基于操作的CRDT和基于状态的CRDT。

不同副本上的CRDT可以相互偏离，但最终可以安全地合并以提供最终一致的值。换句话说，CRDT具有幂等性，交换性和关联性的合并方法。

这两种选择是等同的，因为可以模拟另一种选择，但基于操作的CRDT需要通信中间件的额外保证。 CRDT用于跨网络中的多台计算机复制数据，执行更新而无需远程同步。这将导致使用传统最终一致性技术的系统中的合并冲突，但CRDT的设计使冲突在数学上不可能。在CAP定理的约束下，它们为可用/分区容忍（AP）设置提供了最强的一致性保证。

在使用它们的

了Riak是CRDT的最流行的开源库，并使用bet365的和LOL的一些例子。以下是一些支持Riak的有用链接。

1- bet365的（使用Erlang和了Riak） http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf

传说的2-联赛用于其在游戏中的聊天系统的了Riak CRDT实现（处理750万个并发用户和每秒11000个消息）

3-滤纸通过的SoundCloud实现一个支持LWW时间标记集： -Blog交：https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events

Answer 2

这三个缩写的扩展都意味着基本上是相同的东西。

如果在不同的序列中应用相同的操作会产生（收敛）相同的结果，则CRDT会收敛。也就是说，这些操作可以进行交换 - 这是一个交互式的RDT。操作可以以不同的顺序应用并且仍然可以得到相同的结果的原因是这些操作是无冲突的。

因此，CRDT意味着同样的事情，无论您使用哪种扩展模式 - 尽管我个人更喜欢“Convergent”。

Answer 3

CRDTs使用数学执行跨分布式群集的一致性，而不必担心共识和一个相关的延迟/不可用性。

CRDT随时可以采用的值集合属于半格（特别是连接半格）类别，它是一个具有最小上界函数的POSET（部分有序集合）（ LUB）。

简而言之，POSET是其中并非所有可比较的项目的集合。例如。在一对数组中：{(2,4), (4, 5), (2, 1), (6, 3)},(2,4)是< (4,5)，但不能与(6,3)进行比较（因为一个元素较大而另一个较小）。现在，一个半格是一个POSET，其中给定2对，即使你不能比较这两个，你可以找到一个比两者都大的元素。

另一种情况是此数据类型的更新需要增加，CRDT具有单调递增的状态，其中客户端从不观察状态回滚。

这个excellent article使用我上面使用的数组作为例子。对于保持这些值的CRDT，如果2个副本试图达成(4,5)和(6,3)之间的一致性，他们可以选择LUB = (6,5)作为共识，并将两个副本分配给它。由于价值 正在增加，这是一个很好的价值来解决。

CRDT有两种方式可以在副本之间保持同步，它们可以定期传输状态（融合复制数据类型），或者可以在更新（增量）时传输更新（增量）（交换复制数据类型）。前者需要更多带宽。

SoundCloud的Roshi就是一个很好的例子（尽管看起来不再处于开发中），它们存储与时间戳相关的数据，其中时间戳明显递增。任何更新进入的时间戳小于或等于所存储的时间戳将被丢弃，这将确保幂电位（重复写入正常）和交换性（乱序写入正常，交换性为a=b means b=a，在这种情况下表示update1后面是update2与update2相同，然后是update1）

写入被发送到所有群集，并且如果某些节点由于缓慢或分区等问题而无法响应，它们预计会在稍后通过read-repair追上，这将确保值汇聚。如上所述，可以通过2个协议实现收敛，将状态或更新传播到其他副本。我相信罗西是做前者的。作为read-repair的一部分，副本交换状态，并且由于数据遵循半晶格属性，它们会聚合。

PS。使用CRDT的系统最终是一致的，即它们在CAP theorem中采用AP（高可用性和分区容忍）。

Another excellent read on the subject.