RFC: user-definable commutative merge operations

[ohohoreilly]

Status: design proposal — do NOT implement yet. Gated on a real workload that needs a merge outside the built-in set. The built-in palette (add/mult/min/max/and/or/xor/union/intersection/symdiff, #213) covers the common CRDTs; until a concrete merge is needed, adding it as a built-in via the now-paved #213 groove (~10 sites) is strictly cheaper and lower-risk than this. Forcing function: LWW (last-writer-wins register) is the most likely first real need and is NOT expressible today (>?= only takes int/real, not records). When LWW comes up, that's the decision point to un-gate this.

Motivation

Orly's whole value is coordination-free merges, but the set of coordination-free operations is a closed enum TMutator. #213 showed each new op is a mechanical ~10-site change. The deferred-fold machinery (session.cc emits {mutator, RHS}; ApplyDeferredFold folds them; Augment composes via Rt::Mutate(Rhs, op, other.Rhs)) is completely general — only the vocabulary is hardcoded. This RFC opens the vocabulary so users can declare their own sound monoid (bounded counter, LWW register, top-k, sketches) without an engine change.

Verified spike findings (on record)

1. Storage widening fits in existing bytes — backward compatible

Every persisted entry reserves an 8-byte mutator slot but the mutator uses only 4:

• Writer emits TMutator (4B) then uint32_t mutator_padding = 0 (data_file.cc:490; also merge_data_file.cc:2241/2303/2313).
• Reader reads 4, skips 4 (present_walk_file.h:255-256).
• Sizes pinned by KeyEntrySize/KeyHistorySize (in_file.h:50,54), validated by static_assert (read_file.h:625,684).
• Mutator is not in any sort key/comparator.

=> Repurpose the zeroed padding word as a uint32_t MergeId (0 = builtin enum, non-zero = user merge). No size change, no static_assert break, old files read back as MergeId==0. Note: there is no file-format version field today (only static_asserts), so any AST-encoding change later needs its own versioning.

2. Execution is required on package-less nodes (the load-bearing constraint)

Slaves carry raw deferred entries: manager.cc:695-718 re-adds non-Assign mutators via update->AddEntry(..., entry.Mutator), with a comment citing #54 ("Without this, the slave reconstructs deferred {Add,n} as Assign(n) and silently loses updates"). So a slave that serves a read runs ApplyDeferredFold -> Rt::Mutate — it executes the merge with no package loaded. Therefore a MergeId pointing into package code is unresolvable; the merge must travel as replicable data (a combinator AST) and indy must evaluate it without the orlyscript runtime.

3. The registry home is a near-copy of the index-id machinery

Index-id mechanism (exists)	Merge-registry equivalent
Codegen mints a UUID per (addr,val) (code_gen/package.cc:132)	Compiler mints a MergeId per declared merge
InstallPackage -> SaveIndexNamespaceMapping (server.cc:2051)	InstallMergeRule(id, ast)
Stored in SystemRepo under SystemIDNSIndexId (manager.cc:1277)	New SystemMergeRegistryIndexId
Replicated via TReplicationStreamer, ids pushed first (manager.cc:899) -> definition-precedes-use	same ids-first phase
Startup loads mapping before data; aborts on unknown id (server.cc:982)	load registry first; abort/error on unknown MergeId

So replication, persistence, ordering, bootstrap, and definition-precedes-use all come from mirroring this path.

Proposed design

Closed combinator algebra (option A): a merge is built only from primitives already proven commutative+associative (min/max/+/*/set ops) plus law-preserving combinators (tuple-product, lexicographic-max for LWW, project, constant), lowered to a small serializable AST. This is simultaneously sound-by-construction and package-free interpretable. The fold dispatch point generalizes one line:

result = (MergeId == 0) ? Rt::Mutate(lhs, mutator_enum, rhs)
                        : EvalMerge(Registry[MergeId].Ast, lhs, rhs)   // small fixed TVar->TVar interpreter

EvalMerge runs identically on master and slave (needs only the replicated AST + the two TVars already in scope at every fold site). Absent-key seed reuses #213's IsAbsentKeySeedRhs path, generalized to "the merge declares its identity (or seed-from-RHS)."

Surface (illustrative):

lww is merge<(time_pnt, T)> (a, b) -> max_by_first(a, b) seed_from_first_write;
*<[k]>::(int) merge<lww> v;

Risks / open questions

• Steady-state vs catchup mutator asymmetry. Catchup preserves mutators (manager.cc:695); steady-state apply sends bare key->value with no mutator (manager.cc:1011-1019). Pre-existing Phase 5 of #49: restore wikipedia-pageviews demo + fix two remaining lost-update sites #52/Master->slave replication wire format doesn't carry TMutator #54 territory; user merges inherit whatever correctness the deferred-replication path has. Resolve as a dependency.
• New hot-path code: EvalMerge runs in the fold inner loop on every node — needs the MinMaxDeferredFold-style matrix plus a dedicated slave-fold test.
• AST versioning (no format-version field exists today).
• Soundness trust model: closed-algebra-only (safe, less general) vs property-tested user functions lowered to the algebra. Ship the former first.
• Compiler lowering: turning an orlyscript merge decl into the combinator AST (or proving a function reduces to one).

Phasing (when un-gated)

1. Storage widening (MergeId in the padding word) + round-trip through write/read/fold, no behavior change.
2. Registry + replication (mirror index-namespace mapping).
3. EvalMerge + one shipped merge (lww) end-to-end, master and slave, with the full fold/replication test matrix.

Related: #213 (the built-in path this generalizes). See also the graph-traversal RFC — the killer demo for both is "concurrent agents building one typed knowledge graph, queryable as-of any time."

[ohohoreilly]

Status note (2026-07-06), re-verified against current master — the gate stands, but one item in Risks / open questions has improved since this was written:

• "Steady-state vs catchup mutator asymmetry ... resolve as a dependency" — the dependency issues (Tetris merge should call TMutation::Augment for commutative ops on the same key (field calls do not compose under contention) #49, Disk update walker drops TMutator on read-back #53, Master->slave replication wire format doesn't carry TMutator #54) are all closed. The replication wire format now carries the mutator per entry (orly/indy/util/context_streamer.h, (IndexKey, Op, Mutator) payload), disk read-back preserves it (orly/indy/disk/update_walk_file.h), and the remaining mutator-splitting site (orly/indy/manager.cc, catchup path) re-adds non-Assign mutators via update->AddEntry(..., entry.Mutator). The manager.cc line numbers cited above have drifted; whoever un-gates this should re-verify the steady-state apply path once, but the asymmetry as described appears resolved.

Also for the record: the forcing function has not fired. The LWW-shaped workloads that exist today (grc20-pov, prediction-market) do latest-wins in-engine via the sum-type event log + sorted_by/reduce fold-on-read, so nothing currently needs LWW-as-a-mutator. Gate unchanged.

[ohohoreilly]

Closing as not planned. The design findings above stay on this issue, so it can be reopened as it stands.

Why not now:

• The trigger hasn't happened. The case this was gated on is last-writer-wins on records. Nothing needs it as a merge: the GRC-20 example does latest-wins with the version-in-key, fold-on-read pattern, and no other workload has asked.
• It's a one-way change. Slaves fold commutative entries without the package, so a user-defined merge has to replicate as data. That means a combinator language, an evaluator inside the engine, a replicated registry, and a new meaning for the mutator padding word on disk. Files written with it can't be read without it.
• There's a cheaper path if one merge is needed. Adding a single built-in merge the way Commutative merge ops: add min/max (+ mult absent-key upsert) via an identity refactor #213 added min/max costs a fraction of opening the merge set to users.

Reopen when a workload needs a merge that no built-in can express, or needs several of them.