YATA 与协同编辑
我最近在做一个多人协作的领域驱动设计工具，多个用户可以在同一个房间里通过贴纸在画布上进行事件风暴（Event Storming），它用了 YJS 作为协同编辑层。
YJS 是一种 CRDT 实现，可用于构建实时协作应用。它是 YATA 算法的开源实现，本文主要讲底层的 YATA。
YATA
术语
YATA 使用双链表表示线性数据。每个字符属于一个插入操作。删除不真正移除节点，只是把对应的插入标记为已删除（tombstone）。
链表头尾各有一个特殊的 delimiter（哨兵）节点，保证任何插入都有左右邻居可以参照（在开头/结尾插入时也不例外）。
YATA 使用以下元组来表示一个操作：
\[o_k(id_k, origin_k, left_k, right_k, isDeleted_k, content_k)\]- $id_k$: 操作的唯一标识符
- $origin_k$: 创建时它左边（前一个）的操作 ID。创建时确定、之后永不改变
- $left_k$: 当前的左邻居。会随后续插入而改变
- $right_k$: 当前的右邻居。会随后续插入而改变
- $isDeleted_k$: 操作是否被删除
- $content_k$: 操作的内容
全序 $\lt_{c}$ 只依赖永不改变的 $origin$，这正是不同副本能算出同一顺序、从而收敛的根本原因。
例如，在 $o_i$, $o_j$ 之间插入一个字符 $c$，则会生成一个新的操作 $o_k$，其元组为 $(id_k, o_i, o_i, o_j, false, c)$。
YATA 要保证两个性质：
- 定义：收敛 - 所有副本无论以什么顺序收到操作，最终都得到完全相同的内容。
-
定义：意图保留 - 插入的字符相对位置不会改变（始终待在它创建时的左右邻居之间）。
- 定义：插入冲突 - 在同样两个操作之间插入字符的操作是冲突的。例如， $left_{new}$,$c_1$, $c_2$, $c_3$, $right_{new}$, 那么 $o_{new}$ 和 $c_1$, $c_2$, $c_3$ 是冲突的。
为什么能收敛：冲突消解归结为在冲突操作上定义一个严格全序 $\lt_{c}$（由下面规则 1~3 给出），而 $\lt_{c}$ 只依赖永不改变的 $origin$。因此每个副本对同一批操作都算出同一个顺序 → 内容一致，不需要中心协调，也与到达顺序无关。
解决冲突，需要全序关系 $\lt_{c}$.
规则 1: 插入和原点的连线不能相交。两次插入要么是嵌套的，要么是先后发生的。
规则 2: 传递性。保证不会有第三个元素排到 o1、o2 之间，破坏已定的先后关系。
规则 3: 两次插入原点相同时，创建者 id（creator，即 client/user id，不是操作的 $id_k$）小的排在左边。
插入
插入是最基本的操作类型
// 在一串互相冲突的操作 ops 中，为新操作 i 定位
insert(i, ops):
i.position = ops[0].position // 先假设 i 站在冲突区最左边
for o in ops: // 从左往右扫描每个已存在的冲突操作 o
// 组1 = 规则 1（禁止 origin 红弧交叉）：o 与 i 的两条 origin 弧只能「并排」或「嵌套」
// o < i.origin —— 并排/先后：o 整个在 i 的原点左边（弧不相交）
// 注：本算法里 ops 全在 i.origin 右边，此项恒假、永不触发，
// 仅为忠实照搬规则 1 的完整定义而保留
// i.origin <= o.origin —— 嵌套：o 的原点在 i 的原点右边(或相同)，arc(o) 套在 arc(i) 内
// 组2 = 区分两种「谁在前」的判据：
// o.origin != i.origin —— 原点不同：由上面的位置（规则 1）决定
// o.creator < i.creator —— 原点相同：id 小的在前（规则 3）
if (o < i.origin or i.origin <= o.origin)
and
(o.origin != i.origin or o.creator < i.creator):
// o 应排在 i 前面 → i 往右让一格（规则 1 的嵌套支 / 规则 3）
i.position = o.position + 1
else:
// 条件不成立：要么同原点但 o.creator 更大（不让、继续），
// 要么 o.origin 在 i.origin 左边——此时再往右让红弧就会交叉，
// 触发规则 1 的中断条件，停止扫描
if i.origin > o.origin:
// rule 1 broken：origin 连线将要交叉
break
派生操作
其它数据类型都建立在底层的「有序链表 + 冲突消解」之上。论文把这些封装叫 Manager（List Manager / Replace Manager / Map Manager）：底层只负责定序，Manager 负责「怎么写、怎么读」这套视图。冲突消解只写一次，换一种 Manager 就换一种读写解释。
List（List Manager）
头尾两个 delimiter 之间的一串有序插入。写就是按 YATA 规则在两邻居间插入，读就是按序拼接所有未删除的插入（如文本就是把字符依次连起来）。
替换（Replace Manager）
YATA 没有替换原语，替换的问题会被转化为插入问题。Replace Manager 继承自 List Manager：写就是往最左插，读就是只取最左那个（新值盖住旧值）。并发替换时，队头的插入冲突由规则 3（比 creator）确定性地选出唯一赢家，所以本质是不依赖时钟的确定性 LWW。
Map（Map Manager）
Map = 每个 key 挂一个 Replace Manager，于是每个 key 各自独立地”往最左插、读最左”，实现并发覆盖并收敛。key→Replace Manager 那层字典本身不必是 CRDT，一致性都下压到各自的 Replace Manager 里解决。
附录：收敛性证明（通俗版）
要证什么：$\lt_{c}$ 是冲突操作上的一个严格全序。只要它是全序，每个副本对同一批冲突操作就会排出完全相同的顺序 → 内容一致 → 收敛。
回忆 $\lt_{c}$ 由三条规则合成：规则 1（位置/嵌套，红弧不交叉）、规则 2（传递性）、规则 3（同原点比 creator id）。要证它是全序，需要三件事：反对称、传递、完全。
1. 反对称：不会”既 A 在前又 B 在前”（除非是同一个）
分两种情况看两个冲突操作 A、B：
- 原点相同：由规则 3，比较 creator id。id 是全序、互不相等，不可能 A 的 id 既小于又大于 B → 只有一个方向成立。
- 原点不同：由规则 1，两个原点在链表里各有唯一位置，谁嵌套在谁里面是确定的 → 只有一个方向成立。
所以定序无歧义，A、B 的先后唯一。
2. 传递：A 在 B 前、B 在 C 前 ⇒ A 在 C 前
这正是规则 2 量身定做的。规则 2 说：若 $A \lt_{c} B$，则任何排在 B 后面的元素，A 也排在它前面。于是由 $A \lt_{c} B$、$B \lt_{c} C$ 直接得 $A \lt_{c} C$——不会出现某个 C 卡在 A、B 之间把顺序打乱。
3. 完全：任意两个冲突操作总能比出先后（不会”平局”）
反证：假设 A、B 谁也排不到谁前面。
- 原点相同：那 creator id 必有一个更小（id 全序），规则 3 立刻能定序 → 与假设矛盾。
- 原点不同：把”谁也不在谁前面”展开，会推出形如 $origin_A < origin_B < A < B$ 的排列——而这恰好就是规则 1 明令禁止的红弧交叉 → 矛盾。
所以不存在”平局”，任意两个都能比出先后。
结论
三条都成立 → $\lt_{c}$ 是严格全序。又因为 $\lt_{c}$ 只依赖永不改变的 $origin$（和 creator id），任何两个副本在比较同一批冲突操作时都会得到同一个顺序，因此所有副本最终收敛到相同内容——且与操作到达顺序、是否有中心节点都无关。
附录：规则 1 的本质与 laminar family
把每个插入 i 看成它 origin 圈定的一段区间 $[origin_i, i]$（”我这一段属于这里”）。规则 1（红弧不交叉）的本质，就是要求这族区间构成一个 laminar family（层级族 / 嵌套族）。
什么是 laminar family
一族集合是 laminar 的，指任取其中两个 A、B，必满足：
\[A \subseteq B \quad\text{或}\quad B \subseteq A \quad\text{或}\quad A \cap B = \varnothing\]即要么嵌套、要么不相交，绝不部分重叠（交叉）。用括号看最直观：
laminar: [ [ ] [ ] ] （嵌套 + 并排）
非 laminar: [ ( ] ) （交叉 = 括号错配）
核心性质：laminar ⟺ 一棵树
让每个集合连到”严格包含它的最小集合”作为父节点。因为没有交叉，这个最小包含者永远唯一 → 每个节点恰好一个父亲 → 构成森林/树。所以 laminar family 和树是一回事（配平括号 ↔ 语法树、文件系统目录、层次聚类树状图，本质都是 laminar）。
补一个漂亮的规模界：$n$ 个元素上的（去重非平凡）laminar family 最多只有 $2n-1$ 个集合——即一棵树的节点数，非常省。这也是组合优化里 “uncrossing”（把交叉约束解成 laminar/树）反复被用的原因。
为什么这就是收敛的关键
- 规则 1 强制 origin 区间 laminar → 这堆插入其实组织成一棵树（同 origin 的并发插入是兄弟，嵌套插入是子孙）。
- 树有唯一确定的线性展开（中序/DFS 遍历）→ 把树压平成文档序列的方式唯一。
- 每个副本手里是同一棵树（origin 不变 + 规则 1 保证 laminar），压平方式又唯一 → 同一个序列 → 收敛。
而”交叉”对应的排列 $origin_A < origin_B < A < B$，意思是 B 声称插在 A 区间内部、却排到了 A 外面——自相矛盾，两个插入的意图无法同时满足，允许它就会发散。
所以 YATA 没有事后去”解交叉”，而是用不变的 origin + 规则 1 从一开始就禁止交叉，直接把冲突结构钉成一棵所有人一致、可唯一线性化的树；规则 3（同 origin 比 creator）只是给兄弟节点定左右次序的最后一环。