Loro 1.0 发布 - 可帮你同步文档和版本管理的高性能 CRDTs Lib
Loro 是一个 Conflict-free Replicated Data Type (CRDT) 库,它可以帮助开发者为他们的应用实现实时协作和版本控制。你可以使用 Loro 来构建本地优先软件. Loro 1.0 有着稳定的数据格式、优异的性能还有各类实用的能力支持。Loro 当前支持 Rust、JS(wasm) 和 Swift 语言。
Loro 1.0 的特性
高性能的 CRDTs
一个高性能、通用的 CRDTs 可以显著地减少数据同步的复杂度,并且是本地优先软件的核心组件。
然而,大型 CRDT 文档可能会面临加载速度和内存消耗方面的挑战,尤其是在处理具有大量编辑历史的文档时。Loro 1.0 通过一种新的存储格式解决了这一挑战,将加载速度提高了 10 倍。在使用 Loro 和真实世界编辑数据进行的基准测试,我们将包含数百万次操作的文档的加载时间从 16 毫秒缩短到了 1 毫秒。当使用 shallow snapshot 格式(下文会介绍)时,时间可以进一步缩短到 0.37 毫秒。因此,Loro 不会成为处理如此大文档的应用程序的瓶颈。它扩展了 CRDT 的潜在可能,使其适用于更广泛的应用程序。
丰富的 CRDT 类型
Loro 现在支持与 Peritext 类似的富文本 CRDT,这增强了富文本(带有格式和样式的文本)的合并结果,以更好地满足用户期望。我们的文本/列表 CRDT 基于 Fugue 算法,它可以防止在合并并发编辑时出现交错问题。例如,当同时插入“123”和“Hi”时,它可以避免“1H2i3”之类的意外合并。
Loro 还支持:
Movable List:支持 set、insert、delete 和 move 操作。该算法确保在合并并发移动后,每个元素只占据一个位置。
Map:类似于 JavaScript 对象。
Movable Tree:用于模拟可能需要移动的文件目录、大纲和其他层次结构。它确保在合并并发移动操作后树中不存在循环依赖关系。
Loro 还支持类型之间的嵌套,因此您可以通过它们对 JSON 文档进行建模编辑:
您可以在这里找到此博客中的所有代码示例
import {
LoroDoc,
LoroList,
LoroMap,
LoroText,
} from "npm:loro-crdt@1.0.0-beta.2";
// Create a JSON structure of
interface 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());
版本控制
与 Git 一样,Loro 保存了完整编辑历史的有向无环图 (DAG)。在 Loro 中,DAG 用于表示编辑之间的依赖关系,类似于 Git 表示提交历史的方式。
Loro 支持允许用户在不同版本之间切换、分叉新分支、在新分支上编辑和合并分支的原语。
基于这些操作原语,应用程序可以构建各种类似 Git 的功能:
可以合并多个版本,而无需手动解决冲突
可以将当前分支的更新 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 edit
doc.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!"
您还可以使用 doc.fork()
在当前版本上创建单独的文档。它独立于当前文档,像 git fork 一样工作:
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!"
Loro 中版本控制的当前限制
应用层仍需要大量代码来为用户提供更完整的版本控制功能,例如:
存储和同步版本标签和分支
展示 diff 视图
处理 rebase 和 merge 交互
...
这些问题不适合在当前的 Loro CRDTs 库中解决,因为对架构和环境的过多假设会使其难以在其他场景中使用,因此我们不会内置这些部分。但它们都可以通过额外的库来解决。
发挥 Eg-walker 的潜力
Event Graph Walker (Eg-walker) 是一个开创性的协作算法,它结合了 Operational Transformation (OT) 和 CRDT 的优势,这两种算法都广泛用于实时协作。
虽然 OT 是集中式的,而 CRDT 是分散式的,但 OT 一直都在降低文档开销方面具有优势。CRDT 最初的开销较高,但最近的优化已显著缩小了这一差距,使 CRDT 的竞争力越来越强。Eg-walker 结合利用了这两种方案各自的优势。
Loro 不仅将 Eg-walker 的想法用于 Text 和 List CRDT,而且 Loro 的整体架构也受到了 Eg-walker 的极大启发。因此,Loro 在算法方面与 Eg-walker 非常相似。
在实现细节方面,Loro 与论文中描述的 Eg-walker 有所不同。因此说 Loro 实现了 Eg-walker 可能会引起争议。 例如,Loro 支持除文本之外的其他类型,并且在 Loro 中,我们将每个字符的 ID 存 储在文档状态中(但不存储墓碑),等等。 但它实现了 Eg-walker 的理念,即遍历图表以构建临时 CRDT 来解决冲突。而且,与 Eg-walker 一样,Loro 不需要将 CRDT 结构保存在内存中来编辑文档。
Eg-walker 论文于 2023 年 9 月发布。在正式发表之前,Joseph Gentle 在 Diamond-Type 存储库中分享了该算法的初始版本。受到该设计的启发,Loro 在两年前实现了类似的算法。该算法的简要介绍可在此处找到。
Eg-walker 的特性包括:
它本身符合 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 的功能与论文中描述的 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 的新功能
在过去的一个季度中,我们进行了重大的架构调整,以使 Loro 能够进一步利用 Eg-walker 算法的优势。以下是我们取得的成果
Shallow Snapshot
默认情况下,Loro 会像 Git 一样存储文档的完整编辑历史,因为 Eg-walker 算法在合并远程编辑时需要加载与其并行的编辑以及与最小共同祖先的编辑。Shallow Snapshot 类似于 Git 的 Shallow Clone,可以删除用户不需要的旧历史操作,大大减少文档大小并提高文档导入和导出速度。这允许您冷存储太旧的文档历史记录,主要使用shallow 文档进行协作。以下是示例用法:
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); // 5421
console.log(shallowSnapshotBytes.length); // 869
详细实现原理可以查看 Shallow Snapshot。
优化了文档格式
与已经具有快速导入速度的 v0.16 版本相比,Loro 1.0 版本的文档导入速度提高了 10 到 100 倍。它能够在不到一帧的时间内加载包含数百万次操作的大型文本文档。
这是因为我们引入了一种新的快照格式。当通过此快照格式初始化 LoroDoc
时,我们不会解析相应的文档状态和历史信息,直到用户真正需要这些信息。
Loro 在导入 updates / snapshot 之前会执行完整性检查,我们在每次导出时附加一个 4 字节 xxhash32
校验和,以防止数据损坏。虽然这不能防止恶意篡改,但它可以快速有效地检测由传输错误或存储故障引起的问题。
我们进行完整性检查的主要动机是以相对较低的成本避免由数据错误引起的错误。由于 Loro 使用自己的二进制编码格式,这与 JSON 等用户可理解的文档格式不同,因此如果发生数据错误,排除故障将极其困难。
在 Loro 1.0 的 snapshot 格式中,在没有压缩算法的情况下,其文档大小是旧版本(以及其他主流 CRDT)的两倍。这个额外的大小主要来自于在 1.0 快照格式中对历史操作 + 文档状态进行编码,而不在两者之间重用存储的数据,而在旧版本中我们使用历史操作的顺序来编码文档的当前状态(旧版本的编码从 Automerge 编码的 Value Column 中学习)。
用两倍的文档大小换取十倍的导入速度是值得的,因为导入速度会影响许多方面的性能,而 CRDT 文档的导入速度在大型文档上(> 16ms)通常会被用户注意到。这也为将来的更多优化留下了可能性。
这是否会影响数据传输的效率?
这取决于场景:
对于实时协作:
我们不需要连续传输整个快照。
我们只需要文档更新(其他对等点缺少的操作)。
不使用上面提到的快照格式,因此传输量保持不变。
当需要从远程加载文档时:
如果使用完整快照,它将是以前的两倍。
但是,您可以选择:
使用浅快照格式。
为其他对等点导出一组完整的更新,允许他们计算最新的文档状态。
对于本地存储:
用户通常对本地存储成本不太敏感。
快照格式可用于本地持久性,而不会产生重大影响。
受到 Key-Value Database 设计的启发,我们还将文档状态和历史记录的存储分为了块,每个块大约 4KB 大小,这样当用户真正需要某段历史记录时,我们只需要解压读取这 4KB 的内容,而不需要解析整个文档。这导致了导入速度的质的提升,而且由于序列化格式可以更好地压缩历史记录和状态,内存占用也比以前更低。
延迟加载优化利用了 Eg-walker 的特性,“它不需要一直在内存中保留完整的 CRDT 数据结构,只需要在发生并行编辑时访问历史操作”。
Benchmarks
以下所有基准测试结果均在 MacBook Pro M1 2020 上进行
以下是 Loro 1.0.0-beta.1 版和 0.16.12 版快照导入和导出速度的比较。基准测试基于现实世界中的文档编辑历史。感谢 latch.bio 分享文档数据。基准测试代码可在此处获取。该文档包含 1,659,541 个操作。
在 Loro 中,snapshot 会存储文档历史记录及其当前状态。shallow snapshot 格式类似于 Git 的 shallow clone,可以排除历史记录。在下面的基准测试中,shallow snasphot 的深度为 1(仅保留最近的操作历史记录,其他历史操作将被删除)
task | Old Snapshot Format on 0.16.12 | New Snapshot Format | Shallow Snapshot Format |
---|---|---|---|
Import | 17.3ms +- 0.0298ms | 1.15ms +- 0.0101ms (15x) | 375µs +- 8.47µs (47x) |
Import+GetAllValues | 17.4ms +- 0.0437ms | 1.19ms +- 0.0122ms (14.5x) | 375µs +- 1.60µs (46x) |
Import+GetAllValues+Edit | 17.5ms +- 0.0263ms | 1.21ms +- 0.0120ms (14.5x) | 375µs +- 1.40µs (46.5x) |
Import+GetAllValues+Edit+Export | 32.4ms +- 0.0560ms | 5.46ms +- 0.0772ms (6x) | 844µs +- 5.12µs (38.5x) |
以下是本次基准测试的要点:
Shallow Snapshot 的深度为 1,这意味着它仅包含文档状态和单个历史操作,这就是它速度明显更快的原因
GetAllValue 指的是调用
doc.get_deep_value()
(在 JS 中为doc.toJSON()
)。它加载文档的完整状态并获取相应的类似 JSON 的结构。这表示用户加载文档之前在 CRDT 解析上花费的时间。Edit 是指进行本地修改。如您所见,它对所用时间影响不大,因为 Loro 不需要为本地操作加载完整的 CRDT 数据结构。
Export 是指再次导出完整的文档数据。我们希望将来进一步减少此处花费的时间,因为我们可以继续重用导入中未修改的块的编码。
以下显示了在将 Automerge Paper 的编辑历史记录应用 100 次后对文档的性能。您可以在此处重现结果。该文档包含:
18,231,500 个单字符插入操作
7,746,300 个单字符删除操作
总共 25,977,800 个操作
最终文档中有 10,485,200 个字符
Snapshot Type | Size (bytes) |
---|---|
Old snapshot | 27,347,374 |
New snapshot | 23,433,380 |
Shallow Snapshot | 4,388,215 |
新的 Snapshot 数据较小,因为它在内部编码时对每个块进行了额外的简单压缩
task | Old Snapshot | New Snapshot | Shallow Snapshot |
---|---|---|---|
Parse | 538ms +- 3.23ms | 17.9ms +- 48.5µs (30x) | 14.4ms +- 114µs (37x) |
Parse+ToString | 568ms +- 1.78ms | 20.2ms +- 57.2µs (28x) | 16.8ms +- 81.4µs (34x) |
Parse+ToString+Edit | 561ms +- 940µs | 119ms +- 180µs (4.5x) | 113ms +- 185µs (5x) |
Parse+ToString+Edit+Export | 1460ms +- 22.9ms | 251ms +- 1.60ms (6x) | 206ms +- 360µs (7x) |
Loro 的未来计划
Loro 版本控制器
Loro 在单个文档上的表现现在足以满足大多数文档的实时协作和版本管理需求。因此,我们的下一步将是探索跨文档集合的实时协作和版本控制。
我们相信 CRDT 可以为所有人和所有事物创建一个 Git:
它适用于所有人,因为通过利用 CRDT 的强大功能,我们可以让版本控制更容易理解和供普通人使用。
它(几乎)适用于所有事物,因为 Loro 提供了一组丰富的数据同步类型。我们不再局限于同步纯文本数据,而是可以解决 JSON 类模式的语义自动合并,这可以满足大多数创意工具和协作工具的需求。
我们创建了一个 Loro 版本控制的演示,它基于我们带有版本信息的子文档实现(在应用层实现)。它可以导入整个 React 存储库(约 20,000 个提交,数千个协作者),并支持在这些存储库上进行实时协作。但是,如何更好地管理版本并与 Git 无缝集成仍需要探索。
在合并大量并发编辑时,CRDT 可以自动合并更改,但结果可能并不总是符合预期。幸运的是,Loro 存储了完整的编辑历史记录。这使我们能够在需要时在应用层提供类似 Git 的手动冲突解决方案。
在这些情况下,Loro CRDT 仍有很大的优化空间。目前,Loro CRDT 库不涉及网络或磁盘 I/O,这增强了它的易用性,但也限制了它的功能和潜在的优化。例如,虽然我们已经实现了块级存储,但文档仍然以整体二进制的形式导入和导出。添加 I/O 功能以选择地加载/保存特定块将实现更加显著的性能优化。
结论
Loro 1.0 具有出色的性能改进、丰富的 CRDT 类型和高级版本控制功能。被优化过的文档格式在导入速度和内存使用方面有着巨大的进步。
现在 Loro CRDT 已经稳定,Loro 之后能够开发更好的生态系统。很高兴看到它被应用于各种场景。如果您有兴趣使用 Loro,欢迎加入社区进行讨论。
想要尽早体验我们即将推出的使用 Loro 构建的本地优先应用程序吗?
填写我们的调研问卷,成为第一批试用者。