本博文描述了被使用在 ProseMirror 中的协同编辑技术。而对于 ProseMirror 的介绍，你可以查看这里
协同编辑的问题
一个实时协同编辑系统表示可能有多人在同时对相同的文档进行编辑。该系统保证文档保持同步–某个用户的对文档的更改会被发送给其他用户，并将这些更改显示在他们的文档中。
由于通过任何类型的网络中传输这些更改都是需要时间的，因此此类系统的复杂性在于它们处理并发更新的方式。一个解决方案是允许用户锁定当前文档（或者文档的一部分）从而阻止其他人在同一时刻对文档的更改。但是这个机制会让强迫用户考虑关于锁的问题，并且当他们没有锁的时候（即当其他用户在编辑的时候）必须一直等待。我们不想这么做。
如果我们允许并发的更新，我们就会遇到这样一个情况：用户 A 和用户 B 同时更改了文档，并且他们并没有意识到对方对文档的更改，于是他们就必须以协商的方式来解决最终如何更新文档。A 和 B 的行为可能并不相互影响–比如他们同时编辑文档的不同部分–或者他们的行为相互影响–当他们尝试去更改同一个单词的时候。
Operational Transformation（OT，操作转换）
有关上述问题的研究很多。而且我必须承认，虽然我阅读了很多论文，但是我对这项研究一点也不了解，并且如果你发现误解了某些事情或者某些内容少了一些有趣的参考文献，那么我非常开心你能给我发一封邮件告诉我。
大量的关于这个问题的研究事实上是关于分布式系统的，一组节点相互交换消息，而没有一个中心控制节点。解决此问题的经典方法称为 「Operational Transformation」，即一种分布式算法。它定义了一种描述更改的方法，该方法有两个属性：
-
你可以相对于其他的更改来转换更改。因此，如果用户 A 插入了一个字母「O」在相对父级偏移量为 1 的位置，同时用户 B 也插入了一个字母「T」在偏移量为 10 的位置，那么用户 A 可以相对于自己的更改来转换 B 的更改，即插入「T」在 11 的位置，因为在 B 的更改偏移量的位置之前，一个额外的字符被插入了。
-
不管并发的更改应用到文档的顺序如何，大家都是最终拥有一个相同的文档。这允许 A 相对于自己的更改来转换 B 的更改，并且 B 也可以类似的转换 A 的更改，以让两个用户不会得到不同的文档。
一个 Operational Transformation（OT）系统将本地更改立即应用于本地文档，然后将更改广播给其他用户。这些用户将会在获取到广播的更改进行转换和应用。为了准确的知道远程的更改应该通过哪些本地更改进行转换，该系统还应该在广播更改的时候附带发送一些文档状态的表示。
这个过程听起来相当简单。但是它却是实现的噩梦。一旦你支持了多种琐碎的更改（比如「插入」和「删除」），保证以任何顺序执行更改后产生相同文档变得异常困难。
Joseph Gentle，一位曾经在 Google Wave 工作过的工程师，说过…
不幸的是，实现一个 OT 非常恶心。有成千上百万中算法需要做权衡取舍，而且这些算法大多数都只存在于学术论文中。要正确实现这些算法其实非常困难而且耗时。
中心化
使 OT 机制复杂的设计决策很大程度上源于对其如何对更改进行分发的需求。分布式系统无论在实践上还是在策略上，都有一些很棒的特性，并且在开发中往往很有意思。
不过，你可以通过引入一个「处理更改的中心」来减少很大的复杂性。老实说，我对 Google 将 OT 用在 Google Docs（一种中心化的系统）中表示非常不解。
ProseMirror 的算法是集中式的，因为它只有一个更改处理中心（所有的用户都连接到该中心）来决定应用更改的顺序。这使得实现协同编辑系统变得相对容易并且容易理解。
实际上我并不认为这个「中心化」的特性就是以分布式的方式运行 OT 算法的一个非常大的障碍（即 OT 的分布式算法的难点和障碍不在中心化–译者注）。你还可以用像 Raft 这样的共识算法来选择仲裁器，而不是靠一个中心化的服务来做主。（但是请注意，我实际上并没有尝试过该方式）
ProseMirror 的协同算法
与 OT 一样，ProseMirror 使用基于更改的词汇表（意即它也用 delete、insert 这类表示「更改」意思的词–译者注）并相互转换更改。不过与 OT 不同的是，它不试着去保证以不同顺序应用更改将产生相同的文档。
通过使用一个中心化的服务，甚至可以很容易地让所有客户端以相同的顺序应用更改。你可以使用一种类似于代码版本控制系统中使用的机制。当客户端有一个更改后，他们试着将更改 push 到服务端。如果服务端认为这个更改是基于当前最新的版本的，那么更改就会被接受。如果不是，那么客户端必须首先 pull 其他客户端的更改，然后在重试推送到服务器之前将自己的更改 rebase。
不像 git，文档的历史记录在这个模型中是线性的，并且文档的给定版本可以用简单的使用一个整数来表示。
与 git 还不同的是，所有的客户端都在不断的拉取（或者，推送并监听）对文档的新更改，并在网络允许的范围内尽可能快的跟踪服务器的状态。
唯一困难的部分是 rebasing 其他人的更改到自己的更改。这与 OT 所做的转换非常相似。但是这是通过客户端 自己 的更改而不是远服务端更改来完成的。
位置映射
不过，OT 会相对于 别人的更改 来转换更改，而 ProseMirror 则使用一种称为 position map（位置映射）的派生数据结构对其进行转换。无论何时你对文档应用了一个更改，你就会得到一个新的文档和上述的一个映射，该映射可以用于将旧文档中的位置转换到新文档中相应的位置。映射的最显著的使用场景是，可以用来调整光标的位置，以让其停留在相同的「概念性」位置（conceptual 不知道怎么意译–译者注）–如果一个字符被在光标之前插入，那么光标应该向前（向右）随着周围的文本移动一个位置。
转换更改完全基于位置映射完成。这其实挺好的，这意味着我们不需要写特定更改类型的转换代码。每个更改有一到三个位置信息与它相关，分别表示为 from，to 以及 at。当转换一个相对于给定的其他更改的更改时，这些位置将会通过其他更改的位置映射进行映射。
例如，如果一个字符被插入到位置 5，那么相对于该插入进行转换时，「删除从 10 到 14 的位置」的更改将会变成「删除从 11 到 15的位置」。
每个更改的位置只有在最初应用的文档版本是相同的时候才有意义。一个位置映射定义了更改前后两个文档版本中位置之间的映射关系。为了能够应用更改到不同的版本，必须通过其自身版本和目标版本之间的更改来一步步的映射它。
（为了简单起见，示例将会使用整数作为位置的表示。ProseMirror 中的实际位置由段落中的整数偏移量加上该段落在文档树中的路径组成）
Rebasing Positions
当一个端有多个未推送到远端的本地更改时，那么有意思的就来了（朱一旦口吻）。如果此时有其他人的更改进入，那么所有的本地未提交的更改需要基于这些更改进行转换。假设我们有本地修改 L1 和 L2，并将它们 rebasing 到远程修改 R1 和 R2，其中 L1 和 R1 更改自相同的文档版本。
首先，我们应用 R1 和 R2 到我们原始版本的文档中（客户端必须跟踪它们当前正在显示的文档版本–包括未推送的更改–和尚未包含这些更改的原始版本）。这个操作将创建两个映射 mR1 和 mR2。
译者注：下面这段较难理解，需要读者画图可能更直观。简单来说就是，L2 是基于 L1 对文档的修改进行位置映射（位置调整）后对文档的修改，想正确 rebasing L2，必须先将 L1 及 L1 之前（即 R1 和 R2）的对文档的修改对被影响的位置都映射（调整）一遍，这样 L2 才能获得正确的位置映射，然后在正确的位置开始修改文档。
我们可以简单的向前映射 L1 到 L1*，L1* 是 L1 通过 mR1 和 mR2 映射的版本。但是 L2 是基于 L1 在初始文档版本修改之后的文档进行修改的，因此我们对于 L2 （注：即此处对于 L1 用前面所说的简单映射即可，但是对于 L2 的处理需要接下来的步骤–译者注）必须首先将 L2 通过 mL1 （它是应用 L1 创建的映射） 向后映射（即回滚历史，mL1 的逆操作–译者注）。此时文档与 R1 开始时的文档相同，于是我们可以通过 mR1 和 mR2 来映射 L2 ，最后再通过 mL1* –前面简单应用 L1* 产生的映射–来进行映射。现在我们有了 L2*，可以将其应用于应用过 L1* 后的文档，瞧，我们已经将两个更改 rebasing 到另外两个更改了。
译者注：下面这段中，「在位置 5 插入两个字符」相当于上面的 L1，「在两个字符间（位置 6 ）再插入」相当于上面的 L2。因此 rebasing L2 的时候需要对 L2 先通过 mL1 回滚 L2 的插入位置到最开始的文档，但是此时文档并没有 L2 可映射的位置，因为此时位置还不存在。
映射删除操作和和向后映射（历史回滚–译者注）插入操作会丢失信息。如果你在位置 5 的地方插入两个字符，然后另一个人在位置 6（介于之前插入的字符之间），向后映射（历史回滚，如前所述的 L2–译者注）然后再通过最开始的插入操作向前映射将会使你（在插入这两个字符后光标）位于插入的这两个字符之前或者之后的位置，因为在插入这两个字符之间的位置不能被还没有它们的文档所表示（如何表示一个即将插入但是还未插入的字符的准确位置？–译者注）。
译者注：下面这段是本文的核心，即通过在 map 的时候提供额外的相反的 map 信息，来在当需要向后映射（历史回滚）的时候遇到需要映射到不存在位置的话先恢复该位置内容（使用该映射的镜像）然后进行映射，待其之前的映射完成之后，直接跳过这个映射（因为已经在恢复内容的时候映射完毕了），注意必须保证映射的镜像与映射的内容保持相同的大小（废话，不然位置肯定会算错）。
为了修复这个问题，ProseMirror 协同系统使用映射管道（mapping pipelines），它们不仅是一系列的映射，同时还保存了有关哪些映射是彼此的镜像这种信息。当一个位置在经过这些管道遇到一个删除了该位置周围内容的映射的时候，系统会向前（即向在之前未遇到该位置的时之前的映射–译者注）扫描管道，以查找该映射的镜像。如果找到了这样的映射我们将向前映射跳（就是正常的位置调整–译者注）到它这个位置，并使用该位置在已删除内容中的相对偏移量来恢复该映射插入的内容中的位置。删除操作的映射镜像必须和插入操作的映射镜像保持相同的内容大小。
映射的方向
无论何时插入内容，都可以将这个明确的插入点映射到两个不同的位置（这两个点都是有意义的）：插入内容之前，或者之后。有时候前者是合适的，有时候后者是合适的。ProseMirror 的位置映射系统允许开发者选择他喜欢的方向。
译者注：下面这段话讲的是，假设文档为
abc，在 a 之后，b 之前的位置插入字母 x，那么更改的from和to都为 1；插入内容之后，from向前（向左）映射仍为 1 不变，to向后（向右）映射也变成了 2。
这也是为什么和一个更改相关的位置含有几个不同的位置信息的原因。如果一个更改具有 from 和 to 的位置信息，比如删除或者设置文档某个内容的样式，若在该位置之前或者之后都有内容，那么这些内容不应该被包含到这个更改之内（这些内容只需要在更改发生后映射位置即可–译者注）。因此，from 位置应该向前（向左）映射，而 to 位置应该向后（向右）映射）。
当一个更改通过一个完全包含它的映射进行映射的时候，例如在位置 5 插入一个字符，然后该位置通过删除 2 到 10 创建的更改进行映射，那么在位置 5 插入字符这整个操作将会被简单的丢弃，因为它的上下文不复存在了。
更改类型
ProseMirror 中一个原子的改动被叫做 step（步骤）。一些从用户角度看是单个更改的更改实际上会被分解为几个步骤。例如，如果你选择文本然后按下 enter 键，编辑器将会生成 delete 步骤以删除选择文本然后接着一个 split 步骤以分割当前段落。
下面是存在于 ProseMirror 中的步骤类型：
addStyle和removeStyle增加行内样式到文档中或移除行内的样式。split将一个节点一分为二。例如，它可以被用来当用户按下 enter 键的时候分割段落。它只需要一个单独的at位置信息。join将挨着的两个节点连接起来。该步骤仅对包含相同类型内容的节点有效。它需要from和to的位置信息分别用来指向将要被连接的两个节点的尾部和起始位置（这是为了确保正确将预期的节点连接在一起。若与此同时这两个节点被插入了内容，那么这个连接步骤会被直接忽略）。ancestor被用来修改节点的类型以及增加或者删除它的祖先。可以用来包裹一个 list，或者将段落转换成标题。它需要from和to的位置指向节点的起始和结束位置。replace用零个或者多个节点替换给定文档的一部分，并可以选择在剪切的边缘位置缝合兼容的节点。它的from和to位置定义了应被删除的范围，它的at位置给定了新节点应该插入的位置。
上面所述的类型中，最后一个是最复杂的，我最初的冲动是将其拆分成移除和插入两种步骤类型。但是因为替换步骤创建的位置映射需要将步骤视为原子类型（位置必须从 所有 的替换内容中推出去），于是我通过将其视为单个步骤而取得了更好的结果。
操作的意图
一个实时协同编辑系统必要的属性是它们必须尝试保留更改的 意图。因为更改的「合并」是自动发生的，没有经过用户的交互，这就造成当你对文档的更改通过 rebasing 被重新修改变成了不是你想要的结果的时候会非常恼人。
我尝试定义这些修改步骤以及它们 rebasing 的方式，以让它们 rebasing 的时候不那么奇怪。大多数的时候更改不会相互覆盖，因此也不需要交互。但是当更改有重叠部分的时候，我们必须确保它们合并后的结果是正常的。
有些时候修改必须被简单的丢弃掉。当你在一个段落中输入，但是另一个用户在你的更改被服务端采纳之前删除了这个段落，那么你输入的有意义的上下文就没了，插入到该段落的位置将创建一个毫无意义的文档片段。
如果你尝试将两个 list 拼接在一起，但是其他人在两个 list 之间插入了一个段落，那么你想进行的操作就不可能被执行（你不能将两个不挨着的节点拼接在一起），因此你的操作会被丢弃。
在其他场景中，更改即使被修改过也仍然是有意义的。如果你将位置 5 到 10 的字符加粗，同时另一个用户在位置 7 插入了一个字符，那么最终你得到的结果是位置 5 到 11 都被加粗。
最后，一些更改可以重叠而不会相互影响。比如你将一个单词设置为超链接，同时另一个用户将其加粗，那么最终你们二者对这个单词的更改都会被应用到原始文档上去。
离线
对实时协同编辑来说，静默的修改更改或者丢掉一些更改并没有什么问题，在这种情况下反馈或多或少是即时的-—你看到你正在编辑的段落消失了，于是你就知道有人把它删除了，于是你的更改也没了。
而对于离线编辑来说（即你一直在编辑但是并没有连接到中心服务器）或者说对于一个工作流的分支来说，当你做了大量的编辑工作，之后 将其合并到其他人在此期间编辑过的文档中的时候（无论其他人如何编辑，删除，插入大量的内容，然后再删除最开始的内容等—译者注），我在此描述的这个模型是没用的（OT 也是）。因为这种场景下，（我描述的模型和 OT 都同样-—译者注）可能会默默的删除很多的编辑工作（如果编辑的上下文已经被删除的话），或者当两个用户以不同的方式编辑同一个句子的时候创建一个奇怪的文本组合。
在这种场景下，一个基于 diff 的实现可能更合适。你可能不能做自动合并—-你需要识别出冲突，然后将他们交给用户解决。比如，git 让用户做的那样。
撤销历史
在协同编辑系统中，撤销历史应该如何实现？该问题的广泛接受的答案是，它绝 不应该 使用一个单一的、共享的历史。如果你撤销编辑，那么撤销的应该是 你 做的最后一个编辑操作，而不是撤销文档最后的编辑操作。
这意味着简单的回滚到先前状态来实现文档历史的方法行不通。通过撤销你的更改的状态（如果此时其他人也进行了更改）是一种之前未见过的新的状态（即不是文档历史中的任一以中状态–译者注）。
为了能够实现这一点，我必须定义一种能够被反转的更改（多个步骤），该反转会产生一个新的步骤，该步骤代表了可以抵消原始步骤的更改。
ProseMirror 的撤销历史记录累积了相反的步骤，并且还跟踪了他们与当前文档版本之间的所有的位置映射。为了能反向映射到当前文档版本，这是必须的。
不过不利的一面是，如果用户进行了更改然后空闲了下来，在此期间其他人对文档进行了更改，那么将此用户的更改变成当前版本的文档的位置映射将无限制的堆积起来。为了解决这个问题，历史记录会定期进行 压缩，将反转的更改向前映射，以使他们再次从当前文档开始编辑。这会丢弃中间过程的位置映射。
