Deletes, Tombstones, and the Append-Only Sink

A database deletes a row by marking its tuple dead and reclaiming the space later. An object store cannot do that. A file written to an object store is immutable, and deletion is a separate operation on a whole object, so removing one row from a million-row file means rewriting the file or recording the removal somewhere else.

Most analytical sinks are built on object storage, so the second option is what they do: deletion becomes a record. The record says that a key is gone, and every reader applies it when it reads the file the row is in. That is a tombstone, and it converts a storage operation into a read-time merge whose cost and correctness depend on how the tombstones are stored and how long they are kept.

What a delete looks like in a stream

A log-based capture delivers a delete as a record containing the row’s identity and, depending on the source’s configuration, the row’s previous values. The distinction matters downstream.

A delete with full before-image can be applied to a sink that needs to know what was removed, such as an audit trail or a downstream system that must emit a corresponding delete with the same fields. A delete with key-only image is smaller and is all that a keyed sink needs.

The source’s configuration decides which one arrives. A capture stream configured to emit only keys for deletes produces smaller records and cannot reconstruct the removed row; one configured to emit full row images produces larger records and can. The choice is per-table and is one of the few capture settings whose effect is purely downstream, which makes it easy to set once and regret later.

Why the tombstone must outlive the row

Consider a sink that stores rows in files partitioned by date and holds tombstones in a separate small table. A reader that scans a partition must join it against the tombstones to exclude deleted keys. If a tombstone is removed after some retention period, any file still containing the deleted row’s older version becomes visible again.

This is the resurrection problem, and it is the reason tombstone retention is tied to the lifetime of the data files rather than to the tombstone’s own age. A tombstone can be dropped only when every file that could contain the row’s pre-deletion version has been rewritten or removed.

In a table format with snapshot isolation, the constraint is stated in terms of snapshots: a tombstone may be removed when no live snapshot references a data file containing the deleted key. Since snapshots are retained for a configured period to support time travel and reader isolation, the tombstone’s minimum lifetime is that period plus the interval between compaction runs.

The arithmetic is worth making concrete. A table with daily partitions, a 30-day snapshot retention, and compaction that rewrites partitions older than seven days produces tombstones that must be retained for at least the snapshot retention plus the compaction lag, and in practice longer, because a compaction that fails and is retried extends the window. A tombstone retention shorter than the file lifetime produces silent resurrection, and the symptom is a row count that grows without any insertion.

Merge on read versus copy on write

Two strategies exist for making a deleted row invisible, and they differ in when the work happens.

Copy on write. A delete rewrites the affected data file, omitting the deleted rows, and the table’s metadata points at the new file. Readers see a clean file with no merge step. The cost is paid at write time and is proportional to the file’s size, not the number of deleted rows: deleting one row from a 512 MiB file rewrites 512 MiB.

Merge on read. A delete writes a small file containing the deleted keys, and readers merge the data files against the delete files, excluding matches. The write is cheap and proportional to the number of deletes. The cost moves to every read, which must scan the delete files and perform the exclusion, and to a background compaction that eventually rewrites the data files to remove the deleted rows.

The trade is the familiar one between write amplification and read amplification, and the correct choice depends on the ratio of reads to deletes and on the size of the files. A table that receives many small deletes and is read rarely favours merge on read; a table read constantly and deleted from rarely favours copy on write, because the read path stays simple.

Both strategies need the same guarantee: a reader must see a consistent combination of data files and delete files. In a table format, that is provided by the snapshot’s manifest, which lists exactly which files participate. A reader that discovers files by listing the directory instead of reading the manifest can see a delete file without its corresponding data file, or the reverse, and the result depends on the timing of the listing.

Keys that get reused after deletion

A tombstone names a key. Whether that is sufficient depends on whether keys are reused, which is the same question exactly-once raised for deduplication.

If a key is deleted and a new entity is later inserted with the same key, a tombstone that persists past the new insert will hide the new row. The sink applies the tombstone to every file containing the key, including the file written after the insertion, and the row vanishes.

The mechanisms that prevent this are a monotonic version per key and a tombstone that carries the version it deletes. The tombstone then excludes only versions at or below its own, and a later insert with a higher version survives. This requires the source to provide a monotonic version, which is the property that cursor columns could not obtain from application timestamps and that log-based capture provides for free.

Without a version, the alternative is to forbid key reuse at the source, which is a constraint on the application and is rarely enforced. The practical consequence is that tombstone retention becomes a bound on how quickly a key can be reused: a key deleted and reinserted within the retention window is hidden, and one reinserted after it is not. That is a rule no source schema documents, and it is worth stating explicitly wherever it applies.

Hard deletes and the right to erasure

A deletion request that must remove data, rather than merely hide it, is a different requirement from a logical delete. A tombstone hides; the row’s values remain in the data files until compaction rewrites them, and they remain in the snapshots retained for time travel, and they remain in the object store’s versioned buckets if versioning is enabled.

Removing data physically requires rewriting every file containing the key, expiring every snapshot that references those files, and, where the object store keeps versions, deleting the object versions as well. The last step is the one most often missed: a bucket with versioning enabled retains a deleted object’s previous versions, so a compaction that deletes a file and writes a replacement leaves the original bytes readable by version identifier.

The bound on how long this takes is the compaction schedule plus the snapshot retention plus the object store’s own version retention. Each is configured separately, and the sum is the interval during which a deleted value is still recoverable, which is the number that matters for a compliance statement.

Compaction as the mechanism that makes tombstones finite

Without compaction, tombstones accumulate and every read pays an increasing merge cost. Compaction rewrites data files to exclude deleted rows and then drops the tombstones that are no longer needed, which is what bounds both the read cost and the storage.

The scheduling question is which files to compact. Rewriting a file that contains no deleted rows is wasted work; rewriting a file that contains many is the point. A table format that tracks per-file statistics, among them the minimum and maximum key, the row count, and the count of tombstones matching the file’s key range, can select the files with the highest ratio of deleted to live rows. Without those statistics, compaction is a scan of everything, which for a large table is unaffordable at any useful frequency.

The interaction with ingestion is direct: a compaction that rewrites a file while a write is appending to the table must not lose the append. Table formats handle this by making the commit a metadata operation: the writer adds a new file and a new snapshot, the compactor adds a replacement file and a new snapshot, and the two snapshots are merged by the catalog’s compare-and-swap on the table’s current metadata pointer. A compactor that rewrites files based on a stale metadata read and then commits unconditionally will drop the concurrent append. This is the same lost-update pattern as the backfill racing the live stream, moved from the row level to the file level.

What a reader must do, precisely

The read path for a table with tombstones has a defined sequence, and every reader that skips a step produces a different wrong answer.

Read the table’s current metadata to obtain the snapshot. From the snapshot, obtain the manifest list, and from it the data files and delete files. For each data file, determine which delete files apply: by key range, by partition, or by an explicit association recorded in the manifest. Merge: for each row in the data file, look up its key in the applicable delete files, and exclude it if a tombstone matches with a version at or above the row’s.

The step that is easy to omit is the version comparison. A reader that excludes on key match alone hides a reinserted row, and the bug appears only for keys that were reused, which is a small fraction of keys and therefore a small fraction of tests.

The step that is easy to get wrong is the association. A delete file that is applied to every data file is correct but expensive; one applied only to files whose key range overlaps is correct and cheaper; one applied to files by partition is correct only if the partition boundaries are stable, which they are not when a row’s partition column changes. A row that moves from one partition to another by an update is a delete in the old partition and an insert in the new, and a tombstone scoped to the old partition does not hide the row’s presence in the new one, nor should it, since the insert is the current state.

The invariant

The append-only sink’s contract is that a row is visible if and only if its latest version is an insert and no tombstone at or above that version exists. Every mechanism described here, from the retention bound and the merge strategy to the version on the tombstone and the compaction schedule, exists to make that predicate computable at a bounded cost.

The predicate is also what makes reconciliation meaningful: comparing a sink with tombstones against a source requires the comparison to apply the same predicate, and a check that counts rows in data files without excluding tombstoned ones reports a difference that is not a defect. The reconciliation must read through the same merge, which is why it is cheapest to run against a compacted table rather than a freshly written one.