Peritext:用于富文本协作的新型CRDT


Google Docs 等协作编辑器允许人们实时处理富文本文档,当用户希望立即查看彼此的更改时,这很方便。然而,有时人们更喜欢更异步的协作方式,在这种方式下,他们可以暂时处理文档的私人副本,然后再分享他们的更新。支持 Google Docs 等服务的算法并非旨在支持此用例。
在本文中,我们介绍了 Peritext,一种提供更大灵活性的富文本协作算法:它允许用户编辑文档的独立副本,并提供一种机制,以保留用户的尽可能的意图。一旦版本被合并,该算法保证所有用户都朝着相同的合并结果收敛。
我们详细分析了需要在协作富文本编辑器中处理的各种边缘情况,并解释了为什么现有的纯文本协作算法无法正确处理它们。然后我们解释 Peritext 如何处理这些问题,并演示我们算法的原型实现。
。。。。
许多软件开发人员都熟悉 Git 分支和拉取请求形式的异步工作流。但是,Git 要求的手动合并冲突解决并不方便用户使用,尤其是对于富文本(即带有格式的文本)等复杂的文件格式。
Google Docs ( Operational Transformation )使用的协作算法假设文档具有单一的线性编辑时间线,该时间线由云服务管理。为了支持类似 Git 的分支合并工作流的异步协作,我们需要解决的一个关键问题是:我们如何将一个文档的任意两个版本,它们已经独立编辑过,并以一种保留的方式合并它们尽可能多地了解不同用户编辑背后的意图?
Peritext 是一种用于合并富文本文档版本的新颖算法。它是一种无冲突复制数据类型(CRDT),保证如果两个用户独立合并相同的两个版本,他们将收敛到相同的结果。除了异步协作之外,Peritext 还为本地优先的富文本编辑软件提供了基础,该软件的优点包括允许用户在设备离线时继续工作,并为用户提供更大的隐私、所有权和对其文件的代理权。
Peritext 不是用于异步协作的完整系统:例如,它尚未可视化文档版本之间的差异。此外,在本文中,我们只关注内联格式,例如粗体、斜体、字体、文本颜色、链接和注释,它们可能出现在单个文本段落中。在以后的文章中,我们将扩展我们的算法以支持块元素,例如标题、项目符号、块引用和表格。尽管有这些限制,但 Peritext 是实现富文本异步协作的重要一步。
 
合并难点:保留作者的意图
当作者异步协作时,算法不可能总是完美地合并编辑。举个例子,如果两位编剧正在编辑一部电视节目的剧本,对一集的改动可能需要在未来的剧集中改变情节。由于算法无法自动执行此操作,因此通常需要人工干预才能产生所需的最终结果。
但是,编写工具仍然可以极大地帮助协作过程。当两个用户独立编辑一个文档时,手动合并这些版本既乏味又容易出错。我们需要一个书写系统来帮助作者轻松且一致地执行这些合并。即使自动合并不完美,它也允许作者快速恢复彼此同步,并最大限度地减少他们花费在编写工具上的时间。
在我们实现算法来执行这种自动合并之前,我们首先需要为用户意图定义一个清晰的模型,并定义合并并发编辑时的预期结果。
  
明文插入
示例 1.让我们从一个初步示例开始:对纯文本的并发插入。想象一下 Alice 和 Bob 正在同时编辑一个文档,而不知道彼此的更改。也许 Alice 正在火车上离线编辑,或者 Bob 正在尝试在私有分支中进行一些更改。
在任何一个用户应用他们的更改之前,我们从这句话开始:
每个用户在对方不知情的情况下,在句子中的某处插入一些文本:

  • 爱丽丝:The quick fox jumped.
  • 鲍勃:The fox jumped over the dog.

稍后,两个用户同步备份,我们需要合并他们的更改。直观地,正确的合并结果是将它们的两个插入保持在相同的位置:
The quick fox jumped over the dog.

Bob 在“jumped”这个词之后插入了“␣over the dog”,所以这个词在合并句子中的那个位置结束是有道理的。插入的字符应该保持在相对于它们被插入的上下文的相同位置;文本不应仅仅因为在文档的其他地方添加或删除了某些词而移动。现有的纯文本协作算法已经实现了这种行为。
 。。。
 
现有 CRDT 的局限性
无冲突复制数据类型(CRDT) 是一种算法,允许每个用户编辑其本地文档副本,并确保不同用户的副本可以干净地合并为一致的结果。对于纯文本文件有很多CRDT算法,如RGA因果树木YATAWOOTTreedocLogootLSEQ,以及各种其他。
在构建用于管理富文本的新 CRDT 之前,我们可能会问是否可以简单地使用现有的。事实证明,虽然现有 CRDT 的一些想法对于建模格式化文本非常有用,但以天真的方式应用现有算法并不能产生上面列出的所需行为。在本节中,我们简要描述了使用现有 CRDT 表示富文本的三种方法,并强调了它们的问题。
。。。。
 
Peritext:富文本 CRDT
我们现在介绍我们在 Peritext 中进行富文本协作所采用的方法。我们分四部分描述我们的算法:
  • 使用现有的纯文本 CRDT 表示富文本文档的文本内容
  • 生成表示格式更改的 CRDT 操作
  • 应用这些操作来生成内部文档状态
  • 根据内部状态导出适合文本编辑器的文档

。。。。。

 
原型实现
我们已经实现了 Peritext CRDT 的一个工作原型,它显示在本文的顶部运行。它是用 TypeScript 实现的,代码是开源的。我们的代码是一个自包含的实现,它扩展了Automerge CRDT 库的简化版本,我们希望将来将我们的算法集成回 Automerge。该实现包含对本工作中描述的许多特定场景的测试,以及确保在大量随机编辑跟踪中收敛的自动生成测试套件。
对于编辑器 UI,我们选择基于ProseMirror构建,这是一个流行的库,已在许多协作编辑上下文中使用。它的模块化设计为我们提供了必要的灵活性,可以在适当的时候干预编辑器的数据流。我们还希望我们的 CRDT 能够与其他编辑器 UI 很好地集成,因为我们没有专门为 ProseMirror 专门设计。
目前,我们的实现有点专门针对本文中显示的一小部分标记:粗体、斜体、链接和注释。但是,我们打算将它们作为一组具有代表性的格式标记,并希望它们的行为也能扩展到其他类型的用户可配置标记。
 
结论
我们相信富文本的 CRDT 可以启用新的写作工作流,具有强大的版本控制和对同步和异步协作的支持。在这项工作中,我们已经表明,在将编辑合并到富文本文档时,传统的纯文本 CRDT 无法保留作者的意图。我们开发了一个支持重叠内联格式的富文本 CRDT,并展示了如何有效地实现它。
Peritext 只是实现异步协作系统的第一步:它只是允许自动合并富文本文档的两个版本。要实现异步协作,将需要在可视化编辑历史和更改、突出显示冲突以供手动解决以及其他功能方面进行进一步的工作。由于 Peritext 的工作原理是将文档的编辑历史记录为操作日志,因此它为将来实现这些进一步的功能提供了良好的基础。
在文本中可以找到许多类型的标记,它们可以建模为跨度,它们的语义各不相同。有些标记可以共存,有些则不能。此外,用户对标记行为的期望可能因类型而异。我们相信 Peritext 可以捕捉到这些意图,但仔细的编辑器集成对于实现用户期望至关重要。
内联格式对于像 Trello 卡片描述这样的短文本块就足够了,但较长的文档通常依赖于更复杂的块元素或分层格式,例如嵌套的项目符号点,而 Peritext 目前没有建模。需要进一步工作以确保可以合并对项目符号列表等块结构的编辑,同时保留作者意图。分层格式结构提出了关于意图保留的新问题——例如,当用户同时拆分、加入和移动块元素时会发生什么?
未来探索的另一个领域是在文档中移动和复制文本。如果两个人同时将相同的文本剪切粘贴到文档的不同位置,然后进一步修改粘贴的文本,最明智的结果是什么?
与我们交谈的作家喜欢实时协作写作工具的便利性,但也描述了异步编辑的各种变通方法。例如,一位受访者使用文档的个人副本在编辑期间保护他们的隐私。其他人缺乏版本控制工具,依靠手动加粗的文本来识别编辑器所做的更改。这些变通办法源于缺乏系统的变更跟踪导致的潜在技术匮乏。我们希望 Peritext 和其他用于富文本的 CRDT 将为这些用户启用新的工作流程,这是不可能在现有数据结构之上构建以存储文本文档的。用户可以尝试自己不同的长期运行分支,并通过强大的比较视图轻松地将它们合并在一起。人们可以选择私下工作,或阻止其他人做出的令人分心的变化。与其将文档历史视为版本的线性序列,我们还可以将其视为在细粒度更改数据库之上的大量投影视图。