How CRDTs make multiplayer text editing part of Zed's DNA
如何让 CRDTs 成为 Zed 多人文本编辑的 DNA 的一部分

Programmers spend countless hours interacting with one fundamental tool: their text editor. Before you commit, push, or ship a single line of code, you must first put your hands on the keyboard and type it into the machine. No tool has a bigger impact on the visceral and tactile experience of creating software.
程序员花费无数小时与一个基本工具互动：他们的文本编辑器。在你提交、推送或发布任何一行代码之前，你必须首先将双手放在键盘上，将其输入到机器中。没有任何工具对创建软件的直观和触觉体验有更大的影响。

Yet despite the critical role that editors play in my life as a programmer, I have never found an editor that I truly love. So 16 years ago, I decided to build one. It took a failed attempt, many hard lessons, and the help of some talented friends, but the tool I've been striving to create is finally emerging in the 135k lines of Rust that constitute Zed.
尽管编辑在我的程序员生活中扮演着至关重要的角色，但我从未找到过真正喜爱的编辑器。因此，16 年前，我决定自己打造一个。这经历了一次失败的尝试，许多艰难的教训，以及一些才华横溢的朋友的帮助，但最终，我努力打造的工具终于以 135,000 行 Rust 代码的形态——Zed——呈现在眼前。

Our first goal with Zed is simple: to build an editor that we love using. A tool with consistent high performance. A tool that assists us, but also stays out of our way. A tool that looks great, but also disappears. We want Zed to advance the state of the art for text editing, combining the strengths of other editors while avoiding their weaknesses, then going further. Anything less isn't worth building.
我们的第一个目标就是让 Zed 成为我们喜爱的编辑器。一个性能稳定、高效的工具。一个既能协助我们，又不会干扰我们的工具。一个外观美观，却又不会引人注目的工具。我们希望 Zed 能够推动文本编辑技术的进步，结合其他编辑器的优点，避免它们的缺点，并更进一步。任何低于这个标准的东西都不值得我们去构建。

But beyond executing on the fundamentals, we also see an opportunity to radically improve the way developers collaborate on software. By integrating collaboration as a first-class concern of the code authoring environment itself, Zed will make it easier to link conversations to any piece of text, regardless of whether it was committed last year or just written moments ago. Zed will also make it seamless to write and discuss code with fellow developers in real time.
但除了执行基本要素之外，我们还看到了一个机会，可以彻底改善开发者协作编写软件的方式。通过将协作作为代码编写环境本身的首要关注点，Zed 将使将对话与任何文本联系起来变得更加容易，无论它是去年提交的还是刚刚写下的。Zed 还将使与同行开发者实时编写和讨论代码变得无缝。

This focus on collaboration is one of Zed's defining characteristics, so with our first blog post, we'd like to explore the technology we've built into the core of the editor to make it possible.
这个注重协作的特点是 Zed 的显著特征之一，因此，在我们的第一篇博客文章中，我们想探讨我们融入编辑器核心的技术，使其成为可能。

The pre-history of collaborative editing
协作编辑的史前时期

In December of 1968, Douglas Engelbart demonstrated a host of technologies in front of a standing-room-only audience in San Francisco, including interactive editing, hypertext, and the mouse. The ideas he presented went on to shape modern computing, but when I first watched his famous demo, I was surprised to learn that the system that amazed everyone was actually a collaborative text editor. The very thing I had been trying to build! In 1968.
1968 年 12 月，道格拉斯·恩格尔巴特在旧金山向一座座无虚席的观众展示了一系列技术，包括交互式编辑、超文本和鼠标。他所提出的理念最终塑造了现代计算机的发展，但当我第一次观看他著名的演示时，我惊讶地发现令所有人惊叹的系统实际上是一个协作文本编辑器。这正是我一直试图构建的东西！就在 1968 年。

To build their collaborative editor, Engelbart's team needed to create their own programming language, time-sharing operating system, and cathode ray tube displays. As we set out to build Zed, our task was obviously vastly easier than theirs in almost every way, but we did face one problem that they did not: asynchronous coordination.
为了构建他们的协作编辑器，恩格尔巴特团队需要创建自己的编程语言、分时操作系统和阴极射线管显示器。当我们着手构建 Zed 时，我们的任务显然比他们容易得多，但我们也面临了一个他们没有遇到的问题：异步协调。

In Engelbart's system, collaborators were all connected to the same physical machine via individual terminals. I'm unsure whether their tool ever supported fine-grained concurrent editing, but at least in theory, it would have been possible in this setup to synchronize edits to a shared buffer with a mutex. But this isn't how computers are organized today. Instead of sharing a single machine via directly-connected terminals, we use personal computers that are connected via the internet. And we collaborate over much greater distances. Even at the speed of light, synchronizing access to a shared buffer between two different continents would introduce prohibitive editing latency.
在恩格尔巴特的系统中，所有协作者都通过各自的终端连接到同一台物理机器。我不确定他们的工具是否支持细粒度的并发编辑，但至少在理论上，在这种设置中，可以通过互斥锁同步对共享缓冲区的编辑。但今天计算机的组织方式并非如此。我们不再通过直接连接的终端共享一台机器，而是使用通过互联网连接的个人电脑。我们跨越更远的距离进行协作。即使在光速下，在两个不同大陆之间同步对共享缓冲区的访问也会引入难以承受的编辑延迟。

The challenge of asynchronous coordination
异步协调的挑战

To collaborate over the internet, we need an approach that allows individuals to edit their own replicas of a document independently and have their documents converge to the same contents after they exchange data asynchronously. It turns out this is a hard problem.
为了在互联网上进行协作，我们需要一种方法，允许个人独立编辑自己的文档副本，并在他们异步交换数据后，使文档内容趋于一致。事实证明，这是一个难题。

The animation below illustrates the basic challenge. We start with two replicas of the text In 1968,. We then concurrently insert different text into each replica and transmit a description of our edits to the other replica. But if we naively apply a remote edit without accounting for concurrent changes, we can end up applying it to an invalid location, causing the contents of the replicas to diverge.
动画演示了基本挑战。我们从两个文本副本 In 1968, 开始。然后我们同时向每个副本插入不同的文本，并将我们的编辑描述传输给另一个副本。但是，如果我们天真地应用远程编辑而不考虑并发更改，我们可能会将其应用到无效的位置，导致副本内容发生分歧。

Eventually-consistent text editing with CRDTs
最终一致性文本编辑与 CRDTs

One solution is to somehow transform incoming edits to reflect concurrent changes. In the animation below, you can see how we transform the blue insertion, changing its position from 8 to 20.
一个解决方案是 somehow 将传入的编辑转换为反映并发更改。在下面的动画中，您可以看到我们如何将蓝色插入操作的位置从 8 调整到 20。

This is simple in concept, but defining a correct and performant function that can transform operations is non-trivial, and was the subject of a whole subdiscipline of computer science research known as Operational Transformation, or OT. We experimented with this approach when we first explored collaborative editing back in 2017, but we ultimately chose to work with an alternative theoretical framework called Conflict-Free Replicated Data Types (CRDTs), which we found to be more powerful and intuitive.
这个概念很简单，但定义一个正确且高效的函数来转换操作却非同小可，这曾是计算机科学研究中一个名为操作转换（Operational Transformation，简称 OT）的子学科的课题。我们早在 2017 年首次探索协作编辑时尝试过这种方法，但最终我们选择了另一种名为无冲突复制数据类型（Conflict-Free Replicated Data Types，简称 CRDTs）的理论框架，我们发现它更加强大且直观。

With CRDTs, instead of transforming concurrent operations so they can be applied in a different order, we structure our data so that concurrent operations are inherently commutative, allowing us to apply them directly on any replica without transformation. But how do we make text edits commutative?
使用 CRDTs 时，我们不是将并发操作转换为不同的顺序以应用，而是将我们的数据结构设计成并发操作本身是交换律的，这样我们就可以直接在任何副本上应用它们，无需转换。但我们是怎样让文本编辑具有交换律的呢？

The key is to express edits in terms of logical locations rather than absolute offsets. In the examples above, what if instead of referring to insertion locations in terms of numeric offsets, we described them via content instead? Then it wouldn't matter that concurrent edits have shifted the text, because we only depend on content to resolve the location of the remote edit.
关键在于用逻辑位置来表述编辑，而不是用绝对偏移量。在上面的例子中，如果我们不是用数字偏移量来指明插入位置，而是用内容来描述它们，那么即使并发编辑改变了文本，也不会影响，因为我们只依赖于内容来确定远程编辑的位置。

This approach obviously wouldn't work in practice. The text 68, might appear multiple times, or a concurrent edit may have completely deleted it. To use this sort of content-based logical addressing, we need to do it in a way that's durable in the presence of concurrent changes. But how?
这种方法显然在实际应用中是不可行的。文本 68, 可能会出现多次，或者并发编辑可能已经完全删除了它。为了使用这种基于内容逻辑定位的方法，我们需要在并发更改的情况下确保其持久性。但如何实现呢？

Stable references in unstable text
稳定的引用在不稳定文本中

The problem with expressing logical positions in terms of the buffer's current content is that the text isn't stable. But one thing that is stable is the editing history. We can treat every piece of text that's ever been inserted as immutable. Subsequent edits might split that text apart or delete portions of it, but this doesn't change the text that was originally inserted. If we assign a unique identifier to every insertion, we can now unambiguously refer to a logical location using this identifier combined with an offset into the inserted text. We refer to these (insertion id, offset) pairs as anchors.
问题在于用缓冲区当前内容来表达逻辑位置，因为文本是不稳定的。但有一件事是稳定的，那就是编辑历史。我们可以将每一段曾经插入的文本视为不可变的。后续的编辑可能会将文本分割开来或删除其部分，但这并不会改变最初插入的文本。如果我们为每一次插入分配一个唯一的标识符，现在我们可以使用这个标识符加上插入文本中的偏移量来明确地引用一个逻辑位置。我们将这些（插入 ID，偏移量）对称为锚点。

To generate these unique identifiers, we centrally assign each replica a unique id when it's created, then combine it with an incrementing sequence number. By inheriting uniqueness from the replica id, replicas can generate ids concurrently without risk of collision.
为了生成这些唯一的标识符，我们在创建副本时为其分配一个唯一的 ID，然后将其与递增的序列号相结合。副本通过继承 ID 的唯一性，可以并发生成 ID，而不会出现冲突。

At the start of a collaboration session, participants are assigned replica ids. Replica 0 assigns an identifier of 0.0 to the buffer's initial text, then transmits a copy to replica 1. This initial fragment of text, 0.0, is the first insertion, and it will remain immutable for the life of the buffer.
在协作会议开始时，参与者会被分配副本 ID。副本 0 将为缓冲区的初始文本分配标识符 0.0 ，然后将副本发送给副本 1。这个初始文本片段 0.0 是第一次插入，它将保持不可变，直到缓冲区的生命周期结束。

Now each participant inserts text concurrently, describing the insertion location with offsets relative to insertion 0.0. Each new insertion is assigned its own unique id. When replica 0 inserts December of within insertion 0.0 at offset 3, the fragment labeled 0.0 is split into two pieces. Replica 1 appends Douglas Engelbart at the end of insertion 0.0, at offset 8. Both participants also transmit their operations to the other party.
现在，每位参与者同时插入文本，使用相对于插入位置 0.0 的偏移量来描述插入位置。每次新的插入都会分配一个唯一的 ID。当副本 0 在插入 0.0 内部偏移 3 处插入 December of 时，标记为 0.0 的片段被分成两部分。副本 1 在插入 0.0 的末尾追加 Douglas Engelbart ，偏移 8 。两位参与者也将他们的操作传输给对方。

Now the replicas apply each other's operations. First, replica 1 incorporates the red insertion with id 0.1, splitting insertion 0.0 in two just as occurred when replica 0 originally inserted this text. Then replica 0 incorporates the blue insertion with id 1.0.
现在，副本之间开始应用彼此的操作。首先，副本 1 将红色插入操作（ID 为 0.1 ）应用到自身，就像副本 0 最初插入这段文本时一样，将插入操作 0.0 拆分为两部分。然后，副本 0 将蓝色插入操作（ID 为 1.0 ）应用到自身。

It scans through its fragments, searching for offset 8 of insertion 0.0. The first fragment belongs to 0.0, but it's only 3 characters long. The second fragment belongs to a different insertion, 0.1, and is skipped. Finally, we reach the second fragment containing text from insertion 0.0. This one contains offset 8, and so we insert the blue text there. The replicas converge.
它扫描其碎片，寻找插入点 8 的偏移量 0.0 。第一个碎片属于 0.0 ，但只有 3 个字符长。第二个碎片属于另一个插入点 0.1 ，被跳过。最后，我们到达包含插入点 0.0 文本的第二个碎片。这个碎片包含偏移量 8 ，我们在那里插入蓝色文本。副本会合。

This process can continue recursively, with insertions building upon each other in a tree. In the animation below, both replicas insert additional text at different offsets within the blue insertion with id 1.0. To apply the remote operations, we again scan through the document looking for the fragment of insertion 1.0 that contains the specified offset.
此过程可以递归进行，插入操作在树状结构中层层叠加。在下面的动画中，两个副本在蓝色插入操作 1.0 的不同偏移量处插入额外的文本。为了应用远程操作，我们再次扫描文档，寻找包含指定偏移量的插入片段 1.0 。

In these examples, we're inserting multiple characters at a time, but it's worth noting that in practice, collaborators are often inserting individual characters rather than pasting whole words from their clipboard. Tracking all of this metadata per-character may seem like a lot of overhead, but in practice it isn't an issue on modern computing hardware. Even long edit histories barely compare to the memory savings Zed obtains from not being built with Electron.
在这些示例中，我们一次插入多个字符，但值得注意的是，在实际操作中，合作者通常插入单个字符，而不是从剪贴板粘贴整个单词。跟踪每个字符的这些元数据可能看起来像是很多开销，但在实际操作中，在现代计算机硬件上这并不是一个问题。即使是漫长的编辑历史，与 Zed 从不是用 Electron 构建而节省的内存相比也微不足道。

You may also be asking: Isn't scanning through the entire document like this to apply every remote edit insanely slow? In a future post, I'll explain how we use a copy-on-write B-tree to index these fragments in order to avoid linear scans, but this simplified explanation should give you a basic framework to understand how collaborative editing works in Zed.
您可能还会问：像这样扫描整个文档以应用每个远程编辑，难道不会非常慢吗？在未来的文章中，我会解释我们如何使用写时复制 B 树来索引这些片段以避免线性扫描，但这个简化的解释应该能为您提供一个基本的框架，以了解 Zed 中的协作编辑是如何工作的。

Deletion 删除

If every insertion is immutable, how do we remove text from the document when a user deletes? Rather than mutating inserted text, we instead mark deleted fragments with tombstones. Fragments with tombstones are hidden in the text we display for the user, but they can still be used to resolve logical anchors to concrete locations in the document.
如果每次插入都是不可变的，那么当用户删除文本时，我们该如何从文档中移除文本呢？我们不是修改已插入的文本，而是用墓碑标记被删除的片段。带有墓碑的片段在向用户显示的文本中是隐藏的，但它们仍然可以用来解决逻辑锚点到文档具体位置的映射。

In the animation below, we insert text in replica 1 at a position that is concurrently deleted in replica 0. Because the deleted text is merely hidden rather than actually thrown away, we can still apply the insertion when it arrives at replica 0.
在下面的动画中，我们在副本 1 中插入文本，同时删除副本 0 中的同一位置文本。由于被删除的文本只是被隐藏而非真正丢弃，因此当它到达副本 0 时，我们仍然可以应用插入操作。

If deletions only encode a range, divergence can occur if text is concurrently inserted inside the deleted range. In the example below, note how the yellow C. is visible in replica 0 but hidden in replica 1.
如果删除操作仅编码范围，则在文本同时在该删除范围内插入时，可能会发生分歧。以下示例中，请注意黄色标记 C. 在副本 0 中可见，但在副本 1 中不可见。

To avoid this issue, we also associate deletions with a vector timestamp that encodes the latest observed sequence number for each replica. Using this, we can exclude insertions that occurred concurrently, only hiding text that was actually visible to the user performing the deletion.
为避免此类问题，我们还将与删除操作关联一个向量时间戳，该时间戳编码了每个副本观察到的最新序列号。利用这一点，我们可以排除同时发生的插入操作，仅隐藏实际可见于执行删除操作的用户所看到的文本。

The animation below is much like the one above, except this time we augment the deletion operation with a version vector. When we apply the deletion on replica 1, we exclude the yellow insertion because its id contains a sequence number that isn't included in the deletion's version. This causes the yellow insertion to remain visible on both replicas, preserving the deleting user's intent.
以下动画与上面的动画非常相似，但这次我们在删除操作中增加了一个版本向量。当我们对副本 1 进行删除操作时，我们排除了黄色插入项，因为它的 ID 包含的序列号不在删除的版本中。这导致黄色插入项在两个副本上都保持可见，从而保留了删除用户的意图。

Like insertions, deletions are associated with unique identifiers, which we record on the tombstone. We'll see how these deletion identifiers are used later when we discuss undo and redo operations.
像插入一样，删除操作也关联着唯一的标识符，我们将这些标识符记录在墓碑上。我们将在讨论撤销和重做操作时看到这些删除标识符的用法。

Concurrent insertions at the same location
同时在同一位置进行插入操作

When concurrent insertions occur at the same location, it doesn't matter how we order the insertions, but it definitely does matter that their ordering is consistent across all replicas. One way to achieve consistency is to order all insertions at the same location by their id.
当并发插入操作发生在同一位置时，我们插入的顺序并不重要，但它们在所有副本中的顺序一致性绝对是必要的。实现一致性的一个方法是将同一位置的插入操作按照它们的 ID 进行排序。

However, the problem with this approach is that it can become impossible for certain replicas to insert text prior to an insertion they have already observed.
然而，这种方法的缺点是，对于某些副本来说，在它们已经观察到的插入点之前插入文本可能变得不可能。

We need a consistent ordering of these insertions that respects causality. Our solution is to augment insertions with Lamport timestamps. These logical timestamps are derived from a scalar-valued Lamport clock that is maintained on every replica. Whenever a replica generates an operation, it derives a Lamport timestamp by incrementing its Lamport clock. Whenever a replica receives an operation, it sets its own Lamport clock to the greater of the clock's current value and the timestamp of the incoming operation.
. 我们需要对这些插入操作进行一致的排序，同时保证因果关系的正确性。我们的解决方案是在插入操作中增加 Lamport 时间戳。这些逻辑时间戳是由每个副本上维护的标量值 Lamport 时钟推导出来的。每当一个副本生成一个操作时，它会通过增加其 Lamport 时钟来推导出一个 Lamport 时间戳。每当一个副本接收到一个操作时，它会将其自己的 Lamport 时钟设置为当前时钟值和接收到的操作时间戳中的较大值。

This scheme guarantees that if an operation was present at the time of another operation, then it will have a lower timestamp. Another way of phrasing this is that the Lamport timestamp allows us to sort the operations in causal order. The inverse isn't true. Just because operation A has a lower Lamport timestamp than operation B, it doesn't necessarily mean that it causally preceded operation B, because we have no guarantees about the relationship between the Lamport timestamps of concurrent operations. But we've already established that we don't care how concurrent insertions are ordered, so long as our ordering is consistent.
这个方案保证了如果一个操作在另一个操作发生时存在，那么它的时间戳会更低。另一种说法是，Lamport 时间戳允许我们按照因果关系对操作进行排序。但反过来并不成立。仅仅因为操作 A 的 Lamport 时间戳比操作 B 低，并不意味着操作 A 在因果上先于操作 B，因为我们无法保证并发操作 Lamport 时间戳之间的关系。但我们已经确定，只要我们的排序是一致的，我们并不关心并发插入的顺序。

By sorting insertions descending by their Lamport timestamp and breaking any ties based on their replica id, we achieve a consistent ordering scheme that respects causality.
通过按 Lamport 时间戳降序排序插入操作，并在副本 ID 上打破任何平局，我们实现了尊重因果关系的有序方案。

Undo and redo 撤销和重做

In non-collaborative systems, the undo and redo history can be represented as stacks of simple edit operations. When you want to undo something, you simply pop the edit on the top of the undo stack, apply its inverse to the current text, and push it to the redo stack. But this only allows for a single global undo history for the entire document. The offset of any operation in the history is only valid for the specific state of the document in which that operation was originally applied. This means that operations must always be undone in the exact reverse order in which they occurred.
在非协作系统中，撤销和重做历史可以表示为简单编辑操作的栈。当你想要撤销某个操作时，只需从撤销栈顶部弹出编辑操作，将其逆操作应用于当前文本，并将其推送到重做栈。但这样只能为整个文档提供单个全局撤销历史。历史中任何操作的偏移量仅对原始应用该操作时的文档特定状态有效。这意味着操作必须始终以它们发生的相反顺序进行撤销。

But when collaborative editing, a single undo history for the entire buffer doesn't work. When you undo, you expect to undo text that you yourself typed. Each participant needs their own undo stack. This means we need to be capable of undoing and redoing operations in an arbitrary order. A shared global stack of edit operations isn't enough.
但是，在进行协作编辑时，整个缓冲区的单一撤销历史是不够用的。当你撤销操作时，你期望撤销的是你自己输入的文字。每个参与者都需要自己的撤销栈。这意味着我们需要能够以任意顺序撤销和重做操作。一个共享的全局编辑操作栈是不够的。

Instead, we maintain an undo map, which associates operation ids with a count. If the count is zero, the operation has not been undone. If the count is odd, the operation has been undone. If it's even, the operation has been redone. Undo and redo operations simply update counts in this map for specific operation ids. Then, when we're deciding whether a certain fragment is visible, we first check if that insertion has been undone (its undo count is odd). We then check if it has any deletion tombstones, and whether the undo count of any of those deletions is even.
而不是，我们维护一个撤销映射，它将操作 ID 与计数关联起来。如果计数为零，则表示该操作尚未被撤销。如果计数为奇数，则表示该操作已被撤销。如果为偶数，则表示该操作已被重做。撤销和重做操作只是简单地更新特定操作 ID 的计数。然后，当我们决定某个片段是否可见时，我们首先检查该插入操作是否已被撤销（其撤销计数为奇数）。接着，我们检查是否存在任何删除墓碑，以及这些删除操作的撤销计数是否为偶数。

When sending undo/redo operations, it's fine to assign these undo counts directly. If two users both undo the same operation concurrently, they'll end up setting its undo count to the same value. This preserves their intent, since they both wanted to undo or redo it. In practice, we currently only allow users to undo their own operations, but we may eventually introduce the ability to undo operations of collaborators.
当发送撤销/重做操作时，直接分配这些撤销次数是可以的。如果两个用户同时撤销相同的操作，它们最终会将撤销次数设置为相同的值。这保留了他们的意图，因为他们都想要撤销或重做。实际上，我们目前只允许用户撤销自己的操作，但我们可能最终会引入撤销协作者操作的能力。

Conclusion 结论

There's obviously a lot more to cover. How do we actually implement this scheme so that it's efficient? How do we integrate CRDTs into a broader system that creates the illusion of a shared workspace? How do we make this complex distributed system reliable? And what else can we do with CRDTs other than collaborate? Then there's the rest of the editor. Ropes. Our GPU-accelerated UI framework. Tree-sitter. The integrated terminal. And much, much more.
显然，还有很多内容需要探讨。我们究竟如何实际实施这个方案，使其高效？我们如何将 CRDTs 整合到一个更广泛系统中，以创造共享工作空间的错觉？我们如何使这个复杂的分布式系统可靠？除了协作，我们还能用 CRDTs 做些什么？然后还有编辑器的其他部分。Ropes。我们的 GPU 加速 UI 框架。Tree-sitter。集成终端。以及更多更多。

We're looking forward to talking about all of it in the months and years to come. And more importantly, we're looking forward to applying this technology to ship an editor that makes you happier and more productive. Thanks for reading!
我们期待在未来几个月和几年里讨论所有这些内容。更重要的是，我们期待将这项技术应用于开发一款让您更快乐、更高效的编辑器。感谢阅读！