Build a database storage engine

Write each put as a record at the end of a file: length, key, value. Keep a hash map in memory from key to file offset. A get looks up the offset and reads one record. On startup, scan the file and rebuild the map.

It's the design of Bitcask, and it's pretty fast. Its limits show up right away: the file only grows, the index must fit in RAM, and range scans are impossible because a hash map has no order.

Add a CRC to every record and, on startup, stop reading at the first record whose checksum fails. That's how you detect a write the crash cut in half. Then decide when to fsync: on every write, or batched every few milliseconds.

Measure both. The gap is probably larger than you expect, and it's the trade every database exposes as a setting, like synchronous_commit in Postgres or appendfsync in Redis. Write down which writes you promise to keep and test that promise.

Old versions of overwritten keys waste space. Write the live records to a new file, fsync it, then rename it over the old one. rename is atomic on POSIX filesystems, so a crash leaves either the old file or the new one.

Remember to fsync the directory too. Without it the rename itself can be lost, which is one of the more obscure ways to lose data on Linux.

Lay out the file as fixed-size pages. Each page holds a header, an array of slot offsets, and variable-length cells packed from the end. Interior pages hold separator keys and child page numbers; leaves hold keys and values and link to their right sibling for scans.

The hard part is the split. When a leaf is full, move half its cells to a new page and push a separator into the parent, which may split too. Get inserts right before you attempt deletes and merges. Postgres, for one, never merges half-empty pages; it only reclaims pages once they're completely empty.

Buffer writes in a sorted in-memory memtable backed by your log from milestone 2. When it's full, write it out as an immutable sorted file (an SSTable) with an index block at the end. Reads check the memtable, then SSTables from newest to oldest.

Reads now get slower as files pile up, so add a bloom filter per SSTable, then background compaction that merges files. Deletes become tombstones that compaction eventually drops. You'll see exactly why LSMs win on writes and pay for it on reads.

Stop reading pages straight from the file. Keep a fixed array of in-memory frames and a map from page number to frame. Callers pin a page while they use it, and only unpinned pages can be evicted. A dirty page has to be written back before its frame is reused.

Start with LRU, then try clock, which is roughly LRU without a linked list to update on every hit. A sequential scan will flush your hot pages out of a naive LRU. Postgres fights that with ring buffers for large scans.

Now pages are updated in place, so a crash can leave a split half-written: a new page exists, but the parent doesn't point to it. Log every page change before you make it, stamp each page with the LSN of its last change, and never flush a page before its log records are on disk.

Recovery reads from the last checkpoint and redoes any change whose LSN is newer than the page's. That's the redo half of ARIES. The undo half only matters once you have transactions that can abort, so leave it for the stretch goals.

Group writes into a batch with a single commit record in the log. Recovery applies a batch only if it finds the commit. That gives you atomicity.

For isolation, the cheapest start is a single writer plus snapshot reads: tag each version with a sequence number and let readers ignore anything newer than the one they started at. It's a small version of how RocksDB snapshots and Postgres MVCC let reads run without blocking writes.