What mutation strategies forbid

What do mutation strategies forbid, what are the escapes, and what does each escape cost?

What this article forbids. No strategy achieves O(d) writes, O(1) reads and O(data) space at once without a collector. Unlike the RUM conjecture, here you can see the mechanism: the negation must be evaluated by someone, and the only three parties available are the writer, the reader and a background process. Each is a different cost column. A second prohibition is sharper and less discussed: you cannot reclaim without establishing that no one is reading, and that is either a coordination protocol or a conservative time horizon. There is no local, cheap way to know that a byte is dead.

The escapes and their prices

Strategy	What it buys	What it costs
In-place	Optimal read and space	Double writes; loses free concurrency
Copy-on-write	Pointer-sized atomicity, free snapshots	`U/d` × depth
Merge-on-read	Optimal writes	Unbounded read amplification until a compaction schedule you must derive
Delete vectors	3-6 orders of magnitude cheaper than CoW deletes	Available only if you already gave up cheap reclustering
MVCC	Non-blocking concurrency	Chain traversal on hot rows; reclamation held hostage by the slowest reader

Case, resolvedConstructed case · Kavya at Parcelo

640 GB rewritten to change 1 MB

Kavya's lake needs about 5,000 address corrections a day plus customer deletions; rewriting whole files cost 640 GB a night, and delta files made the reports slower every week. Where it started: Mutation strategies →

The nightly rewrite. Kavya computes U/d for corrections: 128,000,000 ÷ 200 = 640,000×. Copy-on-write is disqualified (step 2 of the decision procedure). In practice, 5,000 corrections spread over about 3,125 files touch about 2,500 distinct files, so the night job really rewrites about 320 GB, still absurd for changing 1 MB.

Delete vectors. For customer deletions she writes positional delete vectors: one bitmap of 640,000 bits (80 KB) per file instead of a 128 MB rewrite. She can use positions because the files are immutable and the writer looks the rows up first (a read before the write). For address corrections she writes the new version of the row as a small delta file (merge-on-read).

The slowing reports. Her reports got slower because deltas accumulated without a schedule: MoR is a loan against every future read. She measures her own numbers (100 deltas per hour per file, one read per second, 2 ms extra per delta, 40 s to rewrite a file) and computes the square-root interval, τ* = √(40 ÷ 360) hours = 20 minutes, for the hot files. She also notes the catch: the positional deletes break when files are rewritten, so the compaction job must rewrite the delete vector in the same transaction as the data. If the team later reclusters the files often (Physical clustering), she will revisit this choice, because equality deletes survive any reorganization.

Finally, Kavya sets the lake's target fill and file size on purpose, instead of discovering write amplification at 95% full.