Lib.rs

crdts：经过充分测试的混合型CRDT家族。

支持基于状态和操作复制的CRDT家族。

什么是CRDT？

CRDTs是高可用可变状态的解决方案。

CRDT扩展为无冲突复制数据类型（Conflict Free Replicated Data Type），它指的是一种知道如何无冲突合并的结构家族。CRDT有两大子家族：CvRDT和CmRDT。它们在复制方式上有所不同。CvRDT是基于状态的，这意味着你需要将整个CRDT状态通过网络发送到你的对等节点。而CmRDT则通过将所有编辑（称为操作或Op）分发到系统中的每个节点来复制。

在这里，我们将快速了解一下CRDTs，为了清晰和简洁，我们只关注CvRDT（所有概念同样适用于CmRDTs）。CvRDT结构定义了一个merge(a, b)操作，它接受状态a和b，产生一个合并后的状态。一个简单的例子是GSet（仅增长集合），它的合并操作是两个集合的并集。

通过构建一个来理解CRDTs的尝试

CRDTs都是关于部分序的，要将一个结构转换为CRDT，你必须首先定义一个特殊的部分序，该部分序覆盖你的结构的状态空间。你必须小心地做这件事，因为部分序也定义了你的合并行为。例如，让我们看一下类似2元组结构的状态空间，它存储在两个槽中的立方体，它的状态空间看起来是这样的

为了使这个结构成为一个CRDT，我们需要一个满足以下约束的状态空间上的部分序

∀ s ⊆ S where S is your state space  # for any subset of the state space ...
∃ lub s and lub s ∈ S                # .. the least-upper-bound of the set is also in the state space

lub是上确界操作，它接受状态空间的一个子集，并产生一个比子集中的所有状态都大或相等的唯一状态。下面是一个满足约束的部分序

现在假设我们要合并这个结构体的两个实例，实际上我们已经完成了最困难的部分，因为偏序关系告诉我们最终的合并状态将会是什么。

合并(a,b) =lub{a,b}

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

查看这个偏序关系，我们可以推导出CRDT的一些其他性质。

1. merge(a, b)总是导致我们向上或保持不变
2. 由于1. 合并是幂等的，因为前面的状态将低于或等于当前状态，重新合并过时的状态将不会有任何效果。
3. merge(a, b)是自反的，交换的，并且结合的

如何使用这个库

与CRDT交互

与CRDT一起工作可能与你习惯的数据结构有所不同。由于我们可能正在处理其他人正在同时编辑的数据，我们需要确保你的本地编辑只影响你看到的数据。

与CRDT交互的坏方法

例如，如果你清除一个Map，我们希望能够说这个清除操作只会影响你意识到的映射中的条目。如果你没有正确跟踪你编辑的因果历史，你可能会删除你不知道的数据。例如，丢失数据的好方法可能是这样做

1. 你从网络上接收一个Map CRDT。
2. 你读取Map的键值对并将它们显示给用户。
3. 你接收了Map CRDT的更新版本，但用户还没有刷新他们的视图。
4. 用户选择清除Map的值。所以你调用你的CRDT上的Map::clear()。

此时，你可能会清除用户不想清除的数据。为了解决这个问题，我们需要在清除操作中包含一个Causal上下文。这个因果上下文是一个向量时钟（VClock），它存储了用户在决定执行Map::clear()时看到的Map的版本。

与CRDT交互的好方法

让我们看看使用crdts与CRDT交互是什么样子。

1. 首先创建CRDT的一个实例，我们将使用MVReg（多值寄存器）CRDT作为此示例。它允许我们存储一个值，并通过保留两个值来解决并发设置值。

let mut reg = MVReg::new();

2. 要在你的CRDT中设置一个值，你需要提供一个上下文（即使是初始值），唯一获取上下文的方法是首先从CRDT中读取。

let read_ctx = reg.read();
assert_eq!(read_ctx.val, vec![]); // the registers is empty!

3. 从CRDT中读取任何状态都会产生一个ReadCtx。要从ReadCtx访问值，请使用.val字段。从上面的例子中我们可以看到寄存器目前没有存储任何值（空的Vec）。

现在要对 reg 进行编辑，您需要推导出您想要进行编辑的适当上下文。对于删除数据的编辑，您需要使用 .derive_rm_ctx()，对于添加新数据，您需要使用 .derive_add_ctx(<actor_id>)，其中 <actor_id> 是在 CRDT 上进行操作的对象的唯一标识符。

let add_ctx = read_ctx.derive_add_ctx(123);
let rm_ctx = read_ctx.derive_rm_ctx();

reg.set("Value".to_string(), add_ctx);                // We set the value of the register using the Add context
reg.clear(rm_ctx);                                    // We remove using the (stale) Rm context
assert_eq!(reg.read().val, vec!["Value".to_string()]) // and we see that the MVReg::clear() did not remove the new value

您可能想知道为什么我们在清除寄存器后有一个 "Value" 字符串。这个 "Value" 字符串是通过一个包含显示有新信息标记的 AddContext 添加的，该信息来自演员 123。清除操作使用了一个从没有从演员 123 获取这些信息的读取中推导出的 RmCtx，只有从 RmCtx 推导出的读取时的数据被删除。

另一个您可能会陷入的陷阱是将从 CRDT 的一部分推导出的上下文重新用于编辑 CRDT 的另一部分。丢失数据步骤

let read_ctx = map.get(&"key 1".to_string());
map.rm(&"key 2".to_string(), read_ctx.derive_rm_ctx());

现在您使用的是从另一个密钥推导出的 RmCtx，这个 RmCtx 应仅用于删除它读取的相同数据。同样，对于 AddCtx，它应仅用于覆盖它从中推导出的数据。

如果您牢记这些，您将会有愉快的时光 :)

进一步阅读

如果您想了解 CRDT 的工作原理，我建议从 aphyr 的 meangirls 仓库的说明文件开始。之后，根据您是否喜欢阅读论文还是直接跳转到源代码示例，您可以查看 riak dt 源代码或 CRDT 的全面研究。

参考文献

• CRDT 的全面研究

• riak dt - Erlang 中的收敛复制数据类型