Buffer Pool Frames, Pin Counts, and Replacement Under Pin Pressure

A storage engine cannot read a page from disk for every tuple access. A single index lookup on a three-level B-tree would issue three reads, and a sequential scan of a million-row table would issue tens of thousands. The buffer pool exists so that the number of physical reads is governed by the working set rather than by the number of logical accesses. It is a cache with a fixed, pre-allocated capacity — every frame is allocated at startup, and the pool never grows — and its correctness depends on more than a replacement policy.

The frame, the tag, and the descriptor

A buffer pool is an array of frames. Each frame is one page-sized region of memory, aligned so that a page can be read into it with a single direct I/O transfer. Frames are paired with descriptors: small structs holding the page identifier currently resident (the tag), a pin count, a dirty flag, and whatever bookkeeping the replacement policy needs.

The mapping runs in both directions. A hash table keyed on the page identifier — a tablespace or file identifier plus a block number, usually packed into a 32-bit or 64-bit value — gives the frame index for a resident page. The descriptor’s tag gives the reverse. On a hit, the hash lookup is the whole cost: a few dozen cycles plus a possible cache miss, against tens of microseconds for a physical read on a spinning disk or a few microseconds on flash. That ratio, roughly three orders of magnitude, is why engines spend real effort on making the hash lookup fast and on keeping the hit rate high, and why a buffer pool smaller than the working set degrades non-linearly: once the hot set no longer fits, every access that would have hit becomes a read.

Pin, latch, and the difference between them

Two independent mechanisms protect a page in a frame, and conflating them is the most common source of confusion about buffer pools.

A pin is a reference count. It says the frame must not be evicted while the count is positive. It says nothing about concurrent modification. A thread that reads a tuple pins the page for the duration of the read and then unpins; several threads may pin the same page simultaneously without conflict.

A latch is a short-duration mutual-exclusion primitive, held only in memory, never logged, never held across a disk write. It protects the page’s internal structure — the directory and free-space pointers of a slotted page, for example. A thread takes a shared latch to read a tuple and an exclusive latch to insert one. Latches are not released on transaction boundaries; they are released as soon as the in-memory operation finishes, which is why they can be implemented as spinlocks or lightweight reader-writer locks rather than as the heavier lock manager used for rows and tables.

The rule that follows is that any code path touching page bytes must hold both a pin and, for the duration of the access, an appropriate latch. A pin without a latch permits a torn read of a page being modified; a latch without a pin permits the frame to be recycled underneath the holder.

/* The pin/unpin contract, with the failure mode made explicit. */
struct buf_desc {
    page_id_t tag;
    int       refcount;   /* pins; frame is evictable only at zero */
    bool      dirty;
    bool      valid;
};

struct buf_desc *buf_pin(page_id_t pid) {
    struct buf_desc *d = hash_lookup(pid);
    if (!d) return NULL;              /* caller must read it in */
    __atomic_add_fetch(&d->refcount, 1, __ATOMIC_ACQUIRE);
    /* After this point the frame cannot be recycled, but its
       contents may still be changing: the caller must latch. */
    return d;
}

void buf_unpin(struct buf_desc *d) {
    __atomic_sub_fetch(&d->refcount, 1, __ATOMIC_RELEASE);
}

The ordering matters: the reference count must be incremented before the caller can safely touch the frame, and the eviction path must observe a zero refcount before it can reuse the frame. Implementations pair the increment with a re-check of the tag under the hash-table lock, because the frame could have been reassigned between the lookup and the increment. This is the same double-checked pattern as a reference-counted object in any concurrent container.

Reading a page in without duplicating work

A miss requires a read, and a read takes long enough that other threads will miss on the same page. If each of them issues its own read, the pool performs redundant I/O and, worse, may end up with two frames claiming the same tag. Engines prevent this with an I/O in progress flag on the descriptor, set atomically by whichever thread wins the race. The winner allocates a frame, marks it, releases the hash-table lock, and reads into the frame. Losers wait on a condition variable attached to that descriptor and, when it is cleared, recheck the hash.

The read itself must not hold the hash-table lock, or every other lookup in the pool blocks for the duration of a disk read. That constraint forces the two-phase structure that appears in every real implementation: look up, miss, reserve a frame under the lock, drop the lock, perform I/O, retake the lock, and publish the tag. Publishing last means a frame is never visible in the hash before its contents are valid, so no reader can observe a half-filled frame.

A subtlety arises with read-ahead. A sequential scan pattern is detectable, and the engine may choose to read the next several blocks into free frames before they are requested. If the pool has no free frames, read-ahead competes with demand paging for capacity; the usual compromise is to read ahead only up to a fraction of the pool and to stop when free frames fall below a reserve.

Replacement: why plain LRU is not enough

Least-recently-used is the textbook policy and the wrong one for databases, for a reason that is structural rather than a matter of tuning. A sequential scan touches every page of a large table exactly once. Under LRU, those pages enter the pool at the most-recently-used end and push out the index pages and hot heap pages that will be needed again. The scan gains nothing — it will not revisit the pages — and the pool loses everything. This is cache pollution by a single query, and it can persist for the length of the scan.

LRU-K generalizes LRU by tracking the time of the k-th most recent reference rather than the most recent. With K=2, a page referenced once has an infinite backward distance and is evicted before any page referenced twice, so a scan’s pages never displace pages with a demonstrated reuse history. The cost is per-page history: the standard implementation keeps a priority queue of the last two reference times per page and a second queue of pages seen only once.

Most engines approximate this rather than implement it exactly, because maintaining timestamps per page costs memory and a heap operation per access. PostgreSQL uses a clock sweep: each descriptor carries a usage count from 0 to 5, incremented on access (up to the cap) and decremented on each pass of the clock hand. A frame with a nonzero count is spared and its count reduced; a frame at zero is a candidate. The hand sweeps repeatedly, so a page that is genuinely hot keeps its count above zero, while a page touched once by a scan falls to zero after one or two sweeps. The scheme costs one saturating increment per hit and no per-page ordering structure.

The consequence worth knowing is that the usage count is capped, so a very hot page cannot accumulate unbounded credit; it merely survives more sweeps. It also means the policy is not strictly LRU and the eviction order depends on where the hand happens to be, which makes buffer pool contents after a given workload not exactly reproducible.

Dirty pages and the write path

A dirty frame must be written before it can be reused. Writing at eviction time is the worst possible policy for latency, because the unlucky thread that needs a frame pays for the write. Engines therefore separate eviction from cleaning: a background writer walks the pool and flushes dirty pages whose usage count is low, so that the frames are clean by the time they are needed. The eviction path then has two cases — clean, reuse immediately; dirty, either write synchronously or, if the policy allows, pick a different victim.

Cleaning cannot run arbitrarily far ahead of the log. A dirty page whose changes are not yet durable in the write-ahead log cannot be written to its final location, because recovery would then see a page newer than the log that describes it. That ordering constraint, and the checkpoint machinery that manages it, is the subject of write-ahead log record ordering. The practical effect on the buffer pool is that cleaning is throttled by log flush progress, so a workload that generates log faster than the disk can absorb it will find itself with a pool full of dirty, unflushable pages.

When every candidate is pinned

The degenerate case is a pool in which all frames have a positive pin count, or all unpinned frames are dirty and cannot yet be written. The pool cannot evict, so a thread needing a frame must wait. If that thread already holds a pin on another page, and the thread holding the frame it needs is waiting on the first, the result is a deadlock in the buffer pool rather than in the lock manager.

Engines mitigate this in three ways. Pins are held for the shortest possible window, and code that must hold several pins acquires them in a fixed order — typically by ascending page identifier, which is also the order that avoids deadlock in the B-tree descent described in page splits and write amplification. The pool reserves a small number of emergency frames that only the eviction path may use. And the pin count is instrumented: a long-held pin is visible in the pool’s statistics and is a real bug, not a tuning problem.

A pool sized well below the working set does not merely miss more; it converts each miss into a wait for a frame, so latency becomes a function of the eviction rate rather than of the I/O device. That is the regime in which the difference between a 4 KiB page and a 16 KiB page matters most: fewer, larger pages mean fewer descriptors and fewer hash lookups, but each miss costs four times the transfer and each page holds four times the unrelated data that must be scanned in memory.