Interview question. A key-value store gets frequent updates to randomly chosen keys. Instead of updating a disk B-tree leaf for each write, it accepts changes into memory and writes sorted files later. Follow one put, one get, and one delete through this engine. Explain what is made durable, what reaches disk, and what the read path must search.
Use a RocksDB-style log-structured merge tree for this exercise. The database owns one local key-value state. Assume its foreground acknowledgment and WAL synchronization settings have been chosen explicitly. We will use the earlier durability lesson rather than claim that every memory update is already power-loss safe.
Think first
You switch a high-update-rate key-value service from in-place B-tree index updates to a RocksDB-style LSM. Walk one update and a subsequent delete through the memtable and files. A read for a missing key becomes unexpectedly expensive. Explain what the engine may have to inspect and how it avoids unnecessary disk reads.
Take a few minutes to form an approach, then compare it with the worked explanation.
Reveal the worked explanation
A cheap foreground write can create expensive future work
In a B-tree, inserting a key may require finding and changing a particular leaf page. An LSM-style engine shifts the organization cost. New updates enter an in-memory structure called a memtable, while a write-ahead log carries the recovery information required by the configured durability contract. RocksDB documents the memtable and WAL as separate destinations for an update. 1
When the memtable reaches its limit, it becomes immutable. A background task writes its sorted contents into an immutable sorted-string table, or SST file. New writes continue into another memtable if buffer capacity permits. The first flushed files belong to level 0, commonly called L0. 2
An LSM write becoming a memtable, level-zero SST files, and compacted lower-level files
There is an important performance distinction here. The foreground write does not need to find and rewrite every old copy of the key immediately. It records the newest version quickly, and the old versions are reconciled later. But the eventual merge work is real. Delaying it is not eliminating it.
Follow three versions of one key
Suppose the application writes these changes over time:
put user:73 = bronze
put user:73 = silver
put user:73 = gold
The newest value may be in the active memtable. An older version may remain in an immutable memtable or in an L0 SST file. An even older one might be in a lower level. A correct read needs to find the newest visible version, not simply the first copy that happens to be found on disk.
The search begins with the in-memory structures, then examines on-disk candidates in an order that respects sequence numbers, versions, or the engine's snapshot semantics. The engine can use index blocks and Bloom filters to avoid unnecessary SST data reads. A Bloom filter can rule out many files for a missing key, though a positive result is not proof that the key exists.
This is one cost of deferring organization. With an LSM, there may be several places to look. In RocksDB leveled compaction, L0 files can overlap in their key ranges, while files at levels beyond L0 are arranged into nonoverlapping key ranges within each level. That difference directly influences how many candidate files a point lookup must consider. 3
Delete is another versioned operation
Now delete user:73. In a log-structured engine, an immediate physical search through every SST file would erase much of the advantage of appending changes. Instead, the deletion normally enters the memtable as a tombstone and is later flushed like another record.
A read must recognize the tombstone as newer than any old value it might find. Compaction can eventually remove obsolete values and, when safe under the engine's snapshot and retention rules, the tombstone itself. Dropping the tombstone too early could reveal an older value. This is the same underlying danger as resurrecting deleted data from an append-only log, but here the distinct question is how versions move through a sorted multi-level read path.
Snapshots complicate cleanup because an older version may remain visible to a reader holding an earlier sequence boundary. “The value has been overwritten” does not automatically mean no active reader needs it.
Why sort files at all?
An unsorted log with an in-memory directory can give efficient point reads, as we saw in the first lesson. But if the application needs prefix iteration or a key range, sorting is useful. Time-ordered scans benefit only when the key schema and comparator preserve the required time order—for example, a tenant prefix followed by an order-preserving timestamp for scans within that tenant. Sorting arbitrary IDs does not put their records in event-time order. Immutable sorted files allow binary searching within index structures and sequential access to neighboring keys. They also enable merging multiple sorted runs into a new sorted run without random in-place updates.
That introduces an important trade. A file that is immutable is easy to read consistently, but updating a key creates a newer record elsewhere. Until the engine reorganizes the files, both copies may consume space and reads may have to consider both.
The memtable, L0 files, and levels below L0 therefore form one logical database, not three independent stores. Its metadata must say which SST files are part of the live version. In RocksDB, a manifest tracks file-set changes as compaction adds and removes files. 2
Where does the cost appear?
For a proposed engine, I would measure foreground write latency and durable acknowledgment separately from memtable flush latency, file count by level, bytes written by compaction, read amplification, cache hit rates, and actual scan latency. A benchmark that finishes before compaction matters tells only part of the story.
The interview explanation should finish with a clear comparison. A B-tree maintains a search-friendly page structure as writes arrive. An LSM records updates quickly and defers more organization into flushes and compactions. Both can have excellent performance. Their costs appear in different places, so access pattern and steady-state load matter more than slogans such as “LSM is always faster for writes.”
For a while, our new engine looks excellent. Then the background file work starts falling behind. The incoming request rate has not changed, yet writes become slow and eventually stop.
If the foreground path is still just a memtable update, what could be blocking it?
Go deeper
A few implementation details worth knowing
A RocksDB memtable is typically a sorted in-memory structure. Flushes write new SSTs in L0. For leveled compaction, the engine merges overlapping sorted data from one level into another. The lower levels are generally much larger, so a key can be rewritten multiple times while moving downward. This creates write amplification in return for fewer overlapping files during reads.
WAL and memtable lifetimes are related but different. A WAL segment cannot necessarily be deleted just because one memtable flushed if it contains updates for another column family. RocksDB's documented WAL lifecycle accounts for that shared log ownership. 1
Point lookups for absent keys deserve an explicit benchmark. With many candidate files, index and Bloom filter checks can still cost CPU and cache capacity. Range scans do not get the same advantage from a Bloom filter that rules out point-key membership. In the default leveled layout, a range scan may need to merge sorted iterators across multiple active sources.
Compaction also has snapshot-awareness requirements. A version that is obsolete for the newest read may still be needed by a long-running snapshot. An engine cannot simply keep the maximum timestamp and discard all other versions without consulting its visibility model.
The next lesson focuses on the background service-rate limit and how RocksDB-style write stalls deliberately protect the store when this deferred maintenance cannot keep up.
Check your reasoning
Trace the foreground write to the memtable and separately describe WAL durability as a configured contract.
Explain immutable memtable flush to an L0 SST and later merging into lower levels.
Walk the read path from newer memory through overlapping L0 and indexed lower-level candidate files.
Explain tombstones and snapshot-aware retention of older versions.
Connect Bloom filters, read amplification, range scans, and the deferred future cost of writes.
Common mistake: Saying a memtable is durable merely because it can be read, or that immutable files mean no duplicate key versions exist.
Read the answer explanation
A Bloom filter can rule out many files without reading their data blocks. — Bloom filters can cheaply reject many candidate files for point-key membership, but false positives remain and range scans have different behavior.
Apply it elsewhere
A time-series store needs to read the latest hour in time order and delete entire weeks of old data. Which aspects of sorting and partitioning become useful?
Compare your approach
Sorted runs support ordered iteration. Time-bucketed files or partitions may permit coarse-grained expiry, though out-of-order and late data change cleanup and query planning.
One more constraint
A long-running snapshot holds versions that compaction wants to remove. What should happen?
Quick revision
An LSM stores new updates in a memtable and records recovery information in a WAL according to the configured durability contract. When a memtable fills, it is frozen and flushed as a sorted immutable SST file in L0. Reads first check newer in-memory state, then relevant on-disk files, using indexes and Bloom filters to reduce work. Deletes are versioned tombstones rather than immediate removal from every file. Compaction later merges sorted runs, drops safe obsolete versions, and reorganizes files. Compared with a B-tree, the LSM moves more organization off the foreground update path. The trade is more background I/O and potentially more sources to inspect during reads. Its steady-state throughput depends on whether that background work can keep up.
