ADR 0061 — OCTOPUS CRDT: OR-Set + LWW-Map (Wave-4 D2 formalization)¶

Status	Date	Author	Supersedes	Superseded by
Accepted	2026-05-16	André Luiz Gallon	partial: LWW-based JetStream KV state	—

Context¶

ADR 0060 D2 (Wave-4 hyperscale) mandates CRDTs (Conflict-free Replicated Data Types) substituirem o LWW (Last-Write-Wins) atual em coordinator collection state. Esta ADR formaliza o subset de CRDTs adotados, contratos de merge, vector clock encoding, e migration path.

Why CRDTs¶

Wave-3 coordinator state vive em NATS JetStream KV com LWW semântica: dois nodes escrevendo para a mesma key cross-region perdem o update mais antigo. Em 50k+ clientes com N regions ativas-active, isso quebra invariantes:

Cell health set: dois nodes adicionam novo cell ao mesmo set cross-region → um set add é perdido
Allowlist IPs: novo IP adicionado em sa-east-1 + outro IP adicionado em us-east-1 → um perdido
Primary election votes: dois nodes votam ao mesmo tempo → vote perdido (cell falha eleger primary determinístico)

CRDTs garantem convergência sem coordinator central: dois replicas que aplicam o mesmo conjunto de ops eventualmente convergem ao mesmo estado, mesmo sem comunicação direta.

Architectural decision¶

8 LOCKED decisions.

D1: OR-Set para colecções (peer membership, allowlists)¶

Observed-Remove Set (Shapiro et al. 2011, RFC 9069 informational reference). Cada element está associado a um conjunto de unique tags (UUIDs) que rastreiam adições observadas. Remove só vale se tag foi observada — caso contrário ignorado (re-add wins).

Wire layout (per element):

type ORSetElement struct {
    Value   string      // arbitrary identifier
    AddTags []uuid.UUID // each add operation gets unique tag
    RemTags []uuid.UUID // tags observed at remove time
}

Merge: union of AddTags, union of RemTags. Element present in final set iff AddTags \ RemTags ≠ ∅.

Tradeoff: storage grows O(operations) not O(elements). Garbage collection via causal stability (D3) — tombstones older than ALL replicas' watermarks are safe to prune.

D2: LWW-Map com vector clocks para keyed scalars¶

Para state que é naturalmente single-value-per-key (cell health score, last heartbeat, current primary), LWW continua válido SE comparações forem feitas em vector clocks, não em wall-clock timestamps:

type VectorClock map[string]uint64  // node_id → version

func (v VectorClock) Compare(other VectorClock) Ordering {
    // returns: <, >, =, or Concurrent
}

Concurrent updates resolvidos por deterministic tie-break: lexicographic min(node_id) wins. Garante convergência sem oracle.

Tradeoff: clocks crescem O(N) com N = número de nodes que já escreveram a key. Pruning quando node não escreve há > 24h.

D3: Causal stability via cluster watermark¶

Garbage collection de OR-Set tombstones + Vector clock pruning depende de causal stability: uma operação é causalmente estável quando todos os replicas a observaram. Implementação:

Cada replica mantém vector watermark publicado periodicamente (5s) no JetStream KV subject octopus.crdt.watermark.{node_id}
Operações cujo vector clock ≤ min(watermarks) podem ser pruned
Watermark vivenciado por TODOS os replicas → operação é causalmente estável

Pruning preserves convergence: o pruning happens em todos os replicas após o ponto onde nenhum replica observará novas ops causally before.

D4: Convergence proof requirements (test discipline)¶

Implementations MUST include property-based tests (testing/quick or gopter) provando:

∀ ops_seq1, ops_seq2:
    ∀ ordering(ops_seq1), ordering(ops_seq2):
        apply(ops_seq1) ∪ apply(ops_seq2) ==
        apply(ops_seq2) ∪ apply(ops_seq1)

i.e., merge é commutative + associative + idempotent (CALM theorem preconditions).

Plus standard invariants:

Adding an element makes it present
Removing an observed element makes it absent
Removing an unobserved element is a no-op (add-wins concurrent semantics)
Vector clock merge is monotonic

D5: Wire encoding — Protobuf for storage, JSON for debugging¶

In JetStream KV bucket values:

Protobuf for production binary efficiency (storage cost matters at 50k+ clients × dozens of state buckets)
JSON wrapper with type tag for debugging tools (crdtctl dump)

Both encodings symmetric — Protobuf is canonical, JSON is derivative.

Schema versioning via field tag — older replicas tolerate unknown fields, NEVER drop them during merge (causality preservation).

D6: Adapter package `pkg/octopus/crdt/`¶

Public API:

// pkg/octopus/crdt/orset/
type ORSet[T comparable] interface {
    Add(value T, replica string) (tag uuid.UUID)
    Remove(value T)  // operates on observed tags only
    Has(value T) bool
    Members() []T
    Merge(other ORSet[T]) ORSet[T]  // commutative
    MarshalProto() []byte
    UnmarshalProto([]byte) error
    GCBefore(watermark VectorClock) int  // returns prunable tag count
}

// pkg/octopus/crdt/lwwmap/
type LWWMap[K comparable, V any] interface {
    Get(key K) (V, ok bool)
    Set(key K, value V, replica string)
    Delete(key K, replica string)  // tombstone with vector clock
    Merge(other LWWMap[K, V]) LWWMap[K, V]
    Keys() []K
    MarshalProto() []byte
    UnmarshalProto([]byte) error
    GCBefore(watermark VectorClock) int
}

// pkg/octopus/crdt/vclock/
type VectorClock interface {
    Increment(replica string)
    Set(replica string, version uint64)
    Compare(other VectorClock) Ordering  // <, >, =, Concurrent
    Merge(other VectorClock) VectorClock  // entrywise max
    Bytes() []byte
}

Stdlib only. No external dependencies beyond github.com/google/uuid (already in project go.mod).

D7: Migration path from current LWW state¶

Existing LWW JetStream KV buckets MUST migrate via dual-write window:

Stage 1 (week 1): deploy CRDT adapter; writes go to BOTH old LWW bucket and new CRDT bucket. Reads still go to old LWW bucket.
Stage 2 (week 2): shadow-read from new CRDT bucket; diff vs LWW; alert on divergence (expected zero for single-region writes).
Stage 3 (week 3): cutover reads to new CRDT bucket per-cell with feature flag OCTOPUS_CRDT_ENABLED=true. Validate metrics.
Stage 4 (week 4): stop writes to old LWW bucket. Decommission.

Feature flag default OFF; no behavior change until explicit opt-in.

D8: Backwards compatibility with Wave-3 LWW state¶

Wave-4 nodes communicating with Wave-3 nodes use a CRDT envelope wrapper that includes both:

CRDT-formatted body (for Wave-4 peer)
Legacy LWW timestamp metadata (for Wave-3 peer fallback)

Wave-3 peers ignore unknown fields, write only LWW timestamp; Wave-4 peers read CRDT body if present, fallback to LWW timestamp otherwise. Backwards-compat envelope removed once 100% of cells upgraded to Wave-4 (PR-W4-16 final cleanup).

Storage cost estimates¶

For 100k clients × ~50 state collections × ~100 elements/collection:

Naive LWW: ~50 MB JetStream KV
OR-Set with tombstones (no GC): ~500 MB (10× overhead from tags)
OR-Set with causal stability GC: ~80 MB (1.6× overhead — acceptable)
LWW-Map with vector clocks: ~100 MB (2× overhead from clocks)

Total Wave-4 CRDT storage: ~180 MB hot. Negligible vs ClickHouse analytics tier.

Performance characteristics¶

Operation	LWW (now)	OR-Set (Wave-4)	Notes
Add	1 op	1 op + UUID gen	UUID v7 ~50ns
Remove	1 op	scan local tags + write	scan O(tags-per-element)
Merge	last-write wins	union of tags	O(n+m) memory, O(m) work
GC	n/a	scan vs watermark	periodic, off-hot-path
Read membership	O(1)	O(1) hash check	identical

OR-Set add/remove latency comparable to LWW (sub-ms). Merge is the new operation — happens during gossip sync (D7 of ADR 0060), not on hot path.

Cross-references¶

ADR 0060 — Wave-4 umbrella D2
ADR 0053 — Wave-1 cell architecture
PR Reviewer Wave-4
Shapiro et al. 2011 — "A Comprehensive Study of Convergent and Commutative Replicated Data Types"
RFC 9069 (informational) — Conflict-Free Replicated Data Type names
CALM theorem (Hellerstein 2010) — "Consistency Analysis in Logical Models"
Future PRs: PR-W4-4 (scaffold), PR-W4-5 (OR-Set impl), PR-W4-6 (LWW-Map impl + migration)