Hotdry.
归档
systems

无需中心协调：交互式 CRDT 入门与 G-Counter、PN-Counter 实战

通过 TypeScript 代码实例深入讲解 CRDT 核心概念，实现无需中心协调的分布式数据一致性，包含 G-Counter、PN-Counter 等常用计数器。

在分布式系统设计中，数据一致性始终是一个核心挑战。传统方案通常依赖中心协调者（如分布式锁或共识算法）来解决冲突，但这会带来显著的延迟开销和可用性损失。CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）提供了一种优雅的替代方案：让每个副本独立工作，通过数学保证最终自动收敛到一致状态。本文将基于交互式教程思路，用 TypeScript 代码逐步实现 G-Counter 和 PN-Counter，帮助读者建立对 CRDT 的直观理解。

分布式一致性的核心困境

考虑一个简单的计数器场景：多个节点各自接收用户操作，需要将计数结果同步到所有副本。如果采用中心化方案，每次 increment 都需要先请求协调者确认，延迟往往高达数十毫秒甚至更高。更棘手的是网络分区时，系统可能完全不可用。CRDT 的设计哲学是放弃强一致性，转而追求高可用和分区容错：通过精心设计的数学结构，使得冲突解决变得确定性且无需外部干预。

CRDT 的核心在于 merge（合并）操作必须满足结合律、交换律和幂等律。这意味着无论合并的顺序如何、是否重复收到同一条消息，最终状态都必然收敛一致。满足这些属性的数据结构被统称为 CvRDT（基于状态的一致复制数据类型），是 CRDT 的重要分支。

G-Counter：只增计数器的实现

G-Counter 是一种只支持递增操作的计数器。每个副本维护一个向量数组，长度等于系统中的节点数量，每个位置记录对应节点的递增次数。读取当前值时，将所有位置求和；合并两个副本时，对每个位置取最大值。

export default class GCounter {
  private id: number;
  private counts: number[];

  constructor(id: number, size: number) {
    this.id = id;
    this.counts = new Array(size).fill(0);
  }

  increment(by: number = 1): void {
    if (by < 0) throw new Error("GCounter only supports increments");
    this.counts[this.id] += by;
  }

  value(): number {
    return this.counts.reduce((a, b) => a + b, 0);
  }

  merge(other: GCounter): void {
    if (other.counts.length !== this.counts.length) {
      throw new Error("Incompatible counters");
    }
    for (let i = 0; i < this.counts.length; i++) {
      this.counts[i] = Math.max(this.counts[i], other.counts[i]);
    }
  }

  state(): number[] {
    return [...this.counts];
  }

  static fromState(id: number, state: number[]): GCounter {
    const c = new GCounter(id, state.length);
    c.counts = [...state];
    return c;
  }
}

这段实现展示了 G-Counter 的精髓：merge 操作对每个副本取最大值，确保了单调递增特性；value 将所有分片求和得到最终计数。两个独立运行的副本即使在离线状态下各自递增，sync 时也能正确合并，不会丢失任何操作。

const N = 2;
const a = new GCounter(0, N);
const b = new GCounter(1, N);

a.increment(3);  // a: [3, 0]
b.increment(2);  // b: [0, 2]

a.merge(b);      // a: [3, 2], value = 5
b.merge(a);      // b: [3, 2], value = 5

可以看到，无论合并顺序如何，双方最终都收敛到相同的向量状态，值为 5。

PN-Counter：支持增减的计数器

现实业务往往需要同时支持增加和减少操作。PN-Counter 通过组合两个 G-Counter 来实现：正数操作累加到 P 计数器，负数操作累加到 N 计数器，最终值等于 P 减去 N。这种设计保持了内部状态的单调性，同时提供了完整的加减能力。

import GCounter from "./GCounter";

export default class PNCounter {
  private positive: GCounter;
  private negative: GCounter;

  constructor(id: number, size: number) {
    this.positive = new GCounter(id, size);
    this.negative = new GCounter(id, size);
  }

  add(delta: number): void {
    if (delta > 0) {
      this.positive.increment(delta);
    } else if (delta < 0) {
      this.negative.increment(-delta);
    }
  }

  increment(by: number = 1): void {
    this.add(by);
  }

  decrement(by: number = 1): void {
    this.add(-by);
  }

  value(): number {
    return this.positive.value() - this.negative.value();
  }

  merge(other: PNCounter): void {
    this.positive.merge((other as any).positive);
    this.negative.merge((other as any).negative);
  }

  state(): { pos: number[]; neg: number[] } {
    return {
      pos: (this.positive as any).state(),
      neg: (this.negative as any).state(),
    };
  }
}

PN-Counter 的合并操作分别对正负计数器进行，确保增减操作不会相互抵消。实际业务场景中，这种计数器常用于分布式环境下的投票统计、库存变化追踪等需要双向调整的场景。

const N = 2;
const r1 = new PNCounter(0, N);
const r2 = new PNCounter(1, N);

r1.increment(3);
r2.increment(2);
r2.decrement(1);

console.log(r1.value()); // 3（尚未同步，看不到 r2 的操作）
console.log(r2.value()); // 1（2 - 1）

r1.merge(r2);
r2.merge(r1);

console.log(r1.value()); // 4
console.log(r2.value()); // 4

最终结果 4 等于总增量 5 减去总减量 1，与网络顺序无关。

分布式一致性属性与工程实践

G-Counter 和 PN-Counter 都具备 AP 特性：优先保证可用性和分区容错，牺牲强一致性。更新操作在本地立即完成，无需等待远程确认，这带来了极低的写入延迟。工程实践中需要注意几个关键点：

向量长度需要在系统初始化时确定，动态添加节点需要额外的迁移策略。状态同步采用 gossip 协议或点对点推送，定期交换合并。监控指标应包括版本向量差异、收敛时间等，以便及时发现异常。

对于需要强一致性的场景，CRDT 可以与传统的共识算法结合，在关键路径上引入协调步骤。更多场景下，CRDT 本身提供的最终一致性已经足够，比如实时协作编辑、聊天消息同步、分布式缓存失效等。

资料来源：本文代码示例参考自 CRDT 社区广泛验证的实现模式，概念阐述基于分布式系统经典理论。

查看归档