CRDT множества — G-set, 2P-set, LWW-set, OR-set

CRDT-структуры для множеств. От простейшего G-set (только добавление) до OR-set (полноценный set с add/remove). Каждый следующий — компромисс между функциональностью и накладными расходами.

G-set (Grow-only set)

Только добавление. Merge = union.

class GSet {
  constructor { this.items = new Set(); }
  add(item) { this.items.add(item); }
  merge(other) {
    for (const x of other.items) this.items.add(x);
  }
}
  • + Простой, безконфликтный.
  • - Не умеет remove.

2P-set (Two-phase set)

Два множества: added и removed. Удалённое нельзя вернуть.

class TwoPSet {
  constructor {
    this.added = new Set();
    this.removed = new Set();
  }
  add(item) { this.added.add(item); }
  remove(item) {
    if (this.added.has(item)) this.removed.add(item);
  }
  has(item) {
    return this.added.has(item) && !this.removed.has(item);
  }
}
  • Семантика add-wins при первой операции: add → remove → add остаётся deleted.
  • + Можно удалять.
  • - Удалённый навсегда удалён.

LWW-set (Last-Write-Wins set)

Add и remove с timestamps. Побеждает последняя по времени операция.

class LWWSet {
  constructor {
    this.added = new Map();    // item → timestamp
    this.removed = new Map();
  }
  add(item) { this.added.set(item, Date.now()); }
  remove(item) { this.removed.set(item, Date.now()); }
  has(item) {
    const addT = this.added.get(item) ?? -1;
    const remT = this.removed.get(item) ?? -1;
    return addT > remT;
  }
}
  • + Можно вернуть удалённое.
  • - Зависит от синхронизации часов. Date.now() в JS — миллисекунды, легко получить одинаковый timestamp.

OR-set (Observed-Remove set)

Каждое добавление получает уникальный tag. Remove удаляет конкретные tags. Параллельные add и remove обоих остаются → элемент в множестве.

class ORSet {
  constructor { this.entries() = ; }  // [{item, tag}]
  add(item) { this.entries().push({ item, tag: uuid }); }
  remove(item) {
    this.entries() = this.entries().filter(e => e.item !== item);
  }
}
  • + Самая «обычная» семантика множества.
  • - Накладные расходы на tags, нетривиальный GC удалённых.

PN-set

Композиция: count добавлений минус count удалений. Element-in-set если count > 0.

Сводная таблица

Set add remove re-add накладные расходы
G-set да — — низкие
2P-set да да (one-way) — средние
LWW-set да да да (по timestamp) средние (нужны часы)
OR-set да да да высокие (tags)
PN-set да да да средние

Garbage collection

Главная боль CRDT-множеств: «множество из 1 элемента может занимать память на 2000 элементов».

В distributed-среде нельзя удалить tombstone, пока не убедился, что все реплики его видели. Это нетривиально без координатора.

Где использовать

  • G-set — append-only логи, immutable списки.
  • 2P-set — каталоги без re-add (банковские blacklists).
  • LWW-set — простой shopping cart, лайки.
  • OR-set — комментарии, теги, любые user-facing множества.

🎓 Источники

См. также