实时协作-yjs基本理解2-向量时钟

April 12, 2017

向量时钟（Vector Clock）是分布式系统中用于记录和比较事件发生顺序的一种数据结构。每个节点都维护着一个向量时钟，向量时钟是一个列表，每个元素对应一个系统节点的逻辑时钟值。逻辑时钟值是一个非负整数，表示一个节点已经发生的事件的数量。

在 Yjs 中，每个用户或客户端可以被视为一个节点。向量时钟用于追踪每个节点的操作顺序。具体来说，每个 Yjs 节点（客户端）都维护一个向量时钟，其中，向量时钟的键是节点的 ID，值是节点已执行的操作的数量。

当一个节点执行一个新的操作时，它会在其向量时钟中对应的元素值加一。当一个节点接收到其他节点的更新时，它会将自己的向量时钟与接收到的向量时钟进行比较，并据此决定更新的顺序。

向量时钟的比较规则如下：

  • 如果一个向量时钟的所有元素值都大于或等于另一个向量时钟的对应元素值，我们说第一个向量时钟“发生在”第二个向量时钟之后。
  • 如果一个向量时钟的所有元素值都小于或等于另一个向量时钟的对应元素值，我们说第一个向量时钟“发生在”第二个向量时钟之前。
  • 如果两个向量时钟中的一部分元素值大于对方，另一部分元素值小于对方，我们说这两个向量时钟是并发的。

Yjs 使用向量时钟来解决并发操作的问题。当两个并发的操作修改了同一个数据元素时，Yjs 会根据向量时钟的顺序来决定哪个操作应该被接受。具体来说，Yjs 会选择向量时钟值较大的操作，也就是后发生的操作。

需要注意的是，Yjs 的向量时钟实际上是一种优化的实现，称为版本向量（Version Vector）。版本向量只跟踪那些修改了共享数据的节点的逻辑时钟值，而不是所有节点的逻辑时钟值。这使得 Yjs 能够以更低的内存和网络开销处理大量的节点和操作。

以下是一个简单的实例，演示了如何在 Yjs 中使用和更新向量时钟：

class VectorClock {
  constructor() {
    this.clock = {};
  }

  // 获取当前节点的时钟值
  get(siteId) {
    return this.clock[siteId] || 0;
  }

  // 增加当前节点的时钟值
  increment(siteId) {
    this.clock[siteId] = this.get(siteId) + 1;
  }

  // 合并两个向量时钟，取各自时钟值的最大值
  merge(otherClock) {
    for (let siteId in otherClock.clock) {
      this.clock[siteId] = Math.max(this.get(siteId), otherClock.get(siteId));
    }
  }

  // 比较两个向量时钟
  compare(otherClock) {
    let greater = false;
    let lesser = false;
    for (let siteId in this.clock) {
      if (this.get(siteId) > otherClock.get(siteId)) {
        greater = true;
      } else if (this.get(siteId) < otherClock.get(siteId)) {
        lesser = true;
      }
    }

    if (greater && lesser) {
      return 0; // concurrent
    } else if (greater) {
      return 1; // this clock happened after otherClock
    } else if (lesser) {
      return -1; // this clock happened before otherClock
    } else {
      return 0; // identical
    }
  }
}

let clockA = new VectorClock();
let clockB = new VectorClock();

clockA.increment('A');
clockB.increment('B');

console.log(clockA.compare(clockB)); // Output: 0, A and B are concurrent

clockA.merge(clockB);
console.log(clockA.compare(clockB)); // Output: 1, A happened after B

在这个例子中，我们首先创建了两个向量时钟 clockA 和 clockB，然后使它们各自增加一次。此时，clockA 和 clockB 的值是并发的（即，它们的值无法确定先后顺序），所以 clockA.compare(clockB) 的结果是 0。

然后我们调用 clockA.merge(clockB)，这将会取 clockA 和 clockB 的各自元素的最大值，合并后 clockA 的值变大，所以 clockA.compare(clockB) 的结果是 1，表示 clockA 发生在 clockB 之后。

这个例子很简单，在实际的 Yjs 系统中，可能有多个节点，并且每个节点都可能有多个操作。Yjs 使用向量时钟来跟踪所有这些操作，并确保它们能够以一致的方式合并。

阅读量

目录