Bitcask: a tiny log-structured key-value store
How an append-only data file plus an in-memory key directory gives one-seek reads and fast writes, how deletes and merges work, and the limits of the design.
On the roadmap:Advanced · step 3: Storage engines
Lesson 1 of 6 · 11 min read · quiz · exercise
The idea in one paragraph
Keep all data in append-only files. Never modify old bytes. Keep, in memory, a hash table called the keydir that says where the latest value of each key lives. A write appends to the file and updates the keydir. A read looks up the keydir and does one disk read at the recorded position.
Figure SDA-SQR-01-1 · Bitcask write and read paths · © forcsguy.com
The record format
Each record in a data file looks like: CRC, timestamp, key size, value size, key, value. The CRC lets the engine detect torn or corrupt writes after a crash. When the active file reaches a size limit it is closed (becomes immutable) and a new active file starts.
Deletes and updates
- An update simply appends a newer record; the keydir points to it. The older record becomes garbage.
- A delete appends a special tombstone record and removes the key from the keydir.
Merging (compaction)
Over time the files fill with stale records. A merge process reads the immutable files, keeps only the latest live record per key, writes them into new files and deletes the old ones. It can run in the background without blocking reads and writes.
Figure SDA-SQR-01-2 · Merge reclaims space · © forcsguy.com
Recovery
On start, the keydir is gone and must be rebuilt. Reading every record of every file works but is slow for large stores. Hint files hold just the keys and positions for each data file, so recovery reads much less data. Torn writes at the end of the last file are detected by the CRC and truncated.
Strengths and limits
| Strength | Limit |
|---|---|
| Very fast writes: sequential appends | Every live key must fit in RAM |
| Reads need one seek | No range scans: the keydir is a hash table, not ordered |
| Simple crash recovery from an append-only log | Merge needs spare disk space and I/O |
| Easy backups: files are immutable | Single writer per store |
When keys do not fit in memory or you need ordered scans, an LSM-tree (memtable, sorted files, compaction) is the usual answer, as in RocksDB. When you need transactions and ad hoc queries, use a database.
Real-world reading
Check your understanding
Question 1 of 3
0 correct so far
Why are Bitcask writes fast?
Go deeper
- Bitcask: a log-structured hash table for fast key/value data by Sheehy and Smith: the original design note
- Designing Data-Intensive Applications, chapter 3 by Martin Kleppmann: hash indexes, SSTables and LSM-trees compared
Topics covered in this lesson
Practise it: A write-heavy key-value node
Everything below is already set up for this lesson: change the design, run the traffic, and see whether you meet the goal.
- 1The task
- 2Build and test
Half the traffic is writes. One storage node's append-only log is fast, but a single node has limits.
Goal: Under 1% errors, database below 90% busy.
Spread keys across several nodes.
Build it yourself
- Bitcask in miniature labAn append-only data file plus an in-memory key directory: one-seek reads, tombstone deletes, merge and recovery on restart.About 40 min
- Write-ahead log labRecord every change in an append-only file before applying it, so a crash can be replayed, and a half-written last record is detected and ignored.About 40 min
Try it yourself
You store 200 million keys of average 40 bytes with 24 bytes of keydir overhead each. Estimate keydir memory, and say what you would do about start-up time after a crash.
Click what a strong design here would need:
More in Building blocks
© 2026 forcsguy.com. Original lesson text and diagrams. Books and sites linked above belong to their authors.