CRDT是否适合共享编辑？

CRDT经常被誉为构建协作应用程序的圣杯，因为它们不需要中央权威机构来解决同步冲突。它们为扩展后端基础设施提供了新的可能性，也非常适合作为根本不需要服务器的分布式应用程序的数据模型。

但是，一些文本编辑器开发人员报告说不使用它们，因为它们会带来太大的开销。

就在最近，Marijn Haverbeke写到了他反对将CRDT用作CodeMirror 6的数据模型的考虑：

[..]。这种表示的成本很高，最后，我认为收敛位置的要求太模糊了，无法证明额外的复杂性和内存使用水平是合理的。(来源)。

XI编辑器使用CRDT作为其数据模型，以允许不同的处理(语法高亮、类型检查器等)。在不阻塞进程的情况下并发访问编辑器状态。他们恢复到同步模型，因为..。

显然，每个人都认识到CRDT有很大的潜力，但他们得出的结论是，使用它们的内存开销对于现实世界的应用程序来说肯定太昂贵了。

他们提出了一个合理的观点。大多数CRDT为文档中创建的每个字符分配唯一的ID。为了确保文档始终能够收敛，即使在删除字符时，CRDT模型也会保留此元数据。

在JavaScript这样的动态语言中，这似乎特别昂贵。其他语言允许您使用结构(例如C或Rust)在内存中高效地表示所有这些字符和ID。在JavaScript中，所有内容都表示为一个对象-基本上是一个需要跟踪其所有键和值的键值映射。CRDT为文档中的每个字符分配多个属性，以确保冲突解决。仅将文档表示为CRDT的内存开销可能是巨大的。

每次用户交互都会创建更多的元数据，CRDT需要保留这些元数据以确保冲突解决。CRDT创建数百万个对象来存储所有这些元数据的情况并不少见。JavaScript引擎管理堆上的这些对象，检查它们是否被引用，如果可能，垃圾收集它们。另一个主要问题是，随着对象创建数量的增加，创建其他对象的成本呈指数级增加。这如下图所示：

所以问题来了，CRDT是否真的适合网络上的共享编辑，或者它们是否强加了太高的成本，以至于在实践中不可行。

如果您不认识我，我是名为YJS的CRDT实现的作者，该实现专门为在Web上构建共享编辑应用程序而设计。

在本文中，我将向您介绍CRDT的一个简单优化，并研究使用YJS进行共享编辑的确切性能权衡。我希望让您相信，即使对于具有较长编辑历史的大型文档，开销实际上也非常小。

YJS是使用CRDT作为数据模型构建协作应用程序的框架。它有一个不断发展的扩展生态系统，可以使用不同的编辑器(ProseMirror、Remirror、Quill、CodeMirror等)、不同的网络技术(WebSocket、WebRTC、Hyper等)和不同的持久层(IndexedDB、LevelDB、Redis等)实现共享编辑。大多数共享编辑解决方案都绑定到特定的编辑器和特定的后端。使用YJS，您可以通过您的自定义通信通道、对等的WebRTC网络或可伸缩的服务器基础设施，使任何受支持的编辑器协作并交换文档更新。我对这个项目的愿景是，您可以简单地使用对您的项目有意义的技术来组合您的协作应用程序。

这不仅仅是一些很酷的原型副项目。YJS是一项久经考验的技术，几家公司都使用它来实现协作。我在这里只提到我的赞助商：

我维护了一组可重现的基准测试，用于比较不同的CRDT实现。YJS是迄今为止基于Web的CRDT实现中速度最快、编码效率最高的。在本文中，我将经常将CRDT-Benchmark存储库中包含的特定基准称为，例如，"；[B1.11]"；。

您很可能已经熟悉了CRDT如何工作的一般概念。如果不是，如果你想潜入这个兔子洞，我推荐这个有趣的互动系列：

描述YJS'；冲突解决算法YATA的概念文件可以在Researchgate上找到。这里讨论的概念非常通用，几乎可以扩展到任何CRDT。

为了确定性能成本，我们将检查YJS是如何维护数据的。请允许我描述CRDT模型是如何使用JavaScript对象表示的。这将在稍后进行相关讨论。

与其他CRDT类似，YATA CRDT为每个字符分配唯一的ID。然后在双向链表中维护这些字符。

唯一ID是Lamport时间戳。它们由唯一的用户标识符和随着每次字符插入而增加的逻辑时钟组成。

当用户从左到右键入内容"；ABC"；时，将执行以下操作：INSERT(0，"；A"；)·INSERT(1，"；B"；)·INSERT(2，"；C"；)。对文本内容进行建模的YATA CRDT的链表如下所示：

请注意，如何通过唯一的client-id和不断增加的时钟计数器的组合来唯一标识每个字符。

YJS将链接列表的项表示为Item对象，其中包含一些内容(在本例中为字符串)、唯一ID、指向相邻Item对象的链接以及与CRDT算法相关的其他元数据。

所有CRDT都会为每个字符分配某种类型的唯一ID和附加元数据，这对于大型文档来说非常耗费内存。我们不能去掉元数据，因为它是解决冲突所必需的。YJS还唯一地标识每个字符并分配元数据，但可以高效地表示此信息。较大的文档插入被表示为单个Item对象，使用字符偏移量来单独唯一地标识每个字符。下面的项将字符"；A"；唯一标识为{CLIENT：1，CLOCK：0}，将字符"；B"；唯一标识为{CLIENT：1，CLOCK：1}，依此类推。

如果用户将大量内容复制/粘贴到文档中，则插入的内容由单个项目表示。此外，可以将从左向右书写的单字符插入合并到单个项目中。重要的是，我们能够在不丢失任何元数据的情况下拆分和合并项目。

这种类型的CRDT模型的复合表示及其拆分功能已在用于智能和大规模协作系统的字符串CRDT算法中首次描述。YJS对YATA采用了这种方法，并且还包括合并Item对象的功能。

记住了这个简单的优化，让我们来看看文档上的修改次数与需要保留的元数据数量之间的关系。我们将通过创建的Item对象的数量来衡量元数据，并在稍后检查单个Item的成本。

用户与文本编辑器的每次交互都可以表示为插入或删除操作。

INSERT(INDEX：NUMBER，CONTENT：STRING)任何大小的插入都会创建集成到文档中的单个项目。在某些情况下，集成需要拆分现有项目。因此，我们每次插入最多只能创建两个项目。

DELETE(INDEX：NUMBER，LENGTH：NUMBER)删除项目仅将其标记为已删除。即item.delete=true。因此，由于可以删除Item.content，因此项目删除是自由的，并且将减少使用的内存量。该项目不需要保留用于解决冲突的内容。但删除一定范围的内容可能需要拆分两个现有项目。因此，删除的成本也是最多创建两个项目。

通过使用CRDT的复合表示，元数据的量仅与用户产生的操作量有关。而不是插入的字符量。这在实践中产生了巨大的不同。大多数较大的文档都是通过复制粘贴现有内容或将段落移动到其他位置来创建的。任何类型的操作，即使是复制-粘贴和撤消/重做，也最多只能创建两个Item对象。

YJS还支持富文本和结构化文档。上述关于元数据量仅与操作量有关的说法对于这些类型的文档仍然有效。但是，为更复杂的作业衡量作业成本不在本文的讨论范围之内。实践中一个有趣的观察是，结构化文档(例如，使用与ProseMirror编辑器的y-prosemirror绑定)上长时间运行的编辑会话的文档大小实际上比线性文本文档小得多。这是由于在YJS中发挥作用的其他优化，可能会在另一篇博客文章中进行研究。

通过CRDT可以处理的每秒(并发)操作量来衡量性能已经成为学术研究中的常见做法。这可能是具有高吞吐量的数据库应用程序的重要基准。但在共享编辑应用程序中，相对较少的用户每秒只会产生几个操作。因此，单个操作的集成过程花费1纳秒还是100纳秒都无关紧要。此外，冲突很少发生，因为大多数CRDT的地址字符相对较多，并且只有当两个用户同时在同一位置插入字符时才会发生冲突。

当我们仅使用特定场景(例如，在随机位置插入的数量)对性能进行基准测试时，我们最终可能会得到仅在此特定场景中表现良好的CRDT。在实践中，其他性能特征也起到一定的作用。我尝试在CRDT-Benchmark存储库中捕获不同场景中的相关性能特征。它表明，一些CRDT在某些场景中表现良好，但在其他场景中表现不佳。例如，RGA实现在附加内容时执行得很好，但在仅预先添加内容时运行时行为非常糟糕。用于共享编辑的CRDT应该在所有情况下都能很好地执行。下面的列表描述了共享编辑应用程序的生命周期，并更深入地了解了不同性能特征之间的相关性。

文档是从网络或本地文件加载的。解析编码文档通常需要相当长的时间，尤其是在文档很大的情况下。ParseTime表示解析编码文档所需的时间。在我看来，parseTime是最重要的性能特征，因为它会在应用程序开始时阻塞进程。所有其他任务都可以在用户不工作时执行。

该文档与其他对等方同步。如果文档是在脱机状态下修改的，则可能会发生冲突。[B2]基准测试仅测量由两个客户端(例如，在客户端-服务器环境中)产生的同步冲突。[B3]基准衡量同步多个客户端之间的冲突(P2P环境中可能发生的同步冲突)所需的时间。在大多数CRDT实现中，加载文档时需要再次解决同步冲突；因此在查看基准时要特别注意parseTime。

用户将更改应用于本地文档。YJS使用链表表示文档中的字符。除非编辑器直接使用CRDT模型，否则编辑器将使用索引位置应用INSERT和DELETE操作。CRDT实现需要遍历其内部表示以查找位置、执行更改，然后生成发送给其他对等点的更新。时间表示执行特定任务所需的时间(例如，追加一百万个字符、同步N个并发更改等)。[B1]基准模拟单个用户在文档上执行更改，而不会实际产生冲突。它表明，当涉及到在文档上简单地应用更改时，一些CRDT有很大的开销。

协作者向远程对等点发送文档更新。我们假设在远程对等点上应用单个更新不会花费大量时间。应用多个操作包含在[B2]和[B3]基准中。大多数CRDT实现都支持某种形式的增量更新功能。每个更改都会产生一个发送给其他对等方的小更新。AvgUpdateSize表示文档更新的平均大小。它只是确认CRDT会产生小幅增量更新。

文档存储在数据库中或发送到远程对等点。EncodeTime表示将文档转换为二进制表示所需的时间。DocSize表示编码文档的大小。

CRDT基准自述文件显示了与共享编辑相关的许多不同方案的性能特征。在本文中，我们只介绍几个衡量最相关性能特征的基准：

Mem在应用所有更改后使用JavaScript引擎的堆大小。在CRDT基准存储库中，memUsed只是所用内存的近似值，因为我们不能可靠地运行垃圾收集器来删除以前基准的痕迹。我单独运行了本文的基准测试，并在性能检查器中直接测量了堆大小，以获得更准确的结果。

DocSize编码文档的大小。YJS有一个非常高效的编码器，可以将Item对象写入二进制压缩格式。它通过网络(WebSocket、HTTP、WebRTC等)发送。其他客户端，所以我们希望确保文档大小是合理的。

ParseTime解析编码文档所需的时间。收到来自网络的编码文档后，我们希望尽快呈现它。因此，我们希望在合理的时间内对其进行解析。

在YJS的最好情况下，用户从左到右编写内容。在这种情况下，所有操作都合并到单个项目中。

绝对最糟糕的情况是用户从右向左书写内容。虽然这在某些语言中并不是不可能的，但是复合表示的当前实现不能应用，并且每次插入都会创建一个项。这个场景准确地反映了YJS在没有复合优化的情况下的性能开销。

在编写大型文档时，用户通常会产生多少插入操作？如果我在一个文件中从头开始编写YJS，我将编写大约200k个字符。整个CodeMirror源代码由568k个字符组成。好吧，假设YJS在从右向左书写时需要处理一百万个插入操作。这相当于一个非常大的文件。情况有多糟？

我们担心YJS使用太多内存来表示所有这些Item对象。毕竟，JavaScript中的内存使用效率似乎很低，而且我们还必须担心创建JavaScript对象的时间呈指数级增长。

为了对最坏的情况进行基准测试，我们将通过在位置0产生一百万个单字符插入操作来创建一百万个Item对象：

将*作为Y从'；yjs'；const ydoc=new Y.Doc()const ytext=ydoc.getText('；Benchmark'；)//从右向左插入一百万个字符(let i=0；i<；1000000；i++){ytext.insert(0，'；y'；)}//将ydoc转换为其二进制表示const encodeAsUpdateV2(Ydoc)const docSize=encodedDocument.byteLengthconsole.log(`docSize：${docSize}bytes`)//=>；1,000,046字节//测量加载包含1M个字符的yjs文档的时间const start=Date.now()const ydoc2=new Y.Doc()Y.applyUpdateV2(ydoc2，

事实证明，最坏的情况并不是太糟糕。YJS不会消耗过多的内存。我想说，考虑到应用于文档的更改数量，112MB的总内存消耗是相当可以忍受的。在不到400ms的时间内解析这样大小的文档似乎也没有那么糟糕。请记住，这对YJS来说绝对是最糟糕的情况。

我展示了元数据的数量只与产生的更改数量有关，而与插入的内容数量无关。正确地看待一百万次插入：一台键盘压力测试机需要139小时，每分钟120次击键才能生成一百万次插入。

JavaScript对象的工作方式类似于键值映射。这意味着每个对象都需要跟踪其所有关键点，并将它们映射到各自的值。C-struct不需要将键保留在内存中，只需要以有效的编码格式保存值。因此，当在JavaScript中使用大量对象时，自然会有很多恐惧。但是JavaScript引擎中的对象表示实际上相当高效。当您创建许多具有相同结构的对象(它们都有相同的键条目)时，JavaScript引擎表示它们的效率几乎与C-Structs一样高。在V8/Chrome中，这种优化称为隐藏类。在SpiderMonkey/Firefox中，同样的优化被称为形状。这种类型的优化确实比Web更古老，是所有JavaScript运行时引擎的一部分。因此，对象表示不是我们需要担心的问题。

让我们回到最坏的情况，检查一下每件物品到底消耗了多少内存。

一个Item由一些内容(在本例中为ContentString)和一个ID对象组成。反过来，ID由一个不断增加的数字时钟和一个在此场景中不变的数字客户端标识符组成。因此，我们只有100多万(数量)个对象。因此，每个项目的成本是88字节的内存使用量(不包括其内容)。您可以将Item、ID和(Number)的浅尺寸相加得到这个数字，然后除以项目数量。除了插入的字符串的大小之外，每个ContentString对象还消耗16个字节。

另外5.2Mb仅用于使用数组对这些项进行索引。通常，与创建的项目量相比，所需的索引信息量可以忽略不计。

基于Web的CRDT实现的性能与其创建的对象数量直接相关。分析最坏情况下的运行时性能，我们可以观察到40%的时间用于执行V8内存清理(主要和次要GC)。

这是动态编程语言的一大缺点。但是，在下一节中，我们将看到我们的优化减少了实际创建对象的次数，因此也显著提高了性能。

YJS针对人类输入行为进行了优化。一个非常明显的观察是，文本通常是从左到右插入的。虽然我们经常需要纠正拼写错误，但我们倾向于删除整个单词，然后重新开始。YJS利用了这一行为，并通过表示单个项目中的连续插入来优化批量插入。复制-将巨大的文本块粘贴到文档中也只创建单个项目。此外，删除是自由的，并且减少了使用的内存量。正如我们在实际工作中所看到的那样，这些优化在实践中产生了巨大的差异。

.