Under the Hood: The Bitcask Architecture
Originated as the default storage engine for Basho's Riak distributed database, Bitcask is an ultra-fast key-value storage engine designed for workloads where the entire keyspace fits in RAM, but values exceed available memory. It provides predictable O(1) read and write latencies with no seeks on write (appends land in the page cache; durability depends on the configured sync strategy) and at most one disk seek on read.
Bitcask Internal Components
Compaction & The Hint File Optimization
When log segments accumulate stale records, a background merge process reads immutable data files and writes only the latest valid keys to new files. To prevent having to read multi-gigabyte data files on restart to rebuild the in-memory Keydir, Bitcask writes a companion Hint File alongside each merged data file.
Each hint file entry holds the timestamp, key size, value size, value position and key: the value bytes are replaced by the position of the value in the data file. On startup, Bitcask scans the tiny hint files linearly into RAM, rebuilding the million-key Keydir in seconds.
Worked example: capacity planning
Riak's Bitcask guidance budgets a fixed overhead of roughly 40-50 bytes per key in the keydir, plus the key itself. For 200 million keys averaging 36 bytes:
- RAM per replica: 200 million x (36 + about 45) bytes is roughly 16 GB.
- With 3 replicas across a cluster, about 48 GB of keydir RAM in total, spread over nodes.
- If values average 2 KB, disk per replica is about 400 GB for one live version, plus dead versions awaiting merge.
The design wins when values are large relative to keys; with 30-byte keys and 50-byte values the keydir costs as much as the data.
What is actually stored
| Structure | Fields | Purpose |
|---|---|---|
| Data file entry | crc, timestamp, key size, value size, key, value | The durable record |
| Keydir entry (RAM) | file id, value size, value position, timestamp | Find the latest value in one read |
| Hint file entry | timestamp, key size, value size, value position, key | Rebuild the keydir without reading values |
Merge, step by step
- Select immutable (non-active) data files whose fragmentation or dead bytes exceed a threshold.
- For each record, keep it only if the keydir still points at that exact file and offset.
- Write survivors to new merged data files and emit matching hint files.
- Atomically update keydir entries to the new locations, then delete the old files.
Bitcask versus an LSM-tree
| Property | Bitcask | LSM-tree |
|---|---|---|
| Keys in RAM | All | Only indexes and filters |
| Point read | One read, predictable | Memtable, filters, one or more blocks |
| Range scan | No | Yes |
| Write amplification | Low (merge only) | Higher (multi-level compaction) |