社区来稿丨Loro 1.0 发布：可帮你同步文档和版本管理的高性能 CRDTs Lib

Loro 1.0 的特性

高性能的 CRDTs

丰富的 CRDT 类型

• Movable List：支持 set、insert、delete 和 move 操作。该算法确保在合并并发移动后，每个元素只占据一个位置。

• Map：类似于 JavaScript 对象。

• Movable Tree（https://loro.dev/blog/movable-tree）：用于模拟可能需要移动的文件目录、大纲和其他层次结构。它确保在合并并发移动操作后树中不存在循环依赖关系。
  
  

Loro 还支持类型之间的嵌套，因此您可以通过它们对 JSON 文档进行建模编辑：

您可以在这里（https://github.com/zxch3n/loro-blog-examples）找到此博客中的所有代码示

 

  

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

  
  
import {     LoroDoc,     LoroList,     LoroMap,     LoroText,} from "npm:loro-crdt@1.0.0-beta.2"; 
// Create a JSON structure ofinterface JsonStructure {    users: LoroList<        LoroMap<{            name: string;             age: number;         }>     >;     notes: LoroList<LoroText>;} 
const doc = new LoroDoc<JsonStructure>();const users = doc.getList("users");const user = users.insertContainer(0, new LoroMap());user.set("name", "Alice");user.set("age", 20);const notes = doc.getList("notes");const firstNote = notes.insertContainer(0, new LoroText());firstNote.insert(0, "Hello, world!"); // { users: [ { age: 20, name: "Alice" } ], notes: [ "Hello, world!" ] }console.log(doc.toJSON());
 
 

  

 

版本控制

• 可以合并多个版本，而无需手动解决冲突
• 可以将当前分支的更新 rebase / squash 到目标分支（WIP）
  
  
  

import { LoroDoc } from "npm:loro-crdt@1.0.0-beta.2";
const doc = new LoroDoc();doc.setPeerId("0");doc.getText("text").insert(0, "Hello, world!");doc.checkout([{ peer: "0", counter: 1 }]);console.log(doc.getText("text").toString()); // "He"doc.checkout([{ peer: "0", counter: 5 }]);console.log(doc.getText("text").toString()); // "Hello,"doc.checkoutToLatest();console.log(doc.getText("text").toString()); // "Hello, world!"
// Simulate a concurrent editdoc.checkout([{ peer: "0", counter: 5 }]);doc.setDetachedEditing(true);doc.setPeerId("1");doc.getText("text").insert(6, " Alice!");// ┌───────────────┐     ┌───────────────┐// │    Hello,     │◀─┬──│     world!    │// └───────────────┘  │  └───────────────┘//                    │//                    │  ┌───────────────┐//                    └──│     Alice!    │//                       └───────────────┘doc.checkoutToLatest();console.log(doc.getText("text").toString()); // "Hello, world! Alice!"

import { LoroDoc } from "npm:loro-crdt@1.0.0-beta.4";
const doc = new LoroDoc();doc.setPeerId("0");doc.getText("text").insert(0, "Hello, world!");doc.checkout([{ peer: "0", counter: 5 }]);const newDoc = doc.fork();newDoc.setPeerId("1");newDoc.getText("text").insert(6, " Alice!");// ┌───────────────┐     ┌───────────────┐// │    Hello,     │◀─┬──│     world!    │// └───────────────┘  │  └───────────────┘//                    │//                    │  ┌───────────────┐//                    └──│     Alice!    │//                       └───────────────┘doc.import(newDoc.export({ mode: "update" }));doc.checkoutToLatest();console.log(doc.getText("text").toString()); // "Hello, world! Alice!"

• 存储和同步版本标签和分支

• 展示 diff 视图

• 处理 rebase 和 merge 交互

• ...

发挥 Eg-walker的潜力（https://arxiv.org/abs/2409.14252）

‍‍‍

在实现细节方面，Loro 与论文中描述的 Eg-walker 有所不同。因此说 Loro 实现了  Eg-walker 可能会引起争议。例如，Loro 支持除文本之外的其他类型，并且在 Loro 中，我们将每个字符的 ID 存 储在文档状态中（但不存储墓碑），等等。但它实现了 Eg-walker 的理念，即遍历图表以构建临时 CRDT 来解决冲突。而且，与 Eg-walker 一样，Loro 不需要将 CRDT 结构保存在内存中来编辑文档。

• 它本身符合 CRDT 的定义，因此具有 CRDT 的强最终一致性特性，可用于分布式环境

• 本地操作速度快：与之前的 CRDT 相比，它处理操作的速度极快，因为它不需要基于 CRDT 数据结构生成相应的操作

• 远程操作合并速度快：OT 合并远程操作的复杂度为 O(n^2)，而 Eg-walker 与主流 CRDT 一样，为 O(nlogn)，仅在极少数最坏情况下达到 O(n^2)。这意味着当并发操作数达到 10,000 时，用户将明显感受到 OT 的延迟，而 CRDT 可以轻松处理。并且在大多数真实场景基准测试中，它比其他 CRDT 更快。

• 内存占用更低：由于不需要在内存中持久存储 CRDT 结构，因此其内存占用比一般的 CRDT 更低

• 导入速度更快：CRDT 文档通常需要很长时间才能加载，因为它们需要解析相应的 CRDT 结构或操作来构建 CRDT 数据结构。如果没有这些结构，它们就无法继续后续编辑，从而导致导入时间过长。eg-walker 与 OT 算法一样，只需要当前文档状态，不需要构建这些额外的结构，即可让用户直接开始编辑文档，从而实现更快的导入速度

Loro 和 Eg-walker 的区别

• 在本地操作和导入更新的性能特征方面，Loro 和 Eg-walker 相似。

• Loro 除了支持文本之外还支持多种数据类型，例如 Map、List、Movable List、Tree、Counter 等。有些 CRDT 类型不容易直接与 Eg-walker 结合，因此我们需要在 Loro 中进行额外的适配和调整。

• Loro 的文档状态具有额外的元数据，包括每个字符的ID。此元数据用于支持光标同步等功能。文本上的ID可以为评论等功能提供稳定的位置信息表达。

• 在 Eg-walker 论文中描述的算法中，用户 A 和 B 可以从同一份纯文本文档初始化 CRDT 文档并开始协作，而无需任何历史信息。而且，形成这两个纯文本文档的历史可以不同。然而，在 Loro 中，必须确保 A 和 B 协作的文档的历史相同。

• 我们的文本不仅支持纯文本，还支持富文本，其中包括粗体、斜体和字体样式等格式化属性。这使得我们的文本数据格式不同于纯文本，无法直接使用纯文本描述方法进行描述。

• Loro 的设计不仅支持实时协作，还支持版本控制。因此，我们为每个操作提供了额外的数据结构和信息，以便更快地切换版本。
  
  

Loro 的新功能

Shallow Snapshot

import { LoroDoc } from "npm:loro-crdt@1.0.0-beta.2";
const doc = new LoroDoc();for (let i = 0; i < 10_000; i++) {    doc.getText("text").insert(0, "Hello, world!");}const snapshotBytes = doc.export({ mode: "snapshot" });const shallowSnapshotBytes = doc.export({    mode: "shallow-snapshot",    frontiers: doc.frontiers(),});
console.log(snapshotBytes.length); // 5421console.log(shallowSnapshotBytes.length); // 869

优化了文档格式

这是否会影响数据传输的效率？

1. 对于实时协作：

• 我们不需要连续传输整个快照。
• 我们只需要文档更新（其他对等点缺少的操作）。

• 不使用上面提到的快照格式，因此传输量保持不变。

2. 当需要从远程加载文档时：

• 如果使用完整快照，它将是以前的两倍。
• 但是，您可以选择：
1. 使用浅快照格式。

2. 为其他对等点导出一组完整的更新，允许他们计算最新的文档状态。

3. 对于本地存储：

• 用户通常对本地存储成本不太敏感。
• 快照格式可用于本地持久性，而不会产生重大影响。

Benchmarks

以下所有基准测试结果均在 MacBook Pro M1 2020 上进行

在 Loro 中，snapshot 会存储文档历史记录及其当前状态。shallow snapshot 格式类似于 Git 的 shallow clone，可以排除历史记录。在下面的基准测试中，shallow snasphot 的深度为 1（仅保留最近的操作历史记录，其他历史操作将被删除）

• Shallow Snapshot 的深度为 1，这意味着它仅包含文档状态和单个历史操作，这就是它速度明显更快的原因

• GetAllValue 指的是调用 doc.get_deep_value()（在 JS 中为 doc.toJSON()）。它加载文档的完整状态并获取相应的类似 JSON 的结构。这表示用户加载文档之前在 CRDT 解析上花费的时间。

• Edit 是指进行本地修改。如您所见，它对所用时间影响不大，因为 Loro 不需要为本地操作加载完整的 CRDT 数据结构。

• Export 是指再次导出完整的文档数据。我们希望将来进一步减少此处花费的时间，因为我们可以继续重用导入中未修改的块的编码。

• 18,231,500 个单字符插入操作

• 7,746,300 个单字符删除操作

• 总共 25,977,800 个操作

• 最终文档中有 10,485,200 个字符

• 新的 Snapshot 数据较小，因为它在内部编码时对每个块进行了额外的简单压缩

Loro 的未来计划

Loro 版本控制器

• 它适用于所有人，因为通过利用 CRDT 的强大功能，我们可以让版本控制更容易理解和供普通人使用。

• 它（几乎）适用于所有事物，因为 Loro 提供了一组丰富的数据同步类型。我们不再局限于同步纯文本数据，而是可以解决 JSON 类模式的语义自动合并，这可以满足大多数创意工具和协作工具的需求。

在合并大量并发编辑时，CRDT 可以自动合并更改，但结果可能并不总是符合预期。幸运的是，Loro 存储了完整的编辑历史记录。这使我们能够在需要时在应用层提供类似 Git 的手动冲突解决方案。

结论