实时协作-yjs基本理解4-Ytext

April 12, 2017

Yjs 中的 Y.Text 是一种特殊的 CRDT (Conflict-free replicated data types)，它是用于处理分布式环境中的实时合作文本编辑的数据结构。Y.Text 允许多个用户同时在文本的任何位置进行插入和删除操作，无需担心冲突或数据不一致。 Y.Text 的工作原理基于两个主要的概念：

操作的唯一标识符： 在 Yjs 中，每个插入或删除操作都由一个全局唯一的标识符标识。此标识符是由生成操作的用户的唯一标识符和一个递增的逻辑时钟值组成的。这保证了即使两个用户在相同的位置进行操作，他们的操作也可以被区分开。
操作的部分排序： Yjs 使用这些唯一标识符为所有的操作定义了一个部分排序。具体来说，如果操作 A 的标识符小于操作 B 的标识符，那么我们就说操作 A 在操作 B 之前。当两个操作在同一位置发生时，这种排序可以用来解决冲突：我们总是选择标识符较小的操作先执行。

从操作和合并的角度看： 1. 插入操作 每一个字符都被赋予一个全局唯一的标识符（ID）。这个 ID 由两部分组成：生成该操作的客户端的唯一 ID 和一个在该客户端中的递增的逻辑时钟。因此，即使在网络延迟的情况下，不同客户端的操作也能被准确地区分开。 2. 删除操作 删除操作在 Yjs 中实现的方式是，每个字符的删除信息被记录下来，并与插入操作一同被传播到所有的副本。当一个副本收到一个删除操作时，它会从文档中删除对应的字符。 3. 更新操作、在 Y.Text 中，并没有明确的“更新”操作。它通过组合删除和插入操作来达到“更新”的效果。例如，如果想在某个位置替换一个字符，你可以在那个位置先删除那个字符，然后再插入新的字符。 4. 冲突解决 当两个或更多的操作在同一位置发生时，Yjs 通过比较他们的 ID 来决定他们的顺序。因为 ID 是全局唯一的，并且有一个定义好的顺序，所以所有的副本都会得到相同的结果，无论他们收到操作的顺序如何。 5. 并发操作 当两个并发的操作到达时，Yjs 会根据前面提到的规则决定他们的顺序。这样，只要所有的副本都收到了所有的操作，他们最终就会达到相同的状态。

另外在Yjs中，通过维护一个操作日志来保存所有的插入和删除操作。操作日志是Yjs的核心数据结构，通过它可以在任何时候重建当前的文档状态。以下是一个自己实现的粗略的代码示例，用于说明这些概念：

class YText {
  constructor() {
    this.ops = []; // 操作日志
    this.text = []; // 文本的当前状态
    this.clientId = Math.random().toString(36).substring(2); // 随机生成客户端ID
    this.clock = 0; // 逻辑时钟
  }

  insert(index, char) {
    const id = { clientId: this.clientId, clock: this.clock++ };
    this.ops.push({ type: 'insert', id, index, char });
    this.text.splice(index, 0, { id, char });
  }

  delete(index) {
    const { id } = this.text[index];
    this.ops.push({ type: 'delete', id, index });
    this.text.splice(index, 1);
  }

  // 处理来自其他客户端的操作
  receive(operation) {
    if (operation.type === 'insert') {
      this.text.splice(operation.index, 0, { id: operation.id, char: operation.char });
    } else if (operation.type === 'delete') {
      const index = this.text.findIndex(c => compareIds(c.id, operation.id) === 0);
      if (index >= 0) {
        this.text.splice(index, 1);
      }
    }
    // 对文本进行重新排序
    this.text.sort((a, b) => compareIds(a.id, b.id));
  }
}

// ID比较函数
function compareIds(id1, id2) {
  if (id1.clientId < id2.clientId) {
    return -1;
  } else if (id1.clientId > id2.clientId) {
    return 1;
  } else {
    return id1.clock - id2.clock;
  }
}

在这个例子中，我假设操作是按顺序接收的，即没有网络延迟或乱序操作的问题。在实际的 Yjs 中，处理这些问题需要更多的逻辑和数据结构，包括状态向量、删除集、并进行操作转换等。

请注意，这个示例代码是一个非常简化的版本，Yjs 的实际实现会更复杂，因为它需要处理各种网络问题，例如乱序的操作和网络分区，还需要进一步分析源码。

阅读量

Written by xi ming You should follow him on Github

实时协作-yjs基本理解4-Ytext

目录