原文地址: josephg.com/blog/crdts-… 作者: Seph Gentle (闻名开源框架 sharedb/ottypes 作者)
译者简评:
这是一篇介绍 CRDTs 数据结构及对应算法优化的文章,根据主流开源框架: automerge 、 yjs 展开,后边介绍作者在它们之上所做的一些创造性的优化: diamond-types ,是一篇十分有深度的文章。
榜首部分:主要介绍了 automerge 在数据结构及算法在功用上的一些中心问题,以及当下它为什么没有很快被处理。
第二部分:重点论述了 Yjs 双向链表数据结构挑选处理的问题及功用的掣肘,以及 Yjs 所做的一些创造性的优化。
第三部分:重点分享了作者本人在 Rust 上根据 b-trees 数据结构规划的 CRDTs 的完结,在一些功用体现上比 Yjs 的完结版别要快 5x 之多。
一起作者罗列而且盛赞 Yjs 、automerge 所作出的一些创造性奉献,言外之意让人动容,称自己的 diamond-types 是站在伟人的膀子上,而且建议当下假如有协同修改的需求,可以挑选生态完善,功用俱佳的 Yjs。
以下为正文。
几年前,我真的被一篇学术论文所困扰。
法国的一些研讨人员进行了比较,展现了完结实时协作修改的多种办法(如 Google Docs)。 他们完结了许多算法——CRDTs 和 OT 算法等等。 他们对它们进行了基准测验,以检查它们的体现。 (酷!!)一些算法运转得相当好。 但其它的算法需求 3 秒以上的时刻来处理修改会话中的简略张贴操作。 哎呀!
那是什么算法? 好吧,这很为难,可是..这是我的。 我的意思是,它不是我创造的 – 但它是我用于 ShareJS 的算法。 咱们用于 Google Wave 的算法。 我知道一个实际(坚持)该算法并没有花费 3 秒来处理大型张贴作业。那么测验中究竟产生了什么?
我仔细看了他们的论文。 在他们的完结中,当用户张贴一大块文本(如 1000 个字符)时,他们的代码将刺进拆分为 1000 个独自的操作,而不是运用 1000 个字符创立 1 个操作。 而且这些操作中的每一个都需求独自处理。 好吧 – 当然,假如你这样做会很慢! 这不是操作转化算法的问题。 这仅仅它们 特定完结 的问题。
令人气愤的是,有几个人给我发了这篇论文的链接,并(有针对性地)问我对此有何看法。 写成一篇已宣布的科学论文,这些速度比较似乎是关于宇宙的一个实际。 这或许不是真的 – 一些代码的完结细节,或许由一个过度严重的研讨生编写,这或许是他们一堆代码中的一部分。
“不!不是每个人的Review技能都正确!请信任我!”。 可是我没有宣布论文来证明我的建议。 我可以很好作业的代码,但感觉没有一个聪明的计算机科学人员关心这个。 我又是谁呢? 这不重要。
即便议论这些东西,咱们也有言语问题。 咱们将每个体系描绘为一个“算法”。 Jupiter 是一种算法。 RGA 是一种算法。 但实践上有两个十分不同的方面:
- 并发修改的黑盒 行为 。 当两个客户端一起修改相同的文本区域时,会产生什么? 它们是否兼并,假如兼并,按什么顺序兼并? 都有些什么样的规矩?
- 体系的白盒 完结 。 咱们运用什么编程言语? 什么数据结构? 代码优化得怎么?
假如某些学者的代码运转缓慢,这实践上教会了咱们什么? 或许这就像测验。 代码测验的全部通过,但永久不能 证明 没有过错。 相同,缓慢的完结尽管很慢,但永久不能证明体系的每个完结都会很慢。 假如您等候的时刻满足长,就会有人发现更多过错。 而且,或许有人可以规划一个更快的完结。
多年前,我将旧文本 OT 代码翻译成 C、Javascript、Go、Rust 和 Swift。 每个完结都具有相同的行为和相同的算法。 但功用甚至不挨近。 在 javascript 中,我的转化函数每秒运转大约 100 000 次。 不错! 可是 C 中的相同函数每秒执行 20M 次迭代。 那快了 200 倍。 不可思议!
学者们是在测验这段代码的慢版别仍是快版别? 或许,在没有注意到的状况下,他们有一些算法的快速版别和其他算法的慢版别。 这些信息从论文上是无法得到的!
使 CRDT 变快
如您所知,我最近对 CRDT 产生了兴趣。 关于初学者来说,CRDT(无抵触仿制数据类型)是一种花哨的编程工具,可以让多个用户一起修改相同的数据。 它们让您可以毫无推迟地在本地作业。 (您甚至不用在线)。 当您与其他用户和设备同步时,全部都会神奇地同步并终究保持共同。 CRDT 最好的部分是它们可以完结全部这些作业,甚至不需求云中的中心计算机来监视和控制全部。
我想要没有谷歌的谷歌文档。 我期望我的运用程序可以在我的全部设备之间无缝同享数据,而无需期望所依赖的某些草创公司的服务器在下一个十年依然存在。 我以为它们是协作修改的未来。 或许全部软件的未来 – 但我还没有准备好议论这个。
可是你在学术论文中读到的大多数 CRDT 都十分慢。 十年前,我决议中止阅览学术论文并将其驳回。 我以为 CRDT 有一些固有的问题。 每个字符的 GUID?对方位的东西感觉很张狂! 可是——承认这一点很为难——我想我和那些研讨人员犯了相同的过错。 我正在阅览描绘不同体系行为的论文。 我以为这意味着咱们知道怎么以最佳办法实施这些体系。 哇,我错了。
错到什么程度? 好。 运转此 修改盯梢 , Automerge (一种流行的 CRDT,由一位 受欢迎的研讨人员 编写)需求近 5 分钟才干运转。 我有一个 新的完结 ,可以在 56 毫秒内处理相同的修改盯梢。 那是 0.056 秒,快了 5000 多倍。 这是我从优化作业中获得的最大速度进步 – 我对此感到十分高兴。
让咱们谈谈为什么 automerge 现在很慢,我将带您完结使其超快的全部过程。
首要,咱们需求从:
automerge 是什么?
Automerge 是一个协助您进行协作修改的库。 它由马丁克莱普曼 (Martin Kleppmann) 编撰,他的著作和 出色的讲演 让他颇有名望。 Automerge 根据一种称为 RGA 的算法,假如您对此感兴趣,可以在学术论文中阅览该算法。
www.youtube.com/watch?v=x7d…
Automerge(以及 Yjs 和其他 CRDT)将同享文档视为字符列表。 文档中的每个字符都有一个仅有的 ID,每逢您刺进到文档中时,您都会为要刺进的内容命名。
幻想下我(seph)在一个空文章中输入“abc”。Automerge 创立 3 个 items:
- 刺进 ’ a ‘ (seph, 0) 在ROOT之后
- 刺进 ‘ b ‘ (seph, 1) 在 (seph, 0) 之后
- 刺进 ‘ i ‘ (seph, 2) 在 (seph, 1) 之后
- 刺进 ‘ b ‘ (seph, 1) 在 (seph, 0) 之后
让咱们看看Mike(人名)在 ’ a ‘ 和 ’ b ‘ 之间刺进一个 ‘X’,咱们得到 ’aXbc‘,咱们得到如下:
- 刺进 ’ a ‘ (seph, 0) 在ROOT之后
- 刺进 ‘ X ‘ (mike, 0) 在 (seph, 0) 之后
- 刺进 ‘ b ‘ (seph, 1) 在 (seph, 0) 之后
- 刺进 ‘ i ‘ (seph, 2) 在 (seph, 1) 之后
请注意“X”和“b”都同享同一个父级。 当用户在文档中的同一方位一起键入时,就会产生这种状况。 可是咱们怎么确认哪个字符先呈现呢? 咱们可以只运用他们的署理 ID 或其他东西进行排序。 可是啊,假如咱们这样做,文档终究或许会变成 abcX,即便 Mike 在 b 之前刺进了 X。 那真的会很混乱。
Automerge (RGA) 通过奇妙的技巧处理了这个问题。 它为每个Item添加一个额定的整数,称为 序列号 。 每逢你刺进一些东西时,你将Item的序列号设置为比你见过的最大序列号大 1:
- 刺进 ’ a ‘ (seph, 0) 在ROOT之后 seq: 0
- 刺进 ‘ X ‘ (mike, 0) 在 (seph, 0) 之后 seq: 3
- 刺进 ‘ b ‘ (seph, 1) 在 (seph, 0) 之后 seq: 1
- 刺进 ‘ i ‘ (seph, 2) 在 (seph, 1) 之后 seq: 2
这是一个算法版别 “哇,我看到一个序列号,竟然这么大!”。 “是吗?我的更大!”
规则是子项首要根据它们的序列号排序(更大的序列号在前)。 假如序列号匹配,则更改有必要是并发的。 在这种状况下,咱们可以根据署理 ID 对它们进行任意排序。 (咱们这样做是为了让全部对等点终究得到相同的成果文档。)
Yjs – 咱们稍后会看到更多 – 完结了一个名为 YATA 的 CRDT。 YATA 与 RGA 相同,仅仅它通过略微不同的 hack 处理了这个问题。 但这儿的差异并不重要。
Automerge (RGA) 的行为由该算法界说:
- 构建树,将每个Item连接到其父项
- 当一个项目有多个子项时,先按序列号再按 ID 对它们进行排序。
- 成果列表(或文本文档)通过运用深度优先遍历把树打平制造。
那么你应该怎么 完结 automerge 呢? automerge 库以一种清楚明了的办法完结它,行将全部数据存储为一棵树。 (至少我是这么以为的 – 在输入“abc”之后,这是 automerge 的 内部状态 。呃,呃,我不知道这儿产生了什么。全部这些 Uint8Arrays 都在做什么?不管怎么,automerge 库有用,通过这些Items构建一个Tree。
关于一个简略的基准测验,我将运用 Martin 自己制造的 修改盯梢 来测验主动兼并。 这是马丁输入学术论文的逐字记载。 此盯梢中没有任何并发修改,但用户简直从未真正将光标放在彻底相同的方位然后输入,所以我不太忧虑这一点。 我也只计算在 本地 运用此盯梢所需的时刻,尽管这并不抱负,但还可以(代表是正确的)。 假如您喜爱这类作业,Kevin Jahns(Yjs 的作者)在这儿有一个更广泛的 基准测验 。 这儿的全部基准测验都是在我的 chonky ryzen 5800x 作业站上完结的,在合适的时分运用 Nodejs v16.1 和 rust 1.52。 (剧透!)
修改轨道有 260 000 次修改,终究文档巨细约为 100 000 个字符。
正如我上面所说,automerge 需求不到 5 分钟的时刻来处理此盯梢。 这仅仅每秒 900 次修改,这或许没问题。 可是当它完结时,automerge 正在运用 880 MB 的 RAM。 哇! 这是每次按键 10kb 的内存。 在高峰期,automerge 运用了 2.6 GB 的 RAM!
为了了解有多少开支,我将把它与 基准 进行比较,在基准中咱们仅仅将全部修改直接拼接到一个 javascript 字符串中。 这丢弃了咱们进行协作修改所需的全部信息,但它让咱们了解 javascript 的运转速度。 实际证明,在 V8 上运转的 javascript 速度很快:
Test | Time taken | RAM usage |
---|---|---|
automerge (v1.0.0-preview2) | 291s | 880 MB |
Plain string edits in JS | 0.61s | 0.1 MB |
这是一个图表,显现了在整个测验过程中处理每个操作所花费的时刻,均匀每组 1000 个操作。 我以为这些峰值是 V8 的垃圾收集器企图开释内存。
在挨近结尾的最慢峰值中,一次修改需求 1.8 秒的处理时刻。 糟糕。 在实践的运用程序中,整个运用程序(或浏览器选项卡)有时会在您打字的过程中冻住几秒钟。
当咱们将全部内容均匀并缩放 Y 轴时,图表更易于阅览。 咱们可以看到均匀功用跟着时刻的推移逐步(大致线性地)变差。
为什么 automerge 这么慢?
Automerge 运转缓慢的原因有许多:
- 跟着文档的增加,Automerge 的根据中心树的数据结构变得又大又慢。
- Automerge 大量运用 Immutablejs 。 Immutablejs 是一个库,它为 javascript 目标供给相似 clojure 的 copy-on-write 语义。 这是一组很酷的功用,但 V8 优化器和 GC 尽力优化运用 immutablejs 的代码。 因而,它会增加内存运用量并下降功用。
- Automerge 将每个刺进的字符视为一个独自的Item。 还记得我之前讲过的论文,仿制+张贴操作很慢吗? Automerge 也是如此!
Automerge 从来没有考虑过功用。 他们的团队正在研讨算法的代替 Rust 完结 来运转 wasm,但在编撰本文时它没有落地。 我想让 master 分支正常作业,可是在它准备好之前他们有一些问题需求处理。 切换到 automerge-rs 后端也不会使此测验中的均匀功用更快。 (尽管它的确将内存运用量折半并使功用更平滑。)
你不能让电脑更快。 你只能让它做更少的作业。
咱们怎么让计算机在这儿做更少的作业? 通过检查代码和改进许多小东西,可以获得许多功用上的成功。 可是 automerge 团队有正确的办法,最好从整体优化开端,在转向优化单个办法之前修正中心算法和数据结构。优化的函数很或许在优化中心算法和数据结构时被删去去,那么这样的小的优化就没有意义了。
到现在为止,Automerge 最大的问题是其杂乱的根据树的数据结构。 咱们可以用更快的办法替换它。
改进数据结构
幸运的是,有一种更好的办法来完结 CRDTs,这是 Yjs 中创始的。 Yjs 是由 Kevin Jahns 制造的另一个(竞赛)开源 CRDT 完结。 它很快,文档完善,生态完善。假如我今日要构建支撑协作修改的软件,我会运用 Yjs。
Yjs 不需求整篇博文来评论怎么使其更快,由于它现已十分快了,咱们很快就会看到。 它通过运用一个聪明的、显着的数据结构“技巧”完结,我以为该范畴的其他人没有想到它。 而不是像 automerge 那样将 CRDT 完结为树:
state = {
{ item: 'a', id: ['seph', 0], seq: 0, children: [
{ item: 'X', id, seq, children: []},
{ item: 'b', id, seq, children: [
{ item: 'c', id, seq, children: []}
]}
]}
}
Yjs 仅仅将全部Item放在一个单一的列表中:
state = [
{ item: '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: [..] }
]
这看起来很简略,可是怎么在列表中刺进一个新项目呢? 运用 automerge 很容易:
- 找到 Parent Item
- 将New Item 刺进到 Parent Item 的 Children 中的正确方位
可是完结上面的方针会很杂乱:
- 找到 Parent Item
- 从 Parent Item 之后开端,遍历列表直到咱们找到应该刺进新项的方位(?)
- 刺进那里,拼接成数组
本质上,这种办法仅仅一种花哨的刺进排序。 咱们正在运用列表完结列表 CRDT。 天才!
这听起来很杂乱 – 你是怎么确认 New Item 的方位的?但它的完结杂乱程度和它的数据杂乱度相同。 很难了解,可是一旦了解了,大约20行代码就可以完结整个刺进功用:
(但假如这看起来令人困惑,请不要惊慌 – 咱们或许可以让地球上今日了解此代码的每个人都进入一个小会议室。)
const automergeInsert = (doc, newItem) => {
const parentIdx = findItem(doc, newItem.parent) // (1)
// Scan to find the insert location
let i
for (i = parentIdx + 1; i < doc.content.length; i++) {
let o = doc.content[i]
if (newItem.seq > o.seq) break // Optimization.
let oparentIdx = findItem(doc, o.parent)
// Should we insert here? (Warning: Black magic part)
if (oparentIdx < parentIdx
|| (oparentIdx === parentIdx
&& newItem.seq === o.seq
&& newItem.id[0] < o.id[0])
) break
}
// We've found the position. Insert at position *i*.
doc.content.splice(i, 0, newItem) // (2)
// .. And do various bookkeeping.
}
我在我的实验性 reference-crdts 代码库中运用这种办法完结了 Yjs 的 CRDT (YATA) 和 Automerge。 这是刺进功用,还有一些注释 。 这个函数的 Yjs 版别在同一个文件中,假如你想看看。 尽管是来自不同的论文,但刺进的逻辑简直相同。 尽管代码不尽相同,但这种办法在语义上与实践的 automerge、Yjs 和 sync9 代码库相同。 ( Fuzzer verified (TM) )。
假如你有兴趣更深化地了解这一点,我在几周前的一次 braid 会议上 评论了这种办法 。
重要的一点是这种办法有一下更多好处:
- 咱们可以运用平面数组来存储全部内容,而不是不平衡的树。 这使得计算机处理的全部都变得更小、更快。
- 代码真的很简略。 更快更简略移动 Pareto efficiency frontier 。 这样做的主意是稀有的,而且是真正的黄金。
- 您可以像这样完结许多 CRDT。 Yjs、Automerge、Sync9 和其他作业。 您可以在同一个代码库中完结许多列表 CRDT。 在我的 reference-crdts 代码库中,我一起完结了 RGA(automerge)和 YATA(Yjs)。 他们同享他们的大部分代码(除了这个函数之外的全部代码)而且他们在这个测验中的体现是相同的。
理论上,当在文档中的同一方位存在并发刺进时,该算法会减慢速度。 但这在实践中真的很罕见 – 您简直总是在父项之后刺进。
运用这种办法,我对 automerge 算法的完结比真正的 automerge 快了大约 10 倍。 它的内存效率进步了 30 倍:
Test | Time taken | RAM usage |
---|---|---|
automerge (v1.0.0-preview2) | 291s | 880 MB |
reference-crdts (automerge / Yjs) | 31s | 28 MB |
Plain string edits in JS | 0.61s | 0.1 MB |
我期望我能将 全部 这些差异归因于这个甜美而简略的数据结构。 可是这儿的许多差异或许仅仅 immutablejs 对 automerge 进行了处理。
它比 automerge 快得多:
1000次扫描导致死机
咱们现在正在运用干净且快速的中心数据抽象,但完结依然 不快 。 咱们需求修正此代码库中的两大功用瓶颈:
- 找到要刺进的方位,以及
- 实践把它刺进到数组中
(这些行为在上面的代码块中标记为 (1) 和 (2) )。
为了了解为什么这个代码是必要的,假定咱们有一个文档,它是一个项目列表。
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 个没有删去的字符。 假如用户在文档中心(文档方位 50 000)键入一个 ‘a’,那么它对应于咱们数组中的什么索引? 为了找出答案,咱们需求扫描文档(越过已删去的项目)以找出正确的数组方位。
因而,假如用户在方位 50 000 刺进,咱们或许有必要线性扫描超越 75 000 个项目或其他东西才干找到刺进方位。 哎呀!
然后当咱们实践刺进时,代码会这样做,这是双重的:
doc.content.splice(destIdx, 0, newItem)
假如数组当时有 150 000 个项目,javascript 将需求将 newItem 之后的每个 Item 向后移动一次。 这部分产生在本机代码中,可是当咱们移动这么多 Items 时它或许依然很慢。 (旁白:V8 在这方面的速度实践上令人置疑,所以或许 v8 没有在内部运用数组来完结数组?谁知道!)
但一般来说,将一个 item 刺进到一个包含 n 个 items 的文档中大约需求 n 个过程。 等等,不 – 比这更糟糕,由于删去的项目依然存在。 刺进到曾经有 n 个 items 的文档需求 n 个过程。 这种算法相当快,但每次输入都会变慢。 刺进 n 个字符将花费 O(n^2) 。
假如咱们扩大上图,您可以看到这一点。 这儿产生了许多作业,由于 Martin 的修改方位在文档周围跳来跳去。 可是向右上方有很强的线性趋势,这就是咱们所期望的在刺进时花费的时刻是 O(n) 的:
为什么特别是这种形状? 为什么功用在挨近结尾时变得更好? 假如咱们简略地绘制在整个修改轨道中每个修改产生的 方位 ,运用相同的水平缓垂直刻度,成果是一条十分了解的曲线:
看起来运用更改所花费的时刻主要取决于扫描文档数组所花费的时刻。
改动数据结构
咱们能处理这个问题吗? 咱们可以! “咱们”是指 Kevin 在 Yjs 中处理了这些问题。 他是怎么做到的?
所以请记住,有两个问题需求处理:
- 咱们怎么找到特定的刺进方位?
- 咱们怎么高效地在该方位刺进内容?
Kevin 通过考虑人类实践上怎么修改文本文档来处理榜首个问题。 一般在咱们打字的时分,咱们实践上并不会在一个文档周围跳来跳去。 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', isDeleted: false, id: ['seph', 2], seq, parent: ['seph', 1] },
{ item: 'l', isDeleted: false, id: ['seph', 3], seq, parent: ['seph', 2] },
{ item: 'o', isDeleted: false, id: ['seph', 4], seq, parent: ['seph', 3] },
]
Yjs 仅仅存储:
state = [
{ item: 'hello', isDeleted: false, id: ['seph', 0], seq, parent: null },
]
终究那些讨厌的张贴作业也会很快!
这是相同的信息,仅仅存储得更紧凑。 不幸的是,咱们无法运用此技巧将整个文档折叠为单个项目或相似内容。 该算法只能在 ID 和父项按顺序排列时折叠刺进 – 但每逢用户键入一串字符而不移动光标时就会产生这种状况。 这种状况经常产生。
在这个数据集中,运用跨度换算将数组条目的数量减少了 14 倍。 (180k 条目下降到 12k)。
现在有多快? 这让我大吃一惊——在这个测验中,Yjs 比我的 reference-crdts 完结快 30 倍。 而且它只运用大约 10% 的 RAM。 它比 automerge 快 300 倍!
Test | Time taken | RAM usage |
---|---|---|
automerge (v1.0.0-preview2) | 291s | 880 MB |
reference-crdts (automerge / Yjs) | 31s | 28 MB |
Yjs (v13.5.5) | 0.97s | 3.3 MB |
Plain string edits in JS | 0.61s | 0.1 MB |
老实说,我对这次测验中运用的 ram Yjs 的运用量感到震动并有点置疑。 我确信 V8 中有一些魔法使这成为或许。 这是十分令人印象深入的。
Kevin 说他编写偏重写了 Yjs 的部分内容 12 次,以使这段代码运转得如此之快。 假如有程序员版的跑速社区,他们会喜爱 Kevin。 我甚至不能把 Yjs 放在与其他算法相同的规模上,由于它太快了:
假如咱们隔离 Yjs,您可以看到它的功用基本持平。 与其他算法不同,它不会跟着文档的增加而变慢:
但我不知道挨近结尾的那些尖峰是什么。 从绝对值来看,它们很小,但依然很古怪! 或许当用户在文档周围移动光标时会产生这种状况? 或许当用户删去块时? 我不知道。
这很好,但真正的问题是:咱们能走得更快吗? 老实说,我置疑我能否让纯 javascript 比 Kevin 在这儿办理的更快地运转此测验。 但或许……仅仅或许咱们可以……
比Javascript更快
当我告知 Kevin 我以为我可以做出比 Yjs 快得多的 CRDT 完结时,他不信任我。 他说 Yjs 现已优化得十分好,或许不或许再快得多。 “假如你仅仅把它移植到 Rust,或许会快一点。但不会快许多!现在 V8 真的很快!!”
但我知道一些 Kevin 不知道的作业:我知道内存碎片和缓存。 Rust 不仅仅是 更快 。 它也是一种低级言语,它为咱们供给了控制分配和内存布局所需的工具。
Kevin 现在也知道这一点,他正在尽力运用到 Yrs 上,看看他是否能夺回体现桂冠。
幻想一下咱们在 javascript 中的文档项之一:
var item = {
content: 'hello',
isDeleted: false,
id: ['seph', 10],
seq: 5,
parent: ['mike', 2]
}
这个目标在内存中实践上是这样的:
坏消息: 你的电脑讨厌这个 。
这很糟糕,由于全部数据都是碎片化的。 都是用指针离隔的。
是的,我知道,V8 在或许的状况下尽最大尽力防止此类作业产生。 但它不是魔法。
像这样排列数据,计算机有必要为每一项一项地分配内存。 这很慢。 然后垃圾收集器需求额定的数据来盯梢全部这些目标,这也很慢。 稍后咱们需求读取该数据。 要读取它,您的计算机一般需求从主内存中获取它,这 – 您猜对了 – 也很慢。
主存读取有多慢? At human scale ,每次 L1 缓存读取需求 0.5 秒。 从主内存读取需求挨近 2 分钟! 这是单次心跳与刷牙所需时刻之间的差异。
像 javascript 相同组织内存就像编写购物清单相同。 但不是“奶酪、牛奶、面包”,你的清单实践上是一个寻宝游戏:“沙发底下”、“冰箱顶上”等等。 沙发底下有一张小纸条,上面写着你需求牙膏。 毋庸置疑,这使得去杂货店购物需求做许多作业。
为了更快,咱们需求将全部数据压缩在一起,以便计算机可以在每次读取主内存时获取更多信息。 (咱们想要一次阅览我的购物清单来告知咱们咱们需求知道的全部)。 正是由于这个原因, 链表在实际国际中很少运用——内存碎片会损坏功用 。 我也想脱节链接列表,由于用户有时会在文档周围跳来跳去,这在 Yjs 中具有线性功用本钱。 这在文本修改中或许没什么大不了的,但我期望这段代码在其他用例中也能很快。 我不期望程序需求那些缓慢的扫描。
咱们无法在 javascript 中处理这个问题。 javascript 中独特的数据结构的问题是你终究需求大量的奇特目标(比如固定巨细的数组)。 全部这些额定的目标都会使碎片变得更糟,因而由于您的全部作业,您的程序终究一般会运转得更慢。 这与 immutablejs 有相同的限制,也是为什么它的功用在发布后的十年中没有太大进步。 V8 优化器十分聪明,但它不是魔术,聪明的技巧只能让咱们到此为止。
但咱们不仅限于 javascript。 即便在制造网页时,咱们现在也有 WebAssembly。 咱们可以将其编码为 任何内容 。
为了看看咱们究竟能走多快,我一直在悄悄地用 Rust 构建一个名为 Diamond 类型的 CRDT 完结。 Diamond 与 Yjs 简直相同,但它在内部运用 range tree 而不是链表来存储全部项目。
在引擎下,我的 range tree 仅仅一个略微修改正的 b-tree。 但一般当人们议论 b-trees 时,他们指的是 BTreeMap 。 那不是我在这儿做的。 b-tree 的每个内部节点不存储键,而是存储该 item 的 children 中的字符总数(递归)。 因而咱们可以通过字符方位查找文档中的任何 item,或许在 log(n) 时刻内涵文档中的任何方位刺进或删去。
此示例显现了存储当时具有 1000 个字符的文档的树:
这是一个range tree,对吧? 关于 wikipedia article on range trees 对我在这儿所做的作业的描绘十分单薄。
这处理了咱们之前的线性扫描问题:
- 当咱们想在方位 200 处找到项目时,咱们可以遍历树并向下遍历。 在上面的示例中,方位为 350 的项目有必要在此处的中心叶节点中。 树十分整齐 – 咱们可以在树中仅将 Martin 的修改盯梢存储在 3 个等级中,这意味着在此基准测验中,咱们可以在大约 3 次读取中从主内存中找到任何项目。 实践上,这些读取中的大部分现已在您的 CPU 缓存中。
- 更新树也很快。 咱们更新一个叶子,然后更新它的父级和它的父级的字符数,一直到根。 相同,通过 3 个左右的过程后,咱们就完结了。 比在 javascript 数组中打乱全部内容要好得多。
在这个测验中,咱们从不兼并来自长途对等方的修改,但不管怎么我也做得很快。 兼并长途修改时,咱们还需求通过 ID 查找项目( 例如 [‘seph’, 100] )。 Diamond 简直没有索引可以通过 ID 查找 b-tree。 不过,该代码途径并未在此处进行基准测验。 它很快,但现在你有必要信任我的话。
我没有运用 Yjs 缓存终究一个修改方位的技巧——至少现在还没有。 它或许会有所协助。 我仅仅还没试过。
Rust 使咱们可以彻底控制内存布局,因而咱们可以将全部内容都严密地打包。 与图中不同,我的 b-tree 中的每个叶节点都存储了一个包含 32 个条目的块,这些条目打包在内存中的固定巨细数组中。 用这样的结构刺进会导致一些 memcpy-ing,可是一点 memcpy 就可以了。 Memcpy 总是比我幻想的要快 – CPU 每个时钟周期可以仿制几个字节。 它不是对主内存查找的史诗般的追捕。
为什么是 32 个条目? 我用一堆不同的块巨细运转了这个基准测验,32 个运转杰出。 我不知道为什么成果是最好的。
说到快,究竟有多快?
假如咱们将 此代码编译为 webassembly 并像在其他测验中相同从 javascript 驱动它,咱们现在可以在 193 毫秒内处理整个修改盯梢。 这比 Yjs 快 5 倍。 尽管做了全部支撑协作修改的作业,但修改原生 javascript 字符串的速度比咱们的基线测验快了 3 倍!
Javascript 和 WASM 现在是一个瓶颈。 假如咱们越过 javascript 并 直接在 rust 中运转基准测验,咱们可以在短短 56 毫秒内处理此修改盯梢中的全部 260k 修改。 这比咱们开端运用 automerge 时快 5000 倍以上。 它每秒可以处理 460 万次操作。
Test | Time taken | RAM usage |
---|---|---|
automerge (v1.0.0-preview2) | 291s | 880 MB |
reference-crdts (automerge / Yjs) | 31s | 28 MB |
Yjs (v13.5.5) | 0.97s | 3.3 MB |
Plain string edits in JS | 0.61s | 0.1 MB |
Diamond (wasm via nodejs) | 0.19s | ??? |
Diamond (native) | 0.056s | 1.1 MB |
功用如黄油般顺滑。 b-tree 不关心修改产生的方位。 该体系在整个文档中速度共同。 Rust 不需求垃圾收集器来盯梢内存分配,因而没有神秘的 GC 峰值。 由于内存十分紧凑,因而处理整个数据集(全部 260 000 个)只会导致对 malloc 的 1394 次调用。
噢真惋惜。 它太快了,你简直看不到它周围的 yjs (fleexxxx)。 让咱们扩大一点,看看那条平线:
嗯,简直是一条直线。
请记住,此图表显现的是慢速版别。 该图表由 javascript 生成,通过 WASM 调用 Rust。 假如我在本地运转这个基准测验,它又快了大约 4 倍。
为什么 WASM 比本地执行慢 4 倍? 对 WASM VM 的 javascript 调用真的那么慢吗? LLVM 是否更好地优化了原生 x86 代码? 仍是 WASM 的内存边界检查会减慢它的速度? 我很好奇!
数组结构仍是结构数组?
这个完结还有另一个小的、重要的变化——我不确认我是否喜爱它。
在 Rust 中,我实践上是在做这样的作业:
doc = {
textContent: RopeyRope { 'hello' },
clients: ['seph', 'mike'],
items: BTree {[
// Note: No string content!
{ len: 5, id: [0, 0], seq, parent: ROOT },
{ len: -5, id: [1, 0], seq, parent: [0, 0] }, // negative len means the content was deleted
...
]},
}
请注意,文档的文本内容不再存在于项目列表中。 现在它在一个独自的数据结构中。 我为此运用了一个名为 Ropey 的 Rust 库。 Ropey 完结了另一个 b 树来有用地办理文档的文本内容。
这不是遍及的成功。 不幸的是,咱们来到了令人不安的工程权衡之地:
- Ropey 可以进行文本特定的字节打包。 所以运用ropey,咱们运用更少的RAM。
- 刺进时,咱们需求更新 2 个数据结构而不是 1 个。这使得全部都慢了两倍多,而且使 wasm 包的巨细增加了一倍(60kb -> 120kb)。
- 关于许多用例,不管怎么咱们终究都会将文档内容存储在其他当地。 例如,假如您将此 CRDT 与 VS Code 挂钩,则修改器将始终保存该文档的副本。 因而,底子不需求将文档存储在我的 CRDT 结构中。 这种完结办法可以很容易地封闭那部分代码。
所以我依然不确认我是否喜爱这种办法。
但不管怎么,我的 CRDT 完结在这一点上是如此之快,以至于算法的大部分时刻都花在了更新 ropey 中的文档内容上。 Ropey 自身需求 29 毫秒来处理此修改盯梢。 假如我仅仅……封闭ropey会怎样? 这只小狗究竟能跑多快?
Test | Time taken | RAM usage | Data structure |
---|---|---|---|
automerge (v1.0.0-preview2) | 291s | 880 MB | Naive tree |
reference-crdts (automerge / Yjs) | 31s | 28 MB | Array |
Yjs (v13.5.5) | 0.97s | 3.3 MB | Linked list |
Plain string edits in JS | 0.61s | 0.1 MB | (none) |
Diamond (wasm via nodejs) | 0.20s | ??? | B-Tree |
Diamond (native) | 0.056s | 1.1 MB | B-Tree |
Ropey (rust) baseline | 0.029s | 0.2 MB | (none) |
Diamond (native, no doc content) | 0.023s | 0.96 MB | B-Tree |
Boom。 这尽管有点没用,但现在比 automerge 快 14000 倍。 咱们在 23 毫秒内处理了 26 万次操作。 那是每秒 1100 万次操作。 我可以通过按键使我的家庭互联网连接饱满,而且我还有 CPU 可用。
咱们可以计算每个算法处理修改的均匀速度:
但这些数字具有误导性。 请记住,automerge 和 ref-crdts 并不稳定。 它们一开端很快,然后跟着文档的增加而变慢。 尽管 automerge 均匀每秒可以处理大约 900 次修改(这速度快到用户不会注意到),但在此基准测验期间最慢的修改使 V8 阻滞了整整 1.8 秒。
假如我运用对数刻度,咱们可以将全部内容放在一个美丽的图表中。 这看起来十分整齐:
呵呵 – 看看底部的两行。 yjs 和 diamond 的颤动彼此映衬。 yjs 变慢的时期,diamond 变快。 我想知道那里产生了什么!
但对你的直觉来说,对数可读是垃圾食品。 在线性尺度上,数据如下所示:
我的朋友们,这就是让计算机少做许多作业的办法。
结论
多年前我读过的那篇愚蠢的学术论文说一些 CRDTs 和 OT 算法很慢。 每个人都信任这篇论文,由于它是已宣布的科学。 可是论文是过错的。 正如我所展现的,咱们 可以 使 CRDsT 变快。 假如咱们对咱们的实施策略发挥构思,咱们 可以 让他们快的张狂。 通过正确的办法,咱们可以使 CRDT 变得如此之快,以至于咱们可以与原生字符串的功用竞赛。 那篇论文中的体现数字不仅仅是过错的。 他们是“一位亿万富翁,猜想一根香蕉值 1000 美元”,这有点过错。
但你知道吗? 我现在有点欣赏那篇论文。 他们的过错是可以的。 这是人类。 我曾经在学术上感到不足 – 或许我永久不会那么聪明! 但这整件事让我意识到一件清楚明了的作业:科学家不是神,突如其来,带着真理的礼物。 不,他们是美丽的、有缺陷的人,就像咱们其他人相同。 拿手咱们所痴迷的全部,但在其他任何当地都处于中等水平。 我可以很好地优化代码,但我依然把西葫芦和黄瓜搞混了。 而且,不管我从朋友那里得到什么戏弄,那都可以。
十年前,Google Wave 的确需求一个高质量的列表 CRDT。 当 CRDT 的论文开端呈现时,我感到十分振奋。 LOGOOT 和 WOOT 看起来很重要! 可是当我意识到算法太慢且效率低下而无法实践运用时,那种振奋就消失了。 我犯了一个大过错——我以为假如学者们不能让他们快速完结,那么没有人能做到。
但有时最好的著作来自具有不同技能的人之间的合作。 我不拿手学术论文,我很拿手让代码运转得很快。 可是,在我自己的范畴,我甚至没有测验供给协助。 研讨人员正在尽自己的一份力气使 P2P 协作修改作业。 我仅仅对他们不以为然,继续致力于运营转型。 假如我供给协助,或许十年前咱们会有快速、可行的 CRDT 用于文本修改。 哎呀! 成果证明协作修改需求咱们全部人的协作。 真挖苦! 谁能猜到?!
嗯,这花了十年时刻,来自一群聪明人的一些辛勤作业和一些伟大的主意。 Martin 为 Automerge 创造的二进制编码体系十分出色。 通过运用递加(agent id、sequence)元组来防止 UUID 的体系是天才。 我不知道是谁提出的,但我喜爱它。 当然,我在此描绘的 Kevin 的列表表示 + 刺进办法使全部变得更快、更简略。 我敢打赌,在过去十年中,一定有 100 名聪明人在没有任何人说到的状况下从这个主意中走出来。 我置疑我也不会想到它。 我的奉献是运用运转长度编码的 b-trees 和奇妙的索引。 而且展现 Kevin 的快速列表表示可以适用于任何 CRDT 算法。 我以为之前没有人注意到这一点。
现在,通过十年的等候,咱们总算找到了怎么制造快速、轻量级的列表 CRDT 完结。 实用的去中心化实时协同修改? 咱们下一次来找你。
附录 A: 我想为我的运用程序运用 CRDT。 我该怎么办?
假如您现在正在构建根据文档的协作运用程序,则应该运用 Yjs。 Yjs 具有稳定的功用、低内存运用和强壮的支撑。 假如您需求协助在您的运用程序中完结 Yjs,Kevin Jahns 有时会承受金钱以交换协助将 Yjs 集成到各种运用程序中。 他用它来赞助全职从事 Yjs(和相关)的作业。 Yjs 现已运转得很快,很快它就会变得更快。
automerge 团队也很棒。 我和他们就这些问题进行了一些很好的对话。 他们将功用作为 2021 年的榜首期,并方案运用许多这些技巧来加快主动兼并。 当您阅览本文时,它或许现已快得多了。
Diamond 真的很快,但在我与 Yjs 和 Automerge 具有平等功用之前还有许多作业要做。 一个好的 CRDT 库除了操作速度之外还有许多。 CRDT 库还需求支撑二进制编码、网络协议、非列表数据结构、presence(光标方位)、修改器绑定等。 在编撰本文时,Diamon 简直没有做这些。
假如你想要数据库语义而不是文档语义,据我所知,还没有人在 CRDT 之上做得很好。 您可以运用运用 OT 的 ShareDB 。 我多年前编写了 ShareDB,它运用杰出、维护杰出并通过实战测验。
展望未来,我对 Redwood 感到振奋——它支撑 P2P 修改并方案全面支撑 CRDT。
附录 B:谎话、该死的谎话和基准
这是真的吗? 是的。 可是功用很杂乱,我不会在这儿评论全貌。
首要,假如你想运用我自己运转的任何基准测验,你可以。 但全部都有些混乱。
JS 纯字符串修改基线、Yjs、automerge 和 reference-crdts 测验的基准代码都在这个 github gist 中。 一团糟; 但杂乱的代码总比短少代码好。
您还需求 josephg/crdt-benchmarks 中的 automerge-paper.json.gz 来运转大多数这些测验。 在这个版别中,reference-crdts benchmark依赖于 josephg/reference-crdts 中的 crdts.ts 。
Diamond’s benchmarks 来自 josephg/diamond-types, at this version . Benchmark 靠运转 RUSTFLAGS='-C target-cpu=native' cargo criterion yjs
. 可以通过修改 src/list/doc.rs 顶部的常量来启用或禁用内联绳子结构更新。. 您可以通过运转 cargo run --release --features memusage --example stats
检查内存统计信息.
Diamond 运用此 this wrapper 编译为 wasm,硬编码以指向来自 git 的 diamond-types 的本地副本。 wasm 包运用 wasm-opt 进行了优化。
这些图表是在 ObservableHQ 上制造的。
Automerge 和 Yjs 做相同的作业吗?
在这篇文章中,我一直在比较 RGA(automerge)和 YATA(Yjs + 我的 Rust 完结)的完结功用。
这样做的条件是假定 YATA 和 RGA 的并发兼并行为基本相同,而且您可以在不更改完结或完结功用的状况下在 CRDT 行为之间进行交换。 这是一个我以为曾经没有人看过的新颖主意。
我对这个声明充溢信心,由于我在我的 参阅 CRDT 完结 中展现了它,当运用 Yjs 或 automerge 的行为时,它具有相同的功用(和简直相同的代码途径)。 抵触严峻的修改盯梢或许存在一些功用差异 – 但在实践中这种状况极为稀有。
我也信任您可以修改 Yjs 以完结 RGA 的行为,而无需更改 Yjs 的功用。 您只需求:
- 更改 Yjs 的 integrate 办法(或进行代替),该办法对并发修改运用略有不同的逻辑
- 在每个项目中存储 seq 而不是 originRight
- 将 maxSeq 存储在文档中,并使其保持最新和
- 更改 Yjs 的二进制编码格局。
我和 Kevin 评论过这个问题,他以为在他的库中添加 RGA 支撑没有任何意义。 这不是任何人真正要求的。 在预置项目时,RGA 或许会有古怪的 交错 。
关于 Diamond ,我让我的代码承受一个类型参数,用于在 Yjs 和 automerge 的行为之间切换。 我不确认我是否愿意。 Kevin 或许是对的 – 我不以为这是人们想要的。
嗯,Yjs 有一种办法比 automerge 具有显着的优势: 当 文档中的每个项目都被删去时,Yjs 不会记载。 仅记载每个项目是否已被删去。 这有一些古怪的意义:
- 在每次删去产生时进行存储对内存运用和磁盘存储巨细有很大的影响。 添加此数据后,diamond 的内存运用量从 1.12mb 增加到 2.34mb,并使体系速度下降约 5%。
- Yjs 没有存储满足的信息来完结按键修改重播或其他相似的东西。 (或许这就是人们想要的?记载每个过错的击键是否很古怪?)
- Yjs 需求将有关哪些Item已被删去的信息编码到版别字段中。 在 diamond 中,版别是几十个字节。 在 yjs 中,版别是 ~4kb。 跟着文档的增加,它们会跟着时刻的推移而增加。 Kevin 向我保证,这些信息在实践中基本上总是很小的。 他或许是对的,但这依然让我感到古怪的严重。
现在,Diamond 的主分支包括时刻删去。 可是这篇博文中的全部基准测验都运用 yjs 风格的 diamond 类型分支 ,它与 Yjs 的作业办法相匹配。 这可以与 yjs 进行更公正的比较,但 Diamond 1.0 的功用配置或许略有不同。 (这儿有许多关于 diamond 没有打磨的的双关语,但我现在还不够敏锐。)
这些基准衡量过错的东西
这篇文章只测量了重放本地修改盯梢所需的时刻。 我正在测量由此产生的 RAM 运用量。 可以说,承受来自用户的传入更改只需求 满足 快地产生。 手指底子不会打字很快。 一旦 CRDT 可以在大约 1 毫秒内处理任何本地用户修改,速度更快或许无关紧要。 (而且主动兼并一般现已很好地执行了,除非一些不幸的 GC 暂停。)
实践上重要的的目标是:
- 文件在磁盘或网络上占用多少字节
- 文档保存和加载需求多长时刻
- 更新静态存储的文档(in database)需求多长时刻(更多内容见下文)
我在这儿运用的修改盯梢也只有一个用户进行修改。 当用户进行并发修改时,暗影中或许潜伏着病态的功用案例。
我这样做是由于我还没有在我的 reference-crdts 完结或钻石中完结二进制格局。 假如我这样做了,我或许会仿制 Yjs & automerge 的二进制格局,由于它们十分紧凑。 所以我期望全部这些完结之间得到的二进制巨细是相似的,除了删去操作。 加载和保存的功用或许大致反映我上面显现的基准。 或许。 或许或许我错了。 我曾经错了。 找出答案会很风趣。
我以为现在还没有人认真对待另一项绩效衡量标准。 也就是说,咱们怎么更新静态文档(在数据库中)。 大多数运用程序都不是协作文本修改器。 一般,运用程序实践上是在与充溢微小目标的数据库进行交互。 这些目标中的每一个都很少被写入。
假如您想运用 Yjs 或 automerge 今日更新数据库中的单个目标,您需求:
- 将整个文档加载到 RAM 中
- 做出改动
- 再次将整个文档保存回磁盘
这将十分缓慢。 对此有更好的办法 – 但据我所知,底子没有人在做这件事。 咱们可以运用你的协助!
Kevin 说你可以调整 Yjs 的供给者以合理的办法完结这一点。 我很想看到它在行动。
还有另一种快速制造 CRDT 的办法,我在这儿底子没有说到,那就是 pruning(修剪) 。 默认状况下,像这样的列表 CRDT 只会跟着时刻的推移而增加(由于咱们有必要为全部已删去的 items 保存 tombstones )。 CRDT 的许多功用和内存本钱来自加载、存储和查找不断增加的数据集。 有一些办法可以通过找到彻底脱节某些数据的办法来处理这个问题。 比如Yjs的GC算法,或许 Antimatter 。 也就是说,git 存储库只会跟着时刻的推移而增加,而且似乎没有人会介意太多。 或许只需底层体系满足快就无所谓了?
这个旅程的每一步都改动了太多的变数
优化过程中的每一步都涉及对多个变量的更改,我不会孤立这些更改。 例如,从 automerge 搬运到我的 reference-crdts 完结产生了变化:
- 中心数据结构(tree 到 list)
- 删去了 immutablejs
- 删去了 automerge 的前端/后端协议。 显然,不管出于何种原因,在整个主动兼并过程中弹出的全部 Uint8Array 都消失了。
- javascript 风格彻底不同。 (FP javascript -> imperative)
咱们从这全部中获得了 10 倍的功用。 但我仅仅在猜想 10 倍的加快应该怎么在全部这些变化中分配。
从 reference-crdts 到 Yjs,从 Yjs 到 Diamond 的跳动相同是单一的。 Diamond 和 Yjs 之间的速度差异有多少与内存布局无关,而与 LLVM 的优化器有关?
automerge-rs 并不比 automerge 快这一实际让我信任 Diamond 的功用不仅仅归功于 Rust。 但老实说我不确认。
所以,是的。 这是对我的办法的合理性持批评的态度。 假如这个问题困扰着您,我期望有人可以分解我在此处展现的完结之间的每个功用差异,并梳理出更具体的细分。 我会把它读出来的。 我喜爱基准化剖析这些故事。 这很正常,对吧?
附录 C: 我仍是不明白——为什么 automerge 的 javascript 这么慢?
由于它并没有企图变得快。 检查 automerge 中的这段代码:
function lamportCompare(op1, op2) {
return opIdCompare(op1.get('opId'), op2.get('opId'))
}
function insertionsAfter(opSet, objectId, parentId, childId) {
let childKey = null
if (childId) childKey = Map({opId: childId})
return opSet
.getIn(['byObject', objectId, '_following', parentId], List())
.filter(op => op.get('insert') && (!childKey || lamportCompare(op, childKey) < 0))
.sort(lamportCompare)
.reverse() // descending order
.map(op => op.get('opId'))
}
这在每次刺进时调用,以确认应怎么对项目的子项进行排序。 我不知道它多热(译者:或许是比喻说CUP 产生的温度),但有 许多关于这个的作业 很慢:
- 我可以在这个函数中发现 7 处内存分配。 (应该进步 2 闭包)。 (你能全部找到吗?)
- 在调用此办法之前,项目现已排序为 reverse-lamportCompare。 对反排序列表进行排序是对任何内容进行排序的最慢办法。 这个代码应该只回转 lamportCompare 中的参数(或否定返回值),而不是 sorting ,然后 reverse()’ing 。
- 方针是将新项目刺进到已排序的列表中。 运用 for 循环可以更快地做到这一点。
- 这段代码将 childId 包装到一个 immutablejs Map 中,以便参数匹配 lamportCompare – 然后再次解开它。 停下——我要死了!
但在实践中,这段代码将被 WASM 调用替换为 automerge-rs。 或许在您阅览本文时它现已被 automerge-rs 替代了! 所以不要紧。 尽量不要去想它。 绝对不要提交任何 PR 来处理全部悬而未决的问题。 抽搐 。
称谢
这篇文章是 Braid 项目 的一部分,由 Invisible College 赞助。 假如这是您想为之做出奉献的作业,请与咱们联系。 咱们正在招聘。
感谢在此帖子上线之前供给反应的全部人。
特别感谢 Martin Kleppmann 和 Kevin Jahns 在 Automerge 和 Yjs 方面所做的作业。 Diamond 站在伟人的膀子上。