Remember Ramu Kaka?
If you read Danni, Johny and the Java Feature Flag Problem, you know Ramu Kaka. He runs the tea stall in front of the hospital. He was our feature flag.
Turns out Ramu Kaka is also a database engineer. He just doesn't know it.
Half the hospital drinks chai on credit. Ward boys, nurses, Johny (obviously), and sometimes even Big-B on night shift. Ramu Kaka tracks all of it in a notebook.
His rules are simple:
- He never erases anything. Pen only. Crossing out looks dishonest.
- Every new chai, every payment, he writes a new line at the bottom.
- When the notebook is full, it goes into the drawer and he starts a new one. Old notebooks are never written to again.
- He doesn't remember anyone's balance. He remembers which notebook and which line has their latest entry.
Johny asks "Kaka, how much do I owe?" Kaka doesn't flip through 40 pages. He goes straight to notebook 3, line 112, reads one line, done.
Congratulations👏. That is Bitcask.
Bitcask: A Log-Structured Hash Table for Fast Key/Value Data by Justin Sheehy and David Smith (Basho Technologies, 2010). Six pages. Readable in one chai break. It came out of Riak.
No LSM levels. No bloom filters. No B-tree page splits. An append-only log plus a hash map. That's the whole trick.
On disk: the notebook drawer
A Bitcask instance is just a directory. Only one OS process may open it for writing at a time.
Inside, exactly one file is active. When it crosses a size threshold, it's closed and a new active file is created. Once closed, on purpose or because the server died, a file is immutable. Never opened for writing again.
bitcask-dir/ ┌──────────────────────────┐ │ active data file <── appends only, one writer │ older data file (immutable) │ older data file (immutable) │ older data file (immutable) └──────────────────────────┘ Ramu Kaka's drawer. One open notebook on the counter, the full ones in the drawer. Writes are sequential. No seeking around to patch an old line.
One line in the notebook
Every put appends one entry:
┌───────┬────────┬────────┬──────────┬───────────┬─────────────┐ │ crc │ tstamp │ key_sz │ value_sz │ key │ value │ └───────┴────────┴────────┴──────────┴───────────┴─────────────┘ └─────────────────── covered by crc ─────────────────┘ -
crc: checksum over everything after it in the entry -
tstamp: a 32-bit local timestamp (the paper marks it internal-only, not exposed) -
key_sz,value_sz: sizes, so you know where key ends and value ends -
key,value: the actual bytes
A data file is these entries glued one after another. No header pages, no free lists, no slots.
Johny buys another chai? Kaka doesn't edit the old line. He writes a new one. The old line stays. It's just not the latest anymore. Same in Bitcask: an update is a new append. The old value is still on disk.
Johny clears his tab? Kaka writes JOHNY - CLEARED. That's a tombstone. In Bitcask, delete is a write of a special tombstone value, removed on the next merge.
In memory: Ramu Kaka's brain (the keydir)
After the append, Bitcask updates an in-memory hash table called the keydir. For every key, a fixed-size record points at the most recent entry:
keydir (in RAM) ┌─────────┐ ┌─────────┬──────────┬───────────┬────────┐ │ "johny" │ -> │ file_id │ value_sz │ value_pos │ tstamp │ ├─────────┤ ├─────────┼──────────┼───────────┼────────┤ │ "big-b" │ -> │ file_id │ value_sz │ value_pos │ tstamp │ ├─────────┤ ├─────────┼──────────┼───────────┼────────┤ │ "nurse" │ -> │ file_id │ value_sz │ value_pos │ tstamp │ └─────────┘ └─────────┴──────────┴───────────┴────────┘ Values are not in RAM. Every key is. Ramu Kaka remembers every customer's name and where their line is. He does not remember amounts.
On a write, the keydir is atomically updated to the newest location. Any later read sees it.
The basic flow
put(key, value)
- Build the entry:
tstamp | key_sz | value_sz | key | value, and compute a CRC over it. - Append
crc | entryto the end of the active file. Sequential write. - Optionally fsync (
sync_on_put). Safer, slower. - Only after the append succeeds, point the keydir at it:
key -> (file_id, value_sz, value_pos, tstamp). - If the active file crossed the size limit, close it. It's immutable now. Open a fresh active file.
get(key)
- Look up the key in the keydir. Not there? Not found.
- Seek to
value_posinfile_id, readvalue_szbytes. Done.
That's at most one disk seek. Often not even that. Bitcask leans on the OS page cache on purpose and has no internal read cache of its own.
delete(key)
- It's just a put, with a special tombstone value.
- Remove the key from the keydir.
Ramu Kaka's rule: write the line first, then remember where you wrote it. Flip that order, and a reader can follow a pointer to bytes that don't exist yet.
Merge: Sunday cleanup
Kaka never erases, so the drawer keeps growing. Johny has 300 lines of chai history and exactly one of them matters.
Bitcask merges the non-active (immutable) files into a fresh set with only the live, latest version of each key. Overwritten values and deleted keys are gone.
On Sunday, the nephew copies only each customer's current balance into a fresh notebook. The old notebooks go to the raddi-wala.
The active file isn't touched, so writes keep flowing while the merge runs.
Hint files: when Ramu Kaka gets a fever
One day Ramu Kaka gets dengue and comes back after a week. His memory is blank.
Slow option: read every notebook from the first page. That's what Bitcask does on open if it has nothing better: scan all data files to rebuild the keydir.
Faster option: while merging, the nephew writes a small index card next to each fresh notebook. Name, which line, how long the entry is. No amounts.
That's a hint file. Instead of values, it holds tstamp, key_sz, value_sz, value_pos, and the key. On open, Bitcask scans the hint file instead. Much smaller, much quicker startup.
The data files are the commit log. No separate replay. No WAL sitting next to the data. The log is the data.
The bill (trade-offs nobody puts on the poster)
Bitcask is simple. Simple is not free.
- Every key must fit in RAM. The keydir grows with the number of keys and must fit entirely in RAM. Values can be much larger than RAM, but keys can't. Huge keyspace with tiny values? Bad fit. Ramu Kaka can handle the hospital. Not the whole of Bangalore.
- No range scans. The keydir is a hash table.
list_keysandfoldwalk the whole store. Need ordered iteration? Use an LSM-tree or a B-tree. - Space amplification until merge. Every overwrite leaves garbage on disk until a merge runs. Write-heavy workloads on the same keys burn disk fast.
- Startup time without hints. No hint files means a full scan of every data file. Fine at small size. Painful when the drawer is big.
- Single writer. One process opens a Bitcask for writing. A deliberate simplification, not a bug. Still a constraint.
Torn writes and the CRC
Say the power dies mid-append. Half an entry on disk. Chai spilled on the last line.
That's what the crc is for. On recovery you recompute it. Mismatch = this entry is garbage. A torn entry can only be at the tail of the active file, the only one ever appended to. The sane move (my design choice, not something the paper spells out) is to treat the first bad entry at the tail as the end of the log and truncate there.
CRC does not bring the lost write back. It only stops you from serving corrupted bytes as if they were real.
fsync deserves its own post, coming next. For now: write() returning success only means the bytes are in the OS page cache, not on disk.
Still relevant in 2026?
Yes. The hardware got faster. The ideas didn't expire.
- Append-only is everywhere. Postgres writes a WAL before touching data. Kafka is basically one giant append-only log. Same Ramu Kaka rule: never erase, just add a line.
- Sequential writes still win. SSDs made random reads cheap, but appending to the end of a file is still the simplest, most predictable write you can do.
- RAM is bigger now. "All keys must fit in memory" scared people in 2010. In 2026, plenty of workloads fit comfortably.
- Crash recovery is still the hard part. CRC per entry, replay the log, ignore the torn tail. Every storage engine has to answer this question.
- It's small enough to understand. You can hold the whole design in your head in one evening. Try that with an LSM tree.
So why does Ramu Kaka matter to me?
Cause I am mad or its fancy. I wanted to implement in rust.
Want to see me to pick fight with borrow checker? Follow along on X: @nimxch.
Read the paper: Bitcask: A Log-Structured Hash Table for Fast Key/Value Data, Justin Sheehy & David Smith, Basho Technologies, 2010.