cover_image

Yjs——一个基于CRDT的数据协同框架

有点甜 腾讯AlloyTeam
2021年04月14日 04:00

目前，解决分布式数据一致性问题有两大主流的方案：OT与CRDT。OT算法由于提出时间早，方案成熟，被各大在线编辑产品使用。但因为需要定义与业务强相关的Operation，通过操作转换实现冲突处理，在应用上存在一定的限制。本文介绍一个新的基于CRDT的开源数据协同框架。

目前，解决分布式数据一致性问题有两大主流的方案：Operational transformation（简称 OT）与 Conflict-free Replicated Data Type（简称 CRDT）。

  • OT 算法诞生于 1989 年，通过定义与业务强相关的 Operation，使用操作转换实现冲突处理，解决分布式数据一致性问题。

  • CRDT ，即“无冲突复制数据类型”，最早于 2011 年提出，是一些适应于分布式系统的可以保持最终一致性的数据结构的统称。CRDT 通过使用数学模型无需涉及 index 转换，能够使网络中各个主机副本独立运行且并行更新。

本文主要介绍一个新的基于 CRDT 的开源数据协同框架——Yjs，从源码分析 Yjs 的协同实现。

图片

Yjs是基于论文《Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types》 的改进，是一个 CRDT 的实例，目前在 GitHub 上有 3.2k 🌟。

目前，基于 Yjs 框架开发的应用有以下：

图片

1. 整体架构

图片

  • y-websocket: Websocket Provider 实现了一个经典的 C/S 模型。客户端通过 Websocket 连接到单个端点。服务器在客户端之间分发 awareness 信息且进行文档更新。

  • y-protocols: 简单来说就是提供协同、监听以及历史记录的二进制编码。Awareness 协议实现了一个简单的网络不可感知算法，它可以管理用户状态(如在线状态)，同步光标位置、用户名或电子邮件地址等信息。

  • Ysj: 包含最核心的数据结构及逻辑。如数据类型的定义，数据读写编码 encoding 模块，事件监听，状态管理 StructStore，Undo/Redo 管理器等。

  • 接入层：各种第三方编辑器接入层。

2. 数据结构说明

Yjs 的数据元素使用的是双向链表的存储结构，每个元素包含左右结点，分别指向前一个 struct 及接下来一个 struct 数据。

ID：每个 struct 有一个唯一的 ID，包括一个 client 及 clock。client 是每个注册进来的协同用户的 id，具有全局唯一性。clock 是一个递增的时钟标志，根据 struct 的内容长度进行递增。

比如，某个 struct 记为 s = {client: '123456', clock: 3, len: 4, ...}, 在 s 后新插入一个新的 struct s', s'_ID = createID('123456', s.clock + s.len)。

为什么不使用 clock+1 的递增方式来实现全局唯一性，这里涉及到后续“冲突处理”的一个小技巧。

图片

整个数据结构如下：

图片

yjs 数据结构示意图

数据内容存储在 content 中，从当前文段的 start 位置开始，依次读取节点 right 上的数据，直至结束（right 为空）。

整个 structs 数据通过双向链表连接，对内容的修改可以通过链表操作来实现。因此，Yjs 支持任意数据类型，且与业务无关。如 String、Format、Json，Binary 等。

3. 冲突处理过程

1）远端 peer 数据协同

图片

websocket 数据

2）解析 struct

核心数据转换逻辑包含在 UpdateDecoder.js 、 UpdateEncoder.js 中。decoder 将 uint8Array 解析成 structs（ Array），readClientsStructRefs 处理 struct 插入逻辑。

协同数据描述

图片

decoder 解析过程：

const readStructs = (decoder, transaction, store) => {  const clientsStructRefs = new Map();  readClientsStructRefs(decoder, clientsStructRefs, transaction.doc);  mergeReadStructsIntoPendingReads(store, clientsStructRefs);  resumeStructIntegration(transaction, store);  cleanupPendingStructs(store.pendingClientsStructRefs);  tryResumePendingDeleteReaders(transaction, store);};

3）变更应用

定义两种操作类型：insert & delete，在 resumeStructIntegration 中处理数据的变更。

4）冲突处理

  • 删除操作只标记删除状态

    图片

因此， insert 与 delete 之间不会产生冲突。

  • insert 的 structs 之间冲突

    图片

具体实现步骤：

（1）将变更的 structs 入栈， const stack = store.pendingStack；

（2）对比待插入的 struct 的 origin、rightOrigin 字段与 structStore 中对应位置 Struct' 的 origin、rightOrigin 字段， 判断哪些是存在冲突的数据，记入 conflictingItems 中；

（3）然后根据 ID 的大小，决定冲突数据的应用位置。

  • 不同数据类型调用各自的 integrate、mergeWith、splice 实现，不会产生额外的冲突。

5) 处理删除

找到删除的 struct 位置，标记为 deleted 即可。详见 readAndApplyDeleteSet

6) 遍历及生成 delta

构造 ItemTextListPosition 结构，迭代 right 节点，对 content 内容进行 insertText/formatText/insertAttributes 操作。

图片

7) 创建 node 节点

通过 YElement 创建编辑器数据节点，调用 createNodeFromYElement 接口。

8) 更新 structs

调用 writeStructs 进行 structs 更新。

4. 示例：一次插入操作

1. TextNode 根据 mapping 找到对应的 YText，生成 delta

图片

2. applyDelta

图片

应用 delta，修改 transaction：

  applyDelta (delta, { sanitize = true } = {}) {    if (this.doc !== null) {      transact(this.doc, transaction => {        const currPos = new ItemTextListPosition(null, this._start, 0, new Map())        for (let i = 0; i < delta.length; i++) {          const op = delta[i]          if (op.insert !== undefined) {            const ins = (!sanitize && typeof op.insert === 'string' && i === delta.length - 1 && currPos.right === null && op.insert.slice(-1) === '\n') ? op.insert.slice(0, -1) : op.insert            if (typeof ins !== 'string' || ins.length > 0) {              insertText(transaction, this, currPos, ins, op.attributes || {})            }          } else if (op.retain !== undefined) {            formatText(transaction, this, currPos, op.retain, op.attributes || {})          } else if (op.delete !== undefined) {            deleteText(transaction, currPos, op.delete)          }        }      })    } else {      /** @type {Array<function>} */ (this._pending).push(() => this.applyDelta(delta))    }  }

3. structStore 更新过程

图片

5. 优缺点分析

优点：

  • 支持数据类型丰富；

  • 方便数据分片拉取、编辑；

  • 底层多采用二进制的位运算，提升计算速度；

  • 冲突处理算法简单等。

不足：

  • 历史数据过多，无法有效清除；

  • 双向链表操作复杂，遍历速度慢；

  • 将属性作为节点，且需要成对表示，导致节点过多。

本文主要是基于 Yjs 源码与论文的阅读，重点对 Yjs 的数据结构、处理逻辑等进行分析。Yjs 采用合理等数据结构，巧妙的规避了复杂的冲突处理，是区别于 OT 的一套全新的数据一致性解决方案。源码中还有一些比较巧妙的点，觉得比较有意思，此处就不扩展开了，有兴趣的同学可以私下交流学习。因时间比较仓促，文章内容如有疏漏或错误，望不吝赐教！

参考文献

  • https://github.com/yjs/yjs

  • https://docs.yjs.dev/

  • https://dl.acm.org/doi/abs/10.1145/2957276.2957310

关于AlloyTeam


AlloyTeam 是国内影响力最大的前端团队之一，核心成员来自前 WebQQ 前端团队。
AlloyTeam负责过WebQQ、QQ群、兴趣部落、腾讯文档等大型Web项目，积累了许多丰富宝贵的Web开发经验。

这里技术氛围好，领导nice、钱景好，无论你是身经百战的资深工程师，还是即将从学校步入社会的新人，只要你热爱挑战，希望前端技术和我们飞速提高，这里将是最适合你的地方。

加入我们，请将简历发送至 alloyteam@qq.com，或直接在公众号留言~

期待您的回复😁

最近文章：

继续滑动看下一个
腾讯AlloyTeam
向上滑动看下一个