Compare the eviction policies a database page cache can use - plain LRU, clock-sweep (second-chance), and midpoint-insertion LRU. What problem does each later variant solve?

middlemust knowfreq 55%

answer

LRU: accurate, but list latch on every hit
clock hand: skip pinned, decrement, evict at zero
usage counter capped -> a little frequency, not pure recency
midpoint = admission control, not replacement
promote only on a second, *later* touch

basics

~20 s

Plain LRU is accurate but needs a global list updated on every hit, which contends. Clock-sweep approximates it with a usage counter and a rotating pointer, so hits are lock-free. Midpoint insertion admits new pages into the middle of the list so a scan cannot flush the hot end.

solid answer

~50 s

All three try to keep the pages most likely to be reused. Plain LRU orders frames by last access and evicts the tail. It is a good predictor but every hit must move an entry to the head of a shared list - a hot latch on a busy multi-core server, which is why almost no production engine uses it verbatim.

Clock-sweep (second chance) approximates LRU cheaply: each frame has a small usage counter, a hit just increments it, and a pointer rotates through the frames. On each visit it decrements the counter; a frame found at zero and unpinned becomes the victim. A hit is a single non-blocking increment, and only eviction walks the structure.

Midpoint insertion attacks a different problem - admission. A newly read page enters at the middle of the list and is promoted to the hot end only if it is touched again after some delay. A large sequential scan therefore churns the cold half and never displaces the working set.

All three try to keep the pages most likely to be reused. **Plain LRU** orders frames by last access and evicts the tail. It is a good predictor but every *hit* must move an entry to the head of a shared list - a hot latch on a busy multi-core server, which is why almost no production engine uses it verbatim. **Clock-sweep** (second chance) approximates LRU cheaply: each frame has a small usage counter, a hit just increments it, and a pointer rotates through the frames. On each visit it decrements the counter; a frame found at zero and unpinned becomes the victim. A hit is a single non-blocking increment, and only eviction walks the structure. **Midpoint insertion** attacks a different problem - admission. A newly read page enters at the *middle* of the list and is promoted to the hot end only if it is touched again after some delay. A large sequential scan therefore churns the cold half and never displaces the working set.

code

text · 13 lines

text

loop:
  frame = frames[hand]
  hand = (hand + 1) % nframes
  if frame.pin_count > 0:
      continue
  if frame.usage_count > 0:
      frame.usage_count -= 1
      continue
  # unpinned and cold -> victim
  if frame.dirty:
      flush_log_up_to(frame.page_lsn)
      write(frame)
  return frame

go deeper

for a junior

Know that the pool must evict something, that recency is the usual heuristic, and roughly what LRU means.

for a middle

Explain all three, and crucially why plain LRU is replaced: contention on the hot path, and vulnerability to scans.

for a senior

Tie the policy to observed symptoms - eviction rate, sweep passes per allocation, working set displaced after a batch job - and to the knobs the engine exposes.

for a principal

Reason about the design space: recency versus frequency, admission control, per-workload isolation (ring buffers, scan hints), and why exactness is traded for scalability on many-core hardware.

The problem

The buffer pool is smaller than the data. Every miss forces a choice: which resident page do we throw away? The theoretical optimum (evict the page whose next use is farthest in the future) is unimplementable, so engines use recency and frequency as proxies. Two separate concerns hide here, and mixing them up is the classic interview mistake:

Replacement: given that something must go, which frame is the victim?
Admission / promotion: how much credit does a page that was just read in deserve?

Plain LRU

Keep frames on a doubly linked list ordered by last touch. A hit unlinks the frame and relinks it at the head; eviction takes the tail. LRU predicts well for the access patterns databases actually have - index roots and hot small tables are touched constantly and stay near the head.

Its fatal flaw is not accuracy but concurrency. The list is global mutable state and it must be updated on the common path, i.e. on every hit, by every core. On a 64-core server the list latch becomes the bottleneck: the cache does its job, and the machine still stalls. A secondary flaw is that LRU is purely recency-based, so one visit is enough to make a page look as valuable as a page visited a million times.

Clock-sweep (second chance)

Clock-sweep gives up exactness in exchange for cheap hits. The frames are viewed as a circular array. Each frame carries a small usage count (often capped at a handful, e.g. 0-5). On a hit the accessing session just increments that counter - an atomic add on the frame itself, no shared list, no global latch.

When a frame is needed, a single sweeping pointer (the clock hand) advances frame by frame:

pinned frame -> skip it;
usage count > 0 -> decrement it and move on (this is the 'second chance');
usage count = 0 and unpinned -> this is the victim. If it is dirty, write it out first, then reuse the frame.

The result approximates LRU: frequently touched frames keep re-raising their counter faster than the hand lowers it, while a page touched once falls to zero within a sweep or two. Because the counter is capped, clock-sweep also encodes a little frequency, not just recency - a page touched five times survives longer than one touched once. Cost is paid only by the (rarer) eviction path, and it scales because the hot path writes only to the frame it already touched.

A subtlety: if almost every frame has a high usage count, the hand must make several passes to find a victim. Engines cap the counter precisely to bound this.

Midpoint insertion

Both policies above still have an admission problem. Consider a full scan of a table far larger than the pool. Every page is read once and then never again, yet each one enters at the hot end of an LRU list and is thereby ranked above pages the OLTP workload uses constantly. The scan evicts the working set and replaces it with garbage - cache pollution - and the pool spends the next minutes refilling.

Midpoint insertion (used in InnoDB's LRU, split into a 'young' and an 'old' sublist, and conceptually the same as segmented LRU) fixes this by not trusting a first touch:

a newly read page is linked at the midpoint, i.e. at the head of the old sublist, not at the head of the whole list;
it is promoted into the young sublist only if it is accessed again and typically only if that second access happens after a configured minimum age;
pages never re-referenced drift off the tail of the old sublist quickly.

The time threshold matters: a sequential scan often touches the same page several times in quick succession while reading its rows, so 'accessed twice' alone would still promote scan pages. Requiring the second access to arrive later separates 'genuinely reused' from 'still being read'.

How they combine, and other variants

Real engines mix these ideas: a clock-sweep replacement policy plus ring buffers for bulk operations; or a two-sublist LRU with time-gated promotion; or LRU-K/2Q, which track the K-th most recent reference so that frequency, not just recency, drives ranking. Some engines add explicit hints - a page read as part of a sequential scan or a bulk load can be marked to be evicted immediately after use rather than competing with the working set at all.

What an interviewer wants

Name the tradeoff axis for each: LRU is accurate but contends on every hit; clock-sweep trades exactness for a lock-free hot path; midpoint insertion is about admission and protects the working set from scans. Saying 'we use LRU' with no mention of the concurrency cost or of scan pollution is the shallow answer.

## The problem The buffer pool is smaller than the data. Every miss forces a choice: which resident page do we throw away? The theoretical optimum (evict the page whose next use is farthest in the future) is unimplementable, so engines use recency and frequency as proxies. Two separate concerns hide here, and mixing them up is the classic interview mistake: - **Replacement**: given that something must go, which frame is the victim? - **Admission / promotion**: how much credit does a page that was just read in deserve? ## Plain LRU Keep frames on a doubly linked list ordered by last touch. A hit unlinks the frame and relinks it at the head; eviction takes the tail. LRU predicts well for the access patterns databases actually have - index roots and hot small tables are touched constantly and stay near the head. Its fatal flaw is not accuracy but **concurrency**. The list is global mutable state and it must be updated on the common path, i.e. on every hit, by every core. On a 64-core server the list latch becomes the bottleneck: the cache does its job, and the machine still stalls. A secondary flaw is that LRU is purely recency-based, so one visit is enough to make a page look as valuable as a page visited a million times. ## Clock-sweep (second chance) Clock-sweep gives up exactness in exchange for cheap hits. The frames are viewed as a circular array. Each frame carries a small **usage count** (often capped at a handful, e.g. 0-5). On a hit the accessing session just increments that counter - an atomic add on the frame itself, no shared list, no global latch. When a frame is needed, a single sweeping pointer (the clock hand) advances frame by frame: - pinned frame -> skip it; - usage count > 0 -> decrement it and move on (this is the 'second chance'); - usage count = 0 and unpinned -> this is the victim. If it is dirty, write it out first, then reuse the frame. The result approximates LRU: frequently touched frames keep re-raising their counter faster than the hand lowers it, while a page touched once falls to zero within a sweep or two. Because the counter is capped, clock-sweep also encodes a little *frequency*, not just recency - a page touched five times survives longer than one touched once. Cost is paid only by the (rarer) eviction path, and it scales because the hot path writes only to the frame it already touched. A subtlety: if almost every frame has a high usage count, the hand must make several passes to find a victim. Engines cap the counter precisely to bound this. ## Midpoint insertion Both policies above still have an *admission* problem. Consider a full scan of a table far larger than the pool. Every page is read once and then never again, yet each one enters at the hot end of an LRU list and is thereby ranked above pages the OLTP workload uses constantly. The scan evicts the working set and replaces it with garbage - **cache pollution** - and the pool spends the next minutes refilling. Midpoint insertion (used in InnoDB's LRU, split into a 'young' and an 'old' sublist, and conceptually the same as segmented LRU) fixes this by *not* trusting a first touch: - a newly read page is linked at the **midpoint**, i.e. at the head of the old sublist, not at the head of the whole list; - it is promoted into the young sublist only if it is accessed **again** and typically only if that second access happens after a configured minimum age; - pages never re-referenced drift off the tail of the old sublist quickly. The time threshold matters: a sequential scan often touches the same page several times in quick succession while reading its rows, so 'accessed twice' alone would still promote scan pages. Requiring the second access to arrive later separates 'genuinely reused' from 'still being read'. ## How they combine, and other variants Real engines mix these ideas: a clock-sweep replacement policy plus ring buffers for bulk operations; or a two-sublist LRU with time-gated promotion; or LRU-K/2Q, which track the K-th most recent reference so that frequency, not just recency, drives ranking. Some engines add explicit hints - a page read as part of a sequential scan or a bulk load can be marked to be evicted immediately after use rather than competing with the working set at all. ## What an interviewer wants Name the tradeoff axis for each: LRU is accurate but contends on every hit; clock-sweep trades exactness for a lock-free hot path; midpoint insertion is about *admission* and protects the working set from scans. Saying 'we use LRU' with no mention of the concurrency cost or of scan pollution is the shallow answer.

Why do engines cap the usage counter in clock-sweep at a small value instead of letting it grow?
The hand can only remove one point of credit per visit, so a frame with a large counter needs that many full sweeps before it can ever be evicted. Capping the counter bounds the worst-case number of passes needed to find a victim and keeps eviction latency predictable, while still letting genuinely hot pages outlive one-shot pages.
Under midpoint insertion, why is a second access alone not enough to promote a page to the hot sublist?
A sequential scan typically reads many rows from the same page in rapid succession, so a page can be touched repeatedly within milliseconds while still being pure scan traffic. Engines therefore require the promoting access to arrive after a minimum age, which distinguishes real reuse across time from the burst of touches that finishing one page produces.

saying these in an interview costs you the question

Describing LRU as impractical because it is 'slow to compute' rather than because the list update contends across cores
Treating clock-sweep as a different prediction goal rather than a cheap approximation of LRU
Confusing eviction policy with admission policy - midpoint insertion is about admission
Claiming the engine evicts the oldest page by load time (FIFO) and calling that LRU
Saying pinned pages are evicted and re-read later

Compare the eviction policies a database page cache can use - plain LRU, clock-sweep (second-chance), and midpoint-insertion LRU. What problem does each later variant solve?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The problem

Plain LRU

Clock-sweep (second chance)

Midpoint insertion

How they combine, and other variants

What an interviewer wants

▾common follow-ups2 questions

▾red flags5 flags

§ context

▾related questions4 questions

▾related topics4 topics

The problem

Plain LRU

Clock-sweep (second chance)

Midpoint insertion

How they combine, and other variants

What an interviewer wants

answer

go deeper

context