程序员花费无数时间与一个基本工具互动：他们的文本编辑器。在你提交、推送或发布任何一行代码之前，你必须先亲手将它输入到机器中。没有任何工具能像它一样对创建软件的直观和触觉体验产生如此大的影响。
然而，尽管编辑器在我的程序员生涯中扮演着至关重要的角色，但我从未找到一个我真正喜爱的编辑器。所以16年前，我决定自己构建一个。经过一次失败的尝试、许多艰难的教训，以及一些才华横溢的朋友的帮助，我一直努力创造的工具终于在构成 Zed 的135k行 Rust 代码中浮现。
我们对 Zed 的首要目标很简单：构建一个我们喜欢使用的编辑器。一个性能始终如一的工具。一个能帮助我们，但又不会碍事的工具。一个看起来很棒，但又会“消失”的工具。我们希望 Zed 能提升文本编辑的艺术水平，结合其他编辑器的优点，同时避免它们的缺点，并更进一步。低于此标准的都不值得构建。
但除了执行基本功能之外，我们还看到了一个彻底改进开发者协作软件方式的机会。通过将协作作为代码创作环境本身的一等公民，Zed 将使将对话与任何文本片段联系起来变得更容易，无论它是去年提交的还是刚刚编写的。Zed 还将使与同事实时编写和讨论代码变得无缝。
对协作的关注是 Zed 的主要特征之一，因此在我们的第一篇博客文章中，我们想探讨一下我们为实现这一目标而内置在编辑器核心的技术。
协作编辑的史前史
1968年12月，道格拉斯·恩格尔巴特在旧金山向座无虚席的观众展示了许多技术，包括交互式编辑、超文本和鼠标。他提出的思想后来塑造了现代计算，但当我第一次观看他著名的演示时，我惊讶地发现，让所有人惊叹的系统实际上是一个协作文本编辑器。这正是我一直想构建的东西！在1968年。
为了构建他们的协作编辑器，恩格尔巴特的团队需要创建自己的编程语言、分时操作系统和阴极射线管显示器。当我们着手构建 Zed 时，我们的任务显然在几乎所有方面都比他们容易得多，但我们确实面临着他们没有的一个问题：异步协调。
在恩格尔巴特的系统中，协作者都通过独立的终端连接到同一台物理机器。我不确定他们的工具是否支持细粒度的并发编辑，但至少在理论上，在这种设置下，可以通过互斥锁同步对共享缓冲区的编辑。但这与当今计算机的组织方式不同。我们不通过直接连接的终端共享一台机器，而是使用通过互联网连接的个人计算机。而且我们的协作距离要远得多。即使以光速，在两个不同大洲之间同步对共享缓冲区的访问也会引入令人望而却步的编辑延迟。
异步协调的挑战
要在互联网上协作，我们需要一种方法，允许个人独立编辑自己的文档副本，并在异步交换数据后，使他们的文档收敛到相同的内容。事实证明，这是一个难题。
下面的动画说明了基本的挑战。我们从文本 In 1968, 的两个副本开始。然后我们同时向每个副本插入不同的文本，并将我们编辑的描述传输到另一个副本。但是，如果我们天真地应用远程编辑而不考虑并发更改，我们最终可能会将其应用到无效位置，导致副本内容不一致。
使用 CRDTs 实现最终一致的文本编辑
一个解决方案是某种程度上“转换”传入的编辑以反映并发更改。在下面的动画中，您可以看到我们如何转换蓝色插入，将其位置从 8 更改为 20。
这个概念很简单，但是定义一个正确且高性能的转换操作函数并非易事，它是计算机科学研究的一个子领域，被称为操作转换（Operational Transformation，简称 OT）。当我们在2017年首次探索协作编辑时，我们尝试过这种方法，但我们最终选择了另一种理论框架，称为无冲突复制数据类型（Conflict-Free Replicated Data Types，简称 CRDTs），我们发现它更强大、更直观。
使用 CRDTs，我们不是“转换”并发操作以使其可以按不同顺序应用，而是将数据结构化，使并发操作“本质上是可交换的”，从而允许我们在任何副本上直接应用它们而无需转换。但我们如何使文本编辑具有可交换性呢？
关键在于以逻辑位置而不是绝对偏移量来表达编辑。在上面的例子中，如果我们不是用数字偏移量来指代插入位置，而是用内容来描述它们呢？那么并发编辑是否移动了文本就不重要了，因为我们只依赖内容来解析远程编辑的位置。
这种方法在实践中显然行不通。文本 68, 可能会出现多次，或者并发编辑可能已经完全删除了它。要使用这种基于内容的逻辑寻址，我们需要以在并发更改存在的情况下持久的方式进行。但如何实现呢？
不稳定文本中的稳定引用
用缓冲区的当前内容来表达逻辑位置的问题在于文本不稳定。但有一件事是稳定的，那就是编辑“历史”。我们可以将所有曾经插入的文本都视为不可变的。随后的编辑可能会将其拆分或删除部分，但这不会改变最初插入的文本。如果我们为每次插入分配一个唯一的标识符，我们现在就可以使用此标识符结合插入文本中的偏移量来明确地引用一个逻辑位置。我们将这些（插入ID，偏移量）对称为“锚点”。
为了生成这些唯一标识符，我们会在创建每个副本时集中为其分配一个唯一的 ID，然后将其与一个递增的序列号结合起来。通过从副本 ID 继承唯一性，副本可以并发生成 ID 而不会有冲突的风险。
在协作会话开始时，参与者被分配副本 ID。副本 0 将缓冲区初始文本的标识符分配为 0.0，然后将其副本传输给副本 1。这个初始文本片段，0.0，是第一次“插入”，它将在缓冲区的整个生命周期中保持不变。
现在，每个参与者同时插入文本，使用相对于插入 0.0 的偏移量描述插入位置。每个新插入都被分配一个唯一的 ID。当副本 0 在插入 0.0 的偏移量 3 处插入 December of 时，标记为 0.0 的片段被分成两部分。副本 1 在插入 0.0 的末尾，偏移量 8 处附加 Douglas Engelbart。两个参与者也将其操作传输给对方。
现在，副本相互应用对方的操作。首先，副本 1 整合了 ID 为 0.1 的红色插入，将插入 0.0 分成两部分，就像副本 0 最初插入此文本时发生的那样。然后副本 0 整合了 ID 为 1.0 的蓝色插入。
它扫描其片段，寻找插入 0.0 的偏移量 8。第一个片段属于 0.0，但只有 3 个字符长。第二个片段属于不同的插入 0.1，并被跳过。最后，我们到达包含插入 0.0 文本的第二个片段。这个片段包含偏移量 8，所以我们在这里插入蓝色文本。副本收敛。
这个过程可以递归地继续，插入操作在一个树中相互构建。在下面的动画中，两个副本都在 ID 为 1.0 的蓝色插入中，在不同的偏移量处插入了额外的文本。为了应用远程操作，我们再次扫描文档，寻找包含指定偏移量的插入 1.0 的片段。
在这些例子中，我们一次插入多个字符，但值得注意的是，实际上，协作用户通常是插入单个字符，而不是从剪贴板粘贴整个单词。为每个字符跟踪所有这些元数据可能看起来开销很大，但在实践中，这在现代计算机硬件上并不是问题。即使是长时间的编辑历史，与 Zed 不使用 Electron 构建所节省的内存相比也微不足道。
您可能还会问：这样扫描整个文档来应用每个远程编辑是不是慢得令人发指？在未来的文章中，我将解释我们如何使用写时复制 B 树来索引这些片段，以避免线性扫描，但这种简化的解释应该能为您提供一个理解 Zed 中协作编辑工作原理的基本框架。
删除
如果每次插入都是不可变的，那么当用户删除文本时，我们如何从文档中删除文本呢？我们不是修改已插入的文本，而是用“墓碑”标记已删除的片段。带有墓碑的片段在向用户显示的文本中是隐藏的，但它们仍然可以用于将逻辑锚点解析为文档中的具体位置。
在下面的动画中，我们在副本 1 中插入文本，其位置在副本 0 中同时被删除。因为被删除的文本只是隐藏而不是实际丢弃，所以当它到达副本 0 时，我们仍然可以应用插入。
如果删除只编码一个范围，那么如果文本在删除范围内同时插入，就会发生分歧。在下面的示例中，请注意黄色 C. 在副本 0 中可见，但在副本 1 中隐藏。
为了避免这个问题，我们还将删除与一个“向量时间戳”关联起来，该时间戳编码了每个副本观察到的最新序列号。通过它，我们可以排除并发发生的插入，只隐藏执行删除操作的用户实际可见的文本。
下面的动画与上面的非常相似，只不过这次我们用版本向量来增强删除操作。当我们在副本 1 上应用删除时，我们“排除”黄色插入，因为它的 ID 包含的序列号不包含在删除的版本中。这使得黄色插入在两个副本上都保持可见，从而保留了删除用户的意图。
与插入一样，删除也与唯一的标识符关联，我们将其记录在墓碑上。稍后讨论撤销和重做操作时，我们将看到这些删除标识符的用途。
同一位置的并发插入
当并发插入发生在同一位置时，如何排序这些插入并不重要，但重要的是它们的排序在所有副本中都是一致的。实现一致性的一种方法是按其 ID 对同一位置的所有插入进行排序。
然而，这种方法的问题在于，对于某些副本来说，在它们已经观察到的插入之前插入文本可能会变得不可能。
我们需要一个尊重“因果关系”的这些插入的一致排序。我们的解决方案是为插入添加“Lamport 时间戳”。这些逻辑时间戳是从每个副本维护的标量值“Lamport 时钟”派生出来的。每当副本生成一个操作时，它通过递增其 Lamport 时钟来派生一个 Lamport 时间戳。每当副本“接收”一个操作时，它将其自身的 Lamport 时钟设置为时钟当前值和传入操作时间戳中较大的那个。
这种方案保证了如果一个操作在另一个操作发生时存在，那么它的时间戳会更低。另一种说法是，Lamport 时间戳允许我们按“因果顺序”对操作进行排序。反之则不成立。仅仅因为操作 A 的 Lamport 时间戳低于操作 B，并不一定意味着它在因果上先于操作 B，因为我们无法保证“并发”操作的 Lamport 时间戳之间的关系。但我们已经确定，我们不关心并发插入的排序方式，只要我们的排序是一致的。
通过将同一位置发生的插入按其 Lamport 时间戳降序排序，并根据副本 ID 打破平局，我们实现了尊重因果关系的一致排序方案。
撤销和重做
在非协作系统中，撤销和重做历史可以表示为简单的编辑操作堆栈。当您想要撤销某些内容时，只需弹出撤销堆栈顶部的编辑，对其当前文本应用其逆操作，然后将其推送到重做堆栈。但这只允许对整个文档进行单个全局撤销历史。历史中任何操作的偏移量仅在最初应用该操作的文档的特定状态下有效。这意味着操作必须始终以它们发生的精确相反顺序撤销。
但在协作编辑时，整个缓冲区的单个撤销历史记录不起作用。当你撤销时，你希望撤销“你自己输入”的文本。每个参与者都需要自己的撤销堆栈。这意味着我们需要能够以任意顺序撤销和重做操作。一个共享的全局编辑操作堆栈是不够的。
相反，我们维护一个“撤销映射”，它将操作 ID 与一个计数相关联。如果计数为零，则操作尚未撤销。如果计数为奇数，则操作已撤销。如果为偶数，则操作已重做。撤销和重做操作只是更新此映射中特定操作 ID 的计数。然后，当我们决定某个片段是否可见时，我们首先检查该插入是否已撤销（其撤销计数为奇数）。然后我们检查它是否有任何删除墓碑，以及这些删除的撤销计数是否为偶数。
在发送撤销/重做操作时，直接分配这些撤销计数是没有问题的。如果两个用户同时撤销相同的操作，他们最终会将它的撤销计数设置为相同的值。这保留了他们的意图，因为他们都想撤销或重做它。实际上，我们目前只允许用户撤销自己的操作，但我们最终可能会引入撤销协作者操作的能力。
结论
显然还有很多内容需要涵盖。我们如何实际高效地实现这一方案？我们如何将 CRDTs 集成到一个更广泛的系统中，从而创造出共享工作空间的幻觉？我们如何使这个复杂的分布式系统可靠？除了协作之外，我们还能用 CRDTs 做些什么？然后还有编辑器的其他部分。绳索。我们GPU 加速的 UI 框架。Tree-sitter。集成终端。等等。
我们期待在未来的几个月和几年里讨论所有这些。更重要的是，我们期待应用这项技术，发布一个让您更快乐、更高效的编辑器。感谢阅读！