CRDT 速度提高 5000 倍：优化冒险

法国的一些研究人员进行了比较，展示了可以使用各种 CRDT 和 OT 算法实现并发编辑的多种方法。他们对所有这些进行了基准测试。 （哇，是的！）一些算法运行得相当好。但其他人需要 3 秒以上的时间来处理编辑会话中的简单粘贴操作。哎呀！那是什么算法？好吧，这很尴尬，但是..这是我的。我的意思是，它不是我发明的 - 但它是我用于 ShareJS 的算法。我们用于 Google Wave 的算法。算法 - 坚持 - 我知道一个事实并没有花费 3 秒来处理大型粘贴事件。这里发生了什么？我仔细看了看那张纸。在他们的实现中，当用户粘贴一大块文本（如 1000 个字符）时，他们的代码将插入拆分为 1000 个单独的操作，而不是使用 1000 个字符创建 1 个操作。并且这些操作中的每一个都需要单独处理。 Do'h - 当然，如果你这样做会很慢！这不是操作转换算法的问题。这只是它们特定实现的问题。令人气愤的是，有几个人给我发了这篇论文的链接，并（尖锐地）问我对此有何看法。写成一篇已发表的科学论文，这些速度比较似乎是关于宇宙的一个事实。而不是它们的真正含义 - 一些 Java 代码的实现细节，由一个可能过度紧张的研究人员编写。他们需要编码的一大堆实现中的一个。 “不！同行评审的科学不是每个人都正确！请相信我！”。但是我没有发表论文来证明我的主张。我有工作代码，但感觉没有一个聪明的计算机科学人员关心这个。我是谁？我不是人。当我们考虑 CRDT 和其他协作编辑系统时，我们会遇到语言问题。我们将每个系统描述为一个“算法”。 Jupiter 是一种算法。 RGA 是一种算法。但实际上有两个非常独立的方面：并发编辑的黑盒行为。当两个客户端同时编辑相同的文本区域时，会发生什么？它们是否合并，如果合并，按什么顺序合并？都有些什么样的规矩？

系统的白盒实现。我们使用什么编程语言？什么数据结构？代码优化得如何？如果我的实现运行缓慢，那实际上告诉我们什么？也许这就像测试。通过的测试套件表明，但永远不能证明没有错误。同样，缓慢的实现表明，但永远不能证明系统的每个实现都会很慢。如果您等待的时间足够长，就会有人发现更多错误。而且，也许有人可以设计出更快的实现。我已经将我的旧文本 OT 代码翻译成 C、Javascript、Go、Rust 和 Swift。每个实现都具有相同的行为和相同的算法。但性能甚至不接近。在 javascript 中，我的转换函数每秒运行大约 100 000 次。不错！但是 C 中的相同函数每秒执行 20M 次迭代。那快了 200 倍。哇！学者们是在测试这段代码的慢版还是快版？也许，在没有注意到的情况下，他们有一些算法的快速版本和其他算法的慢版本。从纸上看是不可能的！如您所知，我最近对 ​​CRDT 产生了兴趣。我认为它们是协作编辑的未来。也许所有软件的未来 - 但我还没有准备好谈论这个。你在学术论文中读到的大多数 CRDT 都非常缓慢，十年前我决定停止阅读学术论文并驳回了它们。我认为 CRDT 有一些固有的问题。每个角色的 GUID？疯狂来自那些陌生的土地！但是——承认这一点很尴尬——我想我和那些研究人员犯了同样的错误。我正在阅读描述不同系统行为的论文。我认为这意味着我们知道如何以最佳方式实施这些系统。哇，我错了。错到什么程度？好。运行此编辑跟踪，Automerge（一种流行的 CRDT，由一位受欢迎的研究人员编写）需要近 5 分钟才能运行。我有一个新的实现，可以在 56 毫秒内处理相同的编辑跟踪。那是 0.056 秒，快了 5000 多倍。这是我从优化工作中获得的最大速度提升 - 我对此感到非常高兴。让我们谈谈为什么 automerge 目前很慢，我将带您完成使其超快的所有步骤。

Automerge 是一个帮助您进行协作编辑的库。它由马丁·克莱普曼 (Martin Kleppmann) 撰写，他的著作和出色的演讲让他颇有名气。 Automerge 基于一种称为 RGA 的算法，如果您对此感兴趣，可以在学术论文中阅读该算法。 Automerge（以及 Yjs 和其他 CRDT）将共享文档视为字符列表。文档中的每个字符都有一个唯一的 ID，每当您插入到文档中时，您都会为要插入的内容命名。假设 Mike 在 a 和 b 之间插入了一个“X”，所以我们得到“aXbc”。然后我们有： 注意 'X' 和 'b' 都共享同一个父节点。当用户在文档中的同一位置同时键入时，就会发生这种情况。但是我们如何确定哪个角色先出现呢？我们可以使用他们的代理 ID 或其他东西进行排序。但是啊，如果我们这样做，文档最终可能会变成 abcX，即使 Mike 在 b 之前插入了 X。那真的会很混乱。 Automerge (RGA) 通过巧妙的技巧解决了这个问题。它为每个项目添加一个额外的整数，称为序列号。每当你插入一些东西时，你将新项目的序列号设置为比你见过的最大序列号大 1：这是“哇，我看到一个序列号，它竟然这么大！”的算法版本。 “是吗？我的更大！”规则是子项首先根据它们的序列号排序（更大的序列号在前）。如果序列号匹配，则更改必须是并发的。在这种情况下，我们可以根据代理 ID 对它们进行任意排序。 （我们这样做是为了让所有对等方最终得到相同的结果文档。）

Yjs - 我们稍后会看到更多 - 实现了一个名为 YATA 的 CRDT。 YATA 与 RGA 相同，只是它通过稍微不同的 hack 解决了这个问题。但这里的区别并不重要。当一个项目有多个子项时，先按序列号再按 ID 对它们进行排序。结果列表（或文本文档）可以通过使用深度优先遍历来展平树来制作。那么你应该如何实现自动合并呢？ automerge 库以一种显而易见的方式完成它，即将所有数据存储为一棵树。 （至少我是这么认为的——在输入“abc”之后，这是 automerge 的内部状态。呃，呃，我不知道这里发生了什么。那些 Uint8Arrays 到处做什么？无论如何。）自动合并库有效通过构建项目树。对于一个简单的基准测试，我将使用 Martin 自己制作的编辑跟踪来测试 automerge。这是马丁打字学术论文的逐字记录。此跟踪中没有任何并发​​编辑，但用户几乎从未真正将光标放在完全相同的位置并无论如何键入，所以我不太担心这一点。我也只计算在本地应用此跟踪所需的时间，这并不理想，但可以。如果您喜欢这类事情，Kevin Jahns（Yjs 的作者）在这里有一个更广泛的基准测试套件。这里的所有基准测试都是在我的 chonky ryzen 5800x 工作站上完成的，在合适的时候使用 Nodejs v16.1 和 rust 1.52。 （剧透！）编辑轨迹有 260 000 次编辑，最终文档大小约为 100 000 个字符。正如我上面所说，自动合并需要不到 5 分钟的时间来处理此跟踪。这只是每秒 900 次编辑，这可能没问题。但是当它完成时，automerge 正在使用 880 MB 的 RAM。哇！这是每次按键 10kb 的内存。在高峰期，automerge 使用了 2.6 GB 的 RAM！

为了了解有多少开销，我将把它与基准基准进行比较，在基准基准中，我们只是将所有编辑直接拼接到一个 javascript 字符串中。这丢弃了我们进行协作编辑所需的所有信息，但它让我们了解 javascript 的运行速度。事实证明，在 V8 上运行的 javascript 速度很快：这是一个图表，显示了在整个测试过程中处理每个操作所花费的时间，以 1000 个操作为一组进行平均。我认为这些峰值是 V8 的垃圾收集器试图释放内存。在接近尾声的最慢峰值中，一次编辑需要 1.8 秒的处理时间。钱币。在真实的应用程序中，整个应用程序（或浏览器选项卡）有时会在您打字的过程中冻结几秒钟。当我们将所有内容平均并缩放 Y 轴时，图表更易于阅读。我们可以看到平均性能随着时间的推移逐渐（大致线性地）变差。 Automerge 大量使用 Immutablejs。 Immutablejs 是一个库，它为 javascript 对象提供类似 clojure 的 copy-on-write 语义。这是一组很酷的功能，但 V8 优化器和 GC 努力优化使用 immutablejs 的代码。因此，它会增加内存使用量并降低性能。 Automerge 将每个插入的字符视为一个单独的项目。还记得我之前谈到的那篇论文，复制+粘贴操作很慢吗？ Automerge 也是如此！ Automerge 从来没有考虑过性能。他们的团队正在研究算法的替代 Rust 实现来运行 wasm，但在撰写本文时它尚未落地。我让 master 分支正常工作，但是在它准备好之前他们有一些问题需要解决。切换到 automerge-rs 后端不会使此测试中的平均性能更快。 （尽管它确实将内存使用量减半并平滑了性能。）

我们如何让计算机在这里做更少的工作？通过检查代码和改进许多小事情，可以获得很多性能上的胜利。但是 automerge 团队有正确的方法。最好从宏优化开始。在开始优化单个方法之前修复核心算法和数据结构。当您要在重写时将其丢弃时，优化函数是没有意义的。到目前为止，Automerge 最大的问题是其复杂的基于树的数据结构。我们可以用更快的方式替换它。幸运的是，有一种更好的方法来实现 CRDT，这是 Yjs 中首创的。 Yjs 是由 Kevin Jahns 制作的另一个（竞争）开源 CRDT 实现。它速度快，文档齐全，制作精良。如果我今天要构建支持协作编辑的软件，我会使用 Yjs。 Yjs 不需要整篇博文来讨论如何使其更快，因为它已经非常快了，我们很快就会看到。它通过使用一个聪明的、明显的数据结构“技巧”到达那里，我认为该领域的其他人都没有注意到。而不是像 automerge 那样将 CRDT 实现为树： state = { { item : 'a' , id : [ 'seph' , 0 ] , seq : 0 , children : [ { item : 'X' , id , seq ,孩子：[]}，{项目：'b'，id，seq，孩子：[{项目：'c'，id，seq，孩子：[]}]}]}}状态=[{项目：'a' , id : [ 'seph' , 0 ] , seq : 0 , parent : null } , { item : 'X' , id , seq , parent : [ 'seph' , 0 ] } , { item : 'b' , id , seq , parent : [ 'seph' , 0 ] } , { item : 'c' , id , seq , parent : [ . . ] } ] 这看起来很简单，但是如何在列表中插入一个新项目呢？使用自动合并很容易：

从父项之后开始，遍历列表直到我们找到应该插入新项的位置（？）本质上，这种方法只是一种花哨的插入排序。我们正在实现一个带有列表的列表 CRDT。天才！这听起来很复杂 - 你如何确定新项目应该去哪里？但它的复杂性与数学的复杂性相同。这很难理解，但是一旦你理解了它，你就可以在大约 20 行代码中实现整个插入功能：（但是如果这看起来很混乱，请不要惊慌——我们可能适合当今地球上理解这段代码的每个人进入一个小会议室。) const automergeInsert = ( doc , newItem ) => { const parentIdx = findItem (doc , newItem . parent ) // (1) // 扫描查找插入位置 let i for (i = parentIdx + 1 ; i < doc . content . length ; i ++ ) { let o = doc . content [i ] if (newItem .seq > o .seq ) break // 优化。 let oparentIdx = findItem (doc , o . parent ) // 我们应该在这里插入吗？ （警告：黑魔法部分） if (oparentIdx < parentIdx || (oparentIdx === parentIdx && (newItem . seq === o . seq ) && newItem . id [ 0 ] < o . id [ 0 ] ) ) ) 中断 } // 我们找到了位置。插入位置 *i*。博士。内容 。 splice (i , 0 , newItem ) // (2) // .. 并进行各种簿记。我在我的实验性参考 crdts 代码库中使用这种方法实现了 Yjs 的 CRDT (YATA) 和 Automerge。这是插入功能，还有一些注释。这个函数的 Yjs 版本在同一个文件中，如果你想看看。尽管是非常不同的论文，但插入的逻辑几乎相同。尽管我的代码非常不同，但这种方法在语义上与实际的自动合并、Yjs 和 sync9 代码库相同。 （模糊器验证（TM））。如果你有兴趣更深入地了解这一点，我在几周前的一次编织会议上讨论了这种方法。

我们可以使用平面数组来存储所有内容，而不是不平衡的树。这使得计算机处理的一切都变得更小、更快。代码真的很简单。更快更简单移动帕累托效率前沿。这样做的想法是罕见的，而且是真正的黄金。您可以像这样实现很多 CRDT。 Yjs、Automerge、Sync9 和其他工作。您可以在同一个代码库中实现许多列表 CRDT。在我的参考 crdts 代码库中，我同时实现了 RGA（自动合并）和 YATA（Yjs）。他们共享他们的大部分代码（除了这个函数之外的所有代码）并且他们在这个测试中的表现是相同的。理论上，当在文档中的同一位置存在并发插入时，该算法会减慢速度。但这在实践中真的很少见 - 您几乎总是在父项之后插入。使用这种方法，我对 automerge 算法的实现比真正的 automerge 快了大约 10 倍。而且它的内存效率提高了 30 倍：我希望我可以将所有这些差异归因于这个甜美而简单的数据结构。但是这里的很多区别可能只是 immutablejs 对自动合并进行了处理。我们现在正在使用干净且快速的核心数据抽象，但实现仍然不快。我们需要修复此代码库中的两大性能瓶颈：

为了理解为什么这个代码是必要的，假设我们有一个文档，它是一个项目列表。 state = [ { item : 'a' , isDeleted : false , id : [ 'seph' , 0 ] , seq , parent : null } , { item : 'X' , isDeleted : false , id , seq , parent : [ ' seph', 0 ] } , { item : 'b' , isDeleted : true , id , seq , parent : [ 'seph' , 0 ] } , { item : 'c' , isDeleted : false , id , seq , parent : [ 'seph' , 1 ] } , ... ] 其中一些项目可能已被删除。我添加了一个 isDeleted 标志来标记哪些。 （不幸的是，我们不能只是从数组中删除它们，因为其他插入可能依赖于它们。（天哪！但这是另一天的问题。）想象一下，文档中有 150 000 个数组项，代表 100 000 个字符t被删除了。如果用户在文档中间（文档位置50 000处）键入一个'a'，那它对应于我们数组中的什么索引？要找出来，我们需要扫描文档（跳过已删除的items) 来找出正确的数组位置。因此，如果用户在位置 50 000 处插入，我们可能必须线性扫描过去 75 000 个项目或其他东西才能找到插入位置。哎呀！如果数组当前有 150 000 个项目, javascript 将需要在数组中向前移动新项目之后的每个项目。这部分发生在本机代码中，但是当我们移动这么多项目时，它仍然可能很慢。（旁白：V8 实际上在这部分，所以也许 v8 没有在内部使用数组来实现ent 数组？谁知道呢！）但一般来说，将一个项目插入一个包含 n 个项目的文档将需要大约 n 个步骤。等等，不 - 比这更糟糕，因为删除的项目仍然存在。插入一个曾经有 n 个项目的文档需要 n 个步骤。这种算法相当快，但每次击键都会变慢。插入 n 个字符将花费 O(n^2)。

如果我们放大上图，您可以看到这一点。这里发生了很多事情，因为 Martin 的编辑位置在文档周围跳来跳去。但是向右上方有很强的线性趋势，这就是我们在插入时间为 O(n) 时所期望的：为什么特别是这种形状？为什么性能在接近尾声时变得更好？如果我们简单地绘制整个编辑跟踪中每次编辑发生的位置，使用相同的分桶和平滑，结果是一条非常熟悉的曲线：看起来应用更改所花费的时间主要取决于扫描文档数组所花费的时间。我们能解决这个问题吗？我们可以！ “我们”是指 Kevin 在 Yjs 中解决了这些问题。他是怎么做到的？凯文通过思考人类实际上如何编辑文本文档来解决第一个问题。通常在我们打字的时候，我们实际上并不会在文档周围跳来跳去。 Yjs 不会在每次编辑时扫描文档，而是缓存用户进行编辑的最后一个（索引、位置）对。下一个编辑可能与上一个编辑非常接近，因此 Kevin 只需从上一个编辑位置向前或向后扫描。这对我来说听起来有点狡猾 - 我的意思是，这是一个很大的假设！如果编辑随机发生怎么办？！但是人们实际上不会随意编辑文档，因此它在实践中效果很好。 （如果两个用户同时编辑文档的不同部分怎么办？Yjs 实际上存储了一整套缓存位置，因此无论他们在文档中的哪个位置进行更改，每个用户附近几乎总是有一个缓存的光标位置。 ) 一旦 Yjs 找到目标插入位置，它需要高效插入，而不是复制所有现有项目。 Yjs 通过使用双向链表而不是数组来解决这个问题。只要我们有一个插入位置，链表就允许在恒定时间内插入。

Yjs 还做了一件事来提高性能。人类通常会输入一系列字符。因此，当我们在文档中键入“hello”时，而不是存储： state = [ { item : 'h' , isDeleted : false , id : [ 'seph' , 0 ] , seq , parent : null } , { item : ' e' , isDeleted : false , id : [ 'seph' , 1 ] , seq , parent : [ 'seph' , 0 ] } , { item : 'l ......