一种同时支持状态复制和基于操作复制的锈病CRDT家族

CRDT扩展为无冲突复制数据类型，它指的是知道如何无冲突合并的一族结构。CRDT有两个主要的亚家族：CvRDT和CmRDT。它们的复制方式不同。CvRDT是基于状态的，这意味着您将通过网络将整个CRDT状态发送给您的同行。相反，CmRDT通过将所有编辑(称为操作)分发到系统中的每个节点来进行复制。

在这里，我们将快速浏览一下CRDT，为了清晰和简洁，我们将只关注CvRDT(所有的想法仍然适用于CmRDT)。CvRDT结构定义了使状态a和b产生合并状态的合并(a，b)操作。一个简单的例子是GSet(仅增长集)，它的合并是两个集的并集。

CRDT'；都是关于偏序的，要将结构变成CRDT，必须首先在结构的状态空间上定义一种特殊的偏序。您必须小心执行此操作，因为部分顺序还定义了合并的行为方式。例如，让我们看一下在两个插槽中存储多维数据集的类似2元组的结构的状态空间，它的状态空间如下所示：

要使此结构成为CRDT，我们需要状态空间上满足以下约束的偏序：

∀s⊆S其中S是状态空间的任何子集的状态空间#...∃lub s和lub s∈S#。集合的最小上界也在状态空间中。

Lub是最小上界操作，它取状态空间的一个子集，并产生大于或等于该子集中所有状态的唯一状态。这里是满足以下约束的部分订单：

现在假设我们想要合并这个结构的两个实例，那么事实证明我们已经完成了困难的部分，因为偏序告诉我们最终的合并状态是什么。

合并(a，b)操作与计算集合{a，b}的最小上界完全相同。

通过1.合并是幂等的，因为以前的状态将低于或等于当前状态，重新合并过时的状态将不起作用。

使用CRDT与您可能习惯的数据结构略有不同。由于我们可能正在对其他人同时编辑的数据进行操作，因此我们需要确保您的本地编辑仅影响您看到的数据。

例如，如果您清除地图，我们希望能够说明此清除操作只会影响您知道的地图中的条目。如果您没有正确跟踪编辑的此因果历史记录，最终可能会删除您不知道的数据。例如，丢失数据的一个好方法是这样做：

您将收到地图CRDT的更新版本，但用户尚未刷新其视图。

用户选择清除映射的值。所以在CRDT上调用Map：：Clear()。

此时，您可能已经清除了用户不想清除的数据。要解决此问题，我们需要在Clear操作中包含因果上下文。这个因果上下文是一个矢量时钟(VClock)，它存储用户在决定Map：：Clear()时看到的Map版本。

首先创建CRDT的一个实例，在本例中我们将使用MVReg(多值寄存器)CRDT。它允许我们存储一个值，并通过保留这两个值来解析并发设置的值。

要在CRDT中设置值，您需要提供上下文(即使是初始值)，获取上下文的唯一方法是首先从CRDT读取。

从CRDT读取任何状态都将生成ReadCtx。要从ReadCtx访问值，请使用.val字段。从上面的示例中，我们可以看到寄存器当前没有存储任何值(空VEC)。

现在，要对注册表进行编辑，您将为要进行的编辑派生相应的上下文，对于删除数据的编辑，您将需要使用.duced_rm_ctx()添加所需的新数据。其中<；act_id>；是CRDT上正在操作的任何内容的唯一标识符。

让add_ctx=read_ctx。派生_添加_ctx(123)；设rm_ctx=read_ctx。派生_rm_ctx()；reg.。设置("；值"；。To_string()，add_ctx)；//我们使用add conttreg设置寄存器的值。清除(Rm_Ctx)；//我们使用(陈旧的)RM上下文ASSERT_eq！(注册表。Read().val，vec！["；value"；。To_string()])//并且我们看到MVReg：：Clear()没有删除新值。

现在您可能会想，为什么我们在清除寄存器之后会有一个"；值。"；值"；字符串添加了一个AddContext，其中包含一个标记，表示存在来自参与者123的新信息。清除操作使用从读取派生的RmCtx，其中我们没有来自参与者123的此信息，仅删除在读取时看到的从中派生RmCtx的数据。

您可能落入的另一个陷阱是重用从CRDT的一个部分派生的上下文来编辑CRDT的另一个部分。丢失数据的步骤：

现在您正在使用从另一个密钥派生的RmCtx，此RmCtx应该只用于删除它读取的相同数据。AddCtx也是如此，它应该只用于覆盖派生它的数据。

如果您想了解CRDT是如何工作的，我建议您先从HASTRMENGIRLS报告中的自述文件开始。然后，根据您是喜欢阅读论文还是直接跳到源代码示例，查看Riak DT源代码或全面研究CRDT。