构建 CRDT 协同 Notebook —— “盲”服务器与快照协议

协同从来不是独角戏，它需要服务端的支撑。在 Notebook 的架构中，服务端扮演的角色与传统的 CRDT 应用截然不同。

在构建 Y.js 后端时，最直观的方案通常是：在服务端（Node.js）运行一个 Y.js 实例，接收所有客户端的 Update，在内存中合并成 Y.Doc，然后定时将文档序列化写入数据库。

这种“全知全能”的服务端虽然逻辑简单，但存在致命缺陷：技术栈锁定

Y.js 是 JS 库。如果后端基础设施是 Go/Java，引入 V8 引擎或重写 CRDT 逻辑的成本极高，同时，因为各种原因我们也并不打算使用 Yjs 的 Rust port。

所以，我在构建 Notebook 的后端时，我对它的要求是：服务端不需要理解数据的内容，它只负责传递和存储数据的载体。

TL;DR;

在 Notebook 的后端架构中，仔细斟酌了如何通过清晰界定系统边界来换取可扩展性

我们拒绝了让服务端介入应用层逻辑（CRDT Parsing），保持了服务端的纯粹性（Purity）。
通过 Message 100 解决了分布式协作中的责任归属问题。
通过 Message 101 解决了黑盒数据存储中的一致性修剪问题。

End-to-End 原则与“瘦”服务器

如果某个功能（如 CRDT 合并）必须在端侧（客户端）完成以保证正确性，那么在网络中间节点（服务端）重复实现它就是冗余且低效的。

在我们的架构中：

Websocket 层：仅作为消息总线（Message Bus），按房间号（文档 ID）广播二进制流。
存储层：仅作为二进制大对象（Blob）存储。

服务端看到的 Y.js Update 不是一个对象，而是一串不透明的字节数组（Opaque Byte Array）。这样，我们赋予了服务端极致的性能和语言无关性。

但是，这样的架构带来了一个巨大的挑战：如果服务器看不懂数据，它如何确保持久化数据的完整性？它怎么知道什么时候该保存快照？怎么知道哪些增量更新可以安全删除？

为了解决这些问题，我们扩展了 Websocket 协议，设计了两个关键的自定义消息：Message 100 和 Message 101。

调度与计算分离：Snapshot Request (Msg 100)

在分布式协同中，谁负责生成快照（Snapshot）？

如果每个客户端都上传，会导致惊群效应（Thundering Herd），浪费带宽和 I/O。
如果完全依赖客户端自发上传，当所有客户端都离线时，最后的数据可能未被保存。

在无中心（Peer-to-Peer）或弱中心（如我们的架构）系统中，"谁来做脏活累活（比如生成大快照）" 是一个典型难题。我们的 Message 100 的本质是基于状态机的乐观协调算法。

在多用户协同编辑的场景下，生成全量快照（Snapshot）是一个高成本操作（CPU 密集型 + 网络带宽上传）。我们需要解决的核心问题是：在 N 个活跃的客户端中，如何选举出 Leader 来执行这次保存任务，同时避免惊群效应？

1. 为什么需要协调？—— 避免公地悲剧

如果没有协调，我们只有两种选择：

人人有责：每个客户端定期自动保存。结果：N 个用户同时上传 N 份几乎一样的快照，服务器带宽产生不必要的浪费，用户侧也有不必要的资源浪费。
没人负责：假设别人会保存。结果：所有人都离线了，最后的数据还停留在内存里，服务器重启即丢失，同时， Delta Update 会无止尽的持续增长，最终也是爆掉的结局。

为什么不使用传统共识算法？

面对这个问题，教科书式的标准答案通常是：Consensus Algorithm

传统的分布式系统可能会引入 Raft 或 Paxos 这样重量级的共识算法，或者引入 ZooKeeper/Etcd 这样的外部协调服务。但这对于我们这个 Notebook 应用来说太重了。

在多用户协同的场景下，生成快照是一个典型的分布式协调问题：在 N 个对等的客户端中，我们必须选出一个，且仅选出一个 Leader 来执行保存任务，以避免资源浪费和数据竞争。

未选择的路：重型共识（Raft / Paxos）

如果采用 Raft 或 Paxos 等强一致性算法，架构会变成这样：

选举（Election）：客户端之间需要互相通信（Heartbeats），投票选出一个 Leader。
租约（Lease）：Leader 需要定期续约，维持自己的统治地位。
脑裂（Split-brain）处理：必须通过 Quorum（法定人数）机制防止产生两个 Leader。

为什么我们最终没有用它们？

复杂度爆炸：在不稳定的浏览器环境（Tab 页休眠、网络切换）中实现 Raft 是极度困难且脆弱的。
通信开销（Overhead）：为了维持共识，客户端之间需要持续消耗带宽发送心跳包，即使文档处于空闲状态。
目的错位：Raft 追求的是 “正确性（Correctness）” ——绝对不能有两个 Leader 同时写入。但在我们的场景下，如果偶然有两个客户端同时上传了快照，结果仅仅是浪费了一次上传流量，数据并不会损坏（因为快照是基于 CRDT 状态生成的，是幂等的）。

而我们利用 WebSocket 长连接的特性，在服务端实现了一个极简的乐观协调器（Optimistic Coordinator）。

2. 服务端状态机

虽然服务端看不懂数据，但它是全知的（知道连接状态）。我们在服务端维护了一个轻量级的状态机：

type DocState struct {
    HasUnsavedChanges bool      // 是否有 Pending Updates
    LastSnapshotTime  time.Time // 上次保存时间
    ActiveSessions    []Session // 当前在线的客户端列表
    SnapshotPending   bool      // 是否已经发出了保存指令
}

协调逻辑由一个简单的 Ticker 驱动（伪代码）：

func Tick() {
    if !HasUnsavedChanges { return }           // 没变化，不用存
    if len(ActiveSessions) == 0 { return }     // 没人在线，存不了
    if time.Since(LastSnapshotTime) < 30s { return } // 存太频，歇一会

    if SnapshotPending { return } // 已经在存了，别催

    // 选举 Leader
    // 策略：随机选一个，或者选连接时间最长的（通常最稳定）
    leader := ActiveSessions[0]

    // 发送指令 Message 100
    leader.Send(Msg100_SnapshotRequest)

    SnapshotPending = true
    // 设置超时：如果 15s 后没收到快照（可能客户端崩了），重置 SnapshotPending，下次选别人
    SetTimeout(15s, func() { SnapshotPending = false })
}

3. Message 100 哲学：Inversion of Control

通常的思维是：客户端觉得数据变了 -> 客户端决定保存 -> 客户端上传。 控制流方向：Client -> Server。

Message 100 实现了控制反转：服务端觉得该保存了 -> 服务端指派客户端 -> 客户端计算 -> 客户端上传。 控制流方向：Server -> Client -> Server。

这种反转带来了巨大的架构优势：

全局限流：无论有多少个用户在疯狂打字，对于服务端来说，数据库写入压力永远是恒定的（例如每 30 秒一次）。服务端掌握了流量的主动权。
无状态客户端：前端逻辑变得极其简单。它不需要维护定时器，不需要判断“我是不是 Leader”，不需要处理竞争锁。它只需要做一个听话的 Worker：“收到指令 -> 打包 -> 上传”。
容错性：如果被选中的客户端（Worker）在上传过程中崩溃了，服务端的超时机制（Timeout）会重置状态。在下一个 Tick 中，服务端会自然地选举另一个客户端作为新的 Worker。系统具有自我修复能力。

通过 Message 100，我们在不引入任何复杂共识算法的前提下，利用中心化调度 + 边缘计算的模式，解决了我们的快照生成难题

逻辑时钟旁路：Update Meta (Msg 101)

这里需要注意的是：如何安全地清理增量更新（Pending Updates）？

比如有一个场景如下：

数据库中存有一个快照。
内存缓冲区中积压了 100 个增量 Update。
新的快照上传成功了。
服务端需要从缓冲区中删除那些“已经被包含在新快照里”的 Update，保留那些“新快照之后才到达”的 Update。

物理时间戳不可靠

如果仅凭时间戳（Timestamp）来判断，会出现严重的竞态条件。

快照是在客户端生成的（时间 $T_{gen}$ ），上传并在服务端处理完是（时间 $T_{save}$ ）。在 $T_{gen} \to T_{save}$ 期间到达服务端的 Update，物理时间晚于快照生成时间，实际上未被包含在快照中。

如果服务端简单地删除所有 $T < T_{save}$ 的 Update，就会导致数据丢失。

状态向量（State Vector）与旁路元数据 —— 状态向量与因果一致性

要彻底讲透 Message 101 的精妙之处，必须下沉到 CRDT 的数学模型——偏序关系（Partial Order）与逻辑时钟（Logical Clock）

“时间”是一个极其危险的概念。物理时钟（Wall Clock）存在偏差、漂移和不确定性。如果我们依赖 Date.now() 来判断“哪些更新已经被快照包含”，数据丢失几乎是必然的。

RisingWave Notebook 的后端设计乃至其他的后端设计当中，都应当使用 CRDT 的核心数学模型：向量时钟（Vector Clock）。

1. CRDT 的数学模型：偏序集

Y.js 的每一个操作（Item）都有一个唯一的逻辑坐标 (ClientID, Clock)。

ClientID：唯一标识一个编辑者。
Clock：一个单调递增的整数，代表该用户产生的第 N 个操作。

整个文档的状态，可以由一个 状态向量（State Vector） 唯一描述。它是一个 Map：

SV = \{ Client_A: 10, Client_B: 20, Client_C: 5 \}

这在数学上意味着：文档包含了 Client A 的前 10 个操作，Client B 的前 20 个操作，以及 Client C 的前 5 个操作。

这构成了一个 偏序关系（Partial Order） 。对于任意一个 Update $u$ （其坐标为 $C_u, Clock_u$ ）和一个快照 $S$ （其状态向量为 $SV_S$ ），我们可以定义精确的包含关系：

u \in S \iff SV_S[C_u] \ge Clock_u

这个公式不受网络延迟、服务器时间漂移或快照上传耗时的任何影响。

2. 工程难题：黑盒中的可见性

后端面临的困境是：它存储的 Update 是二进制黑盒（Blob）。服务端无法解析 Blob 内部结构，因此它不知道这个 Blob 里包含的 $C_u$ 和 $Clock_u$ 是多少。

如果为了获取这两个数字而引入 V8 引擎或重写 Y.js 解析器，违背了我们“瘦服务器”的原则。

所以，我们自定义了 Message 101 作为旁路索引。Message 101 的本质，是将 CRDT 的数学坐标从二进制黑盒中“提炼”出来，作为索引（Index）暴露给服务端。

当客户端发送一个 Update 时，它实际上发送了一个二元组：

Payload (Message Sync): Uint8Array[...] —— 这是给其他客户端看的，包含实际数据。
Meta (Message 101): { ClientID: 123, Clock: 45 } —— 这是给服务端看的，包含数学坐标。

服务端将这两者绑定存储：

// 后端的内存结构实际上建立了一个数学索引
type PendingUpdate struct {
    RawData []byte
    // 数学坐标
    Coordinate struct {
        Client uint64
        Clock  uint64
    }
}

3. Trimming Pending Updates

当快照上传完成时，服务端拿到的是快照的边界（Frontier），即 $SV_{snapshot}$ 。

服务端执行的清理逻辑，实际上是在进行向量空间的切割：

KeepSet = \{ u \in Pending \mid u.Clock > SV_{snapshot}[u.Client] \}

4. Example

时刻 T1：客户端 A 生成快照。此时 A 的状态包含 B 的前 20 个操作。 $SV_{snapshot}[B] = 20$ 。
时刻 T2：客户端 B 的第 21 个操作（Update #21）到达服务端。服务端记录 Meta: {Client: B, Clock: 21}。
时刻 T3：客户端 A 的快照上传完成。

如果是物理时间判定：T2 < T3。服务端会错误地认为 Update #21 发生在快照保存之前，应该被包含在快照里，于是删除了它。结果：数据丢失。

如果是向量时钟判定：服务端查表。 $SV_{snapshot}[B] = 20$ 。Update #21 的 Clock 是 21。

21 > 20 \implies \text{保留}

服务端正确地判断出：虽然 Update #21 在物理时间上早于快照保存，但在逻辑时间上，它属于未来。它必须被保留在 Pending 队列中，等待下一次快照。

通过 Message 101，我们不需要在服务端实现复杂的 CRDT 逻辑，仅仅通过极其廉价的整数比较，就实现了 Provably Correct 的数据一致性。这就是理论指导工程的魅力

协同从来不是独角戏，它需要服务端的支撑。在 Notebook 的架构中，服务端扮演的角色与传统的 CRDT 应用截然不同。

这种“全知全能”的服务端虽然逻辑简单，但存在致命缺陷：技术栈锁定

Y.js 是 JS 库。如果后端基础设施是 Go/Java，引入 V8 引擎或重写 CRDT 逻辑的成本极高，同时，因为各种原因我们也并不打算使用 Yjs 的 Rust port。

所以，我在构建 Notebook 的后端时，我对它的要求是：服务端不需要理解数据的内容，它只负责传递和存储数据的载体。

TL;DR;

在 Notebook 的后端架构中，仔细斟酌了如何通过清晰界定系统边界来换取可扩展性

我们拒绝了让服务端介入应用层逻辑（CRDT Parsing），保持了服务端的纯粹性（Purity）。
通过 Message 100 解决了分布式协作中的责任归属问题。
通过 Message 101 解决了黑盒数据存储中的一致性修剪问题。

End-to-End 原则与“瘦”服务器

如果某个功能（如 CRDT 合并）必须在端侧（客户端）完成以保证正确性，那么在网络中间节点（服务端）重复实现它就是冗余且低效的。

在我们的架构中：

Websocket 层：仅作为消息总线（Message Bus），按房间号（文档 ID）广播二进制流。
存储层：仅作为二进制大对象（Blob）存储。

服务端看到的 Y.js Update 不是一个对象，而是一串不透明的字节数组（Opaque Byte Array）。这样，我们赋予了服务端极致的性能和语言无关性。

为了解决这些问题，我们扩展了 Websocket 协议，设计了两个关键的自定义消息：Message 100 和 Message 101。

调度与计算分离：Snapshot Request (Msg 100)

在分布式协同中，谁负责生成快照（Snapshot）？

如果每个客户端都上传，会导致惊群效应（Thundering Herd），浪费带宽和 I/O。
如果完全依赖客户端自发上传，当所有客户端都离线时，最后的数据可能未被保存。

1. 为什么需要协调？—— 避免公地悲剧

如果没有协调，我们只有两种选择：

人人有责：每个客户端定期自动保存。结果：N 个用户同时上传 N 份几乎一样的快照，服务器带宽产生不必要的浪费，用户侧也有不必要的资源浪费。
没人负责：假设别人会保存。结果：所有人都离线了，最后的数据还停留在内存里，服务器重启即丢失，同时， Delta Update 会无止尽的持续增长，最终也是爆掉的结局。

为什么不使用传统共识算法？

面对这个问题，教科书式的标准答案通常是：Consensus Algorithm

未选择的路：重型共识（Raft / Paxos）

如果采用 Raft 或 Paxos 等强一致性算法，架构会变成这样：

选举（Election）：客户端之间需要互相通信（Heartbeats），投票选出一个 Leader。
租约（Lease）：Leader 需要定期续约，维持自己的统治地位。
脑裂（Split-brain）处理：必须通过 Quorum（法定人数）机制防止产生两个 Leader。

为什么我们最终没有用它们？

复杂度爆炸：在不稳定的浏览器环境（Tab 页休眠、网络切换）中实现 Raft 是极度困难且脆弱的。
通信开销（Overhead）：为了维持共识，客户端之间需要持续消耗带宽发送心跳包，即使文档处于空闲状态。
目的错位：Raft 追求的是 “正确性（Correctness）” ——绝对不能有两个 Leader 同时写入。但在我们的场景下，如果偶然有两个客户端同时上传了快照，结果仅仅是浪费了一次上传流量，数据并不会损坏（因为快照是基于 CRDT 状态生成的，是幂等的）。

而我们利用 WebSocket 长连接的特性，在服务端实现了一个极简的乐观协调器（Optimistic Coordinator）。

2. 服务端状态机

虽然服务端看不懂数据，但它是全知的（知道连接状态）。我们在服务端维护了一个轻量级的状态机：

type DocState struct {
    HasUnsavedChanges bool      // 是否有 Pending Updates
    LastSnapshotTime  time.Time // 上次保存时间
    ActiveSessions    []Session // 当前在线的客户端列表
    SnapshotPending   bool      // 是否已经发出了保存指令
}

协调逻辑由一个简单的 Ticker 驱动（伪代码）：

func Tick() {
    if !HasUnsavedChanges { return }           // 没变化，不用存
    if len(ActiveSessions) == 0 { return }     // 没人在线，存不了
    if time.Since(LastSnapshotTime) < 30s { return } // 存太频，歇一会

    if SnapshotPending { return } // 已经在存了，别催

    // 选举 Leader
    // 策略：随机选一个，或者选连接时间最长的（通常最稳定）
    leader := ActiveSessions[0]

    // 发送指令 Message 100
    leader.Send(Msg100_SnapshotRequest)

    SnapshotPending = true
    // 设置超时：如果 15s 后没收到快照（可能客户端崩了），重置 SnapshotPending，下次选别人
    SetTimeout(15s, func() { SnapshotPending = false })
}

3. Message 100 哲学：Inversion of Control

通常的思维是：客户端觉得数据变了 -> 客户端决定保存 -> 客户端上传。 控制流方向：Client -> Server。

Message 100 实现了控制反转：服务端觉得该保存了 -> 服务端指派客户端 -> 客户端计算 -> 客户端上传。 控制流方向：Server -> Client -> Server。

这种反转带来了巨大的架构优势：

全局限流：无论有多少个用户在疯狂打字，对于服务端来说，数据库写入压力永远是恒定的（例如每 30 秒一次）。服务端掌握了流量的主动权。
无状态客户端：前端逻辑变得极其简单。它不需要维护定时器，不需要判断“我是不是 Leader”，不需要处理竞争锁。它只需要做一个听话的 Worker：“收到指令 -> 打包 -> 上传”。
容错性：如果被选中的客户端（Worker）在上传过程中崩溃了，服务端的超时机制（Timeout）会重置状态。在下一个 Tick 中，服务端会自然地选举另一个客户端作为新的 Worker。系统具有自我修复能力。

通过 Message 100，我们在不引入任何复杂共识算法的前提下，利用中心化调度 + 边缘计算的模式，解决了我们的快照生成难题

逻辑时钟旁路：Update Meta (Msg 101)

这里需要注意的是：如何安全地清理增量更新（Pending Updates）？

比如有一个场景如下：

数据库中存有一个快照。
内存缓冲区中积压了 100 个增量 Update。
新的快照上传成功了。
服务端需要从缓冲区中删除那些“已经被包含在新快照里”的 Update，保留那些“新快照之后才到达”的 Update。

物理时间戳不可靠

如果仅凭时间戳（Timestamp）来判断，会出现严重的竞态条件。

如果服务端简单地删除所有 $T < T_{save}$ 的 Update，就会导致数据丢失。

状态向量（State Vector）与旁路元数据 —— 状态向量与因果一致性

要彻底讲透 Message 101 的精妙之处，必须下沉到 CRDT 的数学模型——偏序关系（Partial Order）与逻辑时钟（Logical Clock）

RisingWave Notebook 的后端设计乃至其他的后端设计当中，都应当使用 CRDT 的核心数学模型：向量时钟（Vector Clock）。

1. CRDT 的数学模型：偏序集

Y.js 的每一个操作（Item）都有一个唯一的逻辑坐标 (ClientID, Clock)。

ClientID：唯一标识一个编辑者。
Clock：一个单调递增的整数，代表该用户产生的第 N 个操作。

整个文档的状态，可以由一个 状态向量（State Vector） 唯一描述。它是一个 Map：

SV = \{ Client_A: 10, Client_B: 20, Client_C: 5 \}

这在数学上意味着：文档包含了 Client A 的前 10 个操作，Client B 的前 20 个操作，以及 Client C 的前 5 个操作。

u \in S \iff SV_S[C_u] \ge Clock_u

这个公式不受网络延迟、服务器时间漂移或快照上传耗时的任何影响。

2. 工程难题：黑盒中的可见性

后端面临的困境是：它存储的 Update 是二进制黑盒（Blob）。服务端无法解析 Blob 内部结构，因此它不知道这个 Blob 里包含的 $C_u$ 和 $Clock_u$ 是多少。

如果为了获取这两个数字而引入 V8 引擎或重写 Y.js 解析器，违背了我们“瘦服务器”的原则。

当客户端发送一个 Update 时，它实际上发送了一个二元组：

Payload (Message Sync): Uint8Array[...] —— 这是给其他客户端看的，包含实际数据。
Meta (Message 101): { ClientID: 123, Clock: 45 } —— 这是给服务端看的，包含数学坐标。

服务端将这两者绑定存储：

// 后端的内存结构实际上建立了一个数学索引
type PendingUpdate struct {
    RawData []byte
    // 数学坐标
    Coordinate struct {
        Client uint64
        Clock  uint64
    }
}

3. Trimming Pending Updates

当快照上传完成时，服务端拿到的是快照的边界（Frontier），即 $SV_{snapshot}$ 。

服务端执行的清理逻辑，实际上是在进行向量空间的切割：

KeepSet = \{ u \in Pending \mid u.Clock > SV_{snapshot}[u.Client] \}

4. Example

时刻 T1：客户端 A 生成快照。此时 A 的状态包含 B 的前 20 个操作。 $SV_{snapshot}[B] = 20$ 。
时刻 T2：客户端 B 的第 21 个操作（Update #21）到达服务端。服务端记录 Meta: {Client: B, Clock: 21}。
时刻 T3：客户端 A 的快照上传完成。

如果是物理时间判定：T2 < T3。服务端会错误地认为 Update #21 发生在快照保存之前，应该被包含在快照里，于是删除了它。结果：数据丢失。

如果是向量时钟判定：服务端查表。 $SV_{snapshot}[B] = 20$ 。Update #21 的 Clock 是 21。

21 > 20 \implies \text{保留}

服务端正确地判断出：虽然 Update #21 在物理时间上早于快照保存，但在逻辑时间上，它属于未来。它必须被保留在 Pending 队列中，等待下一次快照。

构建 CRDT 协同 Notebook —— “盲”服务器与快照协议

阅读此文章之前，你可能需要首先阅读以下的文章才能更好的理解上下文。

TL;DR;

End-to-End 原则与“瘦”服务器

调度与计算分离：Snapshot Request (Msg 100)

1. 为什么需要协调？—— 避免公地悲剧

为什么不使用传统共识算法？

未选择的路：重型共识（Raft / Paxos）

为什么我们最终没有用它们？

2. 服务端状态机

3. Message 100 哲学：Inversion of Control

逻辑时钟旁路：Update Meta (Msg 101)

物理时间戳不可靠

状态向量（State Vector）与旁路元数据 —— 状态向量与因果一致性

1. CRDT 的数学模型：偏序集

2. 工程难题：黑盒中的可见性

3. Trimming Pending Updates

4. Example

构建 CRDT 协同 Notebook —— “盲”服务器与快照协议

阅读此文章之前，你可能需要首先阅读以下的文章才能更好的理解上下文。

TL;DR;

End-to-End 原则与“瘦”服务器

调度与计算分离：Snapshot Request (Msg 100)

1. 为什么需要协调？—— 避免公地悲剧

为什么不使用传统共识算法？

未选择的路：重型共识（Raft / Paxos）

为什么我们最终没有用它们？

2. 服务端状态机

3. Message 100 哲学：Inversion of Control

逻辑时钟旁路：Update Meta (Msg 101)

物理时间戳不可靠

状态向量（State Vector）与旁路元数据 —— 状态向量与因果一致性

1. CRDT 的数学模型：偏序集

2. 工程难题：黑盒中的可见性

3. Trimming Pending Updates

4. Example