The problem: find one value in a 50 GB file#
TL;DRthe 30-second version
- Keep every value in a file on disk, and never change bytes you've already written — just append new ones to the end.
- Keep a small map in memory — the keydir — from each key to where its value sits in the file.
- A read is one map lookup plus one jump to that spot on disk. A write is one append. A delete appends a 'gone' marker called a tombstone.
- The catch: the map holds every key, so all your keys must fit in RAM. The values live on disk and don't count.
Start with the simplest store that could work: one file, and to save a pair you add it to the end. Writing is trivial. Reading is the trouble — to find the value for user:1 you'd read the file from the top, checking keys, until you hit it. On a 50 GB file that's up to 50 GB read to answer one lookup. Unusable.
The obvious fix — keep the file sorted by key so you can binary-search it — quietly brings back the thing we're trying to avoid. Keeping a file sorted means shifting bytes on disk every time you insert in the middle, and that random shuffling is slow. So the real question gets sharper: how do you find where a key's value lives without reading the file, and without keeping it sorted?
The fix: a map in RAM over a file you only append to#
Here's the move. Keep a small map in memory that answers exactly one question: for each key, where in the file is its value? So the map holds key → (which file, which byte offset, how many bytes). Now a read is two cheap steps — look the key up in the map (instant, it's in RAM), then jump straight to that offset on disk and read just those bytes. One lookup, one jump, no scanning, no matter how big the file grows. This map is the keydir.
| keydir key | file | offset | size |
|---|---|---|---|
| user:1 | data.2 | 42 | 5 |
| user:2 | data.1 | 0 | 3 |
| B:user:5 | data.1 | 14 | 9 |
That fixes reads. But values change — someone overwrites user:1 with a new value. You could go back and rewrite the old bytes in place, but that's a random write into the middle of the file, and if the power cuts mid-write you're left with a value that's half old and half new: corrupt. So don't rewrite. Append the new value to the end, exactly like a fresh write, and repoint the keydir at the new spot. The old value is still sitting on disk, but nothing points to it anymore — it's dead weight. This is the append-only rule: never change bytes you've already written.
Deleting has the same snag — you can't cut bytes out of the middle of an append-only file. So you append again: a tiny record called a tombstone that means 'this key is gone.' A read that lands on a tombstone reports not-found, and the key is dropped from the keydir.
Append-only has one obvious cost: every overwrite and every delete leaves dead bytes behind, so the file only grows. Fix it with a background job called merge (or compaction): it reads the old files, copies just the values the keydir still points to into a fresh file, and deletes the originals. Dead records vanish; live data stays. Merge is the only thing that ever frees space.
One loose end. The keydir lives only in RAM, so a crash wipes it. You could rebuild it by scanning every file top to bottom — but that reads all the values back just to relearn their offsets, which is slow. So when merge writes a compacted file, it also writes a small hint file beside it: just the keys and their offsets, no values. On restart you read the hints and rebuild the keydir in a fraction of the time. That's the whole engine — the default storage backend Basho built for Riak.
The one number that decides everything#
Everything hinges on one number. The keydir keeps an entry for every live key, and the whole thing has to fit in RAM. Notice what's not in it: the values. An entry is just the key plus a small fixed pointer — which file, the offset, the size, a timestamp. So the memory you need scales with how many keys you have, not how much data. Ten-byte keys or ten-megabyte values cost the keydir the same.
PredictYou have 10 million keys, and each keydir entry costs about 64 bytes. How much RAM does the index need — and does it fit on a 16 GB machine?
Hint: Multiply keys × bytes-per-entry, then compare to 16 GB.
10,000,000 × 64 bytes ≈ 640 MB. It fits easily. Now try 10 billion keys: ~640 GB — no ordinary machine holds that, even if the values would. The values could be 50 GB or 50 TB and it wouldn't change this number. Key count is the ceiling.
One more limit follows from the design. Range scans (give me every key from B:user:1 to B:user:9) are not supported — the file isn't sorted, so there's no order to scan.
In an interview#
Isn't this just an in-memory database like Redis?
No — and the difference is the whole point. Only the keys and small pointers live in RAM (the keydir); the values sit on disk. A pure in-memory store has to hold every value in RAM too, so it's bounded by total data size. Bitcask is bounded only by key count, so it serves a dataset far larger than memory while still reading in a single seek.
When would I pick an LSM tree over Bitcask?
When the key set won't fit in RAM, or you need ordered/range scans. An LSM keeps data sorted on disk and scales past memory, at the cost of read amplification (several files, Bloom-gated). Bitcask trades those away for a single-seek read and an engine you can operate without thinking. Same log-structured family, opposite bet on ordering.
Big values are fine, so how many keys is too many?
Value size barely matters — values live on disk. Key count is the ceiling: budget the hashed key plus a fixed pointer (tens of bytes) per live key. Tens of millions of keys is a gigabyte-ish of RAM and totally fine; tens of billions is not. Out-of-memory errors with plenty of free disk is the signature of hitting that limit.
When to reach for Bitcask (and when not to)
| Bitcask | LSM tree | B-tree | Pure in-memory | |
|---|---|---|---|---|
| Read cost | 1 lookup + ≤1 seek | memtable + several files (Bloom-gated) | tree descent, ~log(n) pages | 1 lookup, no disk |
| Write cost | 1 sequential append | append + later compaction (write-amp) | in-place random page update | 1 in-memory write |
| Range scans | Not supported (unordered log) | Good — merge sorted SSTables | Excellent — ordered leaves | Depends on structure |
| Memory need | All keys in RAM | Indexes/filters; data on disk | Cache hot pages; data on disk | All keys AND values in RAM |
| Durability | Append log + CRC, easy recovery | WAL + immutable SSTables | In-place, careful crash handling | Needs external snapshot/AOF |
| Best for | Bounded keys, predictable reads | Write-heavy, large datasets | Read-heavy OLTP, range queries | Hot data that fits in RAM |
- Good fit: bounded key sets with large or small values — session/profile stores, device and feature state, counters, caches with durability; workloads that value tight tail-latency SLAs and trivial crash recovery. Riak used it as the default per-node backend for exactly this: predictable latency and a recovery that is just a log scan.
- Weaker fit: very large or unbounded key counts (the keydir won't fit), or anything that leans on range scans, prefix scans, or ordered iteration. Riak offers LevelDB (an LSM) for those workloads.
- Watch out: overwrite- or delete-heavy traffic generates dead records fast, so merge must be scheduled and resourced; and startup time grows with dataset size unless hint files are present.
Where it breaks
- Crash mid-write: the active file may end with a torn, partial record. On the next open, the CRC check fails for that record and it is discarded; all earlier records are intact because they were never mutated. Worst case is losing the last few unsynced writes — Bitcask relies on the OS to flush, so set the sync policy to fsync per write or on a timer if you need a tighter bound, trading throughput for durability.
- Keydir rebuild after crash: the in-memory index is always lost on restart and must be rebuilt — fast from hint files, slow from a full data-file scan. A large store with no hint files can have a long, write-blocking recovery.
- RAM exhaustion: the keydir grows with the live key count. Add too many distinct keys and the process runs out of memory — there is no graceful spill-to-disk. This is the failure that most often forces teams off Bitcask.
- Merge competing with foreground traffic: merge runs in the background against the immutable files while the active file keeps taking writes, but it reads and rewrites a lot of data, so it competes for disk I/O. Run it at peak and latency spikes; defer it forever and dead records bloat disk and slow the next recovery.
References & further reading
- Sheehy & Smith — Bitcask: A Log-Structured Hash Table for Fast Key/Value Data (Basho, 2010) — the original design paper
- Riak KV docs — Bitcask backend — configuration, tuning, and the keys-in-memory caveat
- basho/bitcask — reference implementation (Erlang/C) — the source: record format, merge, hint files
- Martin Kleppmann — Designing Data-Intensive Applications, Ch. 3 — uses Bitcask to introduce log-structured storage and hash indexes