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

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

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

节点执行新操作时，会将向量时钟中对应元素的值加一。节点接收其他节点的更新时，会比较本地和接收到的向量时钟，并据此决定更新顺序。

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

若一个向量时钟的所有元素值都大于或等于另一个向量时钟的对应元素值，则第一个向量时钟发生在第二个向量时钟之后。
若一个向量时钟的所有元素值都小于或等于另一个向量时钟的对应元素值，则第一个向量时钟发生在第二个向量时钟之前。
若两个向量时钟中部分元素值大于对方、另一部分小于对方，则两个向量时钟并发。

Yjs 使用向量时钟处理并发操作。当两个并发操作修改同一数据元素时，Yjs 根据向量时钟的顺序决定接受哪个操作：选择向量时钟值较大的操作，即后发生的操作。

Yjs 的向量时钟使用了版本向量（Version Vector）这种优化实现。版本向量只跟踪修改过共享数据的节点的逻辑时钟值，不跟踪所有节点的逻辑时钟值，以减少处理大量节点和操作时的内存与网络开销。

下面的示例说明如何使用和更新向量时钟：

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.compare(clockB) 返回 0。

调用 clockA.merge(clockB) 后，会按元素取 clockA 和 clockB 的最大值。合并后的 clockA 值变大，clockA.compare(clockB) 返回 1，表示 clockA 发生在 clockB 之后。

实际的 Yjs 系统可能包含多个节点，每个节点也可能执行多个操作。Yjs 使用向量时钟追踪这些操作，并以一致的方式合并它们。

相关文章