Yjs解析

朝花夕拾

Yjs解析

By ZTao-z 0

1. YATA算法解析

YATA算法是Yjs库的核心冲突解决算法，这里主要讲解下这个算法成立的三个规则：

规则1：禁止发生冲突的插入操作之间的origin连线（红线）发生交叉。

如上图所示，图中展示了两个冲突的插入操作基状态$O_{1}$，$O_{2}$，以及他们对应的插入内容$O’_{1}$，$O’_{2}$，插入后的最终状态，只能出现两种情况：$O_{1}O’_{1}O_{2}O’_{2}$或者$O_{1}O_{2}O’_{2}O’_{1}$，绝对不能出现$O_{1}O_{2}O’_{1}O’_{2}$ 这种交叉的情况，否则算法的正确性不能保证。即满足：

$$o_{1} <_{rules1}o_{2} \Leftrightarrow o_{1} < origin_{2} \lor origin_{2} \leq origin_{1}$$

规则2：指定 $<_{c}$ 上的传递性。$o_{1} <_{c} o_{2}$确保没有大于$o_{2}$但小于$o_{1}$的操作$o$

$$o_{1} <_{rules2} o_{2} \Leftrightarrow \forall o : o_{2} <_{c} o \rightarrow o_{1} \leq o \Leftrightarrow \nexists o : o_{2} <_{c} o < o_{1}$$

规则3：当两个冲突操作具有相同的原点时，创建者id较小的操作位于左侧

$$o_{1} <_{rules3} o2 \Leftrightarrow origin_{1} \equiv origin_{2} \rightarrow creator_{1} < creator_{2}$$

2. 操作序列号生成

Yjs会给每个操作生成一个操作id，该id由一个(clientId, clockId)元组构成。clientId表示房间内客户端的标识符，全局唯一；clockId采用名为 Lamport timestamp 的逻辑时间戳，可以理解为是个从零开始的单调递增计数器，具体的更新逻辑为：

  • 收到本地事件时，localClock += 1
  • 收到远端事件时，localClock = max(remoteClock, localClock) + 1

3. 存储结构

  • StructStore：依据逻辑时序创建的结构化数据。其为房间内每个客户端分配一个扁平的数组，数组内存储该客户端的操作列表。该数据类型方便进行二分查找对应某一客户端的某一操作。
  • 双向链表：依据文档结构顺序创建的结构化数据。文档的每个操作都会插入到此链表中，可以理解为这个链表维护整个文档的最新状态。

4. 删除机制

采用双缓冲队列机制。删除的节点先放到一个临时队列A中，一段时间后再放到可删除队列B，最后清空B队列即完成删除。

5. 撤销机制

Yjs每次更新都会生成一次Transaction（转换），主要有以下两个流程：

  • 记录本次更新新增的item
  • 往DeleteSet中添加本次更新导致被删除的item

基于上述的数据结构，撤销一次Transaction可以简化为下面两个操作：

  • 将该次Transaction新增的item标记为删除
  • 重新插入该次Transaction删除的item

6. 同步机制

各客户端维护一个StateVector。Yjs 通过 StateVector 的概念来定位逻辑时间轴，这种数据结构实际上就是一组记录了某时刻全部客户端 (clientId, clockId) 的元组。

同步文档状态时，Yjs划分了两个阶段：

  • 阶段1：待同步用户向房间内所有其他用户发送自身的StateVector；
  • 阶段2：其他用户收到该用户的StateVector后，用各自的本地数据计算出最小所需Update数据，然后发回给待同步用户。

7. 参考文献

[1] https://zhuanlan.zhihu.com/p/452980520

[2] https://juejin.cn/post/7027487213525041166

[3] https://juejin.cn/post/7049148428609126414