The page cache — RAM is 1000x faster than disk — Build a B-tree storage engine (SQLite-style)

Build a B-tree storage engine (SQLite-style) (11 scenes)

Scene 07 · The page cache — RAM is 1000x faster than disk

The pager caches pages in RAM with LRU; you're fast iff the working set fits, slow the moment it doesn't.

Previously

Every B-tree descent we drew assumed each page touch hit the disk. In reality the pager keeps recent pages in RAM — and that one fact rewrites the cost model for everything we've built so far.

Scene 07

The page cache — RAM is 1000x faster than disk

Watch

Diagram

Top: a fixed-size grid of CACHE SLOTS (RAM), reordered left = MRU, right = LRU. Bottom: the DB file as a horizontal strip of pages on disk. A read first checks the cache: HIT lights green and the latency meter reads in microseconds; MISS lights red, an arrow drops to the disk strip to fetch the page, the LRU slot is evicted, and the latency meter jumps to milliseconds.

Sources

We run the same 3-page B-tree descent twice. First run: cold cache → 3 misses → ~30 ms total. Second run: same path → 3 hits → ~3 µs total.

Implementation

Pager.read_page(page_no)

the only routine the B-tree ever uses to touch a page

1def read_page(page_no):
2    if page_no in cache:
3        page = cache[page_no]            # HIT: ~1 us, RAM
4        touch_lru(page_no)               # mark as MRU
5        return page
6    # MISS: page is not resident
7    if len(cache) >= cache_size:
8        evict_lru(cache)                 # make room
9    page = disk_read(page_no)            # ~10 ms, syscall
10    cache[page_no] = page
11    touch_lru(page_no)
12    return page

evict_lru(cache)

drop the least-recently-used page to make room

1def evict_lru(cache):
2    victim = pick_least_recently_used(cache)
3    del cache[victim.page_no]
4    return victim

PreviousIndexes — a second B-tree NextWAL — durability without rewriting the file every commit