Why does a log-structured store delete data by writing a tombstone instead of removing it, and when is the deleted data physically removed?
answer
- files cannot be edited
- a delete is a write
- the marker hides older data
- gone only after a merge
basics
~20 sIts sorted files are immutable, so a delete is written as a marker, a tombstone, that hides older data for that key. The data and the marker disappear only when compaction merges the files holding them and it is safe to forget the delete.
solid answer
~50 sA log-structured store never edits its sorted files, so it cannot erase a value in place. A delete is instead **written like any other mutation**: a **tombstone** carrying a timestamp, which travels through the log, the memory buffer and into a new file. At read time the tombstone **hides** every older entry for the same key or range, so the data looks gone immediately. Physically, both the old data and the tombstone stay on disk until **compaction** merges the files that hold them: when the tombstone meets the data it shadows, the data is dropped. The tombstone itself can be dropped only when nothing older could still reappear — once every file with older data for the key has been merged in and, in stores whose replicas reconcile with each other, after a grace period long enough for every replica to have seen the delete.
go deeper
Know that a delete writes a tombstone that hides older data, and that space is reclaimed only later by compaction.
Explain how a tombstone hides entries by timestamp and the conditions for dropping the data and the tombstone.
Predict the space and read-latency effects of heavy deletes and design key layouts that delete by range or by file.
Be ready to set data-deletion policies, such as retention and erasure deadlines, that account for how late space and data are really reclaimed.
## Why a delete cannot be an erase In a log-structured store: - data files are **immutable** sorted files, never edited after they are written; - a key's older versions may sit in several files; - replicas may hold their own copies. Erasing a value in place is impossible — there is no place to erase it from that would cover every copy. So a delete is recorded as **new information**. ## The tombstone A **tombstone** (delete marker) is a small entry saying *"everything for this key, up to this timestamp, is deleted"*. It can cover: - a single cell (one column of one row), - a whole row, - a range of rows or a whole partition, in stores that support range deletes. It is written through the normal path: commit log, memory buffer, flush into a new sorted file. ## Reading with tombstones When a read merges entries for a key, a tombstone **hides every entry with an equal or older timestamp**. Data written later, with a newer timestamp, is visible again. So from the application's point of view the delete takes effect immediately. ## When space is actually reclaimed Two things must happen before bytes are freed: 1. **The data is dropped** when compaction merges a file containing the tombstone with a file containing the older data it shadows. The merged output omits the shadowed data. 2. **The tombstone is dropped** when it is safe to forget that the delete happened: - no file outside the compaction still holds older data for that key (otherwise the data would reappear), and - in stores whose replicas reconcile by comparing data, a **grace period** has passed so every replica has received the delete. Stores where each key range is served by one server can drop delete markers at a **major compaction**, one that rewrites all of a range's files into a single file, because after it no older data can remain anywhere for that range. ## Consequences for design | effect | why | |---|---| | deletes use space at first | a tombstone is a new write, and the data is still there | | disk space returns late | it waits for the right files to be merged | | heavy deletes slow reads | reads must skip tombstones until they are purged | | bulk expiry is cheaper by file | dropping whole expired files avoids per-row tombstones | ## Interview angle Say why deletes are writes, how a tombstone hides older data by timestamp, and the two conditions for reclaiming space: merge with the data, then safely forget the marker.
- Why does deleting a lot of data at first increase disk usage?Every delete writes a tombstone, and the deleted data stays in older files until compaction merges them. Until then the store holds both the data and the markers.
- What does a range tombstone save compared with deleting rows one by one?One marker covers a whole range of rows instead of one marker per row, so fewer entries are written and reads skip one marker rather than thousands. Not every store or every key layout supports range deletes.
It is like correcting a bound ledger by adding a line that says "strike entry 42" instead of tearing out the page; the page is only removed when the ledger is recopied.
saying these in an interview costs you the question
- Believing a delete immediately frees disk space
- Saying deleted data is removed from the data file in place
- Thinking a tombstone can be dropped as soon as it is written
- Assuming data written after a delete with an older timestamp becomes visible