Buffer Replacement: LRU, Clock and Scan Resistance
When every frame is full, one page has to go. Least-recently-used is the obvious answer and it fails twice: its exact list costs a lock on every hit, and one sequential scan through a large table evicts the entire working set. Clock approximates LRU with a bit per frame; ring buffers, midpoint insertion and LRU-K keep a scan from flooding the pool.
Why this exists
The mechanism as the answer to a problem — read this before the name.
- Problem
The pool has 6 frames and all hold pages; a seventh page is requested. Which frame should be reused — knowing that the page in it may be wanted again in a microsecond or never?
↓ - Naive solution
Evict the least recently used page: keep an exact list ordered by last access, move a frame to the head on every hit, evict from the tail. If a page has not been used for a while, it is the least likely to be used next.
↓ - Why it breaks
Two ways. Every hit — thousands per millisecond, from many backends — must unlink and relink a list node under a lock, so the hot path serialises on the list. And a sequential scan touches every page once, each one "most recently used" for an instant: with more pages than frames the scan marches the whole working set out of the pool, replacing it with pages that will never be read again.
↓ - Better idea
Approximate recency with one bit per frame instead of a list position, and give pages that were touched once — by a scan — less protection than pages that keep being touched.
↓ - Internal mechanism
Clock (second chance): frames in a circle, a reference bit set on each hit, a hand that sweeps clearing bits and evicts the first frame whose bit is already clear. Scan resistance on top: confine a scan to a small ring of frames (PostgreSQL), or insert new pages at a midpoint and promote only on a second access after a delay (InnoDB), or track the last K accesses (LRU-K).
↓ - Trade-offs
Clock is a coarser signal than LRU — it cannot tell "used once a second ago" from "used a hundred times a second ago" without a usage counter. Scan rings mean a scan that would have fit in the pool no longer warms it. Every policy has a workload that defeats it; the engine chooses the one whose failure mode is rarest.
↓ - Real database
PostgreSQL: clock-sweep with a usage count (0–5) and 256 KB ring buffers for large sequential scans. InnoDB: LRU with a 3/8 old sublist and a 1-second promotion delay. Most LSM engines: LRU or Clock over blocks with a separate high-priority region for index and filter blocks.
Choose your depth
The same mechanism at four altitudes. Start where you are; come back deeper.
A full cache has to throw something away to make room, and the only information it has is the past. "Throw away what was used longest ago" is the natural rule, and for most workloads it is close to the best possible.
The rule breaks when a workload reads a huge amount of data once — a full-table scan. Every page it reads is briefly the newest thing in the cache, so the scan pushes out the genuinely hot pages and replaces them with pages nobody will ask for again. Databases fix this by treating "read once" and "read repeatedly" differently.
The decision and the information available
The optimal policy is known and unreachable: evict the page whose next use is furthest in the future (Belady's OPT). No engine knows the future, so every real policy predicts it from the past. Recency (LRU) assumes a page used recently will be used again soon; frequency (LFU) assumes a page used often will keep being used; both are usually right, and each has a workload that makes it wrong. The pool also has constraints the textbook cache does not: a pinned frame cannot be evicted at all, and a dirty frame costs a write before it can be reused, so among equal candidates the clean one is cheaper.
The scale matters for the design. A pool of 4 million frames (32 GB at 8 KB) with a hundred backends each requesting thousands of pages per second cannot afford a policy that takes a global lock per hit. The policy must make its decision with a few bits per frame, updated without coordination, and choose a victim in amortised O(1).
LRU: the exact list and what it costs
Exact LRU keeps every frame in a doubly linked list ordered by last access, plus the page table to find a frame's list node. Hit: unlink the node and relink it at the head. Miss: evict the tail node. The list is the LRU Cache data structure and it is O(1) per operation — but every hit mutates the list, and the list is shared. With 64 backends hitting the root page of the same index, all 64 are moving the same node to the head under the same lock. Recency is being tracked with far more precision than the eviction decision needs.
The second cost is the one that matters more: LRU has no memory beyond "last access". A page read once by a scan a microsecond ago ranks above a page read a thousand times that was last touched two microseconds ago.
before hit on p7: head → p12 → p3 → p7 → p19 → p20 → p21 → tail
↑ unlink, relink at head (under lock)
after hit on p7: head → p7 → p12 → p3 → p19 → p20 → p21 → tail
↑ next victimSequential flooding
A workload has a hot set of three pages {3, 7, 12} in a 6-frame pool: every request is a hit. Then a reporting query runs SELECT count(*) FROM events, a 24-page table. Under LRU the scan's pages arrive one per request, each briefly the most recent. By page 6 of the scan the hot set is at the tail; by page 9 it is gone; at the end of the scan the pool holds pages 19–24, which will never be read again. The hot set then costs three misses to rebuild — trivial at 24 pages, and catastrophic at 5 million, where "rebuilding the working set" takes minutes of elevated latency for every query in the system.
Plain Clock does only slightly better: the hot pages have their reference bits set, so they survive the first sweep of the hand, but a scan longer than the pool sweeps more than once. The fix is not a smarter recency estimate; it is recognising that a scan's pages are read exactly once and should never displace pages that have been read twice.
request: 3 7 12 | 1 2 3 4 5 6 7 8 9 10 11 12 …
pool: [3] [3] [3] [3] [3] [3] [3] [3] [3] [3] [3] [3] [10][10][10]
[7] [7] [7] [7] [7] [7] [7] [7] [7] [7] [7] [7] [11][11]
[12][12][12][12][12][12][12][12][12][12][12][12][12]
[1] [1] [1] [1] [1] [1] [1] [8] [8] [8] [8] [8]
[2] [2] [2] [2] [2] [2] [2] [9] [9] [9] [9]
[4] [4] [4] [4] [4] [4] [4] [4] [4]
hit? m m m m m H m m m H m m m m H
↑ 3, 7, 12 still hit while resident … then evicted by 5, 6, 8, 9Clock: second chance with one bit
Arrange the frames in a circle. Each frame has a reference bit, set to 1 whenever the page is hit — a single store, no lock, no list. A hand points at a frame. On a miss, look at the frame under the hand: if it is pinned, skip it; if its bit is 1, clear the bit and advance ("second chance"); if its bit is 0, it is the victim. The hand keeps its position between misses, so a full sweep of N frames costs N bit inspections spread over many misses.
A page that is hit at least once per sweep never gets evicted; a page not hit since the hand last passed is evicted on the next pass. That is LRU with recency quantised to "since the last sweep" — and it turns out to be nearly as good for the hit rate, at a fraction of the cost. Engines often replace the bit with a small counter (PostgreSQL: 0–5, incremented on hit, decremented by the hand) so that a page hit a hundred times survives more sweeps than one hit once, which is a step toward frequency without the bookkeeping of LFU.
1function victim(frames, hand):2 loop:3 f = frames[hand]4 hand = (hand + 1) mod N5 if f.pin > 0: continue # in use: cannot evict6 if f.ref == 1: f.ref = 0; continue # second chance7 return f # ref == 0 and unpinned: evict8 9on hit(f): f.ref = 1 # one store, no lock10on load(f): f.ref = 1 (or 0 for a bulk scan so it is the first to go)Refinements: LRU-K, 2Q and midpoint insertion
The insight behind every scan-resistant policy is the same: a page accessed once is a worse bet than a page accessed twice, however recent the single access. LRU-K records the timestamps of the last K accesses and ranks by the K-th most recent; with K = 2, a page seen once has no second timestamp and is always the first victim. 2Q approximates LRU-2 with two queues: new pages enter a small FIFO probation queue; only a second access while on probation moves them into the main LRU. Midpoint insertion (InnoDB) is 2Q inside one list: new pages enter at the 5/8 mark, and only a later access promotes them to the young head. Ring buffers (PostgreSQL) attack the problem from the other side: the scan itself is told to reuse a tiny private set of frames, so its pages never compete with the main pool at all.
| Policy | Per-hit cost | Victim cost | Scan resistance | Used by |
|---|---|---|---|---|
| Exact LRU | List relink under lock — high | O(1) | None: floods | Textbooks, small caches |
| Clock (second chance) | Set one bit — negligible | Amortised O(1) | Weak: survives one sweep | PostgreSQL (with usage count), many OSes |
| Clock + scan ring | Same as Clock | Same | Strong: scan confined to 32 frames | PostgreSQL seq scans, VACUUM, COPY |
| LRU-K (K = 2) | Two timestamps | Priority queue or scan | Strong: once-only pages lose | Research, some caches |
| 2Q / midpoint LRU | List relink, but only on promotion | O(1) | Strong: probation before young | InnoDB (3/8 old, 1 s delay) |
PostgreSQL: clock-sweep and ring buffers
Every shared buffer has a usage count from 0 to 5. A hit increments it (saturating at 5); the clock hand, run by any backend that needs a victim, decrements the count of each buffer it passes and takes the first one at 0 with no pins. Five is deliberately low: a hot page can survive at most five sweeps without a hit, so a pool cannot fill with pages that were hot an hour ago.
Sequential scans of tables larger than a quarter of shared_buffers, VACUUM, and bulk writes (COPY, CREATE TABLE AS) use a buffer access strategy: a ring of 256 KB (32 buffers) for scans, 256 KB for VACUUM, 16 MB for bulk writes. The scan allocates buffers only from its ring and reuses them as it advances, so a 40 GB scan touches 32 frames of the pool. Pages in the ring are loaded with usage count 0, and if another backend hits one — it was genuinely hot — the ring simply moves on without it. The practical consequence: a large scan does not warm the pool either, which surprises people who run SELECT count(*) to "preload" a table.
InnoDB: the old sublist
InnoDB keeps one LRU list per buffer pool instance, split at a midpoint: the young sublist (default 5/8) at the head and the old sublist (3/8, innodb_old_blocks_pct = 37) at the tail. A page read from disk is inserted at the head of the *old* sublist. It moves to the young head only when it is accessed again — and only if that access comes at least innodb_old_blocks_time milliseconds (default 1000) after the first. A table scan reads each page once; a read-ahead brings in neighbours that may never be touched; both churn through the old 3/8 and are evicted from its tail without ever reaching the young sublist, where the working set lives.
SHOW ENGINE INNODB STATUS reports young-making rate and not young counts; a high not-young rate during a scan is the policy working. Because the pool holds the clustered index itself, protecting the young sublist is protecting the table's hot rows and the upper levels of every index at once.
Key points
- Eviction predicts the future from the past; LRU and Clock both use recency, and both are defeated by a workload that reads everything once.
- Exact LRU costs a locked list relink on every hit; Clock replaces it with a reference bit and a sweeping hand at almost no per-hit cost.
- Sequential flooding: one scan larger than the pool evicts the whole working set under LRU or plain Clock, and the system pays for minutes afterward.
- Scan resistance comes from treating once-read pages differently: ring buffers (PostgreSQL), midpoint insertion (InnoDB), LRU-K and 2Q.
- A consequence: large scans in PostgreSQL do not warm the pool, and a page must be read twice, a second apart, to become "young" in InnoDB.
LRU vs Clock replacement
When to use — and when not
- Clock or a usage-count variant fits any high-concurrency pool where hits vastly outnumber misses and a global lock per hit would serialise backends.
- Scan rings or midpoint insertion fit whenever bulk reads coexist with an OLTP working set — which is every production database with reporting queries.
- Exact LRU fits when the cache is small, single-threaded and the workload has no scans — an application-side cache, not a database buffer pool.
- A scan ring fits poorly when you actually want the scan to warm the pool (a deliberately preloaded table after failover): use
pg_prewarmor read via an index instead.
Failure modes
- A nightly report scans the largest table and every dashboard is slow until 9 am: sequential flooding on an engine or version without ring buffers, or a scan that used an index and thus bypassed the ring.
- Expecting
SELECT count(*)to warm the cache in PostgreSQL; the ring buffer ensures it does not. - Every buffer at usage count 5 under a uniformly hot workload, so each miss sweeps the whole pool several times before finding a victim.
- Application-side LRU caches with the same flooding problem in front of the database, so the flood hits two layers.
Where you meet this
Back up to the practical layer, and across to the rest of Engineer Atlas.
- DSALRU cache (hash map + doubly linked list) → Buffer replacementThe interview data structure is the naive policy; the engine's policy is what remains after you remove the list.
- DSALFU cache → Usage-count clock sweep
- Operating SystemsPage replacement (second chance, aging) → Clock in the buffer pool