STAGE 1 · THE PAGE DECK

The Quarry

A database file is not a stream of bytes, it is a strip of numbered 4 KiB cells, and exactly one component owns them.

What you're wiring up

Databases never read files byte by byte. They carve the file into fixed-size pages, 4 KiB here because that is the granularity the operating system and the disk already use, and always move whole pages between disk and memory. Everything you build in later stages, trees and logs and tables, is just an opinion about what the bytes inside a page mean.

This stage builds the pager: the single component allowed to touch the file. Read a page, write a page, allocate a page, plus a small cache so a hot page is not fetched twice. It also gives you one choke point for fsync, which is the thing that makes crash safety tractable three stages from now.

Page 0 is special. It is the meta page, holding a magic number, a format version and the page count, so the engine can recognize its own file and refuse someone else's. Later stages bolt the tree root and the free list onto that same page.

# page 0 is the meta page
offset 0   magic    BYHDB\x01   (6 bytes)
offset 6   version  u16
offset 8   pages    u32

# every other page: 4096 raw bytes at offset id*4096

Assembly steps

[ 01 ]

Fix the file format: PageSize 4096 and a 16-byte meta header (magic, version, page count). Open(path) either creates a fresh file with a valid meta page or validates an existing one.

hint

Reject bad magic or a bad version with a distinct error. The harness checks the behavior, not your wording.

hint

Pick little-endian once and use it everywhere. Mixed endianness is the classic works-on-my-machine, corrupt-everywhere-else bug.

[ 02 ]

Implement ReadPage(id) and WritePage(id, data) with ReadAt and WriteAt at offset id*PageSize. An out-of-range read is an error, never zero-filled silence.

hint

Copy into a fresh buffer on read. Handing out a shared slice lets a caller's scribbles corrupt your cache later.

[ 03 ]

Implement AllocatePage: bump the page count, extend the file, rewrite the meta page.

hint

The meta page is just page 0. Update it through your own WritePage, with no special path.

[ 04 ]

Add a dumb page cache: a map of page id to bytes, a MarkDirty, and a Flush that writes every dirty page and then calls Sync. No eviction yet.

hint

Flush is the only place Sync is ever called. Keeping fsync at one choke point is what makes Stage 4 possible.

[ 05 ]

Fill in the debug commands the harness uses to look inside your file: byhdb pages prints the meta header, byhdb page hex-dumps one page.

hint

The starter ships the CLI scaffold and flag parsing. You are only filling in handlers.

Go deeper (after it passes)

Read DDIA's storage and retrieval chapter next: it sets the page-oriented choice you just made against the log-structured (LSM) alternative. Then start docs/file-format.md in your repo. Writing your own format spec is the explain-it-back step, and each stage adds a section.