Building a Bitcask-style storage engine from scratch

A database is only as trustworthy as the layer that actually puts bytes on disk. So I started my
distributed-systems build at the very bottom — before any network or replication — with one question:
where do the bytes go, and how do I get them back after a kill -9?

What I built

A single-node key-value store — Put, Get, Delete — in a couple hundred lines of Go, modeled on
Riak’s Bitcask. Two moving parts:

append-only log ──▶ [k1|v1][k2|v2][k1|v3]...       (source of truth, on disk)
in-memory index ──▶ { k1: offset=…, k2: offset=… }  (rebuilt from the log on startup)

Every write appends one record — crc | timestamp | keyLen | valLen | key | value — to the end of a
single file. An in-memory map (the keydir) remembers where each key’s latest record lives. A read is
one map lookup plus one ReadAt. That’s the whole engine.

The concepts that made it work

• Append-only beats in-place. Sequential writes crush random writes on both SSDs and spinning
  disks, and “only ever append” makes recovery and concurrency almost trivial — one writer, always
  moving forward. An overwrite or delete is just a newer record.
• The index is a cache; the log is the truth. The keydir holds nothing you can’t reconstruct. On
  startup I throw it away and rebuild it by replaying the log — later records win, tombstones erase
  keys. That one principle — durable log + derived projection — is the spine of everything that
  follows.
• Every record carries a CRC. Four bytes of checksum per record means every read and every
  recovery scan self-verifies. Corruption gets caught, not silently served.
• Compaction reclaims the dead. Overwritten and tombstoned records pile up forever, so a Merge()
  pass rewrites the log keeping only what the keydir still points at — because the index, by
  definition, is the set of live records.

The thing that bit me

Crash-safety isn’t “just add fsync.” The subtle part is recovery. A process killed mid-write
leaves a half-written record at the tail of the log. My first instinct — treat any decode failure
as corruption — would refuse to open a database that’s actually fine. The right model: a truncated
record at the very end is normal (the last write didn’t finish) → stop cleanly and truncate it off.
A checksum mismatch in the middle of the log is real damage → surface it loudly. Telling those two
apart is the entire game.

Tradeoffs & the road not taken

The defining limitation: every key must fit in RAM, because the keydir is in memory. And there are
no range scans — keys sit on disk in write order, not sorted. I chose Bitcask anyway: the index
fits comfortably at this scale, point reads/writes are all I need, and its simplicity keeps the
ideas legible. When I’d switch:

• LSM-tree (RocksDB, Cassandra) — writes dominate and the dataset dwarfs RAM; sorted data and
  range scans come back.
• B-tree (Postgres, InnoDB) — reads dominate and you need in-place updates and transactions.

Where this sits in the system

Last week: nothing — this is the foundation. Next: put this store behind an RPC server, where a client
that retries a dropped request forces me to admit that “exactly-once” is a comfortable lie. And
this append-only log? It comes back — replicated across machines — as Raft’s log, and then as a Kafka.
Same primitive, all the way up.

Part of a series building a distributed database from scratch.