Deletes, versions and reclaiming space

Why are deletes the hardest write, and what decides when old versions can be reclaimed?

Delete vectors and tombstones

A delete is the pathological update: a negation with no positive half to carry it. There is nothing to append. You must either rewrite the unit or record a negative assertion in a place that every future reader is sure to look.

Tombstones

A tombstone puts the negation in the data stream. In an LSM tree, it is a marked key sorted alongside the real keys, and it takes part in merges like any other record. It has one nasty property:

You cannot discard it until you are certain that no older run (file) anywhere still contains that key, and being certain requires a compaction that reaches the bottom level. This is why Cassandra has gc_grace_seconds (the time a tombstone is kept). It also causes a well-known operational failure: a partition accumulates 100,000 tombstones, and a query scanning it touches 100,000 records to return zero rows.

Think about that: a delete is the only operation whose cost grows with data you no longer have. Every monitoring system measures rows that are present. None measures rows that are absent. So the failure is invisible until it is not. This is the silent signature that characterizes failures here (the variance rule).

From these three supports, we state the principle:

Delete vectors

A delete vector puts the negation in a compact side structure that belongs to one immutable unit: a bitmap (one bit per row; 1 means "dead") read once alongside the file.

The recent direction of travel in table formats is exactly this arithmetic being acted on. Iceberg is moving positional deletes from delete files (rows that must be merged like data) to binary deletion vectors (a bitmap that is applied as a filter).

Why not start here?

A delete vector is a list of addresses, and an address means something only if positions are stable. This is the identity versus ordering principle from Layout models: you get stable identity or useful ordering, not both. Delete vectors are unlocked by immutability plus positional stability, a property you bought earlier, in the layout and file-format choices, possibly without knowing you were buying it.

Summary. You either rewrite the unit or carry the negation until every copy of the fact is gone. Bitmaps are available only to those who already bought stable positions.

Positional versus equality deletes

This is the cleanest fork in the part, and a structural repeat.

A positional delete says: file F, row 1234 is dead. Applying it at read time is O(1): you are already reading F, so you check the bitmap. Producing it needs the position, so the writer must first find the row: a read before the write. Cheap to apply, expensive to produce.
An equality delete says: any row where id = 42 is dead. Producing it is O(1): record the condition, no lookup. Applying it means every row of every file written before the delete must be tested against the condition, over an unbounded set of files. Cheap to produce, expensive to apply.

It is the same deferral decision as CoW versus MoR, applied one level up: to the identity of the target instead of to the data itself. You decide once whether to do the work now or later for the bytes, and then you decide again, independently, for the question of which bytes. The choice "pay now or pay later" repeats at two levels. This is the conserved-cost rule working at two levels of one system at once, and it predicts that wherever you find one deferral, you should look for a second one hiding above it.

There is another axis, durability of the assertion:

A positional delete is an address. Anything that moves rows (compaction, reclustering, a Z-order rewrite) invalidates it, so it must be rewritten in the same transaction that moves the data.
An equality delete refers to content. It survives any reorganization.

Positional is fast and tied to the physical layout. Equality is slow and independent of the layout. If you expect to recluster often, the fast option is quietly more expensive than it looks.

Summary. Positional deletes pay at write time and break when data moves. Equality deletes pay at read time and survive anything.

Out-of-place update and garbage collection

Any strategy that does not overwrite must grow two organs: an indirection layer, so readers can find the current version, and a collector, so the dead can be reclaimed. This convergence appears in SSD translation layers, in LSM trees and in table-format manifests, because it is a root cause below every layer. Its collector has one cost law everywhere: it moves u/(1−u) live bytes for every byte it frees, a price that explodes near full utilization. For a table, that makes the fill target a write-amplification decision, not housekeeping.

Multi-versioning and version chains

Once you stop overwriting, you have versions whether you wanted them or not. MVCC (multi-version concurrency control) is the decision to expose them: stamp each version, and let each reader pick the version that is consistent with its snapshot. It buys the most valuable property in concurrent storage: readers never block writers, and writers never block readers. It is nearly a free by-product of out-of-place update. That is why systems that adopt out-of-place update for write-amplification reasons end up with snapshot isolation they did not set out to build.

What exposing versions costs (chain traversal on hot rows, index amplification and PostgreSQL's HOT optimization, newest-first versus undo designs, and the isolation level that decides which version a reader sees) is concurrency control's subject. One consequence belongs here, because it decides when space comes back.

The oldest reader pins everything

You cannot reclaim a version that any active reader might still need. Therefore the oldest active reader pins the entire reclamation frontier. A single long-running transaction stops vacuum for the whole database. The damage is not proportional to what that transaction touches. It is proportional to what the whole system writes while it runs. Cause and effect are separated, and there is no local signal at the point of failure. This is the slowest-reader problem of every collector, and paying it is a maintenance decision. What the layout decides is that every out-of-place design creates it.

Compaction policy

When and how an LSM tree merges its runs is where the read/write/space triangle becomes a calculation. Leveled compaction keeps one run per level (write amplification about T·L, read amplification about L, space near 1). Tiered compaction collects T runs per level before merging (write amplification about L, read amplification about T·L, space up to T). The arithmetic is derived with the LSM tree. The two policies trade a factor of the size ratio T between write and read amplification, so which one is right is a statement about your read:write mix, not about your engine.

At file level the same policy question appears as the small-file problem. The target file size is the batch-size rule divided out against the object-store request cost, the identical calculation you did for the row-group size, now applied to the output of compaction rather than the output of ingestion.