Rust · Database Systems · Storage Engines

Bedrock — a relational database engine

A single-node relational database engine, built in Rust from the storage layer up — buffer pool, indexes, query execution, transactions, and recovery, each implemented from the paper rather than imported from a crate. The target is a real, Postgres-shaped engine: durable, concurrent, and fast, built one rigorously-tested layer at a time.

Language Rust, zero dependenciesApproach Every layer built from the paper up, no shortcutsCurrent focus Buffer pool manager (storage layer)Target Production-track single-node relational engineConcurrency Latch-based, RAII page guardsRoadmap storage → indexes → execution → transactions → recovery → beyond

Why from scratch

Reference implementations explain what a database does. Porting every algorithm to Rust by hand — with no query engine crate, no storage-engine crate, not even a hashing crate — is what forces understanding why each piece exists and where it actually breaks under concurrency.

Target architecture

Bedrock target architecture SQL text flows through a parser and cost-based optimizer into a Volcano-style pull executor, which drives a buffer pool manager backed by a replacer and a disk scheduler, which talks to the disk manager and the page file. SQL text (CLI / client) parse QUERY ENGINE Parser / binder AST Cost-based optimizer plan Volcano executor next() pulls tuples Buffer Pool Manager frames · page table (page_id → frame_id) · free list ReadPageGuard / WritePageGuard — RAII via Drop Replacer ARC (two lists + ghost lists) · LRU-K Disk Scheduler background thread · mpsc request queue Disk Manager read_exact_at / write_all_at, 8 KB pages db.pages TRANSACTIONS & RECOVERY Lock manager / MVCC isolation levels · deadlock detection WAL + ARIES recovery durability · crash-consistent replay

Components

Buffer Pool Manager
owns: frame allocation, page pinning
page tablefree listpin counts
Maps page_id to frame_id via a HashMap; a free list tracks unused frames before the replacer is consulted. `new_page`, `delete_page`, `checked_read_page`, `checked_write_page`, and `flush_page` are the surface every higher layer calls through.
ARC Replacer
owns: eviction policy
adaptiveghost listsself-tuning
Two cache lists (recently-seen once, seen more than once) plus two ghost lists of recently-evicted pages, with an adaptive target size that shifts based on ghost-list hits. Chosen over plain LRU because it resists sequential-scan pollution — a full table scan can't evict the pool's genuinely hot pages.
Disk Scheduler
owns: I/O dispatch
background threadmpsc channeldecoupled I/O
A dedicated thread consumes a queue of read/write requests and dispatches them to the disk manager, completing each through a channel the caller awaits on. Decouples buffer-pool logic from blocking file I/O and is the seam where batching or prefetch would land later.
Page Guards
owns: safe concurrent access
RAIIDropno manual unpin
`ReadPageGuard`/`WritePageGuard` pin a page on construction and unpin (flushing if dirty) automatically on drop. Rust's ownership model makes this nearly free — the C++ original needs hand-written move constructors to get the same guarantee.
LRU-K Replacer
owns: alternate eviction policy
k-distanceVecDeque + HashMapbenchmarkable
Evicts by backward k-distance rather than most-recent-use, so a page touched once doesn't look "hot" just because it was touched recently. Implemented behind the same `Replacer` trait as ARC specifically so both can be benchmarked head-to-head on the same access pattern.
Count-Min Sketch
owns: probabilistic frequency estimation
sketch matrixpairwise-independent hashingbounded error
The primer project: an approximate frequency counter in bounded memory, with a provable error bound instead of an exact count. The first proof, before touching storage, that a probabilistic data structure's guarantees can be reasoned about precisely rather than taken on faith.

How it's being built

01
Probabilistic primer
Count-Min Sketch · pairwise-independent hashing
"Why a sketch before a storage engine"

The first project is a probabilistic data structure, not a database component — deliberately so. Understanding a data structure's *error bound* rather than just its API is the same discipline the rest of the engine demands, just in a smaller, self-contained problem first.

"Bounded memory over exact counts"

A Count-Min Sketch trades exact frequency counts for a fixed-size matrix and a provable one-sided error bound — it never undercounts, only ever overcounts within a known probability. That asymmetry, and why it's acceptable, is the actual lesson.

02
Storage: buffer pool and replacement
ARC · LRU-K · disk scheduler · page guards
"ARC over plain LRU"

Plain LRU is vulnerable to sequential flooding: one full table scan evicts every genuinely hot page in the pool. ARC's two ghost lists let it adapt toward whichever access pattern — recency or frequency — is actually winning, without a fixed policy choice baked in ahead of time.

"A trait shared by both replacers"

`Replacer` (`record_access`, `set_evictable`, `evict`, `remove`, `size`) is implemented by both ARC and LRU-K, so the buffer pool manager depends on the trait, not a concrete policy — and the two can be benchmarked against each other on an identical Zipfian access pattern.

"A background thread for disk I/O, not blocking calls"

The disk scheduler owns a dedicated OS thread and an mpsc queue; buffer-pool code enqueues a request and awaits its completion instead of blocking on the read/write syscall directly. This is the seam where request batching or read-ahead would attach later without touching the buffer pool at all.

"RAII page guards instead of manual pin/unpin"

A page guard pins its page on construction and unpins — flushing first if dirty — when it drops. Every code path that can return early (an error, a panic during a test) still releases the pin correctly, because it's not a step anyone has to remember.

03
What's next
B+Tree indexes · query execution · transactions · recovery
"B+Tree with concurrent latch crabbing"

The next layer is the index: a disk-backed B+Tree with search, insert, and delete, then concurrent access via latch crabbing (and later, optimistic latch coupling) so multiple threads can traverse and modify the tree safely at once.

"A Volcano-model executor and a cost-based optimizer"

Each relational operator (scan, filter, join, aggregate) will be its own executor implementing a common `next()` iterator interface — the classic Volcano model — so a query plan is a tree of operators pulled one tuple at a time, the same shape as Postgres's own executor. Above it, a cost-based optimizer picks join order and access paths from table statistics instead of executing whatever order the query happened to be written in.

"Transactions and recovery close the single-node engine"

Lock manager and MVCC-style concurrency control give isolation; write-ahead logging and ARIES-style recovery give atomicity and durability. Together they're what turns a fast storage engine into an actual ACID database — correct under crashes and concurrent writers, not just fast on a single thread.

Engineering depth

sysdes
Volcano — the pull-based execution model
Every operator (scan, filter, join, aggregate) implements the same `next()` interface and pulls one tuple at a time from its child. A query plan is a tree of these iterators; execution is just calling `next()` on the root and letting the pulls cascade down. The same shape as Postgres's own executor, and the reason a new operator only ever has to implement one method to slot into any plan.
sysdes
Cost-based optimization
Given a parsed query, there are usually many valid join orders and access paths that return the same rows — a sequential scan versus an index scan, or joining A⋈B⋈C in three different orders. The optimizer estimates the cost of each candidate plan from table/index statistics and picks the cheapest, rather than executing whatever order the query happened to be written in.
sysdes
ACID as four separable guarantees
Atomicity (a transaction's writes all happen or none do), Consistency (invariants hold before and after), Isolation (concurrent transactions don't see each other's half-finished state), and Durability (a committed write survives a crash) are four different problems with four different mechanisms — a WAL for atomicity and durability, MVCC or locking for isolation. Treating them as one bundled feature is how you end up not understanding why any of them actually hold.
sysdes
Why 8 KB pages
Smaller pages mean more page-table entries and more disk seeks for the same data; larger pages waste I/O bandwidth reading data a query doesn't need and hold more contention under concurrent writes. 8 KB (Postgres's own default) is the standard middle ground, and matters doubly here because it must also line up with the buffer pool's frame size — a page is always exactly one frame.
sysdes
Page vs. frame
A page is 8 KB of logical data, on disk or in memory; a frame is the fixed 8 KB block of memory that holds one page while it's resident. The buffer pool is an array of frames; the page table is what makes "logical page" and "physical frame" two different, mappable things.
sysdes
Why the OS page cache isn't enough
The database knows which pages are hot, which are dirty, and when a page must be durable before a transaction commits — information the OS page cache doesn't have. A database-managed buffer pool can make eviction and flush decisions the OS fundamentally can't.
sysdes
Sequential flooding
A full table scan touches every page exactly once, which under plain LRU looks identical to "every page is hot" — and evicts pages a concurrent, more selective query actually needs. Frequency-aware policies like ARC exist specifically because recency alone is an insufficient signal.
rust
Zero dependencies, on purpose
No crates.io hashing, queueing, or storage library — `std::collections`, `std::sync`, and `std::os::unix::fs::FileExt` do the whole job. The constraint is deliberate: importing `lru` or `crossbeam` would answer the exact question the project exists to ask.
rust
Drop as the concurrency-safety mechanism
Page guards, and later lock guards, lean on `Drop` to make "release this resource" not something a caller can forget — a guarantee a C++ equivalent needs hand-written move constructors and destructors to express, and Rust gets from the ownership model directly.
rust
mpsc channels as the async/await stand-in
The disk scheduler's request/response flow plays the same role Rust `Future`s or C++ promises would, using nothing but `std::sync::mpsc` — a oneshot-style reply channel per request, joined cleanly on shutdown.
dsa
ARC's adaptive target size
The split between the two cache lists isn't fixed — a ghost-list hit on the recency side nudges the target toward recency, and vice versa for frequency. The policy adapts to the actual workload instead of assuming one access pattern up front.
dsa
LRU-K's backward k-distance
Eviction is ranked by the time of the K-th most recent access, not the single most recent one — a page touched once isn't treated as equally hot as a page touched K times, which plain LRU can't distinguish.
dsa
VecDeque + HashMap for O(1) bookkeeping
Both replacers need O(1) access recording and O(1) eviction. A `HashMap` for direct lookup alongside a `VecDeque` (or an ordered structure) for eviction order is the standard pairing for this shape of problem.

Stack

std::collections
HashMap, VecDeque, BTreeMap for replacer + page-table bookkeeping
std::sync
Mutex/RwLock latches, atomic pin counts
std::sync::mpsc
disk scheduler's request/response queue
std::os::unix::fs::FileExt
positioned 8 KB page reads/writes (read_exact_at, write_all_at)
std::thread
the disk scheduler's dedicated background worker
Cargo workspace
one crate, zero external dependencies

Decisions worth discussing

storage
ARC over LRU: a plain recency policy is defenseless against sequential flooding — one full scan can evict every hot page. ARC's ghost lists let the policy shift toward whichever access pattern, recency or frequency, the workload is actually exhibiting.
storage
A page table separate from the frame array: pages and frames are different lifetimes — a page can exist on disk with no frame at all. Keeping page_id → frame_id as its own map is what makes eviction and re-fetch correct instead of coincidentally working.
rust
RAII page guards over manual pin/unpin calls: a pin that isn't released on every exit path — including panics and early returns — is a latent bug that only shows up under load. Tying release to `Drop` removes the failure mode instead of relying on discipline to avoid it.
rust
Zero dependencies as a constraint, not an accident: every data structure this project needs already exists on crates.io. Building each one anyway is the entire point — a shortcut here would be a shortcut around the thing being learned.
systems
A background-thread disk scheduler instead of synchronous reads in the buffer pool: decoupling I/O dispatch from buffer-pool logic is what makes request batching or read-ahead a future addition to one component, not a rewrite of two.