Buffer pools and page replacement

Prerequisites: Memory hierarchy, pages, and storage indexes.

Learning objectives

• Distinguish a page identifier from a buffer frame.
• Trace pinning, dirty eviction, and replacement.
• Explain scan pollution and WAL ordering.

A disk-oriented database moves fixed-size pages between storage and a buffer pool in memory. A page identifier names durable content; a frame is a memory slot that currently holds some page. A page table maps identifiers to resident frames. Fetching a resident page is a buffer hit. A miss requires a free frame or eviction, followed by a read. These are logical operations; the operating system and device may add their own caching.

A client pins a frame while using it, preventing replacement from repurposing that memory. A pin is not a transaction lock: it protects residency, not logical isolation. Latches briefly protect in-memory structure changes. Locks or other concurrency mechanisms govern transaction-visible conflicts. Confusing these responsibilities produces either unsafe memory access or unnecessary serialization.

A dirty page differs from its durable copy. Evicting a clean unpinned page can simply discard the cached copy. Evicting a dirty page requires safely writing it first. If the database uses write-ahead logging, the associated log records must reach durable storage before that data page does. Otherwise a crash could preserve a modified page without the information needed to recover it.

Trace a three-frame pool under least-recently-used replacement. Read A,B,C, then A: the recency order is B,C,A from oldest to newest. Reading D evicts B if all frames are unpinned. If B is pinned, the replacement mechanism must choose an eligible alternative or wait according to its policy. If B is dirty, eviction includes a write before D can occupy that frame. A cache-capacity count alone misses this work.

Exact LRU can be expensive under heavy concurrency because each access updates shared ordering metadata. Clock-style policies approximate recency with reference bits and a rotating hand. Replacement quality also depends on workload. A one-pass scan across thousands of pages can evict a small frequently reused working set, a phenomenon called scan pollution. Databases may use separate scan handling, multiple queues, or admission policies to limit that effect.

Dirty-page cleaning in the background can create reusable frames before a foreground request needs them. But aggressive cleaning increases writes and competes for bandwidth. Checkpointing and recovery goals also influence flushing. The useful metrics include hit rate, pinned-frame pressure, dirty-page backlog, eviction stalls, and I/O latency. A high hit rate can coexist with terrible tail latency if the remaining misses wait behind expensive writes.

This model assumes page-oriented storage. Memory-resident engines and direct-I/O configurations alter the surrounding details, but ownership, safe eviction, and durability ordering remain questions to answer explicitly.

Practice problem

With two initially empty frames and exact LRU, process reads A,B,A,C,B, assuming clean unpinned pages. Count hits and misses, and list each eviction. Repeat the moment C is requested with B pinned and A unpinned. Explain why the result changes, and describe what extra correctness condition applies if the chosen victim is dirty in a write-ahead-logged engine.

Worked solution

The first A and B miss; the second A hits, making B the least recent page. C misses and evicts B. The final B misses and evicts A, yielding one hit and four misses. At the C request, a pinned B cannot be evicted even though it is least recent, so the manager must choose unpinned A or follow another permitted waiting policy. If the victim is dirty, its updates must be written safely before reusing its frame, and the WAL describing those updates must be durable before the page write. Pinning alone says nothing about whether another transaction may logically read the record.

Check your understanding

The least-recently-used frame is pinned, while a newer unpinned clean frame is available. What can a correct buffer manager do?

• Treat the pin as proof that the page is durable.
• Evict the pinned frame because LRU overrides pins.
• Abort every transaction reading the unpinned frame.
• Choose the eligible unpinned frame, or follow its waiting policy.

Explanation

Replacement eligibility is a correctness constraint. LRU ranks eligible candidates but cannot repurpose memory still pinned by a client.

A one-pass scan replaces a small frequently reused working set in an LRU buffer pool. What change directly addresses this pattern?

• Flush every clean page to disk before eviction.
• Admit every scanned page as maximally recent forever.
• Use a scan-aware admission or replacement policy.
• Remove the page table so every lookup reads storage.

Explanation

The issue is cache pollution by low-reuse scan pages; scan-aware handling preserves useful resident pages.

Primary reading

• Buffer pools: Carnegie Mellon University
• Write-ahead logging: PostgreSQL Global Development Group

Open the study and save your work →