“I recommend starting there.”
The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing
提出非交错性质与 Fugue 算法,解决协同编辑中的文本交错
多数复制列表算法(CRDT 与 OT 都在内)有个问题:两个用户同时在同一位置插入文本时,合并结果可能让两段文字交错,使文本损坏难以阅读。论文定义了新的正确性性质“最大非交错”,提出 Fugue 和 FugueMax 两种 CRDT 算法并证明 FugueMax 满足该性质;实现表明 Fugue 的性能与最先进的文本编辑 CRDT 库相当。
评论者推荐从它入手了解文本 CRDT:Fugue 是对 RGA 做小改动的非交错算法,并介绍了每字符一个节点与按连续段实现的对比(第 5 节)。
学习路径
读这篇之前,按顺序读书架上的 3 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出这条路径帮我先理解 CRDT 与 OT 在协同编辑中的位置,再读 Fugue 如何定义并保证文本不交错。
- 1
它是早期列表型 CRDT 的设计,帮助理解复制列表类算法的基本要求。
读无冲突复制数据类型的基本思路、位置标识的设计;之后对照 Fugue 的树结构。
- 2
它给出了含列表的 JSON CRDT,其列表算法正是受到交错问题影响的一类。
读列表的插入与顺序处理方式;留意并发插入同一位置时的排序规则。
- 3
它批判性地对比 OT 与 CRDT,目标论文指出交错问题同时影响两者。
读作者对 CRDT 正确性与复杂度的主张;对照目标论文对交错问题的研究。
- 4The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing
目标论文:定义最大非交错性并提出 Fugue。
读非交错性质的定义、Fugue 与 FugueMax 的树结构算法及其证明思路;再看实验。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“I did a head-to-head comparison of implementations that use a node-per-char (Fugue Simple) vs runs (Fugue), with results in Section 5 of this paper:”
- The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing ↗samwillis · 2023-05-02 · 1 分
- The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing ↗czsun · 2023-06-06 · 1 分
- The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing ↗shunza · 2023-07-09 · 1 分
- The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing ↗danbitengo · 2026-08-22 · 3 分