SuavePlan/suaveplan
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
suaveplan/openspec/changes/crdt-completion/proposal.md
admin fbc70f96e6 Initial Commit
2026-05-27 23:29:53 +01:00

10 KiB
Raw Permalink Blame History

CRDT completion — G-Set and LWW-Map

Package: @suaveplan/crdt Status: PROPOSED Type: feature

Why

The genesis port of @suaveplan/crdt ships seven CRDTs — GCounter, PNCounter, LWWRegister, MVRegister, ORSet, TwoPSet, and RGA — but it omits the two upstream CRDTs that round out the catalogue: GSet (grow-only set) and LWWMap (last-write-wins map).

GSet is the simplest set CRDT and the canonical building block for set-shaped state where elements are only ever added — feature flags reached, IDs seen, addresses indexed. Genesis's TwoPSet (two-phase set, supports add + remove with tombstones) and ORSet (observed-remove set, supports add + remove with unique tags) are heavier alternatives that pay for capabilities GSet consumers never need. Without GSet, every grow-only consumer either rolls their own or accepts a TwoPSet that allocates a removed-set they'll never populate.

LWWMap is the only map CRDT in the upstream catalogue and has no genesis equivalent — LWWRegister covers a single value, but multi-key state (per-tenant settings, per-record metadata, per-row last-modified columns) needs an LWW-Map. Genesis consumers currently have no way to express "merge two map states with last-write-wins per key, preserving tombstones for deletes." RGA is sequence-shaped, not key-shaped — it doesn't substitute.

Both upstream implementations are stable, in production use elsewhere, and verifiable against well-known commutative / associative / idempotent CRDT properties. This change ports both with the genesis-wide additions: injectable Clock, CrdtError-routed throws, and 100% line + property-based test coverage.

What changes

  • ADDED: crdts/g-set/g-set module — class GSet<T> implementing CRDT<Set<T>, GSetState<T>> with add(value), has(value), value(), state(), merge(remote), toJSON(), fromJSON(json), clone(). Construction signature new GSet<T>(nodeId: string, options?: GSetOptions<T>) matches the genesis CRDT base shape. Also exports GSetState<T> (state envelope) and GSetOptions<T> (initialElements?: T[]).
  • ADDED: crdts/lww-map/lww-map module — class LWWMap<V> implementing CRDT<Map<string, V>, LWWMapState<V>> with set(key, value, ts?), get(key), has(key), delete(key, ts?), keys(), value(), state(), merge(remote), toJSON(), fromJSON(json), clone(), reset(). Tombstones SHALL be preserved on deletes so causal ordering of subsequent re-adds resolves correctly. Tie-break on equal timestamps SHALL compare nodeId lexicographically (consistent with LWWRegister).
  • ADDED: LWWMapEntry<V> and LWWMapTombstone types — { value, timestamp } and { timestamp } respectively.
  • ADDED: LWWMapState<V> type — { type: "lww-map"; entries: Record<string, LWWMapEntry<V>>; tombstones: Record<string, LWWMapTombstone> }.
  • ADDED: GSetState<T> type — { type: "g-set"; elements: T[] }.
  • MODIFIED: LWWMap.set and LWWMap.delete accept an optional Clock from @suaveplan/types via the LWWMap constructor (default Date.now()). Identical to how LWWRegister resolves an absent timestamp argument.
  • ADDED: CRDT_CODES.GSET_INVALID_ELEMENT and CRDT_CODES.LWWMAP_INVALID_KEY error codes for non-JSON-serializable input.
  • ADDED: per-module sibling .md for the two new files (g-set.md, lww-map.md).
  • ADDED: subpath exports ./crdts/g-set/g-set and ./crdts/lww-map/lww-map in package.json for tree-shaking.

Out of scope

  • PN-Counter — already in genesis under crdts/pn-counter. Not affected.
  • Causal CRDTs (Causal Length Set, Causal Tree, Add-Wins / Remove-Wins observed maps) — separate change once the static CRDT catalogue stabilises. They need a different state-envelope design (causal context vectors) than the timestamp-based LWW family.
  • Delta-state CRDT optimization — shipping delta() / applyDelta() methods to reduce sync payloads is its own change; this proposal stays full-state.
  • Persistence adapters — wiring GSet / LWWMap to @suaveplan/db-sqlite for durable storage is a separate change in the @suaveplan/crdt-persistence package (not yet created).
  • Migration tooling — converting an existing TwoPSet to a GSet (when a consumer realises remove was never used) is left to consumers; no automated converter ships in this change.

Source mapping

This change derives from the upstream package at ../suaveplan/packages/universal/crdt/src and the upstream enterprise audit at ../suaveplan/enterprise/crdt.md.

Requirement Source file Source lines Notes
GSet<T> class with add / has / merge / value / clone packages/universal/crdt/src/sets/g-set/g-set.ts L1-L143 Verbatim port; adapt to genesis CRDT<TValue, TState> interface (genesis uses value() not state().elements); adopt genesis CRDT registration error code style
GSetState<T> and GSetOptions<T> types packages/universal/crdt/src/sets/g-set/g-set.types.ts L1-L23 Verbatim port; merge type: "g-set" discriminator into state envelope to match genesis CRDT_TYPES discriminated union pattern
LWWMap<V> class with set / get / has / delete / merge / value / clone / reset packages/universal/crdt/src/maps/lww-map/lww-map.ts L1-L208 Verbatim port; replace Date.now() fallback with injectable Clock; tie-break compares nodeId lexicographically (same as upstream)
LWWMapEntry<V> and LWWMapTombstone types packages/universal/crdt/src/maps/lww-map/lww-map.types.ts L1-L20 Verbatim
LWWMapState<V> type packages/universal/crdt/src/maps/lww-map/lww-map.types.ts L22-L30 Verbatim port; merge type: "lww-map" discriminator into envelope to match genesis pattern
Tombstone-respecting merge semantics packages/universal/crdt/src/maps/lww-map/lww-map.ts L150-L185 Verbatim — mergeEntry skips remote entries older than a local tombstone; mergeTombstone removes a local entry when remote tombstone is newer
Tie-break on equal timestamp via nodeId packages/universal/crdt/src/maps/lww-map/lww-map.ts L48-L54 Genesis already implements this in LWWRegister; port the same comparison into LWWMap.set for cross-CRDT consistency

Requirements with no source line

Requirement Justification
Injectable Clock for timestamp generation in LWWMap.set / LWWMap.delete Genesis-wide CLAUDE.md determinism rule — no module-scope Date.now(). Upstream uses Date.now() directly; genesis takes a Clock parameter on the constructor (matches the pattern already established in @suaveplan/timing, @suaveplan/migration, @suaveplan/etl).
CRDT_CODES.GSET_INVALID_ELEMENT and CRDT_CODES.LWWMAP_INVALID_KEY codes Genesis-wide policy that every thrown error route through @suaveplan/error (CLAUDE.md §Workflow rule 2). Upstream uses native throws; genesis adds typed codes for non-JSON-serializable input (e.g. BigInt keys in LWWMap, circular-reference values in GSet).
type: "g-set" and type: "lww-map" state-envelope discriminators Genesis CRDT.fromJSON / CRDT.toJSON rely on a discriminator field for cross-CRDT serialisation. Upstream's CRDTEnvelope carries the type out-of-band; genesis inlines it for simpler serialisation.
Subpath exports ./crdts/g-set/g-set and ./crdts/lww-map/lww-map Genesis-wide subpath-export rule (CLAUDE.md §6). Upstream ships a single barrel; genesis enforces tree-shakable per-feature subpaths.

Verification approach

Each spec delta requirement carries a **Verified by:** line. The test files that will exist after this change ships:

  • packages/flow/crdt/src/crdts/g-set/g-set.test.ts — add, has, value, state, clone, toJSON round-trip; CRDT properties (idempotent / commutative / associative merge) verified via property-based fixtures
  • packages/flow/crdt/src/crdts/g-set/g-set.spec-conformance.test.ts — CRDT base interface conformance; type-level assertion that GSet<T> is CRDT<Set<T>, GSetState<T>>; non-JSON-serializable element throws CrdtError(GSET_INVALID_ELEMENT)
  • packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts — set, get, has, delete, keys, value, state, clone, toJSON round-trip; tombstone-respecting merge; tie-break by nodeId; concurrent set + delete resolution; reset() clears state
  • packages/flow/crdt/src/crdts/lww-map/lww-map.spec-conformance.test.ts — CRDT base interface conformance; injectable Clock deterministic; tombstone preserved across merge cycles; non-string key throws CrdtError(LWWMAP_INVALID_KEY); CRDT properties (idempotent / commutative / associative merge) verified via property-based fixtures
  • packages/flow/crdt/src/errors/crdt-error.test.ts (extended) — GSET_INVALID_ELEMENT and LWWMAP_INVALID_KEY codes registered

Impact

Affected dependents

Run bunx turbo ls --filter=...@suaveplan/crdt to enumerate. Today grep -rl "@suaveplan/crdt" packages/ --include="package.json" returns only packages/flow/crdt/package.json itself, so this change is purely additive — no in-repo consumers exist yet.

  • @suaveplan/crdt (self) — [x] tests run / [x] docs reviewed / [ ] no action needed
  • (no in-repo dependents) — verified by bunx turbo ls --filter=...@suaveplan/crdt returning a single package.

If tests run is unchecked for any dependent, the change MUST NOT be folded into the canonical spec — finish that work first or split the proposal.

Migration impact

  • All existing genesis CRDT consumers — no break. GSet and LWWMap are net-new exports; the seven existing CRDTs are not touched.
  • Future consumers picking between set CRDTs — pick GSet for grow-only state; pick TwoPSet when remove is needed and re-adds are forbidden after remove; pick ORSet when remove + concurrent re-add must both work (observed-remove semantics).
  • LWWRegister consumers replicating per-key state — the migration target after this change ships is LWWMap. Replacing Map<string, LWWRegister<V>> with a single LWWMap<V> is mechanical — call sites change from register.set(value) to map.set(key, value). Because no in-repo dependent currently does this, no consumer code needs to be touched in this change.
Reference in New Issue View Git Blame Copy Permalink