Reads, deletes and Bloom filters

Writes are cheap in an LSM tree because they only append. The cost moves to reads, which may have to look in several places for one key. Bloom filters, block indexes and the block cache keep that cost small. Deletes add a twist, because a delete also has to be a write.

The read path

A point lookup checks every place the newest version could be, from newest to oldest:

1. The active memtable, then any memtables waiting to flush.
2. Every L0 file, newest first. L0 files are raw memtable flushes, so their key ranges overlap.
3. From L1 down, at most one file per level. Each level is one sorted run, so a binary search over file key ranges finds the only candidate.

Without help, a 5-level tree with 4 L0 files could cost 9 or more disk reads. Two mechanisms keep it near one:

• Bloom filters answer "definitely not in this file" without reading data. At 10 bits per key, the false positive rate is about 1%. A lookup for a key in the last level checks 8 filters, wasting about 8 × 0.01 = 0.08 reads, then makes the one real read.
• Block index and block cache. Index and filter blocks are usually in memory, and hot data blocks sit in the block cache.

A range scan is the weak spot. A Bloom filter cannot answer "all keys from user:100 to user:200". The engine opens an iterator on every level and merge-sorts them. RocksDB's prefix Bloom filters help when scans share a fixed key prefix.

Deletes are writes

An LSM tree cannot remove a value in place, because the old value may sit in any older file. A delete writes a tombstone that shadows older versions on read. The tombstone can be dropped only when compaction has merged it with every older file that might hold the key. Until then:

• Deleted data and tombstones both take space.
• Reads have to skip tombstones. A queue-like pattern of insert, read, delete and repeat leaves long runs of tombstones that every scan wades through. Cassandra warns when one query scans 1,000 tombstones and aborts it at 100,000 by default. "Queues on Cassandra" is a known anti-pattern for this reason.
• Range deletes, such as RocksDB's DeleteRange, write one range tombstone instead of millions of point tombstones.

Walking through it: zombie rows in Cassandra

Replication makes deletes harder. Suppose a key lives on replicas A, B and C. C is down when you delete the key. A and B store the tombstone, and C keeps the old value.

Cassandra keeps tombstones for gc_grace_seconds, which defaults to 10 days, before compaction may purge them. Repair must reach C within that window, to copy the tombstone to it.

Day 0:   delete key. A and B hold a tombstone. C holds the old value (C is down).
Day 11:  C has still not been repaired. A and B purge their tombstones.
Day 12:  C is back. Its old value is now the only copy. Repair copies it to A and B.
         The deleted row has returned as a zombie.

The rule: run a full repair on every node more often than gc_grace_seconds. Do not bring back a node that has been down longer than that without wiping and rebuilding it. See conflict resolution for the wider picture.

Common mistakes

• Using point deletes for a queue. Tombstones pile up and every scan slows down.
• Assuming a delete frees disk space immediately. Space is freed only when compaction reaches the bottom level.
• Missing repairs. Skipping repair for longer than gc_grace_seconds lets deleted data come back.

Check yourself

• Why does a lookup touch about one disk read, not nine? Bloom filters rule out the other files, so the only real read is in the file that holds the key.
• Why can a deleted row come back in Cassandra? A replica that missed the delete keeps the old value, and the tombstones that would have hidden it were purged before that replica was repaired.

Key takeaways

• Point reads check the memtable and then each level. Bloom filters make that about one disk read.
• Range scans must merge every level, because filters cannot help with ranges.
• A delete is a tombstone. Tombstones cost space and slow scans until compaction removes them.
• Repair replicas more often than gc_grace_seconds, or deleted data can come back.

Further learning

Next, see how compaction decides which files to merge and when, in compaction strategies.

Database Internals (Alex Petrov) explains Bloom filters and LSM read paths in more depth.