程序员花费无数时间与一个基本工具交互：他们的文本编辑器。在您提交、推送或发布任何一行代码之前，您必须先将双手放在键盘上，将其输入到机器中。没有哪个工具能比文本编辑器对创建软件的内在和触觉体验产生更大的影响。
然而，尽管编辑器在我作为程序员的生活中扮演着至关重要的角色，但我从未找到一个我真正喜欢的编辑器。所以 16 年前，我决定自己构建一个。经历了一次失败的尝试、许多惨痛的教训以及一些才华横溢的朋友的帮助，我一直努力创造的工具最终出现在构成 Zed 的 13.5 万行 Rust 代码中。
我们使用 Zed 的首要目标很简单：构建一个我们喜欢使用的编辑器。一个具有持续高性能的工具。一个可以帮助我们，但又不会妨碍我们的工具。一个看起来很棒，但也会消失的工具。我们希望 Zed 能够提升文本编辑的水平，结合其他编辑器的优点，同时避免它们的缺点，然后再进一步。任何低于此标准的都不值得构建。
但是，除了执行基本功能之外，我们还看到了一个彻底改进开发人员在软件上进行协作方式的机会。通过将协作作为代码编写环境本身的首要考虑因素，Zed 将使将对话链接到任何一段文本变得更容易，无论该文本是去年提交的还是刚刚编写的。Zed 还可以让开发人员实时编写和讨论代码变得无缝。
这种对协作的关注是 Zed 的一个决定性特征，因此在我们发布的第一篇博文中，我们想探讨我们内置到编辑器核心中的技术，使其成为可能。
协同编辑的早期历史
1968 年 12 月，道格拉斯·恩格尔巴特在旧金山向满座的观众展示了大量技术，包括交互式编辑、超文本和鼠标。他提出的想法后来塑造了现代计算，但当我第一次观看他著名的演示时，我很惊讶地得知让每个人都惊叹的系统实际上是一个协同文本编辑器。正是我一直试图构建的东西！早在 1968 年。
为了构建他们的协同编辑器，恩格尔巴特的团队需要创建自己的编程语言、分时操作系统和阴极射线管显示器。当我们开始构建 Zed 时，我们的任务在几乎所有方面都显然比他们容易得多，但我们确实面临着他们没有面临的一个问题：异步协调。
在恩格尔巴特的系统中，合作者都通过各自的终端连接到同一台物理机器。我不确定他们的工具是否曾经支持细粒度的并发编辑，但至少在理论上，在这种设置中可以使用互斥锁将对共享缓冲区的编辑同步。但这并不是当今计算机的组织方式。我们没有通过直接连接的终端共享一台机器，而是使用通过互联网连接的个人电脑。而且我们的合作距离也远得多。即使以光速，在两个不同大陆之间同步对共享缓冲区的访问也会带来令人望而却步的编辑延迟。
异步协调的挑战
为了通过互联网进行协作，我们需要一种方法，允许个人独立编辑他们自己的文档副本，并在他们异步交换数据后，使其文档收敛到相同的内容。事实证明，这是一个难题。
下面的动画说明了基本的挑战。我们从文本 In 1968, 的两个副本开始。然后，我们并发地将不同的文本插入到每个副本中，并将我们的编辑描述传输到另一个副本。但是，如果我们天真地应用远程编辑而不考虑并发更改，我们最终可能会将其应用到无效的位置，从而导致副本的内容发生分歧。
使用 CRDT 实现最终一致的文本编辑
一种解决方案是以某种方式转换传入的编辑以反映并发更改。在下面的动画中，您可以看到我们如何转换蓝色插入，将其位置从 8 更改为 20。
这在概念上很简单，但是定义一个可以转换操作的正确且高性能的函数并非易事，并且是称为操作转换 (OT) 的计算机科学研究的整个子学科的主题。当我们在 2017 年首次探索协同编辑时，我们尝试了这种方法，但最终我们选择使用另一种称为无冲突复制数据类型 (CRDT) 的理论框架，我们发现它更强大且更直观。
使用 CRDT，我们不是转换并发操作以便可以以不同的顺序应用它们，而是构建我们的数据，使并发操作本质上是可交换的，从而允许我们直接在任何副本上应用它们，而无需转换。但是我们如何使文本编辑可交换呢？
关键是以逻辑位置而不是绝对偏移量来表达编辑。在上面的示例中，如果不是以数字偏移量来引用插入位置，而是通过内容来描述它们呢？那么并发编辑是否已移动文本并不重要，因为我们只依赖内容来解析远程编辑的位置。
这种方法显然在实践中行不通。文本 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 的计数。然后，当我们决定某个片段是否可见时，我们首先检查该插入是否已被撤销（其撤销计数为奇数）。然后，我们检查它是否有任何删除墓碑，以及这些删除中是否有任何删除的撤销计数为偶数。
在发送撤销/重做操作时，可以直接分配这些撤销计数。如果两个用户同时撤销同一操作，他们最终会将撤销计数设置为相同的值。这保留了他们的意图，因为他们都想撤销或重做它。实际上，我们目前只允许用户撤销他们自己的操作，但我们最终可能会引入撤销协作者操作的能力。
结论
显然还有很多要讲的。我们如何实际实现这个方案，使其高效？我们如何将 CRDT 集成到一个更广泛的系统中，从而创造共享工作区的幻觉？我们如何使这个复杂的分布式系统可靠？除了协作之外，我们还可以用 CRDT 做什么？然后是编辑器的其余部分。绳索。我们的GPU加速的UI框架。Tree-sitter。集成的终端。还有更多，更多。
我们期待在未来的几个月和几年里讨论所有这些。更重要的是，我们期待应用这项技术来发布一款让你更快乐、更高效的编辑器。感谢您的阅读！