23

我是分布式系统的新手，我正在尝试深入了解 CRDT 的概念。我意识到它有三个符号：

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

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

4

3 回答 3

33

CRDT 的灵感来自 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-由支持 LWW 时间戳集的 SoundCloud 实现的 Roshi：-博客文章：https ://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events

于 2016-03-15T13:16:38.573 回答
13

CRDT 使用数学在分布式集群中强制执行一致性，而不必担心共识和相关的延迟/不可用性。

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

简单来说，一个 POSET 是一组项目，其中并非所有项目都具有可比性。例如在一对数组中：{(2,4), (4, 5), (2, 1), (6, 3)},(2,4)是 < (4,5)，但不能与之比较(6,3)（因为一个元素较大而另一个较小）。现在，半格是一个 POSET，其中给定 2 对，即使您无法比较两者，您也可以找到一个大于两者的元素（LUB）。

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

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

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

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

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

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

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

于 2017-10-12T01:02:43.567 回答
3

首字母缩略词的这三个扩展都意味着基本相同的事情。

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

所以 CRDT 的意思是一样的，无论你使用三个扩展中的哪一个——尽管我个人更喜欢“收敛”。

于 2015-12-10T02:21:10.207 回答