Project 04 · DATABASE
Ledger
An embedded database written in Rust without external crates: page cache, B+tree indexes, write-ahead log and a hand-written SQL parser.
The challenge
Store data safely through crashes and power loss, with a storage engine that fits in one person's head.
The approach
Ledger is built bottom-up from a fixed-size page format. Every write goes through a checksummed log first, and recovery is tested by killing the process at random points thousands of times.
The layers
Every subsystem, with the code it took and the time it took to write.
01
Pager & page cache
3,980 lines3 weeks
02
B+tree
7,120 lines5 weeks
03
Write-ahead log
4,210 lines3 weeks
04
SQL parser
6,780 lines4 weeks
From the source
Splitting a full B+tree leaf
ledger/src/btree.rs
// split a full leaf node in two
fn split_leaf(&mut self, id: PageId) -> (Key, PageId) {
let right = self.pager.alloc();
let node = self.pager.get_mut(id);
let mid = node.len() / 2;
let moved = node.cells.split_off(mid);
self.pager.get_mut(right).cells = moved;
(self.first_key(right), right)
}
May 2026
Pages written and read back from disk
Jun 2026
Crash-safe writes with the WAL
Aug 2026
SELECT, INSERT and indexes working
Next
Transactions and concurrent readers