你是否好奇过，像 Google Docs 这样的多人协作编辑软件是如何实现实时同步的？这背后蕴藏着复杂的算法和数据结构。Eg-walker 算法，作为一种新型的协同文本编辑算法，巧妙地融合了 OT 和 CRDT 的优点，以更低的内存占用、更快的文件加载速度和更高的合并效率，为多人协作编辑带来了革命性的突破。
你是否也曾抓狂？协同编辑的痛点
想象一下，你和你的团队正在线上协作完成一份重要文档。你奋笔疾书，灵感如泉涌，突然，软件卡顿了！你焦急地等待，进度条却纹丝不动，宝贵的思路也随之消散。好不容易恢复正常，你发现同事的修改与你的冲突，文档变得一团糟，更糟糕的是，软件崩溃了，你几个小时的工作成果付诸东流…...
相信你对这一幕并不陌生。这就是协同编辑软件的痛点：卡顿、冲突、崩溃，这些问题如同挥之不去的梦魇，困扰着无数用户。
现有的协同文本编辑算法主要分为两大类：Operational Transformation (OT) 和 Conflict-free Replicated Data Type (CRDT)。OT 算法虽然速度快，但是合并大量改动时效率低下；CRDT 算法虽然可以处理大量改动，但速度慢且占用大量内存。
有没有一种算法可以兼顾速度和效率呢？
Eg-walker 横空出世：破局者
来自独立研究者 Joseph Gentle 和剑桥大学学者 Martin Kleppmann 的一项最新研究成果为我们带来了新的希望：Eg-walker 算法！
Eg-walker 算法就像一位横空出世的超级运动员，完美融合了 OT 和 CRDT 的优点，实现了令人瞩目的性能提升：
• 兼顾速度与规模: Eg-walker 算法在最佳情况下比现有 CRDT 算法快几个数量级，就像短跑运动员一样敏捷；并且在最坏情况下也只略慢于最快的现有 CRDT 算法，就像马拉松运动员一样耐力持久。
• 内存占用极低: Eg-walker 算法只在合并并发操作时才使用 CRDT 数据结构，并在合并完成后丢弃其状态，就像卸下了沉重的负重，轻装上阵，从而避免了 CRDT 算法高内存占用的问题。
• 文件小巧灵活: Eg-walker 算法的事件图存储格式经过优化，比等效的 CRDT 状态更小，就像精简了装备，提高了效率，这使得文档加载速度更快，并且在网络传输时消耗更少的带宽。
• 支持任意分支合并: Eg-walker 算法支持任意分支/合并模式，就像一位全能运动员，可以适应各种比赛规则，这使得它非常适合于具有长运行分支的异步协同编辑场景，例如版本控制系统或点对点协同软件。
• 点对点协同利器: Eg-walker 算法不依赖于中央服务器，因此可以用于点对点网络，就像一位自由的运动员，不受场地限制，这对于无法访问互联网或云服务的设备来说非常重要。
Eg-walker 算法揭秘
1. 事件图：协同编辑的幕后英雄
Eg-walker 算法的核心是 事件图，它就像一位默默无闻的幕后英雄，记录着文档编辑的每一个细节。事件图使用有向无环图 (DAG) 来表示文档的编辑历史，每个节点代表一个编辑操作 (插入或删除)，同时记录了其父节点，形成了事件发生的顺序关系。
例如，下图展示了两个用户对同一个文档“Helo”进行编辑的事件图：
Figure 1. 两个用户对文档“Helo”进行编辑，分别插入字母 l 和感叹号 ! 的事件图
用户 1 先在索引 3 的位置插入了字母 "l"，同时用户 2 在索引 4 的位置插入了感叹号 "!"。由于这两个操作是并发发生的，因此它们在事件图中是相互独立的节点 e5 和 e6，拥有相同的父节点 e4。
下图展示了与上述编辑历史对应的事件图：
Figure 2. 与 Figure 1. 对应的事件图
2. 版本：时间旅行的里程碑
在事件图中，每个节点都代表一个 版本，就像时间旅行中的里程碑，记录着文档在特定时刻的状态。Eg-walker 算法利用版本来优化性能，例如清除内部状态并跳过不必要的计算。每个版本的事件集合就是其所有祖先节点的集合。
例如，在 Figure 2. 中，节点 e5 代表用户 1 插入 "l" 字符后的文档版本，节点 e6 代表用户 2 插入 "!" 字符后的文档版本。
3. 重放编辑历史：穿越时空，还原真相
通过根据事件图中的操作顺序重放编辑历史，Eg-walker 可以重建任何时间点的文档状态，就像拥有了穿越时空的能力，可以还原文档的每一次修改。Eg-walker 会对事件图进行拓扑排序，然后依次应用每个事件的操作，最终得到完整的文档内容。
例如，下图展示了一个更复杂的事件图，其中包含了多个分支和合并操作：
Figure 3. 一个包含来自三个用户的多个分支和合并操作的事件图
Eg-walker 可以通过拓扑排序，按照一定的顺序重放这些事件，例如 eA1, eA2, eB1, eA3, eB2, eA4, eC1, eC2, eA5, eB3, eA6, eB4, eC3，最终得到一致的文档状态。
4. 算法流程：巧妙融合，化解冲突
Eg-walker 算法巧妙地融合了 OT 和 CRDT 的优点，就像一位经验丰富的调解员，能够化解并发操作带来的冲突，保证文档最终的一致性。它使用整数索引来标识插入和删除位置，并像 OT 一样转换这些索引以合并并发操作。同时，Eg-walker 使用 CRDT 算法来保证最终一致性，但仅在需要时才调用 CRDT，并在合并完成后丢弃其状态，避免了 CRDT 算法高内存占用的问题。
为了高效地处理并发操作，Eg-walker 维护了一个内部状态，它类似于一个简化的 CRDT 数据结构，用于跟踪每个字符的插入和删除状态。当遇到并发操作时，Eg-walker 会使用这个内部状态来转换操作的索引，以保证最终的一致性。
Eg-walker 使用三个方法来更新内部状态：
•
apply(e)：将事件 e 应用到内部状态，假设当前的准备版本等于 e 的父节点，并且 e 还没有被应用。•
retreat(e)：从内部状态中撤销事件 e，假设准备版本之前包含 e。•
advance(e)：将事件 e 添加到内部状态，假设准备版本之前不包含 e，但效果版本包含 e。
例如，下图展示了一个包含并发操作的事件图：
Figure 4.一个包含并发操作的事件图，其中一个用户将“hi”改为“hey”，另一个用户将“h”改为大写
在这个例子中，用户 1 将“hi”改为“hey”，同时用户 2 将“h”改为大写。Eg-walker 会先应用 e1、e2、e3、e4，然后撤销 e4 和 e3，应用 e5，再应用 e6、e7，最后推进 e3 和 e4，最后应用 e8。
Figure 5. 事件状态
下图展示了应用事件 e1...e4 后的内部状态：
Figure 6. 应用事件 e1...e4 后的内部状态
下图展示了应用所有事件后的内部状态：
Figure 7. 应用所有事件后的内部状态
5. 关键版本：性能优化的秘密武器
关键版本是 Eg-walker 算法性能优化的秘密武器，它可以显著降低内存占用和加快文件加载速度。关键版本是指一个版本，它的所有后续事件都发生在它的所有祖先事件之后。当 Eg-walker 算法遇到一个关键版本时，它可以安全地丢弃之前的内部状态，因为这些状态对后续操作没有影响，从而节省内存和计算资源。
例如，在 Figure 4. 中，节点 e4 是一个关键版本，因为它将事件图划分为两个部分：e1、e2、e3、e4 和 e5、e6、e7、e8。在重放事件图时，如果当前版本是 e4，Eg-walker 就可以清除所有与 e1、e2、e3、e4 相关的内部状态，因为这些状态对后续操作没有影响。
Eg-walker 实力碾压：性能评估
为了评估 Eg-walker 算法的性能，Gentle 和 Kleppmann 收集了来自真实文本文档的编辑轨迹，包括顺序编辑、并发编辑和异步编辑三种场景，并与 Automerge、Yjs 和 TTF 等流行的协同编辑算法进行了对比。结果表明，Eg-walker 算法在内存占用、加载速度和合并效率方面都具有显著优势，堪称协同编辑领域的性能之王！
1. 数据集：来自真实世界的考验
测试数据集来自真实的文本文档，涵盖了三种常见的协同编辑场景：
• 顺序编辑轨迹: 多个用户轮流编辑同一个文档，例如两个人合写一篇文章。
• 并发编辑轨迹: 多个用户同时编辑同一个文档，例如两个人同时修改同一个段落。
• 异步编辑轨迹: 用户离线编辑文档，然后将修改合并到主分支，例如使用 Git 进行版本控制。
2. 评估指标：全方位检验实力
性能评估使用了以下四个关键指标：
• 加载时间: 将文档从磁盘加载到内存所需的时间。
• 合并时间: 将来自远程副本的编辑合并到本地状态所需的时间。
• 内存占用: 算法运行时占用的内存空间。
• 文件大小: 存储事件图所需的文件大小。
3. 结果分析：Eg-walker 实力碾压
Eg-walker 算法在所有测试场景中均表现出色，尤其是在内存占用、加载速度和合并效率方面，显著优于现有的 CRDT 算法，并在大部分情况下与 OT 算法的性能相当。
Eg-walker 的优势:
• 顺序编辑场景: Eg-walker 的性能与 OT 算法相当，并且比 CRDT 算法快一个数量级。
• 并发编辑场景: Eg-walker 的性能与最快的 CRDT 算法相当，并且显著快于 Automerge 和 Yjs 等流行的 CRDT 库。
• 异步编辑场景: Eg-walker 的合并效率比 OT 算法高出几个数量级，并且内存占用显著低于 OT 算法。
下图展示了 Eg-walker、OT 和 CRDT 算法在不同场景下的合并时间：
Figure 8. Eg-walker、OT 和 CRDT 算法在不同场景下的合并时间
可以看出，在处理具有长运行分支的异步编辑轨迹时，Eg-walker 的合并效率远远超过 OT 算法，同时在其他场景下也能保持与最佳算法相当的性能。Eg-walker 算法的优异表现主要归功于其巧妙地结合了 OT 和 CRDT 的优点，并在关键版本优化方面做出了改进。
下图展示了开启和关闭关键版本优化对 Eg-walker 合并时间的影响：
Figure 9. 开启和关闭关键版本优化对 Eg-walker 合并时间的影响
可以看出，关键版本优化对于顺序编辑轨迹和包含较多顺序编辑部分的异步轨迹效果显著，而对于并发编辑轨迹和几乎没有关键版本的异步轨迹影响不大。
下图展示了 Eg-walker、OT 和 CRDT 算法在不同场景下的内存占用情况：
Figure 10. Eg-walker、OT 和 CRDT 算法在不同场景下的内存占用情况
可以看出，Eg-walker 的内存占用始终低于 CRDT 算法，并且在稳定状态下比 CRDT 算法低 1-2 个数量级，这得益于 Eg-walker 只在需要时才调用 CRDT，并在合并完成后丢弃其状态。
下图展示了 Eg-walker 和 Automerge 在不同场景下的文件大小：
Figure 11. Eg-walker 和 Automerge 在不同场景下的文件大小，其中浅色部分表示存储的文本内容大小
可以看出，Eg-walker 的事件图存储格式比 Automerge 的 CRDT 状态更小，尤其是在缓存了最终文档状态的情况下，Eg-walker 的文件大小优势更加明显。
下图展示了在只存储最终文档文本和操作元数据的情况下，Eg-walker 和 Yjs 在不同场景下的文件大小：
Figure 12. 在只存储最终文档文本和操作元数据的情况下，Eg-walker 和 Yjs 在不同场景下的文件大小，其中浅色部分表示最终文档文本的大小
可以看出，Eg-walker 在顺序编辑轨迹和异步轨迹上的文件大小比 Yjs 更小，但在并发编辑轨迹上略大于 Yjs，这可能是因为事件图需要存储额外的边信息来表示并发关系。
Eg-walker 的应用场景：颠覆传统，未来可期
Eg-walker 算法的优异性能，使其在各种协同编辑场景中都具有巨大的应用潜力：
• 在线文档编辑: Eg-walker 算法可以用于 Google Docs、Microsoft Word 等在线文档编辑软件，提升用户体验，减少卡顿和崩溃，提高协作效率。
• 代码协同开发: Eg-walker 算法可以用于 GitHub、GitLab 等代码协同开发平台，支持更复杂的版本控制和分支合并操作，提高开发效率。
• 实时协作平台: Eg-walker 算法可以用于 Figma、Miro 等实时协作平台，支持更流畅的实时编辑和协作体验。
• 点对点协同软件: Eg-walker 算法不需要中央服务器，特别适合用于点对点协同软件，例如去中心化的协作平台、离线协作工具等。
未来，随着 Eg-walker 算法的进一步发展和完善，它将颠覆传统的云协作模式，为我们带来更加高效、便捷、安全的协同编辑体验。
结语：协同编辑的未来，由 Eg-walker 开启
Eg-walker 算法的出现，为协同编辑领域带来了新的突破，它的低内存占用、快速加载速度和高效合并效率，使其成为点对点协同软件的理想选择。未来，Eg-walker 算法有望扩展到其他文件类型，例如富文本、电子表格和图形，为更广泛的协同应用场景提供支持。
你是否对 Eg-walker 算法充满期待？你认为它将如何改变我们的协作方式？欢迎在评论区分享你的想法！
相关链接
• Eg-walker 论文: https://arxiv.org/abs/2409.14252
• Eg-walker 代码实现: https://github.com/josephg/diamond-types
• 编辑轨迹数据集: https://github.com/josephg/editing-traces
