背景

在分布式计算中，无冲突复制数据类型（CRDT）是一种数据结构，可以在网络中的多台计算机之间进行复制，其中副本可以独立并发地更新，而无需副本之间的协调，并且在数学上始终是可能解决可能出现的不一致问题。

CRDT概念由Marc Shapiro，NunoPreguiça，Carlos Baquero和Marek Zawirski于2011年正式定义（论文）。开发最初是由协作文本编辑和移动计算推动的。CRDT也已用于在线聊天系统，在线赌博和SoundCloud音频分发平台中。在NoSQL，分布式Redis，Riak和Cosmos DB 中都有 CRDT 数据类型。

简介

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

因此，许多分布式计算都集中在如何防止对复制数据进行时并发更新的问题上（加锁方案）。但是另一种可能的方法是乐观复制，其中允许进行所有并发更新，并可能造成不一致，并在以后合并或“解决”结果（最终一致性方案）。通过这种方法，最终可以确保副本之间的一致性通过“合并”不同副本来重新建立。 尽管乐观复制在一般情况下可能无法正常工作，但事实证明，确实存在一类重要且实用的数据结构，即CRDT，在这种情况下，它确实可以工作 —— 在数学上始终可以合并或解析不同副本的并发更新。数据结构没有冲突，这使CRDT非常适合乐观复制。

例如，单向布尔事件标志就是个很小的CRDT类型：1bit的值为true或false。True表示某个特定事件至少发生过一次。False表示事件尚未发生。一旦设置为true，就不能将标志设置回false。（发生的事件不能回退）解决方法是“双向的”：合并标记为true的副本（该副本已观察到该事件）和标记为false的另一个副本（即副本未观察到该事件），则解决的结果为true —— 该事件已被观察到。（然后将false标记的副本设置为true，最终达到统一。）

CRDT的类型

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

这两个选择在理论上是等效的，因为一个可以模仿另一个。 但是，存在实际差异。

基于操作的CRDT（CmRDT）

基于操作的CRDT也称为交换复制数据类型(commutative replicated data types)或CmRDT。CmRDT副本仅通过发送更新操作来传播状态。例如，单个整数的CmRDT可能会广播操作（+10）或（-20）。副本接收更新并在本地应用它们。这些运算是可交换的。但是，它们不一定是幂等的。因此，通信基础结构必须确保将副本上的所有操作传递给其他副本，而不进行重复，但以任何顺序进行。

纯基于操作的CRDT 是基于操作的CRDT的变体，可减小元数据的大小。

优缺点
优点：基于操作的CRDT仅需发送通常很小的更新操作。
缺点：基于操作的CRDT需要通信中间件的支持。在将操作传输到其他副本时不会丢失或重复这些操作，并且应将它们按先后顺序进行交付。

基于状态的CRDT（CvRDT）

基于状态的CRDT称为聚合复制数据类型(convergent replicated data types)或CvRDT。与CmRDT相比，CvRDT将其完整的局部状态发送到其他副本， 这些状态在接受到后会被一个函数做 merge 处理，所以这些状态必须是可交换的，关联的，幂等的。merge 函数会为在 CvRDT 之间提供一个 join 操作，将接收到 CvRDT 与本地数据合并。所以将所有的状态设为半格形式，根据与半格相同的偏序规则，其update函数的内部状态必须是单调增加的。

增量状态CRDT（或简称为增量CRDT）是基于状态的优化CRDT，其中仅分发对状态的最近应用的更改，而不分发整个状态。

优缺点
优点 ：基于状态的CRDT通常更易于设计和实施。它们对通信基质的唯一要求是某种八卦协议(gossip protocol)。
缺点：它们的缺点是每个CRDT的整个状态必须最终传输到每个其他副本，这可能会很昂贵。

比较

尽管CmRDT对副本之间传输操作的协议提出了更高的要求，但与内部状态相比，当事务数较少时，CmRDT使用的带宽比CvRDT小。
不过由于CvRDT的合并功能是关联的，因此与某些副本的状态合并会产生对该副本的所有先前状态进行更新。八卦协议可以很好地将CvRDT状态传播到其他副本，同时减少网络使用，并处理拓扑更改。

基于状态的CRDT的存储复杂度的一些下限是已知的。

CRDT的几种实现

G-Counter (Grow-only Counter)

payload integer[n] P
    initial [0,0,...,0]
update increment()
    let g = myId()
    P[g] := P[g] + 1
query value() : integer v
    let v = Σi P[i]
compare (X, Y) : boolean b
    let b = (∀i ∈ [0, n - 1] : X.P[i] ≤ Y.P[i])
merge (X, Y) : payload Z
    let ∀i ∈ [0, n - 1] : Z.P[i] = max(X.P[i], Y.P[i])

此CvRDT为n个节点的群集实现一个计数器。集群中的每个节点都分配了一个ID，范围为0到n -1，可通过调用myId() 来检索该ID 。因此，每个节点在阵列P中被分配了自己的插槽，并在本地增加。更新在后台传播，并通过采用P中每个元素的max()合并。包含比较功能以说明状态的部分顺序。合并函数是可交换的，关联的和幂等的。更新功能根据比较功能单调增加内部状态。因此，这是正确定义的CvRDT，将提供强大的最终一致性。CmRDT等效项在接收增量操作时广播它们。

PN-Counter (Positive-Negative Counter)

payload integer[n] P, integer[n] N
    initial [0,0,...,0], [0,0,...,0]
update increment()
    let g = myId()
    P[g] := P[g] + 1
update decrement()
    let g = myId()
    N[g] := N[g] + 1
query value() : integer v
    let v = Σi P[i] - Σi N[i]
compare (X, Y) : boolean b
    let b = (∀i ∈ [0, n - 1] : X.P[i] ≤ Y.P[i] ∧ ∀i ∈ [0, n - 1] : X.N[i] ≤ Y.N[i])
merge (X, Y) : payload Z
    let ∀i ∈ [0, n - 1] : Z.P[i] = max(X.P[i], Y.P[i])
    let ∀i ∈ [0, n - 1] : Z.N[i] = max(X.N[i], Y.N[i])

CRDT开发中的常见策略是将多个CRDT组合在一起以制作更复杂的CRDT。在这种情况下，两个G计数器组合在一起以创建同时支持增量和减量运算的数据类型。“ P” G计数器计数增量；而“ N” G计数器会计算减量。PN计数器的值是P计数器的值减去N计数器的值。通过让合并的P计数器为两个P G计数器的合并来处理合并，并且类似地，对N个计数器进行处理。请注意，即使通过查询公开的CRDT的外部状态可以返回到先前的值，CRDT的内部状态也必须单调增加。

G-Set (Grow-only Set)

payload set A
    initial ∅
update add(element e)
    A := A ∪ {e}
query lookup(element e) : boolean b
    let b = (e ∈ A)
compare (S, T) : boolean b
    let b = (S.A ⊆ T.A)
merge (S, T) : payload U
    let U.A = S.A ∪ T.A

G集（仅增长集）是仅允许添加的集。元素一旦添加，就无法删除。两个G-Set的合并是它们的结合。

2P-Set (Two-Phase Set)

payload set A, set R
    initial ∅, ∅
query lookup(element e) : boolean b
    let b = (e ∈ A ∧ e ∉ R)
update add(element e)
    A := A ∪ {e}
update remove(element e)
    pre lookup(e)
    R := R ∪ {e}
compare (S, T) : boolean b
    let b = (S.A ⊆ T.A ∧ S.R ⊆ T.R)
merge (S, T) : payload U
    let U.A = S.A ∪ T.A
    let U.R = S.R ∪ T.R

将两个G集（仅增长集）组合以创建2P集。通过添加删除集（称为“逻辑删除”集），可以添加和删除元素。一旦删除，就不能重新添加元素；也就是说，一旦元素e在逻辑删除集中，查询将不再为该元素返回True。2P集使用“ remove-wins”语义，因此remove（e）优先于add(e)。

LWW-Element-Set (Last-Write-Wins-Element-Set)

LWW-Element-Set与2P-Set相似，因为它由“添加集”和“删除集”组成，每个元素带有时间戳。通过将元素插入带有时间戳的添加集中，可以将元素添加到LWW-Element-Set中。通过将元素添加到删除集中，再加上一个时间戳，可以从LWW元素集中删除元素。如果元素在添加集中，并且不在删除集中或不在删除集中，但具有比添加集中的最新时间戳早的时间戳，则该元素是LWW-Element-Set的成员。合并LWW-Element-Set的两个副本包括进行添加集的合并和删除集的合并。当时间戳相等时，LWW元素集的“偏差”起作用。LWW元素集可偏向添加或删除。

OR-Set (Observed-Remove Set)

OR-Set类似于LWW-Element-Set，但是使用唯一的标签而不是时间戳。对于集合中的每个元素，将维护一个添加标签列表和一个移除标签列表。通过生成新的唯一标签并将其添加到该元素的添加标签列表中，将元素插入“或集”中。通过将元素的添加标签列表中的所有标签添加到元素的移除标签（墓碑）列表中，可以将元素从OR集中移除。为了合并两个OR集，对于每个元素，让其添加标签列表为两个添加标签列表的并集，同样为两个删除标签列表。当且仅当添加标记列表减去移除标记列表时，元素才是集合的成员。通过优化可以消除维护逻辑删除集的需求。这避免了墓碑集的潜在无限增长。通过为每个副本维护一个时间戳矢量来实现优化。

Sequence CRDTs

序列，列表或有序集CRDT可以用于构建协作实时编辑器，以替代操作转换（OT）。

一些已知的序列CRDT是Treedoc、RGA、 Woot、Logoot和LSEQ。CRATE是基于LSEQSplit（LSEQ的扩展）构建的分散式实时编辑器，可使用WebRTC在浏览器网络上运行。提出了LogootSplit作为Logoot的扩展，以减少序列CRDT的元数据。MUTE是一个基于Web的在线对等实时协作编辑器，它依赖于LogootSplit算法。

原文：维基百科 Conflict-free replicated data type