Lib.rs

›
#json #crdt #data #command-line #update #replica #melda

app libmelda-tools

Melda 的命令行工具，用于 Delta-State JSON CRDT

所有者 Amos Brocco。

3 个版本

0.1.4 2022年6月21日
0.1.2 2022年6月21日
0.1.1 2022年6月13日

#5 in #replica

GPL-3.0 许可证

36KB
370 代码行（不含注释）

什么是 Melda 工具？

Melda 工具是与 libmelda 一起使用的命令行工具。

什么是 Melda？

Melda 是一种 Delta-State JSON CRDT。CRDT（Conflict-free Replicated Data Types，无冲突复制数据类型）是可以在网络中的多台计算机间复制（复制）的数据结构。每个副本都可以独立并发地更新，而不需要中央协调或同步。每个副本上做出的更新可以在任何时候合并。

存在不同类型的 CRDT：基于操作的 CRDT（在副本之间生成和交换更新操作），基于状态的 CRDT（交换和合并每个副本的全状态）和 Delta-State CRDT，如 Melda（仅交换数据类型版本或状态之间的差异）。

Melda 支持原生 JSON 数据格式，并提供了一种同步对任意 JSON 文档所做的更改的方法。

如何使用 Melda 工具？

您需要克隆此仓库，然后编译 CLI 工具的可执行文件

git clone https://github.com/slashdotted/libmelda-tools
cd libmelda-tools
cargo build

为了理解如何使用 CLI 工具使用 Melda，我们考虑以下情况，其中由虚构的活动规划软件（即待办事项管理软件）使用的共享 JSON 文档由多方并发更新。提供的 JSON 由应用程序生成（通过序列化其数据模型）。我们假设用户 Alice 创建了共享 JSON 文档的第一个版本，该版本将命名为 v1_alice.json。这个第一个版本包含以下数据

{
	"software" : "MeldaDo",
	"version" : "1.0.0",
	"items♭" : []
}

root 对象包含三个字段：一个定义应用程序名称的 software 字段，一个设置软件版本的 version 字段，以及一个映射到 JSON 对象数组（每个待办事项一个）的 items♭ 字段。由于这是第一个版本，因此项目数组为空。♭ 后缀用于让 Melda 以顺序提取所包含的 JSON 对象，以跟踪它们的单独更改。

为了更好地理解 展开 过程的目的，考虑 Melda 如何处理以下两个 JSON 文件。第一个名为 v2_alice_noflat.json 的文件包含

{
	"software" : "MeldaDo",
	"version" : "1.0.0",
	"items" : [
	   {"_id" : "alice_todo_01", "title" : "Buy milk", "description" : "Go to the grocery store"}
	]
}

在这种情况下，Melda 将保持根对象不变，而一个用户对 items 数组所做的更改不会与其他用户的更改合并。例如，如果有两个用户在自己的副本上向数组添加一个元素，然后合并这些副本，则只能看到一个元素。相反，考虑现在文档的另一个版本，名为 v2_alice.json，它包含

{
	"software" : "MeldaDo",
	"version" : "1.0.0",
	"items♭" : [
	   {"_id" : "alice_todo_01", "title" : "Buy milk", "description" : "Go to the grocery store"}
	]
}

在这种情况下，items♭数组中的对象将被单独提取和跟踪。特别是，上述文档产生了两个JSON对象

{
	"_id" : "√",
	"software" : "MeldaDo",
	"version" : "1.0.0",
	"items♭" : [
	  "alice_todo_01"
	]
}

以及待办事项本身

{
	"_id" : "alice_todo_01",
	"title" : "Buy milk",
	"description" : "Go to the grocery store"
}

请注意，每个对象都有其自己的唯一标识符存储在_id字段中。如果客户端应用程序没有提供标识符，Melda将自动生成一个。根对象始终由√标识（此标识符不能由客户端应用程序更改）。由于每个items♭数组对象都是单独跟踪的，因此如果用户向数组添加元素，然后与其他用户的副本合并，所有更改都将被保留。

如果项目集合太大，我们可以要求Melda只存储最新修订版与上一个版本之间的差异数组。为此，我们只需在items字段的键前加上Δ字符（希腊大写字母delta）。因此，版本delta_alice.json可能成为

{
	"software" : "MeldaDo",
	"version" : "1.0.0",
	"Δitems♭" : [
	   {"_id" : "alice_todo_01", "title" : "Buy milk", "description" : "Go to the grocery store"}
	]
}

为了简单起见，在以下内容中我们将不使用差异数组。让我们回到我们的示例情况...到目前为止，我们只考虑了一些JSON数据，但我们还没有看到如何与Melda交互以更新数据结构。

适配器

Melda实现了一种模块化设计，其中CRDT的逻辑与数据存储分离。通过使用适配器来实现数据存储（在我们的情况下，delta状态）。Melda已经提供了不同类型的适配器，支持内存存储（MemoryAdapter）、文件系统存储（FilesystemAdapter）和Solid Pods（SolidAdapter）。此外，可以使用元适配器使用Flate2算法压缩数据（Flate2Adapter）：这样的适配器可以与其他适配器组合。

使用Melda Tools，我们可以通过指定路径（例如file://$(pwd)/todolist，其中$(pwd)返回当前目录的绝对路径）来选择一个将数据存储在文件系统上的适配器（在todolist目录中）。如果我们想使用压缩，我们会添加Flate2Adapter，我们会使用file+flate://$(pwd)/todolist。

创建CRDT

为了创建第一个状态或更新CRDT的状态，我们使用update命令。假设第一个版本的文档存储在文件v1.json中，并包含

{ "software" : "MeldaDo", "version" : "1.0.0", "items♭" : []}

Alice可以使用以下命令在todolist目录内创建/更新CRDT

./target/debug/libmelda-tools update -a "Alice" -d "First commit" -j v1.json -t file://$(pwd)/todolist

请注意，我们假设Melda Tools已以调试模式编译，并且可执行文件是./target/debug/libmelda-tools。

对CRDT的更改将提交到磁盘。我们可以传递可选的author（-a选项）和description（-d选项）以及将与更新一起存储的附加信息。

update的结果要么是错误消息，要么是提交的块的标识符。

成功后，在磁盘（在todolist目录中）应该已经创建了以下内容

todolist/
├── 49
│   └── 49ccea4d5797250208edf9bc5d0b89edf23c30a61f5cb3fafb87069f07276a62.delta
└── b4
    └── b4e50e445542c4737f4cfd7a9193ffd3be3794049d361d114a44f36434257cb3.pack

.delta文件被称为delta block，它包含CRDT中每个对象的版本信息，而.pack文件是存储每个对象的实际JSON内容的data pack。每次提交都产生一个新的delta block（具有不同的名称，对应于其内容的哈希摘要）和可能的数据pack（如果产生了新的JSON值）。todolist目录的结构根据其前缀将文件组织到子目录中。

Alice可以使用（再次）使用update方法执行另一个更新。首先，新版本的文件内容存储在v2.json中

{ "software" : "MeldaDo", "version" : "1.0.0", "items♭" : [
       {"_id" : "alice_todo_01", "title" : "Buy milk", "description" : "Go to the grocery store"}
    ]
    }

然后更新CRDT并提交更改

./target/debug/libmelda-tools update -a "Alice" -d "Add buy milk" -j v2.json -t file://$(pwd)/todolist

更改将反映在磁盘上（在相应目录中创建新包和块）

todolist/
├── 2b
│   └── 2b0a463fcba92d5cf7dae531a5c40b67aaa0f45ab351c15613534fb5bba28564.pack
├── 49
│   └── 49ccea4d5797250208edf9bc5d0b89edf23c30a61f5cb3fafb87069f07276a62.delta
├── b4
│   └── b4e50e445542c4737f4cfd7a9193ffd3be3794049d361d114a44f36434257cb3.pack
└── b6
    └── b6297035f06f13186160577099759dea843addcd1fbd05d24da87d9ac071da3b.delta

读取数据

任何时间都可以使用 read 命令将 CRDT 的状态读取回 JSON 文档

./target/debug/libmelda-tools read -s file://$(pwd)/todolist

这将在终端上打印以下内容

{"_id":"√","items♭":[{"_id":"alice_todo_01","description":"Go to the grocery store","title":"Buy milk"}],"software":"MeldaDo","version":"1.0.0"}

Melda 管理的每个对象都将包含具有相应唯一标识符的 _id 字段。

共享数据

现在我们假设 Alice 将 todolist 目录的当前状态与 Bob 分享（她可以简单地压缩内容并通过电子邮件发送压缩文件给 Bob）。我们假设 Bob 将内容保存在 todolist_bob 目录中。Bob 可以进行一些更新（我们假设存储在 v3_bob.json 中）

{ "software" : "MeldaDo", "version" : "1.0.0", "items♭" : [
       {"_id" : "alice_todo_01", "title" : "Buy milk", "description" : "Go to the grocery store"},
       {"_id" : "bob_todo_01", "title" : "Pay bills", "description" : "Withdraw 500 to pay bill"},
       {"_id" : "bob_todo_02", "title" : "Call mom", "description" : "Call mom to schedule dinner"}
    ]
    }

Bob 使用以下命令更新自己的副本

./target/debug/libmelda-tools update -a "Bob" -d "Add some todos" -j v3_bob.json -t file://$(pwd)/todolist_bob

如您所注意到的，Bob 添加了两个新项目。与此同时，Alice 继续在她的副本上工作，通过删除一个项目（alice_todo_01）和添加一个新项目（alice_todo_02）。Alice 使用的文件名为 v3_alice.json，内容如下

{ "software" : "MeldaDo", "version" : "1.0.0", "items♭" : [
        {"_id" : "alice_todo_02", "title" : "Take picture of our dog", "description" : "It must be a nice one"}
     ]
     }

要更新自己的副本，Alice 使用以下命令行

./target/debug/libmelda-tools update -a "Alice" -d "Some more stuff to do" -j v3_alice.json -t file://$(pwd)/todolist

最后，Bob 将自己的副本与 Alice 分享：现在 Alice 只需要将 Bob 收到的目录内容（例如使用 cp -r todolist_bob/ todolist//*）合并到本地目录中。或者，假设 Bob 修改的数据在 Alice 电脑上的 todolist_bob 目录中。要合并更改回 todolist 目录，Alice 可以使用 meld 方法

./target/debug/libmelda-tools meld -t file://$(pwd)/todolist -s file://$(pwd)/todolist_bob

Alice 然后可以使用以下命令读取 CRDT 的新状态

./target/debug/libmelda-tools read -s file://$(pwd)/todolist

终端上打印的结果应该如下

{"_id":"√","items♭":[{"_id":"bob_todo_01","description":"Withdraw 500 to pay bill","title":"Pay bills"},{"_id":"bob_todo_02","description":"Call mom to schedule dinner","title":"Call mom"},{"_id":"alice_todo_02","description":"It must be a nice one","title":"Take picture of our dog"}],"software":"MeldaDo","version":"1.0.0"}

如您所见，Alice 只有一个待办事项，以及 Bob 添加的两个待办事项。

Alice 和 Bob 都可以使用 log 命令查看对其副本所做的更改的历史记录

./target/debug/libmelda-tools log -s file://$(pwd)/todolist

对于 Alice，结果如下

(A) Block: d0d23eeaf013b216a32386e708fb37489743cb2c9c8153082fc8e944a91eedf6
		Information: {"author":"Bob","description":"Add some todos"}
		Packs: ["515ebf5ebd96fe8210945856d09b53fa673434291a598c893db76bed117b243e"]
		Parents: ["460b4dd46257efbb018201d9c1ada3e165174241b8ef9a30f8f0f0b77a551283"]
(A) Block: ec11159e3497a89d1f0cb23db2600239535c70cc35a4f4b5a96e1d561d2bead3
		Information: {"author":"Alice","description":"Some more stuff to do"}
		Packs: ["967e769c2b65c0a30a9aeed1350ed78c46e98073c61a23421e8a7c4b721e61d0"]
		Parents: ["460b4dd46257efbb018201d9c1ada3e165174241b8ef9a30f8f0f0b77a551283"]
(-) Block: 460b4dd46257efbb018201d9c1ada3e165174241b8ef9a30f8f0f0b77a551283
		Information: {"author":"Alice","description":"Add buy milk"}
		Packs: ["2b0a463fcba92d5cf7dae531a5c40b67aaa0f45ab351c15613534fb5bba28564"]
		Parents: ["49ccea4d5797250208edf9bc5d0b89edf23c30a61f5cb3fafb87069f07276a62"]
(O) Block: 49ccea4d5797250208edf9bc5d0b89edf23c30a61f5cb3fafb87069f07276a62
		Information: {"author":"Alice","description":"First commit"}
		Packs: ["b4e50e445542c4737f4cfd7a9193ffd3be3794049d361d114a44f36434257cb3"]

Delta 块列表包含 origin 块（(O)）和 anchor 块（(A)）。Origin 块是创建的第一个：在我们的场景中只有一个 origin，因为 CRDT 只在单个副本（由 Alice）上创建。然而有两个 anchor 块，分别是 d0d23eeaf013b216a32386e708fb37489743cb2c9c8153082fc8e944a91eedf6（由 Bob 创建）和 ec11159e3497a89d1f0cb23db2600239535c70cc35a4f4b5a96e1d561d2bead3（由 Alice 创建）。这是由于 Alice 执行的合并/meld 操作。多个 anchor 将由下一个提交引用。

Alice 和 Bob 的并发修改也导致冲突。默认情况下，这会自动隐藏，因为 Melda 可以无问题地处理这种情况。但我们可以使用 conflicts 命令显示冲突信息

./target/debug/libmelda-tools conflicts -s file://$(pwd)/todolist

这将显示根文档（√）有冲突，并显示冲突版本（带有 🏆 的是 Melda 当前选择的 winner 版本，冲突以 🗲 显示）

√:
	🏆 3-8f147f811da66dccc212b3147a185c7c68d365e02ae84614e6533b7857d4744a_6258b20: {"items♭":["alice_todo_01","bob_todo_01","bob_todo_02","alice_todo_02"],"software":"MeldaDo","version":"1.0.0"}
	🗲 3-5bf6651423be2df90bf3a7250a5b8d7e457da397ab7a31bd24f96c099c183711_6258b20: {"items♭":["alice_todo_02","alice_todo_01","bob_todo_01","bob_todo_02"],"software":"MeldaDo","version":"1.0.0"}

后续更新将始终考虑 winner。但我们可以使用 resolve 命令解决冲突（并使其从冲突视图中消失）

./target/debug/libmelda-tools resolve -t file://$(pwd)/todolist

此命令默认使用当前 winner 解决所有对象的冲突。可以选择不同的策略来提升不同的 winner。conflicts 命令将确认没有冲突。

出版物

2022

Amos Brocco "Melda: A General Purpose Delta State JSON CRDT". 9th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC'22). April 2022. (已接受)

2021

Amos Brocco "Delta-State JSON CRDT: Putting Collaboration on Solid Ground". (简短公告). 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2021). November 2021.

许可证

(c)2021-2022 Amos Brocco, GPL v3（目前如此...但我会评估在未来改变许可证 - 像BSD3/MIT/...这样的许可证）

依赖关系

~15MB
~286K SLoC