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

Question

我是一个在分布式系统中的新手，我试图对CRDT的概念有一个了解。我意识到它有三个符号：

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

有人能给出我们在分布式系统中使用CRDT的例子吗？提前谢谢。

Answer 1

CRDT的灵感来源于Marc的工作。在分布式计算中，无冲突复制数据类型(简称CRDT)是一种特殊设计的数据结构，用于实现强的最终一致性(SEC)和单调性(无回滚)。有两种方法可以确保SEC:基于操作的CRDTs和基于状态的CRDT。

不同副本上的CRDT可以彼此分离，但最终可以安全地合并，从而提供最终一致的值。换句话说，CRDT有一个幂等的、交换的和结合的合并方法。

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

一些使用它们的示例，

Riak是最流行的CRDT开源库，由Bet365和英雄联盟使用。下面是一些支持Riak的有用链接。

1- Bet365 (使用Erlang和Riak) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf

2-英雄联盟使用Riak CRDT实现其游戏内聊天系统(它处理750万并发用户和每秒11,000条消息)。

3-由SoundCloud实现的支持LWW时间戳集的Roshi：-Blog post：https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events

Answer 2

CRDT使用Math实现分布式集群的一致性，而不必担心一致性和相关的延迟/不可用性。

CRDT可以在任何时候采取的一组值属于半格(特别是连接半格)的范畴，它是一个具有最小上界函数(LUB)的POSET (偏序集)。

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

另一个条件是，对此数据类型的更新需要增加，CRDT具有单调增加的状态，客户永远不会观察状态回滚。

这个优秀文章使用我前面使用的数组作为示例。对于维护这些值的CRDT，如果两个副本试图在(4,5)和(6,3)之间达成共识，它们可以选择一个LUB = (6,5)作为协商一致，并将两个副本分配给它。由于这些值在增加，这是一个很好的解决办法。

CRDTs可以通过两种方式在副本之间保持同步，它们可以通过周期性地(聚合复制数据类型)传输状态，或者在获得更新(增量)时传递更新(增量)(可交换复制数据类型)。前者占用更多带宽。

SoundCloud的罗氏是一个很好的例子(虽然似乎已经不再开发了)，但是它们存储与时间戳相关的数据，其中时间戳明显在增加。任何带有小于或等于存储时间戳的更新都将被丢弃，这将确保幂等性(重复写入可以)和交换性(无序写入可以。交换性是a=b means b=a，在本例中，这意味着update1后面跟着update2和update2后面跟着update1)

写入将发送到所有集群，如果某些节点由于诸如缓慢或分区等问题而无法响应，则希望它们稍后通过read-repair进行追赶，这将确保值的收敛。正如我前面提到的那样，可以通过两个协议实现收敛，将状态传播或更新到其他副本。我相信Roshi做的是前者。作为read-repair的一部分，副本交换状态，并且由于数据依附于半格属性，它们会收敛。

PS。使用CRDT的系统最终是一致的，即它们在盖定理中采用AP (高度可用和允许分区)。

另一本关于这一主题的优秀读物。

Answer 3

这三个缩略语的扩展都意味着基本相同的事情。

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

因此，CRDT的意思是相同的，无论你使用的三个扩展中的哪一个--尽管我个人更喜欢“收敛”。