无需 CRDT 或 OT 的协同文本编辑

_Matthew Weidner | 2025年5月21日 | Keywords: text editing, server reconciliation, Articulated _

协同文本编辑可以说是协同应用中最难实现的功能。即使你使用中心服务器和完全通用的乐观本地更新解决方案（server reconciliation），特别是文本编辑也需要精巧的算法 - 具体来说，需要 text-editing CRDT 或 OT 的核心。

或者说，直到最近我才这么认为。这篇博文描述了一种替代方案，一种直接的协同文本编辑方法，无需 Conflict-free Replicated Data Types (CRDTs) 或 Operational Transformation (OT)。 通过使文本编辑灵活且易于 DIY，我希望这种方法能让你创建丰富的协同应用程序，这些应用程序很难在黑盒 CRDT/OT 库的基础上构建。

本文建立在我之前的文章 Architectures for Central Server Collaboration 的基础上，尽管我会根据需要回顾一些想法以保持其独立性。 特别是，我通常假设你的协同应用有一个中心服务器。 后面的章节 将该方法扩展到去中心化/服务器可选的协作，揭示了与几个文本编辑 CRDT 令人惊讶的联系。

与往常一样，对于协同文本编辑，本文中的任何技术也可以应用于一般的协同列表：食谱中的成分、PowerPoint 胶片、电子表格的行和列等。

来源： 我从 Thymer 的 Wim Cools 在 Hacker News 评论 中学到了这种方法的主要思想。 Jazz's CoLists 也使用了它。 我不知道对该方法有任何现有的公开描述 - 特别是，我没有在 crdt.tech 上的任何论文中找到它 - 但鉴于它的简单性，其他人可能也使用了这种方法。 扩展到去中心化协作基于 Martin Kleppmann、Victor B. F. Gomes、Dominic P. Mulligan 和 Alastair R. Beresford（2018 年）的 OpSets: Sequential Specifications for Replicated Datatypes。

核心问题

[回顾Architectures for Central Server Collaboration - Challenge: Text and Lists]

让我们首先关注协同文本编辑问题的一部分：向服务器提交操作。 当用户在其客户端设备上键入一个单词时，我们需要将此操作传达给服务器，以便服务器可以更新其自己的（权威）状态。

很容易将文本建模为字符数组，并将操作发送到服务器以对数组表示形式进行操作，例如“在索引 17 处插入 ' the'”。 但是，当有多个并发编辑器时，这会失败，如图 1 所示：

See caption

图 1. Bob 向中心服务器提交操作“在索引 17 处插入 ' the'”。 但在他的编辑到达之前，服务器应用了 Alice 的并发操作“在索引 3 处插入 ' gray'”。 因此，在索引 17 处应用 Bob 的操作不再有意义；服务器必须将其“rebase”到索引 22。

我们必须解决的核心问题是：客户端应该向服务器发送什么操作，服务器应该如何解释它们，以便服务器以“显而易见”的正确方式更新其自己的文本？

这种“索引 rebase”挑战在 Google Docs 等实时协作应用中最广为人知，但从技术上讲，它也可能影响非实时应用 - 例如，将项目插入列表的 Web 表单。 这个问题甚至可能出现在单线程本地应用中，这些应用需要转换文本/列表索引以实现内联评论和编辑历史等功能。

现有解决方案的问题

现有解决此核心问题的方案分为两大阵营：Conflict-free Replicated Data Types (CRDTs) 和 Operational Transformation (OT)。 粗略地说：

CRDT 和 OT 算法都在实践中使用。 OT 被 Google Docs 使用； Yjs CRDT 库被众多应用使用。 我个人花了几年时间思考和撰写关于文本编辑 CRDTs 和 密切 相关 算法的文章。 那么，为什么这篇博文会介绍一种不同的方法，以及它有什么优势呢？

CRDT 和 OT 的主要问题在于它们的 概念复杂性。 文本编辑 CRDT 的全序是学术论文中定义的微妙算法，通常难以阅读。 OT 算法必须满足代数“转换属性”，这些属性具有二次方个案例，并且在没有正式验证的情况下 经常存在缺陷。

复杂的算法导致更复杂的实现，CRDT/OT 实现是出了名的困难。 因此，你通常通过库来使用它们，这些库由专家实现，如果没有类似水平的专业知识，你就无法自定义它们。 因为协作是一个全栈问题，所以这些库也是全栈的，接管了你应用程序的核心部分：它们表现为一个联网的黑盒，输入操作并输出状态。

当你的应用程序需要库作者没有预料到的功能时，这种单片、不可修改的方法就成为一种负担。 例如，我很难使用现有的文本编辑 CRDT 或 OT 库来执行以下任何操作：

  1. 在磁盘和内存之间划分状态，仅加载大型文档的必要部分。
  2. 在服务器上强制执行子文档权限，例如，某些用户只能编辑某些段落或使用特定的格式。
  3. 允许 Google Docs 风格的“建议更改”，无论是内联还是在文本旁边。 （我 尝试使用我自己的 CRDT 库实现此功能，但遇到了问题，因为建议可能会从其目标文本移开 - 正是因为我无法控制 CRDT 的全序。）
  4. 将文本存储在易于通过现有键值存储（例如 Replicache）同步的键值表示形式中，而不仅仅是将整个文本存储为 blob 或将整个操作历史记录存储为数组。
  5. 支持除插入/删除之外的操作：移动文本、文档树操作、段落拆分/合并等。

相反，这篇博文中描述的方法非常简单。 我希望你很快就能充分理解它，以便在需要时自己动手做。 完成之后，你可以随意修改内部结构并添加功能。

该方法

主要思想

我们的方法的主要思想很简单：

自己验证一下，这种方法是否能以“显而易见”的正确方式处理图 1 的两个编辑。

一些修正

你可能已经注意到上述描述中的两个小问题。 幸运的是，它们都很容易纠正。

首先，当 Bob 将他的操作发送到服务器时，他还必须指定新元素的 ID：“在 f1bdb70a 之后插入 ' the'，ID 为 […]”。 换句话说，他必须告诉服务器要将哪些 { id, char } 对添加到其内部列表中，而不仅仅是新字符。 （让 Bob 生成 ID，而不是等待服务器分配它们，这使他可以在收到对其第一个操作的响应之前，在后续的“insert after”操作中引用这些 ID。）

其次，Bob 有可能发送像“在 26085702 之后插入 'foo'”这样的操作，但在他的操作到达服务器之前，另一个用户同时删除了 ID 为 26085702 的字符。 如果服务器在响应并发操作时按字面意思删除其 { id: "26085702", char: "x" } 对，那么它将不知道在哪里插入 Bob 的文本。 服务器可以通过在其内部列表中存储 ID 来解决此问题，即使在删除相应的字符之后也是如此：服务器的状态变为列表

Array<{ id: ID; char?: string; isDeleted: boolean }>.

当然，删除的条目不会显示在用户可见的文本中。

总而言之，我们更正后的客户端 -> 服务器通信方法如下：

客户端和服务器文本状态：每个存储一个由 ID 标记的字符列表，包括已删除的 ID。
- 类型：`Array<{ id: ID; char?: string; isDeleted: boolean }>`
- 对应文本：`list.filter(elt => !elt.isDeleted).map(elt => elt.char).join('')`
键入字符 `char`：
1. 客户端查找紧靠插入点之前的字符的 ID，`before`。
2. 客户端为新字符生成一个全局唯一 ID（例如，一个 UUID）：`id`。
3. 客户端向服务器发送操作：“insert ${char} after ${before} with id ${id}”。
4. 服务器按字面意思将此操作应用于其自己的状态：
 a. 在其自己的列表中查找 `before`，包括已删除的条目。
 b. 在列表中 `before` 的条目之后立即插入 `{ id, char, isDeleted: false }`。
删除字符：
1. 客户端查找已删除字符的 ID，`id`。
2. 客户端向服务器发送操作：“delete the entry with id ${id}”。
3. 服务器查找 `id` 的条目，如果尚未设置，则设置 `entry.isDeleted = true`。

你可能仍然对上述方法存在实际的担忧：例如，为每个字符存储一个 UUID 效率很低。 我将在 稍后 讨论优化。

客户端

[回顾Architectures for Central Server Collaboration - Server Reconciliation]

到目前为止，所描述的方法允许我们将操作从客户端发送到服务器，从而更新服务器的状态。 我们设法以一种直接的方式解决了 核心问题，而无需梳理任何 CRDT 或 OT 论文。

对于真正的 Google Docs 风格的协同文本编辑，我们还希望让用户立即看到他们自己操作的效果，而无需等待服务器的响应。 也就是说，应该允许客户端执行乐观本地更新。

当以下情况发生时，乐观本地更新会引起麻烦：

See caption

图 2. Bob 向中心服务器提交操作“在 <n 的 ID> 之后插入 ' the'”。 但在服务器确认他的操作之前，他收到了远程操作“在 <e 的 ID> 之后插入 ' gray'”。 Bob 的客户端应该显示什么状态，既包含远程操作又包含 Bob 的挂起的本地操作？

此时，你可能会说：我们有并发操作，客户端和服务器以不同的顺序接收它们，它们最终必须处于相同的状态。 这是否意味着我们需要一个 CRDT？

幸运的是，答案是否定的！ 乐观本地更新有一个完全通用的解决方案，server reconciliation，它特别与我们的“insert after”操作兼容。 简而言之，你响应新的远程操作 R 更新客户端的方式是：

  1. 撤消所有挂起的本地操作。 这会将状态回退到客户端先前对服务器状态的视图。
  2. 应用远程操作。 这使客户端与服务器的状态保持同步。
  3. 重做任何仍然挂起的挂起的本地操作，即它们未作为远程批处理的一部分得到确认。

Starting in optimistic local state S+L1+L2+L3, Step 1 leads to state S, Step 2 leads to state S+R, and Step 3 leads to state S+R+L1+L2+L3.

在存在挂起的本地操作 L1, L2, L3 的情况下，处理远程操作 R 的 Server Reconciliation 方法。

还有另一种比服务器协调更简单的策略：只要客户端拥有挂起的本地操作，就禁止客户端处理远程操作。 我从 PowerSync 那里了解到了这种策略。 例如，在 图 2 中，Bob 的客户端将忽略来自服务器的第一个消息，而是等待服务器处理 Bob 的消息并发送结果状态。 收到该状态后，Bob 的客户端可以直接覆盖其自己的状态。 除非 Bob 在此期间执行了更多操作 - 那么他的客户端需要忽略服务器的第二个消息并等待第三个消息，等等。 请注意，如果 Bob 连续键入或网络延迟很高，此策略可能会导致无限延迟，因此它不像服务器协调那样“实时”。

与 CRDT 的区别

你可能会反对说，上述方法听起来很像 CRDT。 它的确共享一些功能：特别是，它为每个字符分配一个 ID，并使用 isDeleted 标记（墓碑）。

区别在于，我们的方法以一种直接而灵活的方式处理顺序：客户端告诉服务器在 Y 之后插入 X，它会完全按照你的编程执行此操作，或者执行你编程的其他操作。 这与文本编辑 CRDT 形成对比，在文本编辑 CRDT 中，ID 由一个奇特的算法为你排序。 该排序算法是众多文本编辑 CRDT 之间的区别所在，也是任何 CRDT 论文中复杂的部分； 我们可以完全避免它。

讨论

上一节以我希望足够的细节描述了整个方法，以便开始自己实现它（尽管首先查看下面的 Articulated）。 现在让我们讨论该方法的后果和扩展。

并发插入

对于任何协同文本编辑算法，最有趣的理论问题是：当多个用户同时在同一位置键入时会发生什么？

例如，从文本“My name is”开始，假设 Charlie 键入“ Charlie”，同时 Dave 键入“ Dave”。 如果 Charlie 的操作首先到达服务器，那么最终文本是什么？

让我们检查一下：

总而言之，在同一位置并发插入最终会 反向 服务器收到其操作的顺序。 更一般地说，即使没有并发，具有相同目标 ID 的 insert-after 操作也会以相反的顺序结束。 例如，如果 Dave 以相反的顺序键入他的名字为（e，左箭头，v，左箭头，a，左箭头，D），那么每个操作都将是“在 <'is' 中 's' 的 ID> 之后插入”，并且结果文本将与服务器收到顺序相反：Dave。 （这可能会让你想起一个流行的 CRDT。 我将在 稍后 讨论这个问题。）

请注意，并发插入的单词“ Charlie”和“ Dave”最终一个接一个地出现，而不是逐字符交错（不像 某些文本编辑 CRDT）。 即使 Charlie 和 Dave 将每个字符作为单独的操作发送，也会奏效。 实际上，Dave 在 'D' 之后插入 Dave 中的 'a'（即，insert-after 操作引用 D 的 ID），'v' 在 'a' 之后，等等； 因此，当服务器处理这些单独的操作时，它会更新其状态为

"My name is D Charlie" -> "My name is Da Charlie"
-> "My name is Dav Charlie" -> "My name is Dave Charlie"

尽管之后出现了意想不到的“ Charlie”。

对于向后（从右到左）插入，情况并非如此：如果 Dave 和 Charlie 都大量使用左箭头键入他们的名字，并且服务器以交错的顺序收到这些操作，那么结果文本也会交错。 实际上，只有当 Charlie 和 Dave 同时在线（以便可以交错他们的消息）但顽固地忽略彼此正在进行的编辑时，才会发生这种情况。

灵活的操作

到目前为止，我描述的唯一文本编辑操作是“insert after”和“delete”，服务器按字面意思应用它们。 但是，该方法支持更多可能的操作。 实际上，由于 我们使用了服务器协调，因此服务器可以灵活地响应客户端操作做任何事情 - 客户端最终将处于相同的状态。 这与 CRDT 和 OT 算法形成对比，它们仅允许满足严格代数规则的操作。

例如，考虑上一节中的并发插入示例。 即使它满足协同文本编辑的 数学规范，最终结果“My name is Dave Charlie”也不是很合理。 一个奇特的服务器可以对 Dave 的插入做一些更智能的事情，这些插入与先前收到的并发插入位于同一位置。 例如：

  1. 忽略任何此类操作（将其视为无操作）。
  2. 将 ID 添加到内部列表，但立即将其标记为已删除。 （从用户的角度来看，这仍然是无操作，但它允许服务器处理 Dave 将来引用他早期 ID 的操作。）
  3. 插入文本，但对两个单词应用特殊格式以标记它们以供审核。
  4. 将 Dave 的编辑转换为在主文本旁边显示的“建议”。
  5. 询问 LLM 如何最好地修复文本。 （请注意，Bob 的客户端可能难以在结果状态之上重新调整任何进一步的乐观操作。）

客户端还可以发送具有比“insert after”更奇特的语义的操作，以更好地捕获用户意图 - 从而增加服务器的最终状态在并发编辑的情况下是合理的几率。 一个简单的示例是“insert before”，它是“insert after”的逆向版本。 例如，如果用户在段落上方创建一个标题，他们的客户端可以“insert before”该段落的第一个字符，以防止标题最终出现在与先前段落无关的添加项的中间。

另一个示例是“fix typo”操作，该操作仅在单词仍然存在且尚未修复的情况下才向单词添加字符。 例如，客户端告诉服务器：“在 ID 为 X 的 'color' 中的 'o' 之后插入 'u'，但前提是周围的单词仍然是 'color'”。 这样，如果另一个用户在 fix-typo 操作到达服务器之前删除了 'color'，你最终不会在任何地方找到 'u'。 （此示例避免了 Alex Clemmer 提出的问题）。

你甚至可以定义插入位置在到达服务器后会发生变化的操作。 例如，服务器可以通过将并发插入按字母顺序重新排列来处理在同一位置的并发插入。 或者，如果你为拖放添加“move”操作，那么服务器可以选择以显而易见的方式处理移动文本中的“insert after”操作 - 将它们插入到移动的文本中，而不是在原始位置插入。 这与文本编辑 CRDT 和我自己的 CRDT 式库（position-strings 和 list-positions）形成对比，它们在用户键入时立即在全局全序中修复每个字符的位置。

从技术上讲，其中一些灵活的操作可以在 CRDT 的基础上实现，方法是让服务器在客户端操作后启动自己的操作（例如，对它想要忽略的某些文本应用“delete”操作）。 但是，我不知道 CRDT 实现支持“insert before”操作、取消删除 ID 或更改 ID 在列表中结束的位置。

格式化（富文本）

富文本通过内联格式（粗体、字体大小、超链接、…）等功能增强了纯文本。 为了在我们方法中处理富文本，当用户格式化一系列文本时，我们当然希望将该范围的末尾转换为字符 ID 而不是索引：“应用从 ID X 到 ID Y 的粗体格式”。 （或者： “应用从 ID X（含）到 ID Y（不含）的粗体格式”，以便在该范围末尾的并发插入也将加粗。）

当与 ProseMirror 等富文本编辑器一起使用时，服务器可以按字面意思应用此类操作：查找 X 和 Y 的当前数组索引，并告诉本地 ProseMirror 状态加粗该范围的文本。 ProseMirror 将负责记住粗体范围，以便当服务器稍后收到在该范围内的插入时，它知道也要加粗该文本。 （除非服务器另有决定，例如，响应操作“在 ID Z 之后插入 '...'，粗体设置为 false”。）

我相信这种对我们方法的简单扩展解决了协同富文本格式的棘手冲突解决部分。 但是，我仍然建议阅读 Peritext 论文 以深入了解协同富文本的语义 - 客户端应向服务器发送什么操作，以及服务器应如何处理它们。

去中心化变体

[更多信息请参见Architectures for Central Server Collaboration - Appendix: From Centralized to Decentralized]

到目前为止，我假设你的应用程序有一个中心服务器，该服务器为操作分配一个总顺序（即服务器接收它们的顺序），并响应这些操作更新其权威状态。

如果你没有中心服务器或者你的应用程序是服务器可选的，你可以改为以 去中心化 的方式为操作分配最终的总顺序。 例如，使用 Lamport 时间戳 对操作进行排序。 然后将“按顺序处理我到目前为止收到的操作的结果”视为每个客户端上的权威状态。 我们的方法中每个字符的 ID 和“insert after”操作同样适用于这种去中心化的“非”服务器协调。

从技术上讲，由此产生的算法是一种文本编辑 CRDT：它是一种去中心化的、最终一致的协同文本编辑算法。 我希望它比典型的文本编辑 CRDT 更容易理解和实现 - 它不涉及树或数学证明 - 并且上面关于 灵活的操作 和 格式化 的说明仍然适用于去中心化设置。

尽管如此，你可能会问：如果“非”服务器协调加上我们的“insert after”操作会产生文本编辑 CRDT，那么它是哪个 CRDT？ 答案是：

我没有详细写出这些声明的证明，但如果你 与我联系，我很乐意讨论我的推理。

辅助库：Articulated

回想一下，我们的方法中每个设备的状态都是一个列表

Array<{ id: ID; char?: string; isDeleted: boolean }>;

在实践中，你通常希望将实际文本存储在其他地方 - 例如，作为 ProseMirror 状态 - 因此我们的方法实际上只需要一个列表

Array<{ id: ID; isDeleted: boolean }>;

你将在此列表中执行以下几个主要任务：

  1. 在 ID 和其当前的数组索引之间进行转换，以便你可以与文本编辑 UI（例如 ProseMirror）进行通信。
  2. 在指定的 ID 之后插入一个新的 ID。
  3. 将 ID 标记为已删除。
  4. 将状态转换为序列化形式以进行存储，并从序列化形式转换。

字面数组在任何这些任务中都不是很好。 任务 1-3 需要线性时间，并且数组的内存和存储空间很大 - 每个字符一个完整的对象和 UUID！

Articulated 是我制作的一个小型 npm 库，旨在提供帮助。 它的 IdList 数据结构提供与上述数组相同的功能，但具有类似于流行的文本编辑 CRDT 库中的优化：

作为一个附加功能，IdList 是一个 持久 数据结构。 这对于服务器协调非常有用：每个客户端都可以廉价地存储他们从服务器收到的最新状态的副本以及他们的乐观状态，从而在收到远程操作时可以轻松回滚到服务器的最后状态。

你可以查看 [文档](https://mattweidner.c