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

Question

我是分布式系统的新手，正在尝试了解CRDT的概念。我意识到它有三种表示方法：

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

有人能给出使用CRDT在分布式系统中的例子吗？非常感谢。

- fnaticRC ggwp

---

如果回答解决了你的问题，请标记为已接受的答案。 - Basit Anwer

Answer 1

CRDTs受Marc Shapiro的工作启发。在分布式计算中，冲突自由复制数据类型（CRDT）是一种专门设计的数据结构，用于实现强有力的最终一致性（SEC）和单调性（无回滚）。确保SEC有两个替代方案：基于操作的CRDT和基于状态的CRDT。

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

这两个替代方案是等效的，因为一个可以模拟另一个，但基于操作的CRDT需要通信中间件提供额外的保证。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实现的Roshi，支持LWW时间戳集：

博客文章：Roshi：一种用于时间戳事件的CRDT系统

- Metin Dagcilar

Answer 2

CRDT使用数学来在分布式集群中强制实现一致性，而不必担心共识和相关的延迟/不可用性。CRDT可以在任何时候采取的值的集合属于半格（特别是加入半格），这是一个具有最小上界函数（LUB）的偏序集（POSET）。简单来说，POSET是一组项目，其中并非所有项目都可比较。例如，在一对数组中：{(2,4), (4, 5), (2, 1), (6, 3)}中，(2,4)小于(4,5)，但不能与(6,3)进行比较（因为一个元素更大，另一个元素更小）。现在，半格是指在给定两个对时，即使您无法将它们进行比较，也可以找到大于两者的元素（LUB）的POSET。另一个条件是此数据类型的更新需要增加，CRDT具有单调递增的状态，其中客户端永远不会观察到状态回滚。

这篇优秀的文章以我上面使用的数组为例。对于维护这些值的CRDT，如果两个副本正在尝试在(4,5)和(6,3)之间达成共识，则可以选择LUB = (6,5)作为共识并将两个副本分配给它。由于值是递增的，因此这是一个很好的解决方案。

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

Roshi是SoundCloud的一个很好的例子（尽管似乎不再开发），它存储与时间戳相关联的数据，其中时间戳显然是递增的。任何具有小于或等于存储的时间戳的更新都将被丢弃，这确保了幂等性（重复写入是可以接受的）和可交换性（无序写入是可以接受的。可交换性是指a=b意味着b=a，在这种情况下，update1后跟update2与update2后跟update1相同）

写入操作会发送到所有集群，如果某些节点由于诸如缓慢或分区等问题未能响应，则预计它们稍后通过read-repair进行追赶，以确保值收敛。正如我上面提到的，可以通过2种协议实现收敛，即传播状态或更新其他副本。我相信Roshi采用前者。作为read-repair的一部分，副本交换状态，因为数据遵循半格属性，所以它们会收敛。

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

关于此主题的另一篇优秀文章。

- Siddhartha

Answer 3

这三个缩写的扩展基本上意思相同。

如果在不同的顺序中应用相同的操作可以产生（收敛到）相同的结果，则CRDT是收敛的。也就是说，这些操作可以被交换 - 它是可交换的RDT。之所以可以在不同的顺序中应用这些操作并且仍然获得相同的结果，是因为这些操作是无冲突的。

因此，无论使用哪种扩展，CRDT的意思都是相同的 - 虽然我个人更喜欢“收敛”一词。

- cliffordheath

---

非常感谢@cliffordheath。 您详细解释了这三个术语。 但是，您能否举个例子呢？ - fnaticRC ggwp

CRDT的第一个谷歌搜索结果详细解释了它，并提供了示例。我只是解释了为什么这些名称意味着相同的事情。 - cliffordheath