Pager in Zig that reads and writes 4KB pages by id using positioned I/O (pread/pwrite), and grows the file one page at a time;error.PageFull, never a silent overflow into the next record;Learn Zig Series):Over the last three episodes we built a small search engine, and the one just before this closed it out. Today we start something new and, I argue, even more fundamental: a database engine. Not a thin wrapper around SQLite -- the actual machinery, from the raw bytes on disk upward. And where every database engine begins, without exception, is with a single unglamorous question: how do you lay bytes down on a disk so that you can find them again, change them, and not corrupt everything the next time the power blinks?
The naive answer is "just write records to the file wherever there is room". That answer falls apart almost immediately. Records have different sizes, so deleting one leaves a hole of the wrong shape for the next. Updating a record to be a little longer means it no longer fits where it was, so now you are shuffling the entire rest of the file. Reading one record means you have no idea where it starts unless you scanned everything before it. Every serious database on earth solved this the same way decades ago, and the solution is the subject of this whole episode: the file is not a stream of records, it is an array of fixed-size pages. Let's dive right in!
A page is a fixed-size block of bytes -- 4096 bytes is the near-universal choice, and it is no accident. 4KB is the size of a memory page on essentially every modern CPU, and it is the granularity at which operating systems and SSDs actually move data. When you ask to read one byte from a file, the kernel does not fetch one byte; it faults in an entire 4KB page from the block device into the page cache. So if your database also thinks in 4KB units, every read you issue lines up exactly with what the hardware was going to do anyway -- no wasted transfer, no torn reads straddling two hardware blocks. We touched the OS side of this back in episode 31 on memory-mapped I/O; pages are the same idea, seen from the database's chair.
Fixing the size buys you three enormous simplifications. First, addressing becomes arithmetic: page number 7 lives at byte offset 7 * 4096, full stop. No index, no scan -- a multiply. Second, the file can grow predictably, one page at a time, and free pages can be recycled without fragmentation because every page is interchangeable. Third, and this is the big one for later episodes, a fixed page is the natural unit for a cache: you can hold a fixed number of hot pages in memory (a "buffer pool", built on exactly the LRU cache we wrote in episode 123) and evict cold ones, because they are all the same size and swap in and out cleanly. The B-Tree from episode 108 becomes a tree of pages, each node a page, each child pointer just a page number. Everything a database does is, underneath, reading and writing pages.
So the plan for this episode is small and sharp. We build two things. A Pager, which owns the file and hands you page number N as 4096 bytes, and writes them back. And a SlottedPage, which imposes structure on those 4096 raw bytes so a single page can hold many variable-length records without wasting space. Two abstractions, and by the end they persist real data to a real file. Let us start at the bottom.
We begin with the constants that define our on-disk world. A page is 4096 bytes; a page is addressed by a PageId, for which a u32 gives us four billion pages (16 terabytes) of headroom -- plenty:
const std = @import("std");
pub const PAGE_SIZE: usize = 4096;
pub const PageId = u32;
pub const Page = [PAGE_SIZE]u8;
That Page = [PAGE_SIZE]u8 alias is a small thing that pays off constantly: a page is just a fixed-size array of bytes, and a *Page is a pointer to exactly 4096 bytes. The compiler now knows the size at comptime, which means it can bounds-check our indexing and lets a pointer-to-array coerce cleanly to a slice when the file API wants one.
The Pager itself owns an open file and remembers how many pages currently live in it. The two operations that matter are "read page N into this buffer" and "write this buffer to page N", and the crucial detail is that both use positioned I/O -- pread and pwrite -- which take an explicit byte offset in stead of relying on a mutable file cursor. That matters a great deal: a single seek-less positioned read is atomic with respect to the offset, and it means two threads could later read different pages of the same file without fighting over one shared cursor position:
pub const Pager = struct {
file: std.fs.File,
page_count: PageId,
pub fn init(file: std.fs.File) !Pager {
const end = try file.getEndPos();
return .{ .file = file, .page_count = @intCast(end / PAGE_SIZE) };
}
pub fn readPage(self: *Pager, id: PageId, out: *Page) !void {
if (id >= self.page_count) return error.PageOutOfRange;
const offset = @as(u64, id) * PAGE_SIZE;
const n = try self.file.preadAll(out, offset);
if (n != PAGE_SIZE) return error.ShortRead;
}
pub fn writePage(self: *Pager, id: PageId, data: *const Page) !void {
if (id >= self.page_count) return error.PageOutOfRange;
const offset = @as(u64, id) * PAGE_SIZE;
try self.file.pwriteAll(data, offset);
}
};
Notice how init recovers the page count from the file's existing size: end / PAGE_SIZE. Open an existing database and it already knows how many pages it holds, without any separate metadata. Notice too that both readPage and writePage refuse an out-of-range id with a returned error rather than reading garbage past the end of the file -- the Zig habit of turning "that can't happen" into a value the caller can see. And preadAll returning fewer than PAGE_SIZE bytes is treated as error.ShortRead, because a page half-read from disk is not a page, it is a corruption waiting to be believed.
A brand-new database is an empty file with zero pages. To store anything we must first grow it, and that is a third Pager method: allocate a page. The simplest correct policy -- the one SQLite itself started with -- is to append a fresh, zeroed page at the end and hand back its id:
pub fn allocPage(self: *Pager) !PageId {
const id = self.page_count;
const zero: Page = [_]u8{0} ** PAGE_SIZE;
const offset = @as(u64, id) * PAGE_SIZE;
try self.file.pwriteAll(&zero, offset);
self.page_count += 1;
return id;
}
Zeroing the new page matters more than it looks. A fresh page whose bytes are all zero has, by our layout below, a slot count of zero and is therefore a valid, empty slotted page -- so allocating a page and immediately reading it back gives you a well-formed empty page, not random stack garbage. That [_]u8{0} ** PAGE_SIZE builds the zero page at comptime and costs nothing at runtime beyond the write itself.
A real engine would keep a free list of pages that were allocated, filled, then emptied by deletes, and recycle those before growing the file -- otherwise a database that churns rows would grow forever. We will not build the free list today (it is a natural extension, and honestly a fine thing to try yourself once the rest is in place), but the shape of allocPage is exactly where it would hook in: check the free list first, fall back to append. Having said that, let us give these 4096 empty bytes some structure.
Here is the central problem. A page is 4096 fixed bytes, but the records we want to store -- a name, a row, a JSON blob -- are all different lengths. How do you pack a dozen variable-length records into a fixed page, let some of them be deleted, and still find any record by a stable number? The answer, invented in the 1970s and unchanged since because it is simply correct, is the slotted page.
The trick is to grow two structures toward each other from opposite ends of the page. At the front sits a small header, and right after it a slot directory -- an array of little (offset, length) pairs -- that grows forward, toward the middle. At the very back, the actual record bytes (the "cells") are written, growing backward, toward the middle. The free space is the shrinking gap between them. A record is identified not by its byte position -- which might move -- but by its slot index, and the slot holds the real offset. That indirection is the whole magic: you can shuffle cells around to reclaim space, and as long as you update the slots, every record's public identity (its slot number) never changes.
Our header needs three u16 fields: how many slots exist, where the free space begins (just past the last slot), and where it ends (the start of the lowest cell). We store them as explicit little-endian integers so the on-disk format is identical on every machine, big-endian or little -- the same discipline we used serializing MessagePack in episode 91. A SlottedPage is just a thin wrapper borrowing a *Page; it owns no memory of its own:
const HEADER_SIZE: usize = 6; // num_slots(2) + free_start(2) + free_end(2)
const SLOT_SIZE: usize = 4; // offset(2) + len(2)
const SlottedPage = struct {
bytes: *Page,
fn init(bytes: *Page) SlottedPage {
var sp = SlottedPage{ .bytes = bytes };
sp.setNumSlots(0);
sp.setFreeStart(@intCast(HEADER_SIZE));
sp.setFreeEnd(@intCast(PAGE_SIZE));
return sp;
}
fn numSlots(self: SlottedPage) u16 {
return std.mem.readInt(u16, self.bytes[0..2], .little);
}
fn setNumSlots(self: SlottedPage, v: u16) void {
std.mem.writeInt(u16, self.bytes[0..2], v, .little);
}
fn freeStart(self: SlottedPage) u16 {
return std.mem.readInt(u16, self.bytes[2..4], .little);
}
fn setFreeStart(self: SlottedPage, v: u16) void {
std.mem.writeInt(u16, self.bytes[2..4], v, .little);
}
fn freeEnd(self: SlottedPage) u16 {
return std.mem.readInt(u16, self.bytes[4..6], .little);
}
fn setFreeEnd(self: SlottedPage, v: u16) void {
std.mem.writeInt(u16, self.bytes[4..6], v, .little);
}
};
The std.mem.readInt and writeInt pair is doing real work here. Given a two-byte window into the page and an endianness, they read or write a u16 with no undefined behaviour and no alignment worries, because they operate byte by byte. This is the correct way to serialize integers to a byte buffer in Zig -- never @ptrCast a *u16 onto an arbitrary offset in a []u8 and dereference it, because that offset might not be two-byte aligned and you would be inviting a fault on stricter architectures. Reading self.bytes[0..2] slices the page array with comptime-known bounds, which yields a *[2]u8 -- exactly the fixed-size pointer readInt wants. Slices, integers, endianness, all the way back to episode 5. Everything we need is right here.
Insertion is where the two-ends-toward-the-middle dance actually happens. To add a record we need room for two things: the record bytes themselves, at the back, and one new slot, at the front. If the gap between free_start and free_end cannot hold both, the page is full and we say so. Otherwise we drop the cell at the back, append its slot at the front, and move both fences inward:
fn insert(self: SlottedPage, record: []const u8) !u16 {
const need = record.len + SLOT_SIZE; // one cell + one slot entry
const fs: usize = self.freeStart();
const fe: usize = self.freeEnd();
if (fe - fs < need) return error.PageFull;
// write the cell at the back, growing downward
const cell_offset: u16 = @intCast(fe - record.len);
@memcpy(self.bytes[cell_offset..fe], record);
// append the slot at the front, growing upward
const index = self.numSlots();
const slot_pos = HEADER_SIZE + @as(usize, index) * SLOT_SIZE;
std.mem.writeInt(u16, self.bytes[slot_pos..][0..2], cell_offset, .little);
std.mem.writeInt(u16, self.bytes[slot_pos + 2 ..][0..2], @intCast(record.len), .little);
self.setNumSlots(index + 1);
self.setFreeStart(@intCast(slot_pos + SLOT_SIZE));
self.setFreeEnd(cell_offset);
return index;
}
Walk it once and it is obvious. need is the record length plus one four-byte slot. We compute the free gap in usize to avoid any chance of a u16 subtraction wrapping around (a genuine footgun -- if fe were ever smaller than need and we worked in u16, the wrap would produce a giant "positive" number and we would happily scribble past the buffer). The cell goes at fe - record.len, so it butts right up against the previous lowest cell. We @memcpy the record into that window, whose length is exactly record.len by construction. Then the slot: two little-endian u16s, the cell's offset and its length, written at slot_pos. Finally we advance free_start past the new slot and drop free_end to the new cell -- the two fences have each stepped one notch toward the middle. The return value is the record's permanent handle: its slot index.
The self.bytes[slot_pos..][0..2] idiom might look odd the first time. self.bytes[slot_pos..] takes an open-ended slice from a runtime offset, and then [0..2] re-slices it with comptime bounds to recover a *[2]u8. It is the standard Zig move for "give me a fixed-size window at a runtime position", and writeInt needs that fixed size to know it is writing exactly two bytes.
Reading is the reverse trip: given a slot index, look up the slot to find where the cell lives and how long it is, then return that slice straight out of the page. We hand back a ?[]const u8 -- null if the index is out of range or the slot has been tombstoned:
const Slot = struct { offset: u16, len: u16 };
fn slot(self: SlottedPage, index: u16) Slot {
const slot_pos = HEADER_SIZE + @as(usize, index) * SLOT_SIZE;
return .{
.offset = std.mem.readInt(u16, self.bytes[slot_pos..][0..2], .little),
.len = std.mem.readInt(u16, self.bytes[slot_pos + 2 ..][0..2], .little),
};
}
fn get(self: SlottedPage, index: u16) ?[]const u8 {
if (index >= self.numSlots()) return null;
const s = self.slot(index);
if (s.len == 0) return null; // tombstone: this record was deleted
return self.bytes[s.offset .. s.offset + s.len];
}
The returned slice is a view into the page, not a copy -- zero allocation, exactly the borrowing discipline we have leaned on since episode 5. It is valid for precisely as long as the page buffer it points into stays alive and unchanged, which is the caller's responsibility to respect. Cheap and honest.
Deletion is delightfully lazy. We do not move any bytes; we simply mark the slot dead by setting its length to zero -- a tombstone. The record's cell bytes are still physically sitting in the page, but get now reports the slot as empty, and the slot index is retired:
fn delete(self: SlottedPage, index: u16) void {
if (index >= self.numSlots()) return;
const slot_pos = HEADER_SIZE + @as(usize, index) * SLOT_SIZE;
std.mem.writeInt(u16, self.bytes[slot_pos + 2 ..][0..2], 0, .little);
}
Tombstoning is how every real database deletes, and the reason is the forementioned indirection: because records are addressed by slot index and not by byte position, we must never let a delete shift the meaning of another record's index. Marking dead is safe; the dead cell's space just becomes garbage inside the page. Reclaiming that garbage is a separate, deliberate step called compaction -- you sweep the live cells down to the back, rewrite their slot offsets, and reset the fences. I am deliberately leaving compaction as a thing you can add on top (it is a satisfying afternoon), because the point today is that delete is correct and O(1) even before you optimize the space back. Now, the moment of truth: does any of this actually survive a trip to the disk?
An in-memory data structure that claims to be a database is worth nothing until you power-cycle it, so we write the test that matters: insert some records, flush the page to a real file through the pager, then read the raw bytes back into a completely fresh buffer and check the records are all still there. We use std.testing.tmpDir so the test writes to a throwaway directory the test harness cleans up for us -- no litter left on your disk:
test "records survive a round-trip through the pager" {
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
const file = try tmp.dir.createFile("units.db", .{ .read = true });
defer file.close();
var pager = try Pager.init(file);
const id = try pager.allocPage();
var buf: Page = undefined;
var page = SlottedPage.init(&buf);
_ = try page.insert("zig");
_ = try page.insert("is");
_ = try page.insert("systems programming");
try pager.writePage(id, &buf);
// read it back into a brand-new buffer, no shared state with the writer
var fresh: Page = undefined;
try pager.readPage(id, &fresh);
const reread = SlottedPage{ .bytes = &fresh };
try std.testing.expectEqual(@as(u16, 3), reread.numSlots());
try std.testing.expectEqualStrings("zig", reread.get(0).?);
try std.testing.expectEqualStrings("systems programming", reread.get(2).?);
}
This passes, and it is worth savouring why. We never re-init the fresh page -- we wrap the raw bytes straight from disk with SlottedPage{ .bytes = &fresh } and immediately ask it questions. It answers correctly because the header we wrote (slot count, offsets, lengths) is in the page bytes, serialized as little-endian integers, so the reconstructed page reads its own structure back out of the disk image. That is the entire point of a persistent format: the bytes are self-describing. The writer and reader share nothing but the file. Wowzers, that is a real database's storage layer, in under a hundred lines.
The other behaviour a storage layer absolutely must get right is refusing to overflow. A page that silently wrote past its 4096 bytes would corrupt the next page, and a corruption that shows up three commits later is the worst kind of bug there is. So we test that filling a page returns error.PageFull cleanly, and never a scribble:
test "a full page returns an error instead of overflowing" {
var buf: Page = undefined;
var page = SlottedPage.init(&buf);
const big = [_]u8{'x'} ** 1000; // each insert needs 1000 + 4 bytes
var stored: usize = 0;
while (page.insert(&big)) |_| {
stored += 1;
} else |err| {
try std.testing.expectEqual(error.PageFull, err);
}
// 4096 - 6 header = 4090 usable; 4 records (4016 bytes) fit, a 5th does not
try std.testing.expectEqual(@as(usize, 4), stored);
try std.testing.expect(page.freeStart() <= page.freeEnd()); // fences never crossed
}
The while (...) |_| { } else |err| { } form is Zig's error-union loop: it keeps looping while insert succeeds, and the else capture fires the instant insert returns an error, binding it to err. We assert the count is exactly four (the arithmetic works out: 4090 usable bytes, each record costs 1004, and four of those is 4016 while a fifth would need 5020) and -- the real safety property -- that free_start never climbed past free_end. The two fences met but did not cross, which is precisely the invariant that keeps one record from corrupting another. This is the kind of test that lets you sleep at night; std.testing will also shout if a leak or an out-of-bounds slice sneaks in, since every buffer here is checked.
And the tombstone, proven end to end -- a deleted record reads back as gone while its neighbours are untouched:
test "deleting a slot tombstones just that record" {
var buf: Page = undefined;
var page = SlottedPage.init(&buf);
_ = try page.insert("keep-me");
const doomed = try page.insert("delete-me");
page.delete(doomed);
try std.testing.expect(page.get(doomed) == null); // gone
try std.testing.expectEqualStrings("keep-me", page.get(0).?); // survivor intact
}
Everything in this episode is a faithful miniature of production reality, and the family resemblance is striking once you go looking. SQLite -- written in C, and very possibly the most deployed database on the planet -- stores its entire database as an array of fixed-size pages (default 4096 bytes, configurable), managed by a pager module whose job is exactly ours: read page N, write page N, cache hot pages, and it uses a slotted-page layout with a cell-pointer array at the top of each B-tree page and cells packed from the bottom. If you read the SQLite pager source, the shape of readPage/writePage/allocPage will look eerily familiar. Postgres, written in C too, uses 8KB pages with a nearly identical slotted structure -- a page header, an array of ItemId line pointers growing down, and tuples growing up to meet them; deletes there are tombstones as well, cleaned later by the VACUUM process, which is compaction under a friendlier name.
In Rust, the embedded engines sled and redb both build on paged storage; redb in particular is an explicit page-and-slotted-B-tree design, using Rust's ownership to track which pages are borrowed by a live transaction. In Go, bbolt (the store behind etcd, and thus behind Kubernetes) is a memory-mapped, paged, copy-on-write B-tree -- it mmaps the file and treats it as an array of pages, which is our Pager fused with episode 31's memory mapping. Four ecosystems, four languages, one idea: the file is an array of fixed-size pages, and a page is a little slotted arena of variable-length records. We built the real thing, not a toy of it.
Zig's particular contribution to this old design is that the dangerous parts are dragged into the open. The buffer is a *Page of known size, so overruns are bounds-checked in safe builds. The integers are serialized with explicit endianness, so the format is portable by construction and not by accident of your CPU. And the failure modes -- a short read, an out-of-range page, a full page -- are all returned values you cannot forget to handle, because the compiler will not let a !void slip by unexamined. A C pager has every one of these hazards too; the difference is that in C they are conventions and comments, and in Zig they are types.
Step back and look at what we have. A Pager that turns a flat file into an addressable array of durable 4KB pages, and a SlottedPage that turns one of those pages into a little arena holding many variable-length records, each with a stable identity, inserted and read and deleted, and proven to survive a round-trip through the disk. That is the bedrock. Every database you have ever used is standing on a floor built out of exactly these two pieces.
But a flat heap of records in pages is not yet a database -- it is a filing cabinet with no index. To get a record right now you would have to know its page and slot, or scan every page in the file. What turns storage into a database is putting a searchable structure on top of these pages, so you can find a record by its key in a few page reads in stead of a linear sweep. And we already know exactly which structure does that, because we spent a whole episode on it: the B-tree from episode 108, except this time its nodes will not live in memory -- each node will be a page, and each child pointer will be a PageId that the pager loads on demand. That is the next brick we lay. Once records can be found by key, the natural question after that is how a human asks for them -- and we happen to have built a recursive-descent parser twice already in this series, so you can guess the shape of what comes later.
For now, go take the two little modules we wrote, point the pager at a file of your own, insert a few hundred records across several pages, and watch a file on your disk fill up with real, self-describing, recoverable data. Then try the two extensions I flagged -- a free list in allocPage, and a compaction pass that squeezes the tombstones out of a page. Get those working and you will understand storage engines better than most people who use one every day. ;-)
Bedankt voor het lezen, en tot de volgende keer! ;-)
@scipio