Build your own Bitcask-style KV store
The simplest possible KV store that still works: an append-only log on disk + an in-memory hash index. Build it from first principles and feel which trade-offs every later store inherits.
- Scenes
- 9 interactive scenes
- Time
- about 63 minutes
- Topic
- Storage Engines & Databases
What you are building, and why
You are designing the simplest thing that could possibly work as a key-value store: clients send put(k, v) and get(k); the server appends each write to a log on disk and remembers where every live record is via a hash table in memory. That's it. There is no B-tree, no LSM, no skiplist, no MVCC, no compaction strategy beyond "rewrite the live records and atomically swap pointers."
Bitcask was Riak's local storage engine and is the canonical worked example of "what does the disk actually need to do?" Every later KV store — LevelDB, RocksDB, TiKV, FoundationDB, Pebble — is "Bitcask plus an answer to one of its limits." Once you have built Bitcask, the design space of every other embedded KV store collapses to a small set of named trades.
Resist the urge to "describe Bitcask." Make decisions yourself, defend them, and let the design push back. The point is to feel why each price is paid and which workload pays it.
What you will be able to explain afterwards
- append-only log + in-memory hash (keydir)
- single-writer write path
- constant-time read path
- RAM-per-key cost model
- merge / compaction with atomic keydir swap
- crash recovery + hint files
- fsync trilemma (validity vs recency)
- tombstone resurrection (riak_kv #925)
Anatomy
Log on disk, hash in RAM — and the four-step write.
- 01Log on disk, hash in RAMA Bitcask is exactly two structures: an append-only log of records on disk + a single in-memory hash (the keydir). Every other property follows from this split.~7 min
- 02Append, fsync, update, ackEvery put is four ordered steps on one open writer. Concurrent writers are rejected at open(), not at write time.~7 min
- 03One hash lookup, one preadget is a constant-time keydir lookup + at most one pread; bounded by one disk seek, zero when the page cache is hot.~7 min
Limits
RAM is paid per key; merge gives back what's dead.
- 04RAM is paid per key, not per byteEvery live key consumes a fixed-size keydir entry (~44.5 B + key length). RAM scales with key count alone — fat values are free, tiny tags OOM.~7 min
- 05Merge — GC without stopping writesMerge scans only immutable files, writes a deduplicated copy, then atomically retargets keydir pointers. The active file is never touched.~7 min
Crash & sync
Recovery, hint files, fsync — pick two.
- 06Crash recovery — scan or hintOn startup the keydir is gone (RAM is gone). Hint files (a merge byproduct) drop cold-start time ~10x; per-record CRCs make a torn tail self-truncating.~7 min
- 06afsync — pick two of safe, fast, simplesync_strategy is a three-way trade (o_sync / interval / none). fsync controls RECENCY; CRC controls VALIDITY — two separate guarantees.~7 min
Sharp edges
Tombstone resurrection and the design ceiling.
- 07Tombstones — deletes that come backIf merge GCs a tombstone before every older segment containing the key has been merged away, restart resurrects the deleted key. The riak_kv #925 fix.~7 min
- 08Design your KV — and feel its limitsCapstone: every choice is a trade against the hash-in-RAM aesthetic. The absence of range/prefix iteration is the ceiling that bridges to LSM.~7 min
Where you'll use this
Product designs whose trade-offs turn on what this curriculum teaches.
More in Storage Engines & Databases
Open the box every design diagram labels "DB": pages, logs, LSM trees, wide-column, documents, graphs and columnar scans, built from scratch.
- Build Build an LSM-tree storage engine (LevelDB / RocksDB style)The simplest possible storage engine that gives you BOTH ordered reads AND more keys than fit in RAM, by accepting a deal: write to RAM at memory speed, log to disk for safety, then merge sorted files in the background forever.
- Build Build a B-tree storage engine (SQLite-style)What actually happens when you run INSERT INTO users(...). One file of fixed-size pages, organized as B-trees, with a write-ahead log that turns commits into appends. Build it from a SQL writer's perspective and feel why every knob exists.
- Build Build a wide-column store (Cassandra / DynamoDB family)One server is not enough — disk fills, throughput maxes, the box dies. Build a multi-node store from first principles: hash sharding, the consistent-hash ring, vnodes, replication, eventual consistency, tunable W+R quorum, hinted handoff, read repair. Every modern Dynamo-style store is a point in this design space.
- Build Build a graph database (Neo4j / Dgraph-style)When the workload is 'friends of friends', a relational join melts. Build a store where edges are first-class — index-free adjacency, traversals that follow pointers instead of joining tables, and a query language (Cypher / GraphQL+) that thinks in patterns. Feel why graph storage shines for traversal-heavy work and stumbles on full-graph aggregates.
- Build Build a columnar OLAP store (ClickHouse / Druid style)OLTP picks one row by key; OLAP scans a billion rows of one column and asks for a percentile. Build the analytical engine that makes that fast: columnar layout, dictionary/RLE/delta compression, vectorized execution, late materialization, MPP shuffle. Internalize why Postgres is 1000× slower than ClickHouse on the same query and why the inverse is also true.
Prefer to design it yourself?
The same subject as a staged workspace: draw the architecture, and a simulator traces requests through the boxes you drew.
Open the Build a Bitcask-style KV store workspace