CRDT счётчики — G-Counter и PN-Counter

Простейшие CRDT для распределённого счёта. G-Counter — только инкремент. PN-Counter — позитив и негатив, через композицию двух G-Counter.

G-Counter (grow-only counter)

Счётчик, который умеет только расти. У каждой реплики свой слот в массиве.

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

  inc(value = 1) {
    this.counts[this.id] += value;
  }

  value {
    return this.counts.reduce((sum, x) => sum + x, 0);
  }

  merge(other) {
    return this.counts.map((v, i) => Math.max(v, other.counts[i]));
  }
}
  • Инкремент — каждая реплика плюсует только в свой слот.
  • Merge — поэлементный max.
  • Value — сумма всех слотов.

Почему работает

Max идемпотентен и коммутативен:

  • max(a, b) === max(b, a) ✓
  • max(max(a, b), c) === max(a, max(b, c)) ✓
  • max(a, a) === a ✓

Поэтому никакой порядок merge'ей не влияет на результат.

PN-Counter (positive-negative)

Может и инкрементиться, и декрементиться. Реализуется через композицию двух G-Counter.

class PNCounter {
  constructor(id, size) {
    this.p = new GCounter(id, size);  // позитивные изменения
    this.n = new GCounter(id, size);  // негативные изменения
  }

  inc(v) { this.p.inc(v); }
  dec(v) { this.n.inc(v); }
  value { return this.p.value - this.n.value; }

  merge(other) {
    this.p.merge(other.p);
    this.n.merge(other.n);
  }
}

PN = composition(GCounter, GCounter) — декремент это инкремент в «негативном» счётчике.

Пример синхронизации

Реплика 0: counts = [5, 0]
Реплика 1: counts = [0, 3]
                    ↓ merge
Обе:       counts = [5, 3]  → value = 8

Функциональный стиль

В академических статьях CRDT часто пишут не классы, а функции:

const init = (size) => new Array(size).fill(0);
const inc = (state, id, v) => { state[id] += v; return state; };
const merge = (a, b) => a.map((v, i) => Math.max(v, b[i]));
const value = (state) => state.reduce((s, x) => s + x, 0);

Delta-based вариант

Δ-G-Counter — хранит изменения с момента последнего sync в Map:

const deltas = new Map();  // id → дельта с последнего sync

Шлёт только дельты, не всё состояние. После доставки — очищает.

🎓 Источники

См. также