Page Cache — Buffer Pool with LRU

Disk I/O is the bottleneck in any database. A page cache (or buffer pool) keeps frequently accessed pages in memory to avoid redundant disk reads.

How It Works

The buffer pool is a fixed-size pool of page-sized slots:

Buffer Pool (capacity: 4 pages)
+--------+--------+--------+--------+
| Page 3 | Page 7 | Page 1 | Page 5 |
+--------+--------+--------+--------+

When the engine needs a page:

1. Check the buffer pool (cache hit → return immediately)
2. If not found (cache miss) → read from disk
3. If the pool is full → evict a page to make room
4. Store the new page in the freed slot

LRU Eviction Policy

LRU (Least Recently Used) evicts the page that hasn't been accessed for the longest time. The intuition: if you haven't needed a page recently, you probably won't need it soon.

Implementation uses a doubly-linked list + hash map:

Most recent ←→ ... ←→ Least recent
 [Page 3] ←→ [Page 7] ←→ [Page 1] ←→ [Page 5]
                                          ↑
                                    Evict this one

On every access, move the page to the front. On eviction, remove from the back.

Hit/Miss Counting

Track statistics to monitor cache effectiveness:

cache.stats → hits: 450, misses: 50, hit_rate: 90%

A good hit rate is >95%. If it's low, the buffer pool is too small for the workload.

Dirty Page Tracking

A dirty page has been modified in memory but not yet written to disk. The buffer pool must track this:

Page 3: clean (matches disk)
Page 7: DIRTY (modified, needs write-back)

When evicting a dirty page, it must be written to disk first. Evicting a clean page is free.

Buffer Pool in PostgreSQL

PostgreSQL's buffer pool (bufmgr.c) uses a clock sweep algorithm (an approximation of LRU) rather than true LRU. Each buffer has a "usage count" that's incremented on access and decremented during the sweep. Buffers with count 0 are evicted. This is more efficient than maintaining a linked list under high concurrency.

Buffer Pool in SQLite

SQLite's page cache (pcache.c) is simpler — it uses a hash table for lookup and an LRU list for eviction. SQLite also supports a pluggable page cache interface, letting applications provide their own caching strategy.

Eviction Counts

Track how many pages have been evicted. High eviction counts with low hit rates indicate the buffer pool is too small:

CACHE STATS → hits:100,misses:20,evictions:15

Your Task

Build a buffer pool with configurable size, LRU eviction, and statistics tracking (hits, misses, evictions).