算法与数据结构 / 文本缓冲 · 从 gap buffer 到 piece table 与 rope / 不可变缓冲与协同编辑的接口 待审核 6 / 6
撤销 · 稳定标识 · CRDT

不可变缓冲与协同编辑的接口

前面四页只关心一件事：单机上一次编辑要花多少代价。本页问两个衍生问题：能不能便宜地回到过去，以及能不能让两个人同时编辑同一份文档。

这两件事看起来无关，实际上要的是同一个性质。

1 · 撤销要的是什么

撤销的朴素做法是每次编辑前存一份整串快照。正确，但每次都是 O(n)O(n) 的空间与时间，一个 1 MB 的文档改一百次就是 100 MB。

改进做法是存「反操作」：插入的反操作是删除同样长度，删除的反操作是插回原内容。空间降到与编辑量同阶，代价是重做时必须严格按顺序回放，且分支历史（撤销之后再编辑）要另外处理。

而 piece table 提供了第三条路：版本就是一份 piece 列表。缓冲从不被改写，任何历史版本引用的那些字符都还在原处躺着。要回到某个版本，把当时那份 piece 列表装回去即可，缓冲一个字节也不用动。

图 1-1 · 每次编辑后的 piece 列表快照与整串快照的体积对照。可编辑文档并在版本轴上前后跳转，观察两个缓冲在整个过程中只增不改。

实测 10 KB 文档跑 500 次连续输入编辑，终态 655 个 piece，全部 500 份快照共 165183 条 piece 记录；同样 500 份整串快照是 5193000 个字符，差 31 倍。差距还会随文档变大而拉开：piece 记录数只跟编辑次数走，整串快照跟文档长度走。

这条路还顺带解决了分支历史。版本是一份独立的列表而不是一串必须顺序回放的操作，跳到任意版本都是常数次赋值，撤销树因此可以是真正的树。Emacs 的 undo-tree 与 Vim 的 :undolist 想要的正是这个，只是它们建在操作日志上而非缓冲结构上。

2 · 只增缓冲与操作日志

把 piece table 的两个缓冲换个角度看：original 是初始状态，added 是一条按时间顺序排列、只追加不修改的记录。而这正是操作日志的形状。

分布式系统里那套「状态即日志的折叠」在文本缓冲上成立得相当直接。当前文档等于「初始状态 + 一串追加 + 一份选择哪些片段、按什么顺序拼接的说明」。前两项是不可变的事实，第三项是可变的视图。

CRDT 的文本类型走的是同一条路。以 RGA 与 Yjs 的 item list 为代表的做法是：每个插入的字符（或字符段）是一条不可变记录，带一个全局唯一的标识；文档是这些记录按某个确定顺序排列后，滤掉已删除项的结果。删除不移除记录，只打一个墓碑标记。

两者的对应关系整齐得可疑：

piece table CRDT 文本类型
original 与 added 缓冲 不可变的插入记录集
piece 列表 记录的排列顺序
删除 = 从列表里摘掉 删除 = 打墓碑
撤销 = 换回旧列表 撤销 = 撤销标记也是一条记录

3 · piece 缺的那一层

对应关系止步于一处，而这一处是决定性的。

piece 的三元组是「哪个缓冲、起始偏移、长度」。偏移是本地的：它指向本副本的 added 缓冲的某个位置。两个副本各自往自己的 added 追加，同一个偏移在两边指向完全不同的字符。把一份 piece 列表原样发给对方，对方拼出来的是乱码。

图 3-1 · 两个副本各自编辑后交换 piece 列表的结果。可切换标识方案，观察本地偏移下的拼接结果与稳定标识下的差别。

补法是给每条插入记录一个全局唯一且不随后续编辑变化的标识，通常是「副本 id 加本副本的自增计数」这样的二元组。piece 于是从「偏移加长度」变成「起始标识加长度」，两个副本交换记录时按标识而非偏移对齐。

标识稳定之后还剩一个问题：两条并发插入落在同一个位置时，谁在前。这需要一个全序，且要求两个副本各自算出的顺序相同。RGA 用「插在哪条记录之后」加标识比大小来定，Yjs 用左右邻居加 origin 链，Logoot 与 LSEQ 用可无限细分的位置标识。不同方案的差别在于并发插入交错时读者眼里的结果是否符合直觉，以及标识本身会不会随编辑次数膨胀。

这套机制在树形数据上的完整讨论见 CRDT 可变树 · 多副本层级如何无冲突收敛，文本序列只是它的一维特例。

4 · 挂树这一手在两边都用

有一件事在两边是同一个答案。

piece table 的 piece 数随编辑次数线性增长，数组实现的定位代价随之线性上升，解法是挂一棵按累计长度索引的平衡树。CRDT 的 item list 同样随编辑次数线性增长，而且更糟：已删除的记录也留着，列表只增不减。协同编辑一份文档一年下来，item 数可以是可见字符数的几十倍。

Yjs 与 Automerge 近年的性能工作里有相当大一部分就是给这条 item list 挂索引结构，让「文档偏移 pp 对应哪条 item」不必线性扫。这与 VS Code 给 piece 挂红黑树是同一手法，只是权重字段从「piece 长度」换成了「item 是否可见」。

于是本系列的两条线在协同编辑上合上：第一条线是「怎样表示文档才能便宜地改」，第二条线是「怎样在表示上挂权重才能便宜地问」。协同编辑同时需要这两条，而且它对第二条的需求比单机编辑器更迫切。

注 · 本页没有实现 CRDT，buffer.ts 里也没有任何副本或标识的概念。上面关于 Yjs 与 Automerge 的叙述取自其公开文档与 Joseph Gentle 的性能拆解文章，未经本系列实测。可实测的只有 piece 快照那一组数字。

5 · 参考文献

  1. Roh, H.-G., Jeon, M., Kim, J.-S., & Lee, J. (2011). Replicated abstract data types: Building blocks for collaborative applications. Journal of Parallel and Distributed Computing, 71(3), 354–368.
  2. Preguiça, N., Marquès, J. M., Shapiro, M., & Letia, M. (2009). A commutative replicated data type for cooperative editing. 29th IEEE International Conference on Distributed Computing Systems, 395–403.
  3. Gentle, J. (2021). 5000x faster CRDTs: an adventure in optimization. josephg.com/blog/crdts-go-brrr.
  4. Kleppmann, M., & Beresford, A. R. (2017). A conflict-free replicated JSON datatype. IEEE Transactions on Parallel and Distributed Systems, 28(10), 2733–2746.