探秘前端 CRDT 实时协作库 Yjs 工程实现 - 掘金

• 建模数据结构

• 解决并发冲突

• 回溯历史记录

• 同步网络状态

import * as Y from 'yjs'

// 应用中的全部协作状态均可在单个 YDoc 容器中承载
// 将该实例传入 WebSocket 等协议的 provider 后即可支持网络同步
const doc = new Y.Doc()

// 在 YDoc 上可以创建不同类型的顶层 YModel 实例
// 这里创建了一个顶层名为 root 的 YMap
const yRoot = doc.getMap('root')

// 也可以用 class 构造器来实例化独立的 YMap 等 YModel
// 可直接用 get set delete 等常见 API 对 YModel 增删改查
const yPoint = new Y.Map()
yPoint.set('x', 0)
yPoint.set('y', 0)

// YMap 的值也可以是 YMap，从而构造出嵌套的数据类型
yRoot.set('point', yPoint)

// YMap 中还可以存入 YText 等其他 YModel，形成复合的数据类型
const yName = new Y.Text()
yName.insert(0, 'Wilson Edwards')
yRoot.set('name', yName)
复制代码

// 可以用 2 份独立的 YDoc 实例来模拟 2 个客户端
const doc1 = new Y.Doc()
const doc2 = new Y.Doc()
const yText1 = doc1.getText()
const yText2 = doc2.getText()

// 在某份 YDoc 更新时，应用二进制的 update 数据到另一份 YDoc 上
doc1.on('update', (update) => Y.applyUpdate(doc2, update))
doc2.on('update', (update) => Y.applyUpdate(doc1, update))

// 制造两次存在潜在冲突的更新
yText1.insert(0, 'Edwards')
yText2.insert(0, 'Wilson')

// CRDT 算法可保证两份客户端中的状态始终一致
yText1.toJSON() // WilsonEdwards
yText2.toJSON() // WilsonEdwards
复制代码

建模数据结构

// Yjs 中的 ID 源码，这样的朴素实现有利于引擎的 hidden class 优化
class ID {
  constructor (client: number, clock: number) {
    // 客户端的唯一 ID
    this.client = client
    // 逻辑时间戳
    this.clock = clock
  }
}
复制代码

• 发生本地事件时，localClock += 1。

• 在接收到远程事件时，localClock = max(remoteClock, localClock) + 1。

// 实践中可以用 doc.store.clients.get(doc.clientID) 查看
doc.store.clients: {
  114514: [Item, Item, Item], // ...
  1919810: [Item, Item, Item] // ...
}
复制代码

• 依据文档结构顺序（即 document order）建模的双向链表。

• 依据逻辑时序（即 insertion order）建模的 StructStore。

const yPoint = new Y.Map()
yRoot.set('a', yPoint) // item 1
yPoint.set('x', 0) // item 2
yPoint.set('y', 0) // item 3
复制代码

解决并发冲突

• origin 字段存储 item 在插入时的左侧节点。

• rightOrigin 字段存储 item 在插入时的右侧节点。

while (o !== null && o !== this.right) {
  itemsBeforeOrigin.add(o)
  conflictingItems.add(o)
  if (compareIDs(this.origin, o.origin)) {
    if (o.id.client < this.id.client) {
      left = o
      conflictingItems.clear()
    } else if (compareIDs(this.rightOrigin, o.rightOrigin)) {
      break
    }
  } else if (o.origin !== null && itemsBeforeOrigin.has(getItem(transaction.doc.store, o.origin))) {
    if (!conflictingItems.has(getItem(transaction.doc.store, o.origin))) {
      left = o
      conflictingItems.clear()
    }
  } else {
    break
  }
  o = o.right
}
复制代码

回溯历史记录

• 在 item 中不会记录它时何时被删除，或是被哪个用户删除了。

• 在 StructStore 中也不会记录删除操作。

• 在删除发生后，本地的 clock 不会递增。

• 这次更新所插入的 item。

• 这次更新所删除 item 的 DeleteSet。

• 将这次 transaction 所插入的 item 标记为删除。

• 将这次更新所删除的 item 标记为恢复。

同步网络状态

• 整份 Yjs 文档可以被编码为 Uint8Array 形式的 update 数据，Yjs 也可以从二进制数据中反序列化出 YDoc 的对象结构。每次文档更新的 transaction 也会计算出增量的更新以供同步，其中包含 item 和 DeleteSet，如前所述。

• Yjs 通过 state vector 的概念来定位逻辑时间轴，这种数据结构实际上就是一组记录了某时刻全部客户端 (client, clock) 的 tuple。

• 阶段一：某个客户端可以发送自己本地的 state vector，向远程客户端获取缺失的文档 update 数据。

• 阶段二：远程客户端可以使用各自的本地 clock 计算出该客户端所需的 item 对象，并进一步编码生成包含了所有未同步状态的最小 update 数据。

总结

• 基于双向链表和 StructStore 的基础数据结构

• 基于 YATA 算法的并发冲突解决机制

• 基于 DeleteSet 和 Transaction 机制的撤销重做

• 基于两阶段划分的同步机制

• YATA 论文介绍了 Yjs 的算法设计与正确性证明。

• Yjs Internals 记录了 Yjs 的关键内部结构，其中很多内容对本文有帮助。

• Are CRDTs suitable for shared editing 由 Yjs 作者 Kevin Jahns 介绍了他实现的若干关键优化。

• 5000x fater CRDTs: An Adventure in Optimization 是 OT 库 ShareDB 作者 Seph Gentle 撰写的博文，深度剖析了 CRDT 工程性能改进的历程。

• How Yjs works from the inside out 是 Seph 为了解 Yjs 而邀请 Kevin 做的视频访谈，虽然很长但相当有启发。

• 个人的 D2 分享介绍了 Yjs 的项目接入实践。