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

April 10, 2017

在现实中，CRDT 的实现需要考虑更多的细节，比如并发操作和网络延迟。为了处理这些问题，一种常见的 CRDT 用于协作编辑的类型是 LSEQ tree。然而，这个类型的数据结构非常复杂，因此在这里，我们将使用一种简化的数据类型——列表 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 来决定元素的顺序。

然而，这个简化版的列表 CRDT 还是存在一些问题的。比如，如果两个编辑器在同一毫秒内插入了一个元素，那么这两个元素的 id 就会是一样的，这就会引发问题。因此，在实际中，我们会使用更复杂的方法来生成这个 id，比如我们可以将时间戳和编辑器的唯一标识符（siteId）组合起来生成 id。

此外，这个例子也没有考虑元素的更新操作。在实际的 CRDT 中，我们通常会把一个更新操作看作是一个删除操作和一个插入操作的组合。

阅读量

Written by xi ming You should follow him on Github

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

目录