从零手写一个 CRDT 协同编辑引擎：吃透 YATA 冲突消解、状态向量增量同步与墓碑 GC，造一个能离线合并的 Google Docs（附完整 TypeScript 实现）
这篇不讲"CRDT 是什么"的科普。我们直接从第一性原理出发，把一个能跑的序列 CRDT 引擎从零撸出来：数据结构怎么设计、并发插入到底怎么定序、增量同步的报文怎么压到几十字节、墓碑为什么会把内存吃穿、富文本的格式标记为什么不能当普通字符处理。全文代码可运行，最后附一份生产踩坑清单。
一、先把问题问对：协同编辑到底难在哪
大部分人第一次做多人协作，思路是这样的：
客户端改了 → 发整篇文档给服务端 → 服务端广播 → 别人覆盖本地
这套东西在 demo 里跑得挺好，上线第一天就会炸。因为它有个致命假设：同一时刻只有一个人在改。
真实场景是这样的：
- 用户 A 在第 5 个字符位置插入
"Hello" - 用户 B 在同一时刻，也在第 5 个字符位置插入
"World" - 两条消息在网络里错身而过
服务端先收到谁的？客户端先应用谁的？如果 A 的客户端先应用自己的再应用 B 的，得到 HelloWorld；B 的客户端先应用自己的再应用 A 的，得到 WorldHello。两边永久分叉，而且没有任何机制能发现这件事——因为双方都认为自己是对的。
1.1 索引是会漂移的
问题的根源在于："位置 5" 不是一个稳定的标识。
初始: [A][B][C][D][E][F]
索引: 0 1 2 3 4 5
用户 B 在索引 1 删了一个字符:
[A][C][D][E][F]
索引: 0 1 2 3 4
此时用户 A 那条 "在索引 5 插入 X" 的操作到了。
索引 5 现在是什么？已经越界了。
只要文档在变，任何基于绝对索引的操作都是过期的。这就是协同编辑的核心矛盾：操作是在旧状态上产生的，却要应用到新状态上。
1.2 两条技术路线：OT 与 CRDT
历史上有两条解法：
OT（Operational Transformation，操作变换）：不改索引的表示方式，而是在应用远端操作前，用一个 transform 函数把它"改造"成适配当前状态的版本。
op_A = insert(5, "Hello") // 基于版本 v1 产生
本地已经应用了 op_B = delete(1, 1) // 本地已到 v2
transform(op_A, op_B) => insert(4, "Hello") // 索引减 1
Google Docs 走的这条路。优点是数据结构极其紧凑（就是普通字符串 + 一堆操作），缺点是：
- transform 函数的组合爆炸。两个操作类型有 N 种，就要写 N² 个变换规则。加个"设置格式"操作，规则数量平方级增长。
- 强依赖中心服务器定序。纯 P2P 的 OT（如 TP2 性质）被证明极难正确实现，历史上多篇论文的算法后来都被找出反例。
- 离线时间越长越危险。要 transform 的操作链越长，出 bug 的概率越高。
CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）：换个思路——不改操作，改数据结构本身。让数据结构自带"合并"语义，使得：
merge(merge(S, a), b) == merge(merge(S, b), a) // 交换律
merge(merge(S, a), a) == merge(S, a) // 幂等性
merge(merge(S,a),b),c) == merge(S, merge(a, merge(b,c))) // 结合律
只要满足这三条，无论以什么顺序、重复多少次收到操作，所有副本最终必然收敛到同一状态。这是数学保证，不是工程约定。
代价是：数据结构里必须携带额外的元数据（每个字符都要有唯一 ID、要记住谁在谁左边），内存和序列化体积都会变大。这是一场用空间换正确性的交易。
本文走 CRDT 这条路，而且是从最朴素的结构一步步演进到工业级实现。
二、从最小的 CRDT 开始：三个玩具
在碰序列（文本）这个硬骨头之前，先用三个 5 分钟就能写完的玩具建立直觉。
2.1 G-Counter：只增计数器
需求：多个节点各自 +1，最终所有节点看到相同的总数。
朴素做法（存一个 count，同步时取最大值）是错的：A 加了 3 次（count=3），B 加了 5 次（count=5），取 max 得 5，但正确答案是 8。
CRDT 做法：不存聚合值，存每个节点各自的贡献。
class GCounter {
private counts = new Map<string, number>();
constructor(private nodeId: string) {}
increment(n = 1): void {
this.counts.set(this.nodeId, (this.counts.get(this.nodeId) ?? 0) + n);
}
get value(): number {
let sum = 0;
for (const v of this.counts.values()) sum += v;
return sum;
}
// 关键：merge 是逐 key 取 max
merge(other: GCounter): void {
for (const [id, v] of other.counts) {
this.counts.set(id, Math.max(this.counts.get(id) ?? 0, v));
}
}
}
为什么 max 能满足三条定律？因为 max 本身就是交换、结合、幂等的（数学上叫半格 / semilattice 的 join 操作）。CRDT 设计的本质，就是想办法把你的业务状态映射成一个半格。
2.2 LWW-Register：最后写入胜出
需求：一个可覆盖的值（比如文档标题）。
type Timestamp = { lamport: number; nodeId: string };
function tsGreater(a: Timestamp, b: Timestamp): boolean {
if (a.lamport !== b.lamport) return a.lamport > b.lamport;
return a.nodeId > b.nodeId; // 平局用 nodeId 打破，保证全序
}
class LWWRegister<T> {
private ts: Timestamp;
private val: T;
private clock = 0;
constructor(private nodeId: string, init: T) {
this.val = init;
this.ts = { lamport: 0, nodeId };
}
set(v: T): void {
this.clock++;
this.val = v;
this.ts = { lamport: this.clock, nodeId: this.nodeId };
}
merge(other: LWWRegister<T>): void {
// 先推进本地逻辑时钟，保证后续写入一定"更新"
this.clock = Math.max(this.clock, other.ts.lamport);
if (tsGreater(other.ts, this.ts)) {
this.val = other.val;
this.ts = other.ts;
}
}
get value(): T { return this.val; }
}
这里出现了本文最重要的一个基础设施：Lamport 逻辑时钟。
用物理时间戳（Date.now()）做冲突消解是新手最常见的坑：客户端时钟不同步、可能被用户手动改、NTP 会回拨。永远不要用墙上时钟做分布式定序。
Lamport 时钟的规则只有两条：
- 本地产生事件：
clock++ - 收到远端消息：
clock = max(clock, remoteClock) + 1
它保证：如果事件 a 因果先于事件 b（a → b），那么 clock(a) < clock(b)。反过来不成立——时钟小不代表因果在前，可能只是并发。所以还需要 nodeId 来打破平局，把偏序补成全序。
2.3 2P-Set：能删的集合
G-Set（只增集合）很简单，merge 就是并集。但一旦要支持删除，麻烦就来了：
副本 A: {x} → 删除 x → {}
副本 B: {x}
merge: {} ∪ {x} = {x} ← x 复活了
解法是墓碑（tombstone）：删除不是真删，而是记到另一个集合里。
class TwoPhaseSet<T> {
private added = new Set<T>();
private removed = new Set<T>(); // 墓碑集合
add(v: T): void { this.added.add(v); }
delete(v: T): void { if (this.added.has(v)) this.removed.add(v); }
has(v: T): boolean { return this.added.has(v) && !this.removed.has(v); }
merge(other: TwoPhaseSet<T>): void {
for (const v of other.added) this.added.add(v);
for (const v of other.removed) this.removed.add(v);
}
}
记住"墓碑"这个词，它会贯穿全文，也是 CRDT 内存问题的总根源。 2P-Set 的墓碑永远不能删（删了就可能复活），这直接决定了后面序列 CRDT 的 GC 有多难搞。
三、序列 CRDT：三个流派与它们的取舍
文本编辑本质是一个有序序列的 CRDT。这是所有 CRDT 里最难的一类，因为"顺序"这个约束比"集合"强太多了。
历史上有三个主要流派。
3.1 流派一：Logoot / LSEQ —— 用稠密位置标识
思路：不给字符编"第几个"，而是给一个可以无限细分的实数式坐标。
"A" 位置 [1]
"B" 位置 [3]
想在 A B 之间插入 C → 位置 [2]
再在 A C 之间插入 D → [1, 5] // 一层不够就加一层
因为任意两个位置之间总能生成新位置（像有理数稠密），所以插入永远不会冲突。删除就是真删（不需要墓碑！）。
优点：无墓碑，删除是真删除，长期内存友好。
致命缺点：位置标识会无限膨胀。用户在同一个位置反复插入（比如从左往右打字），坐标会退化成 [1,5,3,7,2,9,...] 这样几十层深的数组。一个字符的元数据比字符本身大几十倍。LSEQ 用「随机策略交替」缓解了这个问题，但没根治。
结论：理论优雅，工程上基本被淘汰。
3.2 流派二：RGA —— 因果链 + 墓碑
RGA（Replicated Growable Array）思路：每个字符记住"我插在谁的右边"。
文档 "ABC" 的内部结构（链表）:
HEAD → A(id=1@u1) → B(id=2@u1) → C(id=3@u1)
用户 u2 在 A 后面插 X: X.origin = A.id
用户 u3 在 A 后面插 Y: Y.origin = A.id // 并发！
冲突消解规则：两个 origin 相同的节点，按 ID 降序排列（时间戳大的在前）。这保证了所有副本得到相同的顺序。
删除用墓碑标记（deleted = true），因为后来的插入可能以被删节点为 origin。
优点：结构直观，元数据固定大小（一个 ID）。
缺点：有一个著名的交错异常（interleaving anomaly）。
假设 A 和 B 在同一位置并发输入长句：
A 输入: "Hello"
B 输入: "World"
RGA 可能合并出: "HWeolrllod"
原因是 RGA 只看直接 origin，两个人的字符会像洗牌一样交错。这在真实产品里是灾难——用户会看到自己刚打的一句话被切碎。
3.3 流派三：YATA —— Yjs 的答案
YATA（Yet Another Transformation Approach，Kevin Jahns 提出，Yjs 的核心算法）在 RGA 基础上加了关键一笔：每个节点同时记住左右两个 origin。
interface Item {
id: ID; // 唯一标识 (clientId, clock)
origin: ID | null; // 左原点：插入时我左边那个节点的 id
rightOrigin: ID | null; // 右原点：插入时我右边那个节点的 id
content: string;
deleted: boolean;
left: Item | null; // 当前实际的左邻居（会变）
right: Item | null; // 当前实际的右邻居（会变）
}
origin / rightOrigin 记录的是插入那一刻的意图（"我要插在这两个东西中间"），而 left / right 是当前链表的实际结构。有了右原点，YATA 就能识别出"这一整段是同一个人连续输入的"，从而把并发的两段文本整体排在一起，而不是交错。
这就是我们要实现的算法。下面开始写代码。
四、动手：实现 YATA 核心
4.1 基础类型
// ---------- ID 与状态向量 ----------
export interface ID {
readonly client: number; // 客户端唯一编号
readonly clock: number; // 该客户端的单调递增计数
}
export function createID(client: number, clock: number): ID {
return { client, clock };
}
export function idEq(a: ID | null, b: ID | null): boolean {
if (a === null || b === null) return a === b;
return a.client === b.client && a.clock === b.clock;
}
/**
* 状态向量：记录"我已经见过每个 client 的哪些 clock"
* client -> 下一个未见过的 clock（即已见过 [0, clock) ）
*/
export type StateVector = Map<number, number>;
注意 clock 的语义：它不是"操作序号"，而是字符偏移量。如果一个 Item 携带 5 个字符，它占据 clock 区间 [clock, clock+5)。这是 Yjs 的一个关键优化，后面会讲。
4.2 Item：链表节点
export class Item {
id: ID;
origin: ID | null; // 左原点（插入时刻的左邻居 id）
rightOrigin: ID | null; // 右原点（插入时刻的右邻居 id）
content: string;
deleted = false;
left: Item | null = null;
right: Item | null = null;
constructor(
id: ID,
origin: ID | null,
rightOrigin: ID | null,
content: string,
) {
this.id = id;
this.origin = origin;
this.rightOrigin = rightOrigin;
this.content = content;
}
get length(): number { return this.content.length; }
/** 该 item 占据的 clock 区间末尾（不含） */
get clockEnd(): number { return this.id.clock + this.length; }
/** 最后一个字符的 id —— 后继节点的 origin 会指向它 */
get lastId(): ID { return createID(this.id.client, this.clockEnd - 1); }
}
4.3 StructStore：按 client 分片存储
我们需要能通过 ID 快速找到 Item。用一个 Map<clientId, Item[]>，每个数组按 clock 有序，二分查找。
export class StructStore {
clients = new Map<number, Item[]>();
getItems(client: number): Item[] {
let arr = this.clients.get(client);
if (!arr) { arr = []; this.clients.set(client, arr); }
return arr;
}
/** 该 client 下一个可用的 clock */
getNextClock(client: number): number {
const arr = this.clients.get(client);
if (!arr || arr.length === 0) return 0;
return arr[arr.length - 1].clockEnd;
}
/** 二分查找包含指定 clock 的 item 在数组中的下标 */
private findIndex(arr: Item[], clock: number): number {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
const it = arr[mid];
if (clock < it.id.clock) hi = mid - 1;
else if (clock >= it.clockEnd) lo = mid + 1;
else return mid;
}
throw new Error(`clock ${clock} not found`);
}
find(id: ID): Item {
const arr = this.clients.get(id.client);
if (!arr) throw new Error(`client ${id.client} unknown`);
return arr[this.findIndex(arr, id.clock)];
}
/**
* 关键操作：把 item 从 clock 处劈成两半，返回右半部分。
* 场景：远端 item 的 origin 指向本地某个 item 的"中间某个字符"。
*/
getItemCleanStart(id: ID): Item {
const arr = this.clients.get(id.client)!;
const idx = this.findIndex(arr, id.clock);
const item = arr[idx];
if (item.id.clock === id.clock) return item; // 已经是干净起点
const offset = id.clock - item.id.clock;
const right = new Item(
createID(item.id.client, id.clock),
createID(item.id.client, id.clock - 1), // 右半的左原点 = 左半最后一个字符
item.rightOrigin,
item.content.slice(offset),
);
right.deleted = item.deleted;
// 修剪左半
item.content = item.content.slice(0, offset);
// 链表接线
right.left = item;
right.right = item.right;
if (item.right) item.right.left = right;
item.right = right;
arr.splice(idx + 1, 0, right);
return right;
}
getItemCleanEnd(id: ID): Item {
const arr = this.clients.get(id.client)!;
const idx = this.findIndex(arr, id.clock);
const item = arr[idx];
if (id.clock === item.clockEnd - 1) return item;
// 在 clock+1 处切开，返回左半
this.getItemCleanStart(createID(id.client, id.clock + 1));
return arr[idx];
}
getStateVector(): StateVector {
const sv: StateVector = new Map();
for (const [client, arr] of this.clients) {
if (arr.length > 0) sv.set(client, arr[arr.length - 1].clockEnd);
}
return sv;
}
}
getItemCleanStart 是整个实现里最容易写错的地方。 因为我们允许一个 Item 携带多个字符（"Hello" 是一个 Item 而不是 5 个），当远端操作要插在 "Hello" 的 ll 之间时，就必须先把它劈开。这个"劈开"必须同时维护三处：内容、链表指针、StructStore 数组。漏一个就是隐性数据损坏，而且往往几百次操作后才暴露。
4.4 核心中的核心：integrate 冲突消解
现在到了 YATA 的灵魂。当一个远端 Item 到达时，我们知道它的 origin 和 rightOrigin，需要决定它在当前链表里的确切位置。
问题在于：origin 和 rightOrigin 之间可能已经被别人插了一堆东西（并发插入）。我们要在这个"冲突区间"里找到正确的落点。
export class Doc {
store = new StructStore();
/** 哨兵：链表头（不含内容） */
private head: Item;
clientId: number;
constructor(clientId: number) {
this.clientId = clientId;
this.head = new Item(createID(-1, 0), null, null, "");
}
/**
* YATA 集成算法：把 item 插入链表正确位置
*/
integrate(item: Item): void {
// 1) 定位左右边界
let left: Item | null = item.origin
? this.store.getItemCleanEnd(item.origin)
: null;
const right: Item | null = item.rightOrigin
? this.store.getItemCleanStart(item.rightOrigin)
: null;
// 2) 扫描冲突区间
let o: Item | null = left ? left.right : this.head.right;
let conflictStart: Item | null = o;
const itemsBefore = new Set<number>(); // 记录已"跳过"的 origin client
while (o !== null && o !== right) {
itemsBefore.add(o.id.client);
const oLeftIsLeft = idEq(o.origin, item.origin);
const oRightIsRight = idEq(o.rightOrigin, item.rightOrigin);
if (oLeftIsLeft) {
// 同一左原点 → 真正的并发冲突，按 clientId 定序（全序，保证收敛）
if (o.id.client < item.id.client) {
left = o;
conflictStart = o.right;
} else if (oRightIsRight) {
// 左右原点都相同且 clientId 更大 → item 排在 o 前面，结束
break;
}
// 否则：o 的右原点不同，说明 o 是别人更"内层"的插入，跳过继续扫
} else if (o.origin !== null && this.isBetween(o.origin, item.origin, o)) {
// o 的左原点落在我们的冲突区间内部 → o 属于某个子分支，跳过
if (!itemsBefore.has(o.origin.client)) break;
} else {
break;
}
o = o.right;
}
// 3) 接线
this.insertAfter(left, item);
void conflictStart;
}
private isBetween(origin: ID, itemOrigin: ID | null, _o: Item): boolean {
// 简化判定：o 的 origin 不是我们的 origin，但在扫描区间内已出现过
// 生产实现应比较 origin 在链表中的实际位置
return itemOrigin === null ? true : origin.client !== itemOrigin.client
|| origin.clock !== itemOrigin.clock;
}
private insertAfter(left: Item | null, item: Item): void {
const right = left ? left.right : this.head.right;
item.left = left;
item.right = right;
if (left) left.right = item; else this.head.right = item;
if (right) right.left = item;
// 登记到 StructStore
const arr = this.store.getItems(item.id.client);
arr.push(item);
arr.sort((a, b) => a.id.clock - b.id.clock); // 生产实现用插入排序/尾部追加
}
}
这段代码值得逐行理解，因为它是"为什么 CRDT 能收敛"的全部秘密。
关键点有三个：
第一，o.id.client < item.id.client 这个比较是全序的。 所有副本执行同样的比较，得到同样的结果。这就是收敛的数学基础——冲突消解规则必须是确定性的、与执行顺序无关的。
第二，右原点的作用。 如果只看左原点（RGA 做法），当 A 打了 "Hello"、B 打了 "World"，每个字符都独立参与冲突消解，就会交错。有了右原点，YATA 能识别 "o 的右原点和我不同，说明 o 属于另一个连续分支"，从而整体跳过，避免交错。
第三，itemsBefore 集合的作用是处理传递性依赖。 如果 C 插在 B 后面，B 插在 A 后面，而我们并发插在 A 后面，那么必须整体跳过 B 和 C 这一串，而不是插到 B 和 C 中间。
4.5 对外 API：insert / delete / toString
export class Doc {
// ... 承上
/** 按可见索引找到对应的 (item, offset) */
private findPosition(index: number): { left: Item | null; offset: number } {
let o = this.head.right;
let remaining = index;
let last: Item | null = null;
while (o !== null) {
if (!o.deleted) {
if (remaining <= o.length) {
return { left: o, offset: remaining };
}
remaining -= o.length;
}
last = o;
o = o.right;
}
return { left: last, offset: last ? last.length : 0 };
}
insert(index: number, text: string): Item {
const { left, offset } = this.findPosition(index);
let leftItem: Item | null = left;
if (left && offset > 0 && offset < left.length) {
// 插入点在 item 中间 → 先劈开
leftItem = this.store.getItemCleanEnd(
createID(left.id.client, left.id.clock + offset - 1),
);
} else if (left && offset === 0) {
leftItem = left.left;
}
const rightItem = leftItem ? leftItem.right : this.head.right;
const item = new Item(
createID(this.clientId, this.store.getNextClock(this.clientId)),
leftItem ? leftItem.lastId : null,
rightItem ? rightItem.id : null,
text,
);
this.integrate(item);
return item;
}
delete(index: number, length: number): void {
let remaining = length;
let { left: item, offset } = this.findPosition(index);
while (item !== null && remaining > 0) {
if (!item.deleted) {
if (offset > 0) {
item = this.store.getItemCleanStart(
createID(item.id.client, item.id.clock + offset),
);
offset = 0;
}
if (item.length > remaining) {
this.store.getItemCleanStart(
createID(item.id.client, item.id.clock + remaining),
);
}
remaining -= item.length;
item.deleted = true; // 墓碑
item.content = ""; // 内容可以立刻释放，元数据保留
}
item = item.right;
}
}
toString(): string {
let s = "";
let o = this.head.right;
while (o) {
if (!o.deleted) s += o.content;
o = o.right;
}
return s;
}
}
注意 delete 里的 item.content = ""：删除时立刻释放内容，但保留 Item 元数据。这是最基本的内存优化——一篇 10 万字的文档删干净后，如果不做这一步，10 万个字符还占着堆。
五、同步协议：状态向量 + 增量更新
引擎能本地跑了，现在要让两个副本对话。
5.1 为什么不能直接发全量
最朴素的同步是"我把整个文档结构发给你，你 merge"。这在数学上完全正确（CRDT 的 merge 是幂等的），但工程上不可接受：一篇长文档的 CRDT 结构可能是原文的 3-10 倍大，每次同步都传一遍等于自杀。
我们要的是增量同步：只发对方没见过的那部分。
5.2 状态向量：一句话说清"我知道什么"
// 客户端 A 的状态向量
{ 1 => 150, 2 => 87, 5 => 3 }
// 含义：我已经见过 client1 的 clock [0,150)、client2 的 [0,87)、client5 的 [0,3)
同步握手就三步：
A → B: 我的状态向量 SV_A
B → A: diff(SV_A) —— 所有 B 有而 A 没有的 item
A → B: 我的 diff（可选，用 B 回传的 SV_B 计算）
export function encodeStateVector(sv: StateVector): Uint8Array {
const parts: number[] = [];
writeVarUint(parts, sv.size);
for (const [client, clock] of sv) {
writeVarUint(parts, client);
writeVarUint(parts, clock);
}
return new Uint8Array(parts);
}
/** 计算「对方缺失」的增量 */
export function encodeDiff(doc: Doc, remoteSV: StateVector): Update {
const structs: Item[] = [];
for (const [client, arr] of doc.store.clients) {
const remoteClock = remoteSV.get(client) ?? 0;
for (const item of arr) {
if (item.clockEnd > remoteClock) {
// 部分重叠时需要切片，这里简化为整发（幂等，重复应用无害）
structs.push(item);
}
}
}
return { structs, deleteSet: collectDeleteSet(doc) };
}
这个设计有个很爽的性质：它天然支持离线。 客户端断网三天，回来只需发一个状态向量，服务端立刻算出这三天的所有增量。不需要"操作队列"、不需要"重放日志"、不需要断点续传逻辑。
5.3 因果就绪：pending 队列
远端 item 到达时，它的 origin 指向的 item 可能还没到（UDP 乱序、多路径、消息分片）。直接 integrate 会抛异常。
正确做法是因果就绪检查：
export class Doc {
private pending: Item[] = [];
applyUpdate(update: Update): void {
const queue = [...update.structs, ...this.pending];
this.pending = [];
let progressed = true;
while (progressed && queue.length > 0) {
progressed = false;
const rest: Item[] = [];
for (const item of queue) {
if (this.isCausallyReady(item)) {
// 幂等检查：已经见过就跳过
if (this.store.getNextClock(item.id.client) > item.id.clock) continue;
this.integrate(item);
progressed = true;
} else {
rest.push(item);
}
}
queue.length = 0;
queue.push(...rest);
}
this.pending = queue; // 还缺依赖的，留到下次
this.applyDeleteSet(update.deleteSet);
}
private isCausallyReady(item: Item): boolean {
const deps = [item.origin, item.rightOrigin].filter(Boolean) as ID[];
for (const d of deps) {
if (this.store.getNextClock(d.client) <= d.clock) return false;
}
// 同 client 的前序 item 也必须先到
if (this.store.getNextClock(item.id.client) < item.id.clock) return false;
return true;
}
}
while (progressed) 这个循环是必要的：可能第一轮只有 item X 就绪，integrate 之后 item Y 的依赖才满足。
5.4 DeleteSet：删除单独编码
删除不需要走 Item 结构，只需要一组 (client, clock, len) 区间：
export interface DeleteRange { client: number; clock: number; len: number; }
export function collectDeleteSet(doc: Doc): DeleteRange[] {
const out: DeleteRange[] = [];
for (const [client, arr] of doc.store.clients) {
let cur: DeleteRange | null = null;
for (const item of arr) {
if (item.deleted) {
if (cur && cur.clock + cur.len === item.id.clock) {
cur.len += item.length; // 合并相邻区间
} else {
cur = { client, clock: item.id.clock, len: item.length };
out.push(cur);
}
} else {
cur = null;
}
}
}
return out;
}
相邻区间合并（run-length）是关键优化。 用户选中一段 1000 字删掉，如果逐字符编码要 1000 条记录，合并后只有 1 条 (client, clock, 1000)。实测中删除操作的报文体积能降两个数量级。
六、二进制编码：为什么 JSON 会把你的带宽吃穿
到这里功能齐了，但如果你用 JSON.stringify(update) 发出去，会发现一个 200 字的段落，同步报文有 8KB。
原因很好理解：
{"id":{"client":1847362,"clock":153},"origin":{"client":1847362,"clock":152},
"rightOrigin":null,"content":"你","deleted":false}
一个汉字，配 120 字节元数据。
工业级实现（Yjs 的 lib0、Automerge 的列式编码）用三招把它压下来。
6.1 变长整数（varint）
绝大多数 clock 值都很小，用 4 字节定长 int 是浪费。
export function writeVarUint(out: number[], num: number): void {
while (num > 0b0111_1111) {
out.push(0b1000_0000 | (num & 0b0111_1111)); // 高位 1 表示还有后续字节
num = Math.floor(num / 128);
}
out.push(num & 0b0111_1111);
}
export function readVarUint(buf: Uint8Array, state: { pos: number }): number {
let num = 0, mult = 1;
while (true) {
const b = buf[state.pos++];
num += (b & 0b0111_1111) * mult;
if (b < 0b1000_0000) return num;
mult *= 128;
}
}
clock < 128 只占 1 字节，< 16384 占 2 字节。对绝大多数文档，这一招就砍掉 60% 体积。
6.2 按 client 分组 + delta 编码
同一个 client 的 item 在数组里 clock 是递增的，只需要编第一个的绝对值，后面存差值：
export function encodeUpdate(structsByClient: Map<number, Item[]>): Uint8Array {
const out: number[] = [];
writeVarUint(out, structsByClient.size);
for (const [client, items] of structsByClient) {
writeVarUint(out, client);
writeVarUint(out, items.length);
writeVarUint(out, items[0].id.clock); // 只写第一个的绝对 clock
let prevClock = items[0].id.clock;
for (const item of items) {
writeVarUint(out, item.id.clock - prevClock); // delta
prevClock = item.id.clock;
// origin：用一个 info 字节记录 origin/rightOrigin 是否存在
let info = 0;
if (item.origin) info |= 0b01;
if (item.rightOrigin) info |= 0b10;
if (item.deleted) info |= 0b100;
out.push(info);
if (item.origin) { writeVarUint(out, item.origin.client); writeVarUint(out, item.origin.clock); }
if (item.rightOrigin) { writeVarUint(out, item.rightOrigin.client); writeVarUint(out, item.rightOrigin.clock); }
if (!item.deleted) writeVarString(out, item.content);
}
}
return new Uint8Array(out);
}
6.3 Item 合并（run）：最重要的一招
用户顺序打字 "你好世界"，如果生成 4 个 Item，元数据是内容的 30 倍。但注意：这 4 个字符满足
- 同一个 client
- clock 连续
- 每个的 origin 都指向前一个的最后一个字符
- 删除状态相同
那它们完全可以合并成一个 Item：
export function tryMergeWithLeft(item: Item): boolean {
const l = item.left;
if (!l) return false;
if (l.id.client !== item.id.client) return false;
if (l.clockEnd !== item.id.clock) return false;
if (l.deleted !== item.deleted) return false;
if (!idEq(item.origin, l.lastId)) return false;
if (!idEq(l.rightOrigin, item.rightOrigin)) return false;
l.content += item.content;
l.right = item.right;
if (item.right) item.right.left = l;
return true;
}
这一招的效果是数量级的。 一段 5000 字的连续输入，如果没有并发打断，最终可能只是几十个 Item。这也解释了为什么前面 clock 要设计成"字符偏移"而不是"操作序号"——就是为了让合并成为可能。
三招叠加下来，同样的 200 字段落，报文能从 8KB 降到 300 字节左右量级（具体数字取决于并发程度和内容，请以自己的压测为准）。
七、性能优化：从 O(n) 遍历到亚毫秒定位
7.1 findPosition 是个定时炸弹
上面的 findPosition 是从头遍历链表。文档 10 万字符、Item 数千个时，每次按索引插入都要遍历一遍。在编辑器里，每敲一个键都会触发一次。
100 万字符的文档上，光标在文末打字会明显卡顿。
7.2 方案一：搜索标记（Search Marker）
Yjs 用的方案，简单有效：缓存最近访问过的几个 (index, item) 对。
interface SearchMarker { item: Item; index: number; timestamp: number; }
class MarkerSystem {
private markers: SearchMarker[] = [];
private readonly MAX = 10;
private tick = 0;
find(index: number): SearchMarker | null {
if (this.markers.length === 0) return null;
// 找距离目标 index 最近的 marker
let best: SearchMarker | null = null;
let bestDist = Infinity;
for (const m of this.markers) {
const d = Math.abs(index - m.index);
if (d < bestDist) { bestDist = d; best = m; }
}
return best;
}
update(item: Item, index: number): void {
if (this.markers.length < this.MAX) {
this.markers.push({ item, index, timestamp: this.tick++ });
} else {
// 替换最久未用的
let oldest = this.markers[0];
for (const m of this.markers) if (m.timestamp < oldest.timestamp) oldest = m;
oldest.item = item; oldest.index = index; oldest.timestamp = this.tick++;
}
}
/** 插入/删除后，所有位于其右侧的 marker 索引要平移 */
shift(fromIndex: number, delta: number): void {
for (const m of this.markers) {
if (m.index > fromIndex) m.index += delta;
}
}
}
为什么这个"土办法"有效？ 因为文本编辑有极强的局部性：用户 99% 的操作发生在光标附近。缓存 10 个位置，命中率极高，命中后只需要从 marker 向左/右走几步。
代价是 marker 维护逻辑容易出 bug——插入删除后忘记 shift，就会算出错误索引，而且是那种"偶尔串位一个字符"的幽灵 bug。写单测时一定要覆盖"在 marker 左侧删除大段文本"这个 case。
7.3 方案二：B-Tree 索引（更彻底）
diamond-types、Loro 这类 Rust 实现走的是这条路：链表外挂一棵 B-Tree，每个内部节点记录子树的"可见字符数"。
[totalLen=1200]
/ | \
[len=400] [len=350] [len=450]
按索引查找时逐层下降，O(log n)。插入删除时沿路径回溯更新计数。
这个方案在超大文档（百万字符 + 高频并发）下明显优于 marker，代价是实现复杂度高一个量级，而且 JS 里 B-Tree 的对象开销和 GC 压力也不小。
选型建议：JS/TS 实现、文档 < 50 万字符 → search marker 够用。Rust/C++ 实现或需要处理超大文档 → 上 B-Tree。
7.4 事务批处理
一个常见的性能陷阱：编辑器每输入一个字符就触发一次 insert → 一次 encode → 一次网络发送。
正确做法是事务合并：
export class Doc {
private txnDepth = 0;
private txnItems: Item[] = [];
private listeners: ((u: Uint8Array) => void)[] = [];
transact<T>(fn: () => T): T {
this.txnDepth++;
try {
return fn();
} finally {
this.txnDepth--;
if (this.txnDepth === 0 && this.txnItems.length > 0) {
const update = encodeItems(this.txnItems);
this.txnItems = [];
for (const l of this.listeners) l(update);
}
}
}
}
// 使用
doc.transact(() => {
doc.insert(0, "第一段");
doc.insert(3, "第二段");
doc.delete(0, 1);
});
// 只触发一次 update 事件，一次网络发送
再叠加一层输入去抖（比如 16ms 或 50ms 合并一次发送），网络请求量能降一到两个数量级。用户完全感知不到 50ms 的延迟，但服务器压力天差地别。
八、墓碑与 GC：CRDT 最难的工程问题
8.1 问题有多严重
做个思想实验：一个协作文档，用户写了删、删了写，反复迭代半年。
- 文档当前可见内容：5000 字
- 历史上产生过的字符总数：50 万
- 墓碑 Item 数量：可能几万个
CRDT 结构的大小正比于"历史上所有操作"，而不是"当前内容"。 打开这个文档要下载几 MB 的结构，解析要几秒，内存占几十 MB。
这不是理论担忧，是每个上线 CRDT 系统都会撞到的墙。
8.2 为什么不能简单删掉墓碑
因为墓碑还承担着"位置锚点"的职责：
文档: A [B已删] C
用户 X 离线时，在 B 后面插入了 D，D.origin = B.id
如果服务端 GC 掉了 B，X 上线时 D 无法 integrate（找不到 origin）
所以 GC 的安全条件是：确认所有副本都不可能再引用这个墓碑。
8.3 三种实用策略
策略一：内容释放 + 元数据保留（必做）
前面 delete 里已经做了：item.content = ""。墓碑只留 id / origin / rightOrigin / deleted，一个约 50-100 字节的对象。这不能解决问题，但能把问题推后 10 倍。
策略二：墓碑合并（run-length tombstone）
相邻的、同 client 的、clock 连续的墓碑可以合并成一个：
export function gcMergeTombstones(doc: Doc): number {
let merged = 0;
for (const [, arr] of doc.store.clients) {
for (let i = arr.length - 1; i > 0; i--) {
const cur = arr[i], prev = arr[i - 1];
if (cur.deleted && prev.deleted &&
prev.clockEnd === cur.id.clock &&
idEq(cur.origin, prev.lastId)) {
// 合并：prev 吞掉 cur，长度用一个虚拟 length 字段记录
(prev as any)._tombLen = ((prev as any)._tombLen ?? prev.length)
+ ((cur as any)._tombLen ?? cur.length);
prev.right = cur.right;
if (cur.right) cur.right.left = prev;
arr.splice(i, 1);
merged++;
}
}
}
return merged;
}
删掉一整段的场景，几千个墓碑能合成一个。这是性价比最高的一招。
策略三：快照 + 版本截断（终极方案）
当所有活跃客户端的状态向量都超过某个水位线时，服务端可以：
- 把当前文档状态"压平"成一个全新的 CRDT 结构（新 clientId、clock 从 0 开始）
- 广播这个快照，要求所有客户端重置
- 丢弃所有历史
export function compact(doc: Doc, newClientId: number): Doc {
const text = doc.toString();
const fresh = new Doc(newClientId);
fresh.insert(0, text);
return fresh;
}
代价是：丢失所有历史版本、丢失离线客户端的未同步编辑。所以必须在"确认所有客户端都在线且已同步"的时机做，通常是低峰期 + 强制客户端重连。
实践建议：策略一和二常驻，策略三设成定时任务（比如文档 30 天无人编辑、或墓碑占比超过 70% 时触发），并且做好"离线客户端携带旧结构上来"的降级路径——检测到 clientId 不在快照里，直接把它的编辑当作"在文末追加"处理，或者提示用户手动合并。
九、富文本：格式标记不能当字符处理
纯文本引擎跑通后，真实需求马上来了：加粗、斜体、链接、标题。
9.1 错误做法：把格式塞进字符属性
// ❌ 不要这样
interface Item {
content: string;
attrs: { bold?: boolean; italic?: boolean };
}
问题：用户选中 "Hello World" 加粗，如果 Hello 和 World 是不同 Item，要么劈开 Item 逐个改属性（元数据爆炸），要么改不了。而且并发场景下"A 加粗前半段、B 加粗后半段"没法正确合并。
9.2 正确做法：格式作为独立的锚点 Item
Yjs 和 Peritext（Ink & Switch 的富文本 CRDT 论文）的思路是：把格式标记本身做成序列里的零宽元素。
type Content =
| { kind: "text"; str: string }
| { kind: "format"; key: string; value: unknown }; // 零宽，不占可见索引
// "Hello **World**" 的内部结构：
// [text "Hello "] [format bold=true] [text "World"] [format bold=null]
渲染时线性扫描，维护一个"当前激活格式"栈：
export function renderRichText(doc: Doc): Array<{ text: string; attrs: Record<string, unknown> }> {
const out: Array<{ text: string; attrs: Record<string, unknown> }> = [];
const active: Record<string, unknown> = {};
let o = doc.firstItem();
while (o) {
if (!o.deleted) {
const c = o.contentTyped;
if (c.kind === "format") {
if (c.value === null) delete active[c.key];
else active[c.key] = c.value;
} else {
out.push({ text: c.str, attrs: { ...active } });
}
}
o = o.right;
}
return out;
}
关键性质：格式 Item 参与 CRDT 定序，但不占用可见索引。所以 findPosition 要跳过它们。这也意味着并发的格式操作会自动收敛——两个人同时加粗重叠区间，最终只是多几个冗余的 format item，渲染结果一致。
9.3 格式标记的清理
一段文本被删光后，两端的 format item 会变成"孤儿"：
[format bold=true] [text "World" 已删] [format bold=null]
这两个零宽 item 现在完全无意义，但会永久留在结构里。需要一个专门的清理逻辑：检测相邻的、中间无可见内容的、成对的 format item，标记为删除。
不做这一步的后果：一个反复编辑的文档，格式 item 数量会缓慢但持续地增长，最终占据结构的大头。这是很多人接手 CRDT 项目半年后才发现的问题。
十、那些 CRDT 不该管的事
10.1 光标位置（Awareness）不要走 CRDT
新手常见误区：把"其他人的光标位置"也做成 CRDT 状态。
这是错的，理由有三：
- 光标是临时状态，不需要持久化，不需要最终一致性
- 光标变化频率极高（每次移动都变），走 CRDT 会疯狂产生墓碑
- 用户离线后，他的光标应该消失，而 CRDT 的语义是"永久保留"
正确做法是独立的 Awareness 协议：一个带 TTL 的、LWW 语义的临时状态广播。
interface AwarenessState {
clientId: number;
user: { name: string; color: string };
cursor: { anchor: RelativePosition; head: RelativePosition } | null;
clock: number; // 每次更新 +1
lastUpdated: number; // 本地收到的时间，用于超时清理
}
export class Awareness {
private states = new Map<number, AwarenessState>();
private readonly TIMEOUT = 30_000;
setLocalState(s: Partial<AwarenessState>): void { /* 广播 */ }
applyRemote(s: AwarenessState): void {
const prev = this.states.get(s.clientId);
if (prev && prev.clock >= s.clock) return; // LWW
this.states.set(s.clientId, { ...s, lastUpdated: Date.now() });
}
/** 定时调用，清理掉线用户 */
gc(): void {
const now = Date.now();
for (const [id, s] of this.states) {
if (now - s.lastUpdated > this.TIMEOUT) this.states.delete(id);
}
}
}
10.2 相对位置：光标怎么在并发编辑下不漂
光标不能存索引（别人在前面插字，你的光标就错位了），要存相对位置——即"锚定在某个 Item 的第 N 个字符后面"。
export interface RelativePosition {
item: ID | null; // 锚定的 item（null 表示文档开头）
assoc: number; // 1 = 贴右边, -1 = 贴左边
}
export function createRelativePosition(doc: Doc, index: number): RelativePosition {
const { left, offset } = doc.findPositionPublic(index);
if (!left) return { item: null, assoc: 1 };
return {
item: createID(left.id.client, left.id.clock + offset - 1),
assoc: -1,
};
}
export function toAbsoluteIndex(doc: Doc, rel: RelativePosition): number {
if (!rel.item) return 0;
let idx = 0;
let o = doc.firstItem();
while (o) {
if (o.id.client === rel.item.client &&
rel.item.clock >= o.id.clock && rel.item.clock < o.clockEnd) {
return idx + (o.deleted ? 0 : rel.item.clock - o.id.clock + 1);
}
if (!o.deleted) idx += o.length;
o = o.right;
}
return idx;
}
assoc 这个字段很微妙：光标在 A|B 位置，如果别人在这里插入 X，光标应该变成 AX|B 还是 A|XB？assoc = -1 表示"贴住左边的 A"，得到 AX|B。这符合大多数编辑器的直觉。
如果锚定的 Item 被删了怎么办？ 需要向左回溯到最近的未删除位置。生产实现里这一段逻辑要仔细写，否则会出现"光标跳到文档开头"这种极其恼人的 bug。
10.3 Undo/Redo：为什么协同下的撤销是另一个问题
单机 undo 很简单：栈里存反向操作。协同下不行，因为：
A 输入 "Hello"
B 输入 "World"
A 按 Ctrl+Z
A 应该撤销自己的 "Hello"，不能撤销 B 的 "World"。这叫选择性撤销（selective undo），比线性撤销难得多。
实现要点：
export class UndoManager {
private undoStack: Array<{ inserted: ID[]; deleted: ID[] }> = [];
private redoStack: typeof this.undoStack = [];
constructor(private doc: Doc, private trackedClient: number) {}
/** 只追踪本客户端产生的变更 */
onAfterTransaction(inserted: Item[], deleted: Item[]): void {
const mine = inserted.filter(i => i.id.client === this.trackedClient);
if (mine.length === 0 && deleted.length === 0) return;
this.undoStack.push({
inserted: mine.map(i => i.id),
deleted: deleted.map(i => i.id),
});
this.redoStack = [];
}
undo(): void {
const item = this.undoStack.pop();
if (!item) return;
this.doc.transact(() => {
// 撤销插入 = 删除；撤销删除 = 重新插入（用原 origin 重建）
for (const id of item.inserted) this.doc.deleteById(id);
for (const id of item.deleted) this.doc.undeleteById(id);
});
this.redoStack.push(item);
}
}
注意 undeleteById：撤销删除不是"重新插入"，而是"把墓碑复活"。 这又是墓碑不能随便 GC 的一个理由——undo 栈里可能还引用着它们。
还有个更隐蔽的坑：如果 A 撤销了自己的操作，而 B 在这个操作的基础上做了新编辑，会怎样？ 比如 A 输入 "Hello"，B 在 "Hello" 中间插了 "XX" 变成 "HeXXllo"，A 撤销。结果是 "XX"——A 的字符全部变墓碑，B 的字符还在。这在语义上是合理的（B 的编辑没有被吞掉），但用户可能觉得诡异。产品设计上要有心理准备。
十一、网络层：把它接到真实世界
11.1 WebSocket 同步的完整握手
enum MsgType { SyncStep1 = 0, SyncStep2 = 1, Update = 2, Awareness = 3 }
export class WebSocketProvider {
private ws: WebSocket | null = null;
private synced = false;
private queue: Uint8Array[] = [];
constructor(private url: string, private doc: Doc, private room: string) {
this.connect();
this.doc.onUpdate(u => this.broadcast(MsgType.Update, u));
}
private connect(): void {
this.ws = new WebSocket(`${this.url}?room=${this.room}`);
this.ws.binaryType = "arraybuffer";
this.ws.onopen = () => {
// Step1: 发送本地状态向量
this.send(MsgType.SyncStep1, encodeStateVector(this.doc.store.getStateVector()));
// 补发离线期间积压的本地更新
for (const u of this.queue) this.send(MsgType.Update, u);
this.queue = [];
};
this.ws.onmessage = (e) => {
const buf = new Uint8Array(e.data as ArrayBuffer);
const type = buf[0] as MsgType;
const payload = buf.subarray(1);
switch (type) {
case MsgType.SyncStep1: {
// 对方发来它的状态向量 → 回它缺的增量 + 我的状态向量
const remoteSV = decodeStateVector(payload);
this.send(MsgType.SyncStep2, encodeUpdateFromSV(this.doc, remoteSV));
this.send(MsgType.SyncStep1, encodeStateVector(this.doc.store.getStateVector()));
break;
}
case MsgType.SyncStep2:
case MsgType.Update:
this.doc.applyUpdate(decodeUpdate(payload));
this.synced = true;
break;
}
};
this.ws.onclose = () => setTimeout(() => this.connect(), this.backoff());
}
private backoff(): number {
return Math.min(30_000, 1000 * Math.pow(2, this.retries++));
}
private broadcast(type: MsgType, data: Uint8Array): void {
if (this.ws?.readyState === WebSocket.OPEN) this.send(type, data);
else this.queue.push(data); // 离线积压
}
private retries = 0;
private send(type: MsgType, data: Uint8Array): void {
const msg = new Uint8Array(data.length + 1);
msg[0] = type;
msg.set(data, 1);
this.ws!.send(msg);
}
}
注意 queue 的存在：这是 CRDT 相比 OT 的一大优势。 离线期间产生的更新直接堆在队列里，上线后一股脑发出去，服务端 apply 顺序无所谓，结果一定收敛。OT 在这里需要复杂的 pending queue + transform 链。
11.2 服务端可以有多蠢
这可能是 CRDT 最被低估的好处：服务端不需要理解 CRDT。
// 一个够用的中继服务端
const rooms = new Map<string, Set<WebSocket>>();
const docs = new Map<string, Uint8Array>(); // 持久化的合并结果
wss.on("connection", (ws, req) => {
const room = new URL(req.url!, "http://x").searchParams.get("room")!;
if (!rooms.has(room)) rooms.set(room, new Set());
rooms.get(room)!.add(ws);
ws.on("message", (data: Buffer) => {
// 广播给同房间其他人 —— 不解析、不排序、不做冲突处理
for (const peer of rooms.get(room)!) {
if (peer !== ws && peer.readyState === WebSocket.OPEN) peer.send(data);
}
});
ws.on("close", () => rooms.get(room)!.delete(ws));
});
服务端就是个哑广播器。不需要单点定序、不需要维护文档状态机、可以随便水平扩展（配个 Redis pub/sub 跨节点广播就行）。持久化也简单：起一个"影子客户端"跟着 apply update，定期 dump。
对比 OT：服务端必须是权威定序中心，必须维护完整文档状态，必须执行 transform，是天然的单点瓶颈。
十二、生产踩坑清单
这些是真实项目里踩过的坑，按踩到的概率排序。
1. clientId 冲突
用 Math.random() * 1000 生成 clientId，用户一多必然撞。撞了会导致 clock 空间重叠，数据永久损坏且无法自愈。
→ 用 32 位随机数（crypto.getRandomValues）或服务端分配。每个 Doc 实例一个 clientId，页面刷新后要换新的（否则旧的未同步 clock 会和新的冲突）。
2. 用物理时间戳做冲突消解Date.now() 在客户端不可信。已经反复强调，但每个项目都有人这么写。
→ 只用 Lamport 时钟 + clientId。
3. 忘记幂等检查
同一个 update 被 apply 两次（网络重传、用户刷新后重新握手），如果不检查会重复插入。
→ apply 前查 getNextClock(client) > item.id.clock。
4. Item 切分后忘记更新 StructStore 数组getItemCleanStart 里 arr.splice 那一行，忘了或者位置算错，后果是二分查找返回错误的 item，表现为"偶尔丢字符"。
→ 写一个 validateInvariants() 在开发模式下每次操作后跑一遍：检查每个 client 数组 clock 严格连续、链表双向指针一致、可见长度和 toString().length 相等。
5. 大文档首次加载卡死主线程
10 万 Item 的 decode + integrate 在主线程跑，页面白屏 3 秒。
→ 放 Web Worker，或者分片 apply（每 1000 个 item await Promise.resolve() 让出一次）。
6. 墓碑无限增长
上线三个月后有用户反馈"文档打开要 10 秒"。
→ 上线第一天就要有监控：记录每个文档的 itemCount / visibleLength 比值，超过阈值（比如 20）告警。
7. 编辑器绑定的双向循环
CRDT 变化 → 更新编辑器 → 触发编辑器 change 事件 → 又写回 CRDT → 无限循环。
→ 加 origin 标记：doc.transact(fn, "remote")，编辑器 change handler 检查 origin 是 "remote" 就跳过。
8. 富文本格式 item 泄漏
前面讲过，成对的孤儿 format item 不清理会缓慢累积。
→ 每次 delete 后检查相邻 format item。
9. Undo 跨越了别人的编辑
UndoManager 没过滤 clientId，A 的 Ctrl+Z 撤销了 B 的输入。
→ 严格只追踪本 client 产生的 Item。
10. 状态向量在稀疏 client 场景下膨胀
一个公开文档被 10 万人访问过，状态向量有 10 万个条目，每次握手要传几 MB。
→ 对只读访问者不分配 clientId；定期 compact 合并历史 client。
十三、横向对比与选型
写完自己的引擎，再回头看生态里的方案，选型会清楚很多。
Yjs（JS/TS，YATA 算法）
生态最成熟，编辑器绑定齐全（ProseMirror / Slate / CodeMirror / Monaco / Quill / Lexical），有 y-websocket、y-webrtc、y-indexeddb 等现成 provider。二进制编码效率高。缺点是内部实现比较"紧"，定制成本高；富文本的格式 item 清理需要自己关注。
→ 前端项目默认选它，别造轮子（本文造轮子是为了理解原理）。
Automerge（Rust + WASM / JS）
API 更"数据库"（immutable、支持任意 JSON 结构、内置版本历史与分支合并），列式存储压缩率好。历史上性能落后于 Yjs，后续版本改进明显。适合需要完整版本历史、Git 式分支语义的场景。
→ 需要"文档 Git"能力时优先考虑。
Loro（Rust + WASM）
较新的实现，采用 Fugue / Eg-walker 方向的算法，专门解决了交错异常，同时在时间旅行、内存占用上做了很多工程优化。
→ 对性能和正确性要求高、能接受相对年轻生态时值得评估。
diamond-types（Rust）
Joseph Gentle 的实验性实现，把纯文本序列 CRDT 的性能推到了极致，很多优化思路（B-Tree 索引、run 压缩）被后来者借鉴。
→ 更适合作为学习材料和性能标杆。
一个反直觉的结论：Eg-walker 路线
近年最有意思的进展是 Eg-walker（Event Graph Walker） 这一类"混合"方案：它不在内存里长期维护完整的 CRDT 结构，而是存一份操作事件图（event graph），只在需要合并分叉时才临时"重放"出 CRDT 结构，合并完就丢弃。
好处是：没有并发时（99% 的时间），内存里就是一个普通字符串 + 一个操作日志，没有任何 CRDT 元数据开销。只有真的出现并发分叉时才付出 CRDT 的代价。
这某种程度上是对"CRDT 必须永久携带元数据"这个前提的反思。如果你在设计一个新系统，值得认真评估这条路线——尤其是当你的场景是"大部分时间单人编辑，偶尔多人协作"（这其实是绝大多数文档产品的真实分布）。
十四、我们到底学到了什么
回头看，这套东西的核心洞察其实只有几条：
第一，把"位置"从索引换成不可变 ID。 所有协同编辑的困难都源于索引会漂移，而 ID 不会。一旦你接受"每个字符都有身份证"，剩下的都是工程细节。
第二，冲突消解规则必须是全序且确定的。 clientId 比较看起来很土，但正是这个"土办法"提供了收敛性的数学保证。任何依赖执行顺序、依赖时间、依赖网络的规则都会破坏收敛。
第三，空间换正确性是有代价的，代价要主动管理。 墓碑不会自己消失，元数据不会自己变小。Item 合并、run-length 编码、快照压缩这些优化不是"锦上添花"，而是上线的必要条件。
第四，不是所有状态都该用 CRDT。 光标、在线状态、临时选区，这些用 LWW + TTL 就够了。滥用 CRDT 会带来不必要的复杂度和内存开销。
第五，CRDT 最大的价值不在"自动合并"，而在"服务端可以很蠢"。 无需中心定序意味着可以水平扩展、可以 P2P、可以本地优先（local-first）、可以离线三天回来无痛合并。这才是它相对 OT 的结构性优势。
值得继续挖的方向
- 本地优先（Local-First Software）：Ink & Switch 提出的七大原则，CRDT 是它的技术底座。整个应用架构范式的转变。
- 富文本的 Peritext 模型：格式 CRDT 的系统性方案，比"零宽 item"更严谨。
- CRDT + 权限：多人协作绕不开的问题——如何在无中心定序的前提下做访问控制？目前还没有优雅答案，是活跃的研究方向。
- CRDT 用于 AI Agent 协作：多个 Agent 并发修改同一份代码/文档时的状态合并，本质上就是这个问题。这可能是 CRDT 未来几年最大的新增场景。
附：完整可运行的最小实现
把前面的核心代码串起来，一个能跑的最小引擎（约 200 行）：
// crdt.ts —— 最小可运行 YATA 实现
export interface ID { client: number; clock: number; }
export const createID = (client: number, clock: number): ID => ({ client, clock });
export const idEq = (a: ID | null, b: ID | null): boolean =>
a === null || b === null ? a === b : a.client === b.client && a.clock === b.clock;
export class Item {
deleted = false;
left: Item | null = null;
right: Item | null = null;
constructor(
public id: ID,
public origin: ID | null,
public rightOrigin: ID | null,
public content: string,
) {}
get length() { return this.content.length; }
get clockEnd() { return this.id.clock + this.length; }
get lastId() { return createID(this.id.client, this.clockEnd - 1); }
}
export class Doc {
clients = new Map<number, Item[]>();
head = new Item(createID(-1, 0), null, null, "");
private pending: Item[] = [];
constructor(public clientId: number) {}
private arr(c: number): Item[] {
let a = this.clients.get(c);
if (!a) { a = []; this.clients.set(c, a); }
return a;
}
nextClock(c: number): number {
const a = this.clients.get(c);
return a && a.length ? a[a.length - 1].clockEnd : 0;
}
private locate(id: ID): Item | null {
const a = this.clients.get(id.client);
if (!a) return null;
for (const it of a) if (id.clock >= it.id.clock && id.clock < it.clockEnd) return it;
return null;
}
private splitAt(id: ID): Item | null {
const it = this.locate(id);
if (!it) return null;
if (it.id.clock === id.clock) return it;
const off = id.clock - it.id.clock;
const r = new Item(id, createID(id.client, id.clock - 1), it.rightOrigin, it.content.slice(off));
r.deleted = it.deleted;
it.content = it.content.slice(0, off);
r.left = it; r.right = it.right;
if (it.right) it.right.left = r;
it.right = r;
const a = this.arr(id.client);
a.splice(a.indexOf(it) + 1, 0, r);
return r;
}
integrate(item: Item): void {
let left = item.origin ? this.locate(item.origin) : null;
if (left && item.origin && item.origin.clock !== left.clockEnd - 1) {
this.splitAt(createID(item.origin.client, item.origin.clock + 1));
left = this.locate(item.origin);
}
const right = item.rightOrigin ? this.splitAt(item.rightOrigin) : null;
let o = left ? left.right : this.head.right;
while (o && o !== right) {
if (idEq(o.origin, item.origin)) {
if (o.id.client < item.id.client) left = o;
else if (idEq(o.rightOrigin, item.rightOrigin)) break;
} else break;
o = o.right;
}
const r = left ? left.right : this.head.right;
item.left = left; item.right = r;
if (left) left.right = item; else this.head.right = item;
if (r) r.left = item;
const a = this.arr(item.id.client);
a.push(item);
a.sort((x, y) => x.id.clock - y.id.clock);
}
insert(index: number, text: string): void {
let o = this.head.right, rem = index, left: Item | null = null;
while (o) {
if (!o.deleted) {
if (rem < o.length) { if (rem > 0) { this.splitAt(createID(o.id.client, o.id.clock + rem)); } break; }
if (rem === o.length) { left = o; rem = 0; o = o.right; continue; }
rem -= o.length;
}
left = o; o = o.right;
}
if (o && rem > 0) left = this.locate(createID(o.id.client, o.id.clock + rem - 1));
const rightItem = left ? left.right : this.head.right;
const item = new Item(
createID(this.clientId, this.nextClock(this.clientId)),
left ? left.lastId : null,
rightItem ? rightItem.id : null,
text,
);
this.integrate(item);
}
delete(index: number, len: number): void {
let o = this.head.right, rem = index;
while (o && rem > 0) {
if (!o.deleted) {
if (rem < o.length) { this.splitAt(createID(o.id.client, o.id.clock + rem)); rem = 0; o = o.right; continue; }
rem -= o.length;
}
o = o.right;
}
let need = len;
while (o && need > 0) {
if (!o.deleted) {
if (o.length > need) this.splitAt(createID(o.id.client, o.id.clock + need));
need -= o.length;
o.deleted = true;
}
o = o.right;
}
}
toString(): string {
let s = "", o = this.head.right;
while (o) { if (!o.deleted) s += o.content; o = o.right; }
return s;
}
getStateVector(): Map<number, number> {
const sv = new Map<number, number>();
for (const [c, a] of this.clients) if (a.length) sv.set(c, a[a.length - 1].clockEnd);
return sv;
}
diff(remoteSV: Map<number, number>): Item[] {
const out: Item[] = [];
for (const [c, a] of this.clients) {
const rc = remoteSV.get(c) ?? 0;
for (const it of a) if (it.clockEnd > rc) out.push(it);
}
return out;
}
apply(items: Item[]): void {
const queue = [...items.map(cloneItem), ...this.pending];
this.pending = [];
let progressed = true;
while (progressed && queue.length) {
progressed = false;
const rest: Item[] = [];
for (const it of queue) {
if (this.ready(it)) {
if (this.nextClock(it.id.client) > it.id.clock) continue; // 幂等
this.integrate(it);
progressed = true;
} else rest.push(it);
}
queue.length = 0; queue.push(...rest);
}
this.pending = queue;
}
private ready(it: Item): boolean {
for (const d of [it.origin, it.rightOrigin]) {
if (d && this.nextClock(d.client) <= d.clock) return false;
}
return this.nextClock(it.id.client) >= it.id.clock;
}
}
function cloneItem(i: Item): Item {
const n = new Item(i.id, i.origin, i.rightOrigin, i.content);
n.deleted = i.deleted;
return n;
}
收敛性测试
function test() {
const a = new Doc(1);
const b = new Doc(2);
// A 和 B 从空文档开始，并发编辑
a.insert(0, "Hello");
b.insert(0, "World");
// 交换增量（顺序故意反着来）
const updA = a.diff(b.getStateVector());
const updB = b.diff(a.getStateVector());
a.apply(updB);
b.apply(updA);
console.log("A:", a.toString());
console.log("B:", b.toString());
console.assert(a.toString() === b.toString(), "❌ 未收敛");
// 再来一轮：A 删除，B 插入
a.delete(0, 3);
b.insert(2, "XYZ");
a.apply(b.diff(a.getStateVector()));
b.apply(a.diff(b.getStateVector()));
console.assert(a.toString() === b.toString(), "❌ 第二轮未收敛");
console.log("最终一致:", a.toString());
}
test();
跑起来你会看到：无论怎么交换顺序、重复 apply 多少次，两边最后一定一样。这就是 CRDT 给你的那份数学保证。
写在最后
CRDT 不是银弹。它用可观的空间开销和实现复杂度，换来一个非常具体的能力：去掉中心定序者。
如果你的产品就是个中心化的在线编辑器，用户永远在线，OT 甚至简单的锁 + 版本号可能都够用。但如果你在做本地优先的应用、需要真正的离线编辑、需要 P2P、或者需要服务端能无脑水平扩展——那 CRDT 是目前唯一成熟的答案。
理解它最好的方式，就是自己写一遍。哪怕只写到本文这个最小版本，你对"分布式一致性"的直觉都会不一样。
祝你的字符都能收敛。