put

Put value under key, minting a fresh add-tag on behalf of replica — and return the change: one key, the value you supplied, and a short causal note, rather than the whole new map.

A put is additive, not destructive, for the value lattice: reading key back afterwards gives the old value pieced with value. What the put replaces is replica's own previous tag on the key — its earlier contribution is folded into the fresh tag, so a replica never accumulates more than one tag per key. Tags minted by other replicas are left alone; retiring those is remove's job, and taking them here would silently discard a peer's contribution that nobody asked to drop.

This is what to put on the wire. A replicator broadcasts a patch's delta verbatim, so a mutator that handed back the new map would ship every key and every key's value on every write, at a cost that grows with the map; this frame's size does not depend on how large the map is. The idiom is quilter.mutate { it.put(replica, key, value) } — read-modify-write inside the replicator's own lock. To hold the resulting map locally, absorb the patch: map.piece(map.put(…)).

A delta is itself an ORMap, so a peer absorbs it with the ordinary piece join, in any order, with any repeats, and lands on a state that encodes byte-for-byte identically to the author's own. Nothing has to be buffered or delivered in causal order.

The delta carries value, plus whatever this replica has already contributed to the key — never the whole stored value. The frame is flat in the size of the map and flat in the size of other replicas' contributions, which is where the saving lives; on a nested ORMap<K, ORSet<X>> a peer adding one element ships one element, not the roster. What it cannot leave out is its own history, because the tag this put mints supersedes the sender's older tags and therefore has to carry what they were holding. A replica that keeps growing one key on its own pays for that: its deltas grow with its own contribution to that key. The alternative — never superseding — would keep every delta minimal and let a key accumulate one tag per put forever, which is a worse trade for a state that is held, hashed and re-shipped.

The delta's context names the minted tag and the sender's own tags that it supersedes, and that second term must not be simplified away. A delta announcing only the new tag would leave the superseded ones alive on every receiver — and a later remove, retiring only the tags the remover knew about, would resurrect the key. That failure was measured while designing this method (#2044) and is pinned by ORMapDeltaMutatorLawTest.

A concurrent remove is no longer a special case. The key survives — that is add-wins — and so does exactly this delta's contribution, in either order and on every peer, because the remove can only retire tags it observed and this one is not among them (#2086).

Samples

val a = ReplicaId("A")
val b = ReplicaId("B")

// Two peers have converged: "team" already holds a long roster, put there by B.
var alpha = ORMap.empty<String, GSet<String>>()
    .piece { it.put(b, "team", GSet.of("alice", "bob", "carol", "dan")) }
var bravo = alpha

// A adds one member and puts only the change on the wire. The delta carries A's one name —
// not the merged roster — because the receiver re-does that merge against its own copy.
val hire = alpha.put(a, "team", GSet.of("erin"))
check(hire.delta["team"] == GSet.of("erin"))

// A's tag joins B's rather than replacing it, so the key's value is both writes together.
alpha = alpha.piece(hire)
bravo = bravo.piece(hire)
check(alpha == bravo)
check(alpha["team"] == GSet.of("alice", "bob", "carol", "dan", "erin"))

// A concurrent put beats a concurrent remove: B's put mints a tag A's remove never saw.
val concurrent = alpha.put(b, "team", GSet.of("frank"))
check("team" in alpha.piece(alpha.remove("team")).piece(concurrent).keys)

// A remove lands everywhere, because both peers agree on which tags are live. Had A already
// held a tag on "team" and the delta kept quiet about it, that older tag would still be alive
// on bravo — and "team" would come back from the dead there.
val disband = alpha.remove("team")
alpha = alpha.piece(disband)
bravo = bravo.piece(disband)
check("team" !in alpha.keys)
check("team" !in bravo.keys)