Buffer Management

A buffer pool is a region of main memory divided into fixed-size slots called frames, each large enough to hold exactly one disk block (page). The buffer manager maintains a page table — a hash map from page identifiers to frame numbers — so that any component needing a page can ask "is it already in memory?" in expected O(1) time rather than issuing a disk read on every access. Every frame carries two pieces of metadata beyond the raw bytes. The pin count (sometimes called the reference count) records how many active callers currently hold a reference to that frame; a frame with pin count zero is a candidate for eviction, while a pinned frame must never be evicted or overwritten, because doing so would corrupt data underneath a live pointer. The dirty bit records whether the page's contents have been modified since it was loaded from disk; a dirty page must be flushed to disk before its frame can be reused for a different page, or the modification is lost. When a component (the query executor, the index manager, the recovery manager) needs a page, it calls a single operation, conventionally named `pin(page_id)` or `fix(page_id)`. If the page is already resident, the buffer manager increments its pin count and returns the frame. If not, the buffer manager must find a victim frame — an unpinned frame, chosen according to a replacement policy — evict whatever page currently sits there (writing it out first if dirty), read the requested page from disk into that frame, and return it, pinned. When the caller is done, it calls `unpin(page_id, dirty)`, decrementing the pin count and marking the page dirty if it was modified. The replacement policy — LRU, Clock, MRU, or others — is the decision procedure invoked only at the moment a victim is needed and no free frame exists.

The buffer manager exposes a small, disciplined interface, and every other subsystem is expected to use it religiously rather than touching disk directly. ``` structure Frame: page_id data[PAGE_SIZE] pin_count // integer, starts at 0 dirty // boolean, starts at false // policy-specific metadata: last_used_time (LRU), // reference_bit (Clock), etc. structure BufferPool: frames[0 .. N-1] page_table: map from page_id -> frame_index // O(1) average lookup function PIN(page_id): if page_id in page_table: f = page_table[page_id] frames[f].pin_count += 1 NOTIFY_POLICY_ACCESS(f) // update LRU stamp / Clock ref bit return frames[f] // page not resident: need a frame f = FIND_FREE_FRAME() if f is None: f = SELECT_VICTIM() // replacement policy if f is None: error "buffer pool full: no unpinned frame available" if frames[f].dirty: WRITE_TO_DISK(frames[f].page_id, frames[f].data) page_table.remove(frames[f].page_id) READ_FROM_DISK(page_id, frames[f].data) frames[f].page_id = page_id frames[f].pin_count = 1 frames[f].dirty = false page_table[page_id] = f NOTIFY_POLICY_LOAD(f) return frames[f] function UNPIN(page_id, was_modified): f = page_table[page_id] frames[f].pin_count -= 1 if was_modified: frames[f].dirty = true function FLUSH(page_id): f = page_table[page_id] if frames[f].dirty: WRITE_TO_DISK(page_id, frames[f].data) frames[f].dirty = false ``` `SELECT_VICTIM` is where the replacement policy lives. Three classic strategies:

LRU (Least Recently Used). Maintain frames in an ordering by last access time — typically an intrusive doubly linked list plus a hash map, so both "move to most-recently-used end" and "remove least-recently-used unpinned frame" run in O(1). On every `PIN` hit or load, move the frame to the head. To select a victim, scan from the tail toward the head until an unpinned frame is found. ``` function SELECT_VICTIM_LRU(): node = list.tail while node is not None: if node.pin_count == 0: list.remove(node) return node.frame_index node = node.prev return None // all frames pinned ```

Clock (Second-Chance). An approximation of LRU that avoids the overhead of maintaining an exact recency list. Frames are arranged conceptually in a circle with a single moving "hand" pointer. Each frame has one reference bit. On access, set the reference bit to 1. To find a victim, the hand advances; if it finds a frame with reference bit 0, that frame is evicted; if it finds reference bit 1, it clears the bit to 0 (giving the page a "second chance") and moves on. ``` function SELECT_VICTIM_CLOCK(): loop forever: f = frames[hand] if f.pin_count > 0: hand = (hand + 1) mod N continue if f.reference_bit == 1: f.reference_bit = 0 hand = (hand + 1) mod N else: hand = (hand + 1) mod N return f.index ```

MRU (Most Recently Used). Evicts the most recently used unpinned frame instead of the least. This sounds perverse until you consider repeated full scans: in a block nested-loop join, the inner relation is scanned repeatedly in the same order, and the page just used is the one least likely to be needed again soon (the scan has moved past it and won't return until it wraps around), while pages used long ago are about to be needed next. MRU is implemented with the same linked-list machinery as LRU, just selecting from the opposite end.

Time complexity of the core operations. With a hash-based page table, checking whether a page is resident and locating its frame is O(1) expected time. Updating recency information is O(1) for both LRU (splice a node to the head of a doubly linked list) and Clock (flip a bit). Victim selection differs:

• LRU: O(1) amortized in the common textbook implementation, because the tail of the list is examined and, once an unpinned frame is found, it is removed directly. In the worst case, if many frames near the tail are pinned, the scan can take O(k) where k is the number of consecutive pinned frames encountered — bounded by O(N) in the pathological case where nearly the whole pool is pinned.
• Clock: O(1) amortized. Each frame's reference bit is cleared at most once per full sweep of the hand before being considered for eviction, so the total work across a sequence of evictions is linear in the number of frame visits, and in practice the hand rarely sweeps the whole pool. Worst case is O(N) per eviction if all bits are set (a full sweep clearing everything), matching LRU's worst case but with lower constant-factor overhead since no list-splicing is needed on every hit.
• MRU: identical asymptotic profile to LRU; only the end of the list examined differs.

Space overhead. The buffer pool itself uses N × PAGE_SIZE bytes for data, plus O(N) additional words for pin counts, dirty bits, and policy metadata (list pointers or reference bits), plus O(N) for the page table entries. This metadata overhead is negligible relative to page size (typically 4–16 KB per page versus a handful of bytes of metadata).

Correctness invariants. The buffer manager must maintain three invariants at all times: 1. No frame is evicted while pinned. This is enforced structurally: `SELECT_VICTIM` only ever considers frames with pin count exactly zero. Since pin count is only decremented by `UNPIN`, and every `PIN` is matched by an eventual `UNPIN` in correct client code, a frame in active use (pin count ≥ 1) can never be chosen, so no live pointer into buffer pool memory is ever invalidated by eviction. 2. No modification is lost. Whenever a dirty frame is chosen as a victim, its contents are written to disk before the frame is repurposed. This is the WAL-adjacent guarantee: buffer management does not itself guarantee durability against crashes (that is the job of write-ahead logging and the recovery manager), but it guarantees that within a running system, a modification recorded via `UNPIN(..., dirty=true)` is never silently discarded before being persisted. 3. The page table is a bijection between resident pages and frames. At most one frame maps to a given page_id, and the table is updated atomically with eviction/load, so a lookup never returns a stale or half-loaded frame. This is what makes repeated `PIN` calls for the same page cheap and consistent.

Honesty about tradeoffs. LRU requires touching a shared data structure (the linked list) on every single page access, which under high concurrency becomes a serialization bottleneck — every thread pinning a page must take a lock to splice the list. Clock avoids this: setting a reference bit can be done with a relaxed atomic write, and the sweeping hand only needs coordination at eviction time, which is far rarer than access time. This is precisely why most production database buffer managers (PostgreSQL among them) use Clock or Clock-variants rather than exact LRU, despite LRU's cleaner textbook guarantees — the constant-factor concurrency cost dominates in practice. MRU, meanwhile, is not a general-purpose improvement; it is a specialist tool that only helps under specific repeated-scan access patterns and can be worse than LRU otherwise, since it deliberately discards the page most likely to be reused under typical locality assumptions.

Why not just use the OS page cache / virtual memory? A DBMS could, in principle, memory-map its files and let the operating system's paging mechanism evict pages under memory pressure. This is rejected for two reasons that are worth stating precisely. First, the OS replacement policy (commonly a global LRU-like or clock approximation over all processes' pages) has no notion of pin counts or transaction semantics — it can evict a page the DBMS is mid-transaction with, or write a dirty page to disk at a moment that violates the write-ahead-logging rule ("the log record for a change must reach disk before the changed data page does"). Second, the DBMS has application-specific knowledge (e.g., "this page belongs to a sequential scan and won't be revisited soon") that a general OS cannot exploit. Buffer management is therefore implemented entirely in DBMS user space, precisely to retain this fine-grained control.

Consider a buffer pool with N = 3 frames, initially empty, and the request sequence below (each request is a page pin immediately followed by an unpin; "d" marks that the page was modified before unpinning). We trace both LRU and MRU to show how they diverge. Request sequence: `P1, P2, P3, P4(d), P1, P5, P1`

LRU trace:

LRU total: 6 disk reads, 1 hit, 1 dirty flush (when P4 is eventually evicted later, not shown here).

MRU trace, same sequence:

MRU total: 5 disk reads, 2 hits. The interesting contrast is at step 4→5: LRU evicts P1 (the true least-recently-used page at that instant) and immediately pays for it at step 5 when P1 is re-requested — a textbook instance of thrashing under a workload where an "old" page is about to be reused. MRU happened to keep P1 around because it was not the most recently touched, producing a hit. This does not mean MRU is "better" in general — it means the outcome is workload-dependent, which is exactly the point: no single fixed policy dominates on every access pattern, and this is the concrete evidence for that claim rather than an assertion of it.

Sequential flooding illustration. Suppose instead the workload is a full table scan reading pages `P1, P2, P3, P4, P5, P6, ...` once each, interleaved with an index lookup that repeatedly touches a small "hot" page `H`. With a pool of size 3 under LRU: ``` H, P1, P2, P3, H, P4, P5, P6, H, ... ``` Every time the scan brings in three fresh pages, `H` — despite being genuinely hot — gets pushed to the LRU end and evicted, because the scan's one-time-use pages keep looking "more recent" than H by the time H is needed again if the pool is small relative to the scan length. This is sequential flooding: a large one-pass scan flushes genuinely reusable pages out of a small buffer pool. It is the standard justification for giving the buffer manager scan-aware hints (e.g., PostgreSQL's ring buffers for large sequential scans, or MRU-style buffers for such scans) rather than relying on pure LRU everywhere.

Buffer management as a discipline grew out of early virtual memory and paging research, then was specialized and hardened by the database systems community once it became clear that generic OS paging policies were unsuited to transactional correctness requirements.

history 1968 — Denning formalizes the working-set model, explaining thrashing as a mismatch between allocated frames and a program's locality. 1970s — Relational database prototypes (System R, Ingres) build dedicated buffer managers distinct from OS virtual memory, asserting explicit control over page residency. 1976 — The ARIES-precursor line of work on write-ahead logging begins clarifying why buffer eviction timing must be coordinated with log flushing. 1992 — The ARIES recovery algorithm (Mohan et al.) formalizes the precise contract between the buffer manager's dirty-page flushing and crash recovery correctness. 2000s–present — Production engines (PostgreSQL's Clock-sweep buffer replacement, InnoDB's midpoint-insertion LRU) refine replacement policies for concurrency and scan-resistance at scale.

Every relational database engine — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server, SQLite — implements a buffer pool as one of its earliest-loaded, most performance-critical subsystems; PostgreSQL calls it `shared_buffers` and uses a Clock-sweep variant, while InnoDB uses a midpoint-insertion LRU list specifically designed to resist sequential-scan flooding by inserting newly read pages partway into the list rather than at the very head. Buffer management also underlies key-value stores and search engines (e.g., page caches inside storage engines like RocksDB and WiredTiger), any system built on B-tree or LSM-tree storage, and the buffer pool's behavior is a first-class input to query optimizers: an optimizer estimating the cost of a join or scan must account for how many of the needed pages are likely to already be buffer-resident, which is exactly the concern that motivates the next layer of reasoning in Index Selection — choosing access paths partly based on how well they interact with buffer pool locality. Understanding pin counts and dirty bits is also prerequisite to understanding write-ahead logging and crash recovery, since the recovery manager's correctness guarantees are literally statements about the order in which the buffer manager is allowed to flush dirty pages relative to log records.

Ask the tutor: How would you redesign the buffer pool's replacement policy to automatically detect and resist sequential flooding without hurting normal random-access workloads?