Buffer Pool Management: Clock-Sweep Eviction and Page Pinning

The Problem: RAM Is Small, Disk Is Slow

A database's working set of pages is almost always larger than the RAM you can afford to cache it in. The buffer pool (a.k.a. shared buffers, page cache, buffer cache) is a fixed-size array of in-memory frames, each holding one on-disk page (8 KB in PostgreSQL, configurable in others). A parallel array of buffer descriptors — one ~64-byte struct per frame — records each frame's identity (a tag: table + block number), state flags (valid, dirty, I/O-in-progress), and the two counters that drive everything here: usage_count and refcount (the pin count).

When a query needs a page, the manager hashes the tag into a lookup table. On a hit it returns the frame; on a miss it must find a victim frame to reuse — and if that victim is dirty, flush it to disk first. The central question is which frame to evict. The theoretically optimal choice (Belady's MIN: evict the page used furthest in the future) is unknowable online, so real systems approximate least-recently-used. Doing that approximation cheaply, and never evicting a page someone is mid-read on, is exactly what clock-sweep and pinning solve.

How Clock-Sweep Works, Step by Step

Imagine the frames laid out on a clock face. A single clock hand (nextVictimBuffer in PostgreSQL) points at the next candidate. Each access bumps that frame's usage_count up by 1, saturating at a cap (BM_MAX_USAGE_COUNT = 5 in PostgreSQL). The count is a multi-bit generalization of Corbató's single reference bit — it lets genuinely hot pages survive several full revolutions.

To find a victim, the hand advances one frame at a time:

function ClockSweep():
  loop:
    d = descriptor[hand]
    hand = (hand + 1) mod N        # advance, wrapping
    if d.refcount > 0:            # pinned — skip entirely
       continue
    if d.usage_count > 0:
       d.usage_count -= 1          # give a "second chance"
       continue
    return d                       # unpinned AND count==0 -> evict

Two invariants make this correct. First, a pinned frame is never chosen — it is skipped without touching its count. Second, every pass either decrements a count or evicts, so the hand cannot loop forever: after at most BM_MAX_USAGE_COUNT + 1 revolutions some unpinned frame must hit 0. The chosen frame is then unlinked, flushed if dirty, and its descriptor re-tagged with the new page.

Complexity and a Worked Trace

Time: each hand step is O(1). A single eviction is amortized O(1) because every decrement it performs was "paid for" by an earlier access that incremented the count; the worst-case sweep to find one victim is O(n) frames (bounded by roughly (BM_MAX_USAGE_COUNT+1)·N steps). Space: O(1) per frame — just the two small counters plus flags, versus strict LRU's two list pointers and a write to those pointers on every cache hit. That write-on-hit is the hidden cost clock-sweep eliminates.

Trace, 4 frames, hand at A. Usage counts A=2, B=0(pinned), C=1, D=0; we need a victim:

hand@A: refcount 0, count 2  -> count=1, advance
hand@B: refcount 1 (PINNED) -> skip, advance
hand@C: refcount 0, count 1  -> count=0, advance
hand@D: refcount 0, count 0  -> EVICT D, hand now @A

D is evicted after visiting 4 frames. Note B was never a candidate — pinning shields it. If the next request touches A again, A's count rises back toward 5, so a hot page can outlast several sweeps while cold one-shot pages like D fall out quickly.

Where It's Used in Real Systems

PostgreSQL is the canonical example: its freelist.c implements clock-sweep with an atomic nextVictimBuffer so multiple backends can tick the hand without a global lock (a 2015–2016 concurrency overhaul moved refcount, usage_count, and flags into a single atomic word). Every backend that touches a page calls PinBuffer/UnpinBuffer, which increment/decrement refcount.

• Operating systems: the clock/second-chance algorithm is the classic virtual-memory page-replacement policy in Unix-family kernels, using the MMU's hardware referenced bit as the reference bit and the dirty bit to decide write-back.
• Other databases: IBM DB2, Oracle, and many storage engines use clock or clock-variant policies; MySQL's InnoDB instead runs a midpoint-insertion LRU list, a related approximate-LRU tuned for scan resistance.
• Beyond DBs: the same reference-bit-plus-hand idea appears in language runtime object caches and CPU/TLB pseudo-LRU replacement, where true LRU is too expensive in hardware.

Pinning generalizes too: any system that does zero-copy I/O into a shared cache — kernels doing DMA into page-cache buffers, for instance — must pin so the buffer isn't reclaimed mid-transfer.

Clock-Sweep vs. the Alternatives

vs. strict LRU: LRU gives the exact recency ordering but must move a node to the list head on every hit — a write to shared, lock-protected pointers that becomes a contention bottleneck under many concurrent readers. Clock-sweep only writes metadata during the (comparatively rare) eviction sweep, so hits are nearly read-only. The tradeoff: clock-sweep's ordering is approximate, and it can occasionally evict a page a true LRU would have kept.

vs. plain second-chance (1-bit): a single reference bit can only distinguish "touched since last sweep" from "not." A multi-bit usage_count (0–5) encodes frequency, letting a page touched 5 times survive far longer than one touched once — closer to LFU flavor.

vs. ARC / LRU-K / 2Q: these are strictly smarter under mixed workloads because they keep ghost history to tell one-shot sequential scans apart from genuinely reused pages, so a big table scan won't flush your hot working set. Clock-sweep is only weakly scan-resistant; PostgreSQL patches this with a separate ring buffer (BAS_BULKREAD) for large scans so they don't pollute the main pool. The cost of ARC-class policies is more metadata and licensing/complexity — ARC was famously patent-encumbered.

Pitfalls, Failure Modes, and Significance

Correlated-reference / scan pollution: a single large sequential scan touches millions of pages once each, inflating their counts and evicting the true hot set — the classic reason to use a ring buffer for bulk reads.

Pin leaks / pin exhaustion: pinning is a manual balance-the-books protocol. Forget an UnpinBuffer and that frame is permanently ineligible for eviction; leak enough and the pool shrinks until the clock hand can find no unpinned victim and the sweep spins — a genuine liveness bug. Correct code pins for the shortest possible window and unpins in an error-cleanup path.

• Cap too small: a tiny usage_count ceiling makes the policy behave like FIFO (little frequency memory); too large and a hot page can take up to cap+1 full revolutions to age out, slowing victim search. PostgreSQL's cap of 5 is admittedly a heuristic ("wild-ass guess," per the source comments).
• Dirty-victim stalls: if the victim is dirty, the requester may block on a write-back; background writers exist precisely to keep clean, low-count victims available ahead of demand.

Significance: clock-sweep is the workhorse compromise of caching — it captures most of LRU's benefit at a fraction of the per-hit cost and with trivial metadata, which is why a 1969 algorithm still runs inside the database serving this page.

Buffer replacement policies: cost, scan resistance, and metadata

Policy	Eviction cost	Extra metadata per frame	Scan resistance
Strict LRU (linked list)	O(1) but a pointer update on every hit	2 list pointers + hash node	Poor — one big scan flushes the pool
FIFO	O(1)	None (single queue pointer)	Poor — ignores access frequency
Clock / second-chance	Amortized O(1), O(n) sweep worst case	1 reference bit	Weak
Clock-sweep (usage_count 0..5)	Amortized O(1), up to 6 cycles worst case	usage_count + refcount (pin)	Moderate — hot pages accrue count
LRU-K / ARC / 2Q	O(1) amortized	History queues, timestamps	Strong — separates one-shot from reused