实时协作-CRDT基本理解(2)

CRDT 实现还需要处理并发操作和网络延迟。LSEQ tree 是协作编辑中常见的一类 CRDT，但其数据结构较复杂。这里使用简化的列表 CRDT 演示插入、删除和并发操作。

示例用操作日志模拟网络延迟。每个编辑器维护操作日志，记录已执行和待处理的操作；所有操作均为异步操作，可能在任意时间到达任意编辑器。

以下列表 CRDT Demo 支持插入和删除操作：

class CRDTList {
  constructor() {
    this.elements = [];
    this.history = [];
    this.remoteQueue = [];
  }

  insert(value, position) {
    const element = {value, id: Date.now()};
    this.elements.splice(position, 0, element);
    this.history.push({type: 'insert', element, position});
  }

  delete(position) {
    const element = this.elements.splice(position, 1)[0];
    this.history.push({type: 'delete', element, position});
  }

  merge(remoteList) {
    this.remoteQueue.push(...remoteList.history);
    this.processQueue();
  }

  processQueue() {
    while (this.remoteQueue.length > 0) {
      const operation = this.remoteQueue.shift();
      switch (operation.type) {
        case 'insert':
          const insertIndex = this.elements.findIndex(element => element.id > operation.element.id);
          this.elements.splice(insertIndex !== -1 ? insertIndex : this.elements.length, 0, operation.element);
          break;
        case 'delete':
          const deleteIndex = this.elements.findIndex(element => element.id === operation.element.id);
          if (deleteIndex !== -1) this.elements.splice(deleteIndex, 1);
          break;
      }
    }
  }

  print() {
    console.log(this.elements.map(element => element.value).join(""));
  }
}

// 创建两个 CRDT 列表实例
const listA = new CRDTList();
const listB = new CRDTList();

// 端 A 在光标位置 0 插入字符 'X'
listA.insert('X', 0);
listA.print(); // 输出: "X"

// 端 B 在光标位置 0 插入字符 'Y'
listB.insert('Y', 0);
listB.print(); // 输出: "Y"

// 模拟网络延迟，合并两个列表
setTimeout(() => {
  listA.merge(listB);
  listA.print(); // 输出: "YX"
}, 2000);

// 端 A 删除光标位置 0 的字符
setTimeout(() => {
  listA.delete(0);
  listA.print(); // 输出: "X"
}, 3000);

// 模拟网络延迟，合并两个列表
setTimeout(() => {
  listB.merge(listA);
  listB.print(); // 输出: "X"
}, 4000);

示例中的每个元素都有唯一 id，由插入操作的时间戳生成。合并两个列表时，代码根据 id 排序元素。

限制：两个编辑器若在同一毫秒插入元素，会生成相同的 id。实际实现可将时间戳与编辑器唯一标识符（siteId）组合生成 id。

示例未处理元素更新。实际 CRDT 中，更新通常可表示为一次删除和一次插入。

相关文章