按年被提到
20232023 · 4 次2026
系统、数据库与网络›分布式数据与 CRDT·arXiv:2305.00583 · cs.DC

The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing

赋格的艺术:协同文本编辑中最小化交错
Matthew Weidner, Martin Kleppmann · 2023

提出非交错性质与 Fugue 算法,解决协同编辑中的文本交错

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 6 人首次 2023-05-02 · 最近 2026-08-22
6不同的人
6活跃月份
6讨论串
6被引(OpenAlex)

多数复制列表算法(CRDT 与 OT 都在内)有个问题:两个用户同时在同一位置插入文本时,合并结果可能让两段文字交错,使文本损坏难以阅读。论文定义了新的正确性性质“最大非交错”,提出 Fugue 和 FugueMax 两种 CRDT 算法并证明 FugueMax 满足该性质;实现表明 Fugue 的性能与最先进的文本编辑 CRDT 库相当。

HN 为什么提它

评论者推荐从它入手了解文本 CRDT:Fugue 是对 RGA 做小改动的非交错算法,并介绍了每字符一个节点与按连续段实现的对比(第 5 节)。

方法难度 4 / 5约 45 分钟经得起时间
读之前最好知道
1CRDT(无冲突复制数据类型)
2操作变换(OT)
3复制列表(replicated list)
4分布式系统的并发与一致性

学习路径

读这篇之前,按顺序读书架上的 3 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

这条路径帮我先理解 CRDT 与 OT 在协同编辑中的位置,再读 Fugue 如何定义并保证文本不交错。

  1. 1

    它是早期列表型 CRDT 的设计,帮助理解复制列表类算法的基本要求。

    读无冲突复制数据类型的基本思路、位置标识的设计;之后对照 Fugue 的树结构。

  2. 2
    A Conflict-Free Replicated JSON Datatype无冲突复制的 JSON 数据类型 · 2016

    它给出了含列表的 JSON CRDT,其列表算法正是受到交错问题影响的一类。

    读列表的插入与顺序处理方式;留意并发插入同一位置时的排序规则。

  3. 3
    Real Differences between OT and CRDT in Correctness and Complexity for Consistency Maintenance in Co-Editors协同编辑中 OT 与 CRDT 在正确性与复杂度上的真实差异 · 2019

    它批判性地对比 OT 与 CRDT,目标论文指出交错问题同时影响两者。

    读作者对 CRDT 正确性与复杂度的主张;对照目标论文对交错问题的研究。

  4. 4
    The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing赋格的艺术:协同文本编辑中最小化交错 · 2023 · 就是这篇

    目标论文:定义最大非交错性并提出 Fugue。

    读非交错性质的定义、Fugue 与 FugueMax 的树结构算法及其证明思路;再看实验。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐josephg · 2025-08

“I recommend starting there.”

推荐从这里入手:Fugue 是不交错的文本 CRDT,与 RGA 只差一个小改动
CRDT: Text Buffer原评论 ↗
引用mweidner · 2023-12

“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:”

指出论文第 5 节对比了每字符一节点的 Fugue Simple 与按段的 Fugue 两种实现
CRDT Concepts: Causal Trees原评论 ↗
被提交为 story · 4 次