多人在线协作的神秘代码：Yjs 底层解密

正文

请到「今天看啥」查看全文

。

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

解决并发冲突（Yata算法）

什么是冲突呢？

冲突（Conflict）是指当多个用户同时对同一文档的同一位置进行独立操作时，这些操作因顺序或逻辑矛盾导致文档状态无法直接合并的现象。

冲突的核心原因

1. 并发性 ：操作在不同客户端独立产生，网络延迟导致操作到达服务器的顺序不确定。
2. 位置重叠 ：多个操作作用于相同逻辑位置（如插入到同一字符后）。
3. 缺乏全局时序 ：没有统一的时钟或顺序保证所有客户端对操作的理解一致。

YATA 算法 背后的核心思想是通过维护操作的顺序和冲突解决机制，确保所有并发修改能够正确合并，并保持文档在所有副本之间的一致性。当存在新Item 插入、现有Item 更新或删除时执行 integrate(transaction,offset) 方法，使得Yjs 能够处理不同客户端的并发操作，并确保最终文档状态一致。

Y A T A ! 这几个字符每个都对应一个 item（或者说一次字符插入的 operation）。它们通过 left 和 right 字段连接在一起。在插入新字符 T 的时候，Yjs 就会 根据 item 的 ID（逻辑时间戳） 在链表中查找合适的插入位置，将新字符对应的 item 接入链表中。 接下来根据源码来看 integrate(transaction,offset) 是如何实现？

tips： Transaction（事物） 在 Yjs 中是用于管理和封装一系列对文档的更改操作，一个Transaction关联一个Y.doc，采用structStore存储其对应的操作历史、状态同步。

更新时钟和分割内容（处理偏移量）

if (offset > 0) {
  this.id.clock += offset;
  this.left = getItemCleanEnd(transaction, transaction.doc.store, createID(this.id.client, this.id.clock - 1));
  this.origin = this.left.lastId;
  this.content = this.content.splice(offset);
  this.length -= offset;
}

offset偏移量，用于准确确定用户插入或删除的位置。当存在偏移量的时候，会根据偏移量更新clock逻辑时间戳，然后找到新位置下的文档结构的左侧item节点并更新origin为它的ID，最后将内容分割（分割内容为原内容从 offset 位置到结束位置）。

处理冲突（parent存在）

1. 判断冲突

if ((!this.left && (!this.right || this.right.left !== null)) || (this.left && this.left.right !== this.right)) 

该条件用于检查当前 Item 对象（即 this）的位置是否存在不一致或潜在的冲突。

• 情况1：当前 item 没有左邻接，存在右邻接

假设初始链表为 B -> C ，用户1在开头插入A，但由于用户1网络延迟，此时用户2已经在开头插入了D。

最终链表结构：

D -> B -> C
    /
   A

产生的可能原因：头部插入延迟、同步丢失或被覆盖、删除和插入操作并发。

• 情况2：当前 Item 没有左右邻接 Item
• 在一个初始为空的数据结构中插入第一个元素。
• 产生的可能原因：插入在空文档或者是对于YMap的操作。
• 情况3：当前 Item 有左邻接 Item ，但右连接不一致

假设初始链表为 A -> B -> C

请到「今天看啥」查看全文