Interview question. You are building a local key-value engine with put(key, value), get(key), and delete(key). Every write appends a record to one file. Six months later, writes are still cheap, but point reads have become painfully slow and the disk is filling up. Keep point reads fast, reclaim old values, and explain recovery after a crash.
Assume one machine owns this store, values fit comfortably in a record, and the primary access pattern is an individual key lookup. We will not add network replication or SQL queries to solve a local indexing problem.
Think first
Build a single-node key-value engine with an append-only disk format for 20 million live keys. Each key can be updated and deleted. Point lookups must remain fast after six months, and the process may die while old segments are being merged. Describe the read path, merge cutover, and restart recovery.
Take a few minutes to form an approach, then compare it with the worked explanation.
Check the exercise numbers
For the exercise’s 20 million live keys, using the worked example’s illustrative 64 bytes per directory entry gives 20,000,000 × 64 = 1.28 billion bytes, about 1.28 GB before allocator overhead. The exercise does not specify entry size; measure it rather than treating 64 bytes as an engine guarantee.
Reveal the worked explanation
The first design is almost too easy
For put("room:41", "available"), append the key and value to the end of a file. For an update, append another record. There is no need to find the old value first. The next write lands near the end of the file, where the storage engine is already writing.
The difficulty arrives with get("room:41"). If the file contains a billion records, reading every record until we find the latest value is not a realistic point-read strategy. Stopping at the first match is wrong because there might be a newer one farther down the log.
The store needs to remember where the latest record for each key lives. That observation gives us a surprisingly useful design.
Keep an in-memory hash table mapping the key to a file ID, byte offset, and record length. In Bitcask terminology, this is the key directory, or keydir. Each append updates this map after the record is accepted under the store's local write protocol. A point read first consults memory, then reads the value at the recorded offset. The historical versions remain on disk, but we do not scan them for every read. The original Bitcask project is a concrete example of this family of design. 1
Append-only segments and an in-memory key directory pointing at the latest value
Follow one key through three updates
Imagine these records, with byte positions simplified for teaching:
segment-07 at 0010 room:41 = available
segment-07 at 0080 room:56 = held
segment-07 at 0140 room:41 = held
segment-08 at 0030 room:41 = booked
The key directory entry for room:41 points only to segment-08, 0030. The earlier values are still bytes on disk, but they are no longer the live value for this key.
Deleting the key cannot mean merely removing it from the in-memory map. After a restart we would scan the old files and accidentally reconstruct room:41 from its last value. Instead, append a deletion marker, commonly called a tombstone, and update the directory to treat the key as deleted. Recovery then knows that the deletion is newer than the older values.
A single endless file still grows forever. Split it into segments. One segment is actively appended to, and older segments are sealed and immutable. Periodically merge sealed segments, copying only the records that are still current and retaining the deletion information needed to prevent old values from returning.
There is an important safety rule here. Do not delete an old segment just because a new merged file was created. First make the new files complete, verify them, publish a durable generation or manifest that selects them, and only then reclaim old files after readers no longer need them. Otherwise a crash during cleanup could leave the index pointing into deleted storage. The manifest protocol is a proposed design choice for our engine, not a feature promised by every Bitcask implementation.
Restart is an indexing problem too
The in-memory map is gone after a process restart. The values are not necessarily gone, but the engine must rebuild its directory.
The simplest recovery scans the retained segments in their defined order and uses each valid record to update the key directory. That works if we can identify which committed generation of segments is authoritative and which final record, if any, was only partially appended.
Put a length and checksum in each record, with a versioned record format. Recovery should validate boundaries and contents, then stop or isolate a torn tail according to an explicit rule. A checksum detects some corruption. It does not make a record durable, and it is not proof that an older, fully formed record was meant to be accepted by the client.
A hint file or saved directory checkpoint can make startup much faster, but it is an acceleration structure. It must be possible to validate it against the underlying data and recover when that hint is missing or stale. If the engine has 80 million live keys and each in-memory entry averages an illustrative 64 bytes, the key directory alone is about 5.12 GB before allocator overhead. That is a real limit of this design, not a detail a hash table makes disappear.
When would you stop using this layout?
A memory-resident directory is attractive when point reads dominate and the live key set is manageable. It becomes less attractive when keys outgrow memory, ordered range scans matter, or the cost of rebuilding the directory exceeds the recovery objective. An unsorted append log plus a hash map does not provide ordered iteration for free. Adding sorting and a disk-based index changes the engine's shape.
I would test steady writes, lookups for existing and missing keys, deletion followed by restart, a crash at each merge step, and recovery time with a large live key set. For the interview, the valuable answer is not just “append everything.” It is the combination of an append log, an exact latest-location index, an explicit deletion record, and a safe way to replace segments.
We have built a store that can locate its newest value quickly. Now the client calls put, receives success, and the machine loses power before the operating system has finished writing its buffers.
Did that successful write ever become durable?
Go deeper
The segment-generation boundary
For a crash-safe merge, copying live records is only the middle of the protocol. Suppose the engine selects old segments A and B and writes replacement C. While C is being built, a new update can arrive in active segment D. The merge must compare versions or use a stable snapshot of its input generation so it does not replace a newer value in D with an older value copied from A.
An illustrative safe sequence is to seal the source generation, build C, flush and synchronize C, publish an atomic manifest update identifying the new generation, and then retire A and B after readers have released them. Directory entries must be updated consistently with the manifest. The exact rename and directory-sync rules depend on the filesystem and recovery model. An atomic rename alone is not proof that newly written file bytes survive power loss.
A record's checksum is about integrity, not ordering. A sequence or segment order decides which valid record is newer. A tombstone must remain visible while any retained older value might otherwise be resurrected. If expiry and deletion are supported, merge rules must account for their timestamps or generations.
This is also an example of a local storage engine rather than a distributed database. Replication can preserve another copy of a file, but it does not replace the need to know which segments and records form one coherent local state. The next lesson isolates the durability and recovery boundary rather than repeating keydir indexing.
Check your reasoning
Identify the newest value with a key-to-segment-offset directory rather than scanning the full append log.
Encode deletes durably as tombstones and explain why deleting an in-memory entry alone fails on restart.
Separate active and sealed segments and make replacement publication crash-safe before reclaiming inputs.
Rebuild or validate the directory after restart and detect incomplete final records.
Account for memory size, lack of efficient ordered range scans, and limits of this particular design.
Common mistake: Assuming the file is already indexed, or dropping tombstones and old segments without a recovery protocol.
Read the answer explanation
Scanning an old segment can restore the deleted key. — The append log still contains older puts. Without a persistent deletion marker or equivalent authoritative deletion state, rebuilding the directory can resurrect the key.
Apply it elsewhere
A feature-flag engine uses this append-only layout but now has 300 million live keys and must serve ordered prefix scans. What is the next limitation?
Compare your approach
The resident directory becomes expensive and a hash directory does not provide sorted iteration. Compare a disk-based ordered index or LSM-style sorted files without treating that as a free migration.
One more constraint
A crash happens after new merge files are written but before old files are deleted. Which generation should recovery trust?
Quick revision
An append-only file makes writes cheap because an update appends a new record instead of modifying an old location. Point lookups would be slow without an index, so I would maintain an in-memory map from key to the latest segment and offset. Reads use that map to access the value directly. Deletes become tombstone records so recovery does not restore old values. Sealed segments can be merged to reclaim overwritten records, but publication of the replacement must be crash-safe before old files are removed. On restart, rebuild or validate the key directory from retained files. The main limitations are directory memory, recovery time, and lack of efficient ordered scans. A fast append does not by itself promise that the write survived a power failure.
