无冲突复制数据类型

在分布式计算中，无冲突复制数据类型（CRDT）是一种在网络中的多台计算机上复制的数据结构，具有以下特点：

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

开发的最初动机是协作式文本编辑和移动计算。CRDTs也被用于在线聊天系统、在线赌博和SoundCloud音频分发平台中。

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

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

有两种CRDTs的方法，它们都可以提供强大的最终一致性：基于操作的CRDTs和基于状态的CRDTs。

这两种方法在理论上是等价的，因为每种方法都可以模拟另一种方法。基于状态的CRDTs通常在设计和实现上更简单；它们对通信基底的xxx要求是某种流言协议。相比之下，基于操作的CRDTs只传输更新操作，而这些操作通常是小的。

基于操作的CRDTs也被称为交换性复制数据类型，或CmRDTs。CmRDT复制体只通过传输更新操作来传播状态。例如，一个单一整数的CmRDT可以广播操作（+10）或（-20）。复制体接收更新并在本地应用它们。这些操作是互换的。然而，它们不一定是等价的。因此，通信基础设施必须确保一个副本上的所有操作都被传递给其他副本，没有重复，但以任何顺序。

纯粹的基于操作的CRDTs是基于操作的CRDTs的一个变种，它减少了元数据的大小。

基于状态的CRDTs被称为聚合复制的数据类型，或CvRDTs。与CmRDTs相反，CvRDTs将其完整的本地状态发送到其他副本，在那里，这些状态被一个必须是互换的、关联的和同位的函数合并起来。合并函数为任何一对复制体的状态提供一个连接，因此所有状态的集合形成一个半网格。更新函数必须单调地增加内部状态，根据与半网格相同的偏序规则。