Build a 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.

SavedSaved on this device

The problem

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.

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 cover

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)

Reading

Sheehy & Smith — Bitcask: A Log-Structured Hash Table for Fast Key/Value Data (Riak, 2010)
basho/bitcask — Erlang reference implementation
Kleppmann — Designing Data-Intensive Applications, Chapter 3 (storage engines)
rosedblabs/rosedb and prologic/bitcask — production Go ports

About Build a 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.

Difficulty: beginner
Time: about 60 minutes
Stages: 9
Topic: Storage Engines & Databases

How this problem is worked

Nine stages, from what the thing is for to how it compares with the real implementations. Each asks one question, and the simulator runs the architecture you draw against the requirements you wrote.

01Purpose & invariantsWhat is this for, and what must always be true of it?
02Workload characterizationWho writes, who reads, and in what shapes?
03Data model & on-disk formatWhat does the data look like at rest?
04Core algorithmsHow do the write path and the read path actually work?
05Distribution & replicationHow does this scale out and survive losing a machine?
06Consistency & correctnessUnder concurrency and failure, what is guaranteed?
07Failure modes & recoveryWhat actually happens when each part fails?
08Operational characteristicsCan a human run this at three in the morning?
09Trade-offs & comparisonWhere does this sit against the alternatives?

Primary sources for this problem

Sheehy & Smith — Bitcask: A Log-Structured Hash Table for Fast Key/Value Data (Riak, 2010)
basho/bitcask — Erlang reference implementation
Kleppmann — Designing Data-Intensive Applications, Chapter 3 (storage engines)
rosedblabs/rosedb and prologic/bitcask — production Go ports

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.

Browse the full problem catalog, or see what the simulator does and does not model.