CRDT

在分布式计算中，无冲突复制数据类型（CRDT）是一种在网络中的多台计算机之间复制的数据结构，具有以下功能：[1] [2] [3] [4] [5] [6 ] [7] [8]

• 应用程序可以独立、并发地更新任何副本，而无需与其他副本协调。
• 算法（本身是数据类型的一部分）会自动解决可能发生的任何不一致。
• 尽管副本在任何特定时间点可能具有不同的状态，但保证它们最终会收敛。

CRDT 概念由 Marc Shapiro、Nuno Preguiça、Carlos Baquero 和 Marek Zawirski 于 2011 年正式定义。[9] 开发最初是由协作文本编辑和移动计算推动的。 CRDT 还被用于在线聊天系统、在线赌博和SoundCloud音频分发平台。 NoSQL分布式数据库Redis、Riak和Cosmos DB都 具有 CRDT 数据类型。

背景

如果托管副本的计算机之间没有协调，对同一数据的多个副本的并发更新可能会导致 副本之间出现不一致，这在一般情况下可能无法解决。当更新之间存在冲突时恢复一致性和数据完整性可能需要完全或部分删除一些或全部更新。

因此，许多分布式计算都集中在如何防止对复制数据的并发更新的问题上。但另一种可能的方法是乐观复制，即允许所有并发更新通过，可能会产生不一致，结果稍后会合并或“解决”。在这种方法中，副本之间的一致性最终通过不同副本的“合并”重新建立。虽然乐观复制在一般情况下可能不起作用，但有一类重要且实用的数据结构 CRDT 却能发挥作用——始终可以合并或解决数据结构不同副本上的并发更新而不会发生冲突。这使得 CRDT 成为乐观复制的理想选择。

例如，单向布尔事件标志是一个简单的 CRDT：一位，值为 true 或 false。 True 表示某个特定事件至少发生过一次。 False 表示事件尚未发生。一旦设置为 true，该标志就无法设置回 false（已发生的事件无法取消）。解决方法是“true wins”：当合并标志为 true（该副本已观察到该事件）的副本和另一个标志为 false（该副本未观察到该事件）的副本时，解析结果为true — 该事件已被观察到。

类型

基于操作的CRDT(CmRDT)

• 基于状态的 CRDT 通常更易于设计和实现；他们对通信底层的唯一要求是某种八卦协议。它们的缺点是每个 CRDT 的整个状态最终必须传输到每个其他副本，这可能成本高昂。
• 基于操作的 CRDT 也称为交换复制数据类型，或CmRDT

  基于状态的()

• 基于操作的 CRDT 仅传输更新操作，更新操作通常很小。然而，基于操作的CRDT需要通信中间件的保证；当传输到其他副本时，操作不会被丢弃或重复，并且它们按因果顺序传递。
• 基于状态的 CRDT 称为聚合复制数据类型，或CvRDT
• CvRDT 将其完整的本地状态发送到其他副本，其中状态由一个必须具有交换性、结合性和幂等性的函数合并。合并函数为任何一对副本状态提供连接，因此所有状态的集合形成一个半格。更新函数必须根据与半格 相同的偏序规则单调增加内部状态。