Bitcask in miniature
On the roadmap:Advanced · step 3: Storage engines
An append-only data file plus an in-memory key directory: one-seek reads, tombstone deletes, merge and recovery on restart.
In plain words
A key-value store that only ever adds to the end of a file, and remembers in memory where each key's latest value sits. Reading a key is one jump to the right spot.
Why it matters
It shows why writing at the end of a file is so fast, and why many databases are built this way. You also see the price: old values pile up until a clean-up (merge) rewrites the file.
Where you meet it
- Riak's original storage engine
- The idea behind log-structured stores such as LSM-tree databases
- Many embedded key-value stores
You will be able to
- Explain why appending beats updating in place on disk
- Say what a tombstone is and why deletes need one
- Describe how a store rebuilds its index after a crash
In interviews
Comes up in 'design a key-value store' and any question about write-heavy storage.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- Records appended to a data file, one JSON line each
- A keydir mapping key to offset and length
- get() with a single positioned read
- Tombstones for delete, merge() to reclaim space
- Rebuilding the keydir by scanning the file on open
This lab reads and writes files, so it runs on your own computer. Copy the code and the check, then use the commands below.
import fs from "node:fs";
type Loc = { offset: number; length: number };
export class MiniBitcask {
private keydir = new Map<string, Loc>();
private fd: number;
private end = 0;
constructor(private path: string) {
this.fd = fs.openSync(path, "a+");
this.recover();
}
/** Rebuild the keydir by scanning the log from the start. A last record without its newline is a torn write and is dropped. */
private recover(): void {
const data = fs.readFileSync(this.path);
let offset = 0;
for (;;) {
const nl = data.indexOf(10, offset);
if (nl < 0) break;
try {
const r = JSON.parse(data.subarray(offset, nl).toString()) as { k: string; v: string | null };
if (r.v === null) this.keydir.delete(r.k); else this.keydir.set(r.k, { offset, length: nl + 1 - offset });
} catch { break; }
offset = nl + 1;
}
this.end = offset;
fs.ftruncateSync(this.fd, this.end);
}
private append(k: string, v: string | null): Loc {
const line = JSON.stringify({ k, v }) + "\n";
const buf = Buffer.from(line);
fs.writeSync(this.fd, buf, 0, buf.length, this.end);
const loc = { offset: this.end, length: buf.length };
this.end += buf.length;
return loc;
}
put(key: string, value: string): void { this.keydir.set(key, this.append(key, value)); }
delete(key: string): void { if (this.keydir.delete(key)) this.append(key, null); }
get(key: string): string | undefined {
const loc = this.keydir.get(key);
if (!loc) return undefined;
const buf = Buffer.alloc(loc.length);
fs.readSync(this.fd, buf, 0, loc.length, loc.offset); // the single disk read
return (JSON.parse(buf.toString()) as { v: string }).v;
}
/** Rewrite the file with only live records. Returns bytes reclaimed. */
merge(): number {
const before = this.end;
const live = [...this.keydir.keys()].map((k) => [k, this.get(k)!] as const);
fs.closeSync(this.fd);
fs.writeFileSync(this.path, "");
this.fd = fs.openSync(this.path, "a+");
this.end = 0; this.keydir.clear();
for (const [k, v] of live) this.put(k, v);
return before - this.end;
}
get keys(): number { return this.keydir.size; }
close(): void { fs.closeSync(this.fd); }
}
How to run it on your computer
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints bitcask-mini ok when everything passes. You need Node.js installed.
mkdir bitcask-mini && cd bitcask-mini
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- The original design keeps every key in memory, so your set of keys has to fit in RAM. Only the values live on disk.
- Real versions write a CRC with each record, rotate to a new file at a size limit, and keep a hint file so a restart does not have to re-read every value.
- Merging (compaction) runs in the background and rewrites old files without blocking reads or writes.
Bitcask or something else?
| How it stores data | Reads | Writes | Memory | Pick it when | |
|---|---|---|---|---|---|
| Bitcask | Append-only file plus an in-memory key directory | One jump using the directory | Very fast: always at the end of the file | Every key must fit in memory | Writes are heavy and you look things up by key |
| B-tree database | Pages updated in place on disk | A few page reads | Slower: in-place updates jump around the disk | Mostly a cache of pages | You need range queries and rich queries |
| LSM-tree store | A memory table plus sorted files merged in the background | May check several files | Fast and sequential | A moderate index and filters | Heavy writes, range scans, and data bigger than memory |
| Plain log file | Just keeps adding lines | Must scan everything | Fastest | None | You only ever replay the log and never look things up |
What it cannot do
Every key must fit in memory
The directory holds all keys. If you outgrow RAM, this design stops working.
No ordered scans
A hash directory finds one key quickly but cannot list keys in order or by range.
Old values pile up
Updates and deletes leave garbage behind until a merge rewrites the file.
Merging needs spare disk and I/O
A merge writes a new file before removing the old ones, so you need room and spare capacity for it.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Add a CRC to each record and a hint file for faster start-up
- Rotate to a new active file at a size limit
- Run merge in the background without blocking reads