Mutation strategies: what happens when a value changes

What physically happens when a value changes, and who pays: in place, copy-on-write or merge-on-read?

An update is two facts, and storage writes one at a time

Layout (Layout models) asked what should sit beside what. That question had one version of the truth in it. This article begins when the truth changes, and the storage must hold two things at once.

The new constraint is time, and it enters through a fact that sounds trivial but is not: an update is not a primitive operation. It combines two assertions: this is now true, and that is no longer true. Storage gives you one atomic write, at one granularity, at one moment. The positive half is easy, because it is an append. The negative half is hard. "No longer true" is not something you can write at one particular place. It is a property of everywhere the old fact might still be found.

So the whole article has one organizing question, and every mechanism is an answer to it:

There are exactly three places to put it:

1. In the data, by destroying the old bytes: in-place update.
2. In a fresh copy of the containing unit, with an atomic swap: copy-on-write.
3. In a side structure that readers must consult: merge-on-read, tombstones, delete vectors, version chains. This is not one mechanism but a family, distinguished only by the form the negation takes and by how expensive it is to evaluate.

Two consequences follow at once.

• Option 1 is the only strategy that destroys information. That is why it is the only one that needs locks and a log to be safe.
• Options 2 and 3 both accumulate old data. So both need a rule for finding the current version and a process for reclaiming the dead: an indirection layer plus a collector. The immutable-substrate rule is the spine of this article.

What stops mattering here: the read-optimality of the base layout. That was Layout models's bet, and it is now fixed. What starts mattering is how many places the truth might be, and that number is a variable you control.

---

The core lattice: five strategies compared

Let d be the number of changed bytes, U the size of the unit that gets rewritten, and k the number of accumulated deltas (small change records) for a record.

The three cost columns are read amplification, update (write) amplification and memory (space) amplification. This is RUM, but now with arithmetic instead of a conjecture. Notice two things:

• Counting the collector, no row is optimal in more than two columns.
• The only row that needs no collector (in-place) is also the only row that permits no concurrency.

That is not a coincidence. It is the same fact stated twice. Concurrency and reclamation are the same problem, because both are about knowing when old bytes stop mattering.

---

Before strategy 1: the write-ahead log

This mechanism is easy to overlook, and in-place update cannot be understood without it.

A database that changes a page in place has a problem: the change is not atomic, and a crash in the middle leaves the page damaged (see strategy 1 below). The solution is the write-ahead log (WAL): before changing the page, append a record that describes the change to a log file, and make that log write durable (physically on disk). The page itself can be written later. After a crash, the system replays the log, and the data is repaired.

The WAL is itself an out-of-place strategy in disguise: the log is append-only, and the pages are brought up to date from it. We will see below that in-place update is a fiction maintained by out-of-place writes one layer down.

---

In-place update

In-place update is viable only when three conditions hold at once:

1. The medium allows overwriting.
2. The new value is no larger than the space where the old one sat.
3. Nobody else is looking at those bytes.

Each failing condition produces a recognizable piece of machinery.

• Values that grow do not fit. This produces slack space (reserved empty room), forwarding pointers, row migration and page splits. The slotted page (Layout models) exists mostly to absorb this.
• Concurrent readers must not see a half-written row. This produces latches (very short locks that protect an in-memory page). Latches serialize access, which is unacceptable under load, which is why in-place systems under concurrency drift towards versioning.
• The overwrite itself is not atomic. The device's atomic unit is a 512-byte or 4 KiB sector. The database page you are writing is larger (for example 8 KiB or 16 KiB). A crash in the middle of the write leaves a torn page: half old, half new, with no complete copy of either.

The last point deserves a moment. It is a pure granularity mismatch (the mismatch rule) between the page and the sector. An entire group of mechanisms exists to hide a gap of one order of magnitude in write granularity: the write-ahead log, double-write buffers (a staging area where the page is first written whole, so that a good copy always exists) and torn-page detection. The price is:

Now the observation that matters most: in-place update is a fiction, maintained by out-of-place writes one layer down.

• The log is append-only.
• Below the log, the SSD's translation layer (FTL) is append-only. It maintains the illusion of overwrite for the file system.
• Below that, the flash erase block cannot be overwritten at all.

The same illusion is built three times, and each layer hides it from the one above (stacked logs multiply). Each layer has its own indirection and its own collector. The immutable-substrate rule does not merely apply here. It stacks.

Summary. In-place update buys optimal read and space by destroying history. It pays by writing everything twice to survive a crash that it could not otherwise survive.

---

Copy-on-write (CoW)

Do not touch the old unit. Write a new one, then swap a pointer.

The trick, named precisely: CoW converts an atomicity problem of any size into an atomicity problem of one pointer. Whatever your unit is (a page, a 128 MB Parquet file, a whole B-tree), the only thing that must be atomic is the single reference update at the end. Everything before it is invisible. Everything after it is committed. This is why CoW appears in file systems (ZFS, btrfs), in embedded stores (LMDB), and in table formats (Iceberg, Delta, Hudi), which share nothing else in their architecture. Convergence under a constraint, again.

The price: U/d

The write cost is U/d, and U is not yours to choose here. It was set in Layout models. The row-group size you picked to amortize the object-store latency is now the multiplier on every update.

• A 16 KiB page with a 100-byte change: about 160×. That is annoying.
• A 128 MB Parquet file with a 200-byte row change: 128,000,000 ÷ 200 = 640,000×. That is not annoying. It is disqualifying.

That single number is why the lakehouse world (data lakes with table-like management) could not stay with copy-on-write and invented delete vectors (strategy 4). Carry this forward: it is the sharpest example here of a read-side decision turning into a write-side catastrophe.

The second price: propagation up the tree

Copy-on-write also propagates. Rewrite a leaf, and its parent now points to a stale address, so the parent must be rewritten, and its parent, up to the root. Write amplification is U/d × depth, not U/d. This is called the wandering tree problem. The mitigation is to batch many leaf changes before rewriting the spine. That is the batch-size rule again from another direction: a fixed cost (rewriting the path to the root) gives a natural batch size.

What CoW gives you for free

Old versions stay intact and reachable. A reader that holds the old root sees a consistent past state at no extra cost. Snapshot isolation and time travel are not features of CoW systems. They are by-products. That is why every CoW system grows a time-travel interface, whether it planned to or not. The cost is deferred to the collector.

Summary. CoW reduces atomicity to a pointer swap, pays U/d times tree depth, and gets snapshots for free because it was already keeping the old copy.

---

Merge-on-read (MoR)

If U/d is the problem, stop rewriting U. Write the delta (the change) as its own small unit, and make the reader reconcile it with the base. Write cost falls to O(d): optimal, it cannot be improved. Read cost now depends on how many units have accumulated.

This property makes MoR both powerful and dangerous: MoR converts a bounded, known-count cost into an unbounded, unknown-count one. One write is one write. But "every future read of this data" is a quantity you do not control and often do not measure. You finance write throughput with a loan against reads, and the interest grows with read volume.

A decision rule you can derive

Let w be the write rate on the affected data, r the read rate, U the unit size, d the delta size and c the merge cost per delta.

• CoW costs roughly w·U per unit of time.
• MoR costs roughly w·d + r·c·k̄, where k̄ is the mean number of accumulated deltas.

Since U ≫ d, MoR wins when

that is, write volume times unit size against read volume times merge work.

• At a read:write ratio of 1,000:1 on a page-sized unit, MoR is a bad trade.
• At a read:write ratio of 1:1,000 on a 128 MB file, it is the only workable trade.

The compaction interval is derived, not guessed

k̄ is not fate. It is set by how often you compact (merge the deltas back into the base). Compact every τ (tau, a time interval). Deltas accumulate at rate w, so the average count is k̄ ≈ w·τ/2, and read cost grows linearly with τ, while the cost of compacting falls as U/τ. Balancing the two gives a square-root interval, τ* ∝ √(U ÷ w): the same shape as the economic order quantity of a warehouse. When to pay that bill back, and how to compute τ* from your own numbers, is a maintenance decision. What the layout decides here is that the bill exists, and that it grows with every read.

Summary. MoR buys optimal writes with a loan against every future read. The compaction interval is the repayment schedule: √(fixed cost ÷ accrual rate), as always.