Ditto

Ditto 是一个用于使用 CRDT（无冲突复制数据类型）的库。CRDT 是可以在多个站点之间复制、并发编辑且合并时不会产生冲突的数据结构。Ditto 提供了多种常用数据类型

• Register<T>: 一个可替换的值
• Counter: 一个 i64 值，可以递增
• Set<T>: 一个类似于 HashSet 的唯一值集合
• Map<K, V>: 一个类似于 HashMap 的键值对集合
• List<T>: 一个类似于 Vec 的有序元素序列
• Text: 一个类似于 String 的可变文本容器
• Json: 一个 JSON 值

Ditto 的目标是快速、正确且易于使用。如果您有任何问题、建议或其他反馈，请随时提交 issue、pull request 或直接联系 Ditto 开发者。

示例

extern crate ditto;
extern crate serde_json;
use ditto::List;

fn main() {
    // Create a List CRDT. The site that creates the CRDT
    // is automatically assigned id 1.
    let mut list1 = List::from(vec![100,200,300]);

    // Send the list's state over a network to a second site with id 2.
    let encoded_state = serde_json::to_string(&list1.state()).unwrap();
    let decoded_state = serde_json::from_str(&encoded_state).unwrap();
    let mut list2 = List::from_state(decoded_state, Some(2)).unwrap();

    // Edit the list concurrently at both the first and second site.
    // Whenever you edit a CRDT, you receive an op that can be sent
    // to other sites.
    let op1 = list1.insert(0, 400).unwrap();
    let op2 = list2.remove(0).1.unwrap();

    // Each site sends its op to the other site for execution.
    // The encoding and decoding has been left out for brevity.
    list1.execute_op(op2);
    list2.execute_op(op1);

    // Now both sites have the same value:
    assert_eq!(list1.state(), list2.state());
    assert_eq!(list1.local_value(), vec![400, 200, 300]);
}

您可以在 crate 仓库的示例和测试目录中找到更多示例。

使用 CRDT

Ditto CRDT 被设计成尽可能模仿标准数据类型 API。您可以插入和删除列表和映射元素、替换文本元素等。每次编辑都会生成一个操作，可以发送到其他站点执行。当您执行从其他站点发送的操作时，您将收到一个 LocalOp，它显示了 CRDT 值的确切变化。

用户需要关注 CRDT 的两个复杂性是

• 如何将操作/状态从一个站点发送到另一个站点
• 如何为每个站点分配一个站点 ID。

Ditto 不包含网络层。但是，您可以在下面的文档中找到有关发送更改和分配站点 ID 的信息。

发送操作和状态

CRDT 和操作可以使用 Serde 序列化。序列化已针对 serde_json（JSON）和 rmp-serde（MsgPack）进行测试，但也可能与其他格式一起使用。

操作必须按照它们生成的顺序发送。也就是说，如果网站先执行编辑A，然后执行编辑B，它必须在发送操作B之前发送操作A。状态可以按任何顺序发送。

同样，操作必须通过一个保证有序交付的网络发送。TCP符合这一要求，因此任何位于TCP之上（HTTP、WebSockets、SMTP、XMPP等）的协议都将作为基于操作的复制的传输层。状态可以通过不保证有序交付的协议发送。

一般来说，在复制CRDT状态时，你应该发送其状态结构体，而不是CRDT结构体，因为CRDT结构体包含站点ID。例如，要复制一个Json CRDT，你应该发送序列化的JsonState，这可以通过调用json_crdt.state()来实现。

分配站点ID

CRDT可以分布到多个站点。站点只是一个用于“客户端”的复杂分布式系统术语。每个希望编辑CRDT的站点都必须有一个唯一的u32标识符。

创建CRDT的站点将自动分配ID 1。你负责分配所有其他站点；Ditto不会为你做这件事。

以下是分配站点标识符的一些策略

• 重用现有的站点标识符（例如，数字客户端ID）
• 使用中央服务器按CRDT分配站点ID
• 使用Raft或Paxos等共识算法确定新站点的ID

站点ID可以延迟分配。如果一个站点只需要对CRDT进行读取访问，它不需要站点ID。如果一个没有ID的站点编辑CRDT，CRDT将在本地更新，但操作将被缓存并无法提供给用户。当站点收到ID时，该ID将回溯应用于站点的编辑，并且缓存的操作将被返回以通过网络发送。

我需要一个集中式服务器来维护一致性吗？

CRDT不需要集中式服务器来确保最终一致性；你可以在点对点协议、客户端-服务器应用程序、联邦服务或任何其他环境中使用它们。但是，你需要一种方法来分配唯一的站点标识符，如分配站点ID部分所述。集中式服务器是其中一种方法，但不是唯一的方法。

服务器还可以作为不可用客户端的操作缓存。如果你在一个站点经常离线的应用程序中使用CRDT（例如，手机应用程序），你可以使用服务器存储操作和状态更改，直到它们被所有站点接收。

重复操作

Ditto CRDT是幂等的——执行操作两次没有影响。只要站点的操作按照它们生成的顺序执行，CRDT就能保持一致性。

发送操作与发送状态

通常，在站点之间发送更改最紧凑的方式是发送一个操作。操作只是用于“更改”的复杂分布式系统术语。每次你本地编辑CRDT时，你都会生成一个可以发送到其他站点并执行的操作。

然而，有时发送整个CRDT状态（例如，如果你一次发送100个或1000个编辑）可能更快更紧凑。如果你不能保证按顺序交付操作，你应该仅通过状态复制。

其他注意事项

收集CRDTs的体积通常比它们的本地等效物要大，因为每个元素都必须有一个唯一的ID。当存储非常小的值的集合时，开销最为显著——一个List<u8>将比一个Vec<u8>大得多。如果集合本身是不可变的，您可以通过将List<T>或Map<K,V>切换到Register<Vec<T>>或Register<Map<K,V>>来显著减少开销。

许可

Ditto可使用以下任一许可：

• Apache License，版本2.0
• MIT许可

任选其一。

贡献

除非您明确说明，否则根据Apache-2.0许可定义，您有意提交以包含在Ditto中的任何贡献，将按上述方式双许可，不附加任何额外条款或条件。