Replication W12: Hierarchical aggregation / re-origin relay mode (large fan-in trees) #444

Workstream W12 of #430 · a distinct replication mode for large fan-in trees — NOT the mesh/transitive model of W4

Summary / motivation

A tree-based cluster with thousands of edge/leaf nodes that broadcast updates up through mid-branch aggregators to a central server. Driven by an active strategic edge-aggregation opportunity (customer redacted). We are not assuming sharding here — this is a fan-in aggregation topology, and uniform per-origin replication (W4) would force the central server (and every mid-branch node) to maintain a transaction log + resume cursor per leaf — O(leaves), thousands of logs — which doesn't scale.

The fix is re-origination: a mid-branch node aggregates its subtree's writes and presents them to its parent under a bounded delivery identity, so the central server tracks O(branches), never O(leaves). Leaf identity lives in the data, not in central's log structure.

The reframe (shared with W4)

Separate two identities that are conflated today (the audit position is the record version):

• Delivery identity — the origin id + cursor used to route/resume. Collapsible at aggregation boundaries.
• Conflict identity — the (originNode, version) used by precedesExistingVersion for LWW + dedup. Must be preserved in-band.

Re-origination re-stamps the delivery identity to the relay while carrying the original conflict identity inside the record. Unifying rule: re-origination collapses the cursor/log dimension only; it never discards the original (leafId, version) (see HA below for why that's mandatory, not optional).

Design — spectrum, simplest first

1. Simple re-origination (disjoint keyspaces — confirmed for this use case). Each edge owns its own keys, so there are no cross-branch write conflicts. A mid-branch node re-stamps its subtree's writes as its own delivery origin and carries the original (leafId, version) in-band (conflict/dedup identity + provenance). Central maintains O(branches) logs/cursors; per-node log/cursor count = O(fan-out degree), recursively bounded up the tree. No cross-branch LWW machinery needed.

2. Conflict-preserving transport (only if coalescing/reordering needs transport-order ≠ version). The relay assigns its own monotonic transport sequence while the record keeps its original version for conflict resolution. Crux to verify: today the resume position is the record version (getRange seeks by version; replication passes startByLog as version floors). Confirm whether rocksdb-js's TransactionLog can key on an append/transport sequence independent of the record version. Simple re-origination (#1) sidesteps this; build #2 only if needed.

Coalescing (the bigger volume win)

For thousands of edges broadcasting, volume matters more than log count. A mid-branch coalesces repeated updates to a key (latest-wins) or CRDT-aggregates them (__op__:'add' exists in core) before forwarding, so central ingests an aggregated stream, not the raw firehose. Per-table completeness-vs-volume choice: lossless "every event" delivery and coalescing are mutually exclusive.

HA / redundant parents (in scope — the hard part)

Two redundant parents M and M′ both aggregate the same subtree. A single logical leaf write then reaches center via two delivery paths, re-stamped as "from M" and "from M′" — which look like two distinct writes unless center can recognize them as the same. The foundation:

• Dedup on the preserved original identity. Because both carry the original (leafId, version) (+ audit-ref lineage), center collapses them via the existing keyed dedup (precedesExistingVersion == 0 / additionalAuditRefs). This is exactly why simple re-origination must still carry original identity — HA, not conflicts, is what makes it mandatory in the disjoint-key case.
• Active-active (both relay; center dedups): no failover gap, ~2× ingest (the expected HA cost). Active-standby (M′ takes over on M's failure): center re-subscribes to M′ from a conservative floor and dedups the overlap by original identity. Both models rest on original-identity dedup.
• Idempotent coalescing only. Latest-wins is safe under double-delivery. CRDT-add is safe only if increments are dedup-keyed by original event id (else redundant parents double-count) — so re-origination must preserve the audit-ref lineage that core's CRDT dedup keys on.
• Open HA questions: preserving audit-ref lineage through re-origination; deterministic re-origin versioning so M and M′ don't diverge; whether M/M′ need any coordination or stay fully independent; central-server HA as a further layer.

Relationship to W4

Orthogonal modes, sharing the delivery-vs-conflict identity split:

• W4 (Replication W4: Per-origin transaction-log convergence (keystone) #434) — mesh/transitive: per-origin cursors multiplexed over per-peer sockets; preserves end-to-end origin identity.
• W12 — tree/fan-in: collapses origin identity at aggregation boundaries.

A node can use both (mesh among peers, re-origin toward a parent). W4 is scoped to not cover trees; W12 is scoped to not alter mesh behavior.

Scope

• Design spike first — the transport-vs-version decoupling (crux above) + the HA dedup/lineage model; pin requirements against the target deployment (lossless vs aggregated; HA model)
• Re-origin relay role: re-stamp delivery origin, carry original (leafId, version) + audit-ref lineage in-band
• Bounded per-node log/cursor count = O(fan-out degree)
• Coalescing (latest-wins; optional idempotent CRDT-aggregate) with per-table completeness-vs-volume config
• HA: active-active dedup at center by original identity; failover/standby resume + overlap dedup
• Provenance: original leaf id queryable as a record attribute
• Cluster tests: N-leaf / B-branch tree → center maintains O(B); redundant-parent dedup; mid-branch failover loses no committed leaf data

Dependencies

Builds on the delivery-vs-conflict identity split (shared with W4) and core's existing keyed dedup / CRDT machinery. Independent of the mesh path otherwise. Design-spike-gated — do not commit the build before the spike resolves the transport-vs-version and HA-lineage questions.

Effort / risk

XL / high. A new replication mode; HA/redundant-parents is the hard part. Spike first, then phase (simple re-origination → coalescing → HA).

Acceptance criteria

• A tree of N leaves under B branches: the central server maintains O(B) logs/cursors, not O(N).
• Redundant parents deliver a leaf write to center without duplication (deduped by original identity).
• Coalescing measurably reduces central ingest for a high-frequency edge workload.
• Failover of a mid-branch parent loses no committed leaf data.

🤖 Filed by Claude on behalf of Kris.