TRENDING
A black manual telephone switchboard with rows of orange jacks and red patch cords plugged into the lower row, above a rotary dial and a handset
November 16, 2026
How to Route Alerts in Alertmanager So Pages Reach the On-Call and Tickets Reach the Queue, and Test Grouping, Inhibition, and Silences Before an Outage Does
A brass nail with a threaded screw section lying on graph paper, a fastener that is both nail and screw
November 16, 2026
Ai2’s XYBench Turns the XY Problem Into a Benchmark, but the Model That Drafted Every Rubric Also Judges the Answers, the Human Baseline Is Graded on Rubrics Read Off Its Own Answers, and the Emphasis Judge Disagrees With the Annotators on 20 to 26 Percent of Validation Responses
An amber warning beacon on a white surface, a flashing-light stand-in for the FBI’s FLASH alert
November 16, 2026
The FBI’s ARTEX Warning Says a Supply Chain Compromise “Enabled Access” to 2,250 Tenants Where Microsoft Counted Sign-In Attempts and Cites “Over 1,600” Consoles Where Censys Counted 1,465, and a Microsoft Post It Cites Mistypes One Indicator in Its Hunting Query
Two eggs and a colour-changing egg timer in a saucepan of water on an induction hob
November 16, 2026
How to Set gRPC Deadlines and Retries in Python, Pass Them Down a Call Chain, and Stop Retries From Charging a Card Twice
A whole lemon and a halved lemon side by side on a black background
November 16, 2026
IBM’s LLMON Turns Prompt-Injection Defense Into a Token Layout, but the “Nearly Zero” Chart Is One Benchmark, the Paper’s Own Red Team Lets 15% to 20% of Indirect Attacks Through, and the Shipped Template Lets a Document Type the Delimiters
16 Nov 2026
SXZ.io SXZ.io
  • Home
Search the Site
Popular Searches:
Technology Amazon AI
Recent Posts
A manual paper cutter with a wooden grid board, a clear plastic guard and a long cutting arm, a picture of text being trimmed to fit
How to Stop Ollama From Silently Cutting Your Prompt, Find the Real Context Window, and Set num_ctx Without Running Out of Memory
November 16, 2026
A brown llama and her gray cria walking across a salt flat beside a red lake in Bolivia
llama.cpp’s v1.0.0 Promises Major Bumps for API and ABI Breaks, but Its Rule Table Lists Only the C API, libmtmd Shares the Version While Its Header Warns of Breaking Changes, and the Release Page Carries a 7-Byte Pointer to a Nightly Build Instead of Binaries
November 16, 2026
A stack of chocolate chip cookies on a white plate beside a cup of tea
NoisyTCP Can Crash a Linux Server Over the Network, but the Fix Has Reached Only Three of the Seven Kernel Lines Still Being Released, Red Hat and Ubuntu Have No Update, and the Researcher’s Own Timings Run From 5 Seconds to 14 Hours
November 16, 2026
SXZ.io SXZ.io
  • Home

Categories

Articles 302 Posts
News 307 Posts
Learning Hub 274 Posts
Home/Learning Hub/How to Build a Buffer Pool in Python and Stop One Table Scan From Flushing Your Hot Pages With Clock Sweep, a Scan Ring, and Midpoint Insertion
Learning Hub

How to Build a Buffer Pool in Python and Stop One Table Scan From Flushing Your Hot Pages With Clock Sweep, a Scan Ring, and Midpoint Insertion

Build a database-style buffer pool in Python, compare FIFO, LRU, Clock and PostgreSQL-style clock sweep on a B+tree-shaped workload, then stop a table scan from flushing hot pages with a scan ring...

November 14, 2026 39 Min Read
20

A database cannot keep its whole file in memory, so it keeps a fixed number of recently used pages there and goes to disk for everything else. That cache is the buffer pool, and the rule that decides which page to throw out when the pool is full is the replacement policy. In this tutorial you will build a working buffer pool in Python, plug four replacement policies into it, measure them on a workload shaped like a B+tree index, and then deal with the problem that makes policy design interesting: one big sequential scan that pushes out every page you actually needed.

Table Of Content

  • The words you need, defined once
  • Prerequisites
  • Step 1: Build the pool: frames, pins, and dirty pages
  • 1.1 A fake disk that counts every read and write
  • 1.2 The pool: a lookup table, a free list, and a place for the policy to plug in
  • 1.3 Getting a frame and fetching a page
  • 1.4 Giving the pin back
  • Step 2: Add the first two policies, FIFO and LRU
  • 2.1 Run six requests by hand
  • Step 3: Add the clock, the cheaper cousin of LRU
  • 3.1 See that the clock is only an approximation
  • Step 4: Generate a workload shaped like a B+tree and measure the policies
  • Step 5: Break the pool with a loop, then with a table scan
  • 5.1 A loop one page bigger than the pool
  • 5.2 One table scan between two stretches of lookups
  • Step 6: Defend the pool against scans
  • 6.1 Defence one: a ring of frames reserved for the scan
  • 6.2 Defence two: midpoint insertion
  • 6.3 Measure both defences
  • 6.4 Break the defences with a scan that touches each page more than once
  • Step 7: Count what each eviction costs
  • Step 8: Handle dirty pages and pins
  • Step 9: Test it, then break it on purpose
  • Step 10: Compare the model with PostgreSQL 18 and InnoDB
  • 10.1 Clock sweep with a usage count
  • 10.2 Which scans get a ring, and how big it is
  • 10.3 Midpoint insertion in InnoDB
  • Confirm the whole thing end to end
  • Common mistakes and how to spot them
  • Forgetting to unpin
  • Reporting one hit rate for everything
  • Oversizing the ring or the usage cap
  • Trusting a delay of zero
  • Forgetting that this is a model
  • Where to go next
  • Sources

By the end you will have roughly 800 lines of tested code (the page shows all of it), tables of measurements you can reproduce digit for digit, and a clear picture of what PostgreSQL 18 and InnoDB do about the same problem. The first half is gentle: pages, frames, pins and a least-recently-used (LRU) rule. The second half adds the clock sweep that PostgreSQL uses, then two defences against scans: a small ring of frames reserved for the scan, and midpoint insertion, the idea behind InnoDB’s old and young lists.

The words you need, defined once

A page is a fixed-size chunk of a database file (PostgreSQL’s is typically 8 kB). A frame is one slot in memory that can hold one page. The buffer pool is an array of frames plus a table that says which page sits in which frame. A hit means the page was already in a frame; a miss means the pool had to read it from disk, which is the slow thing we are trying to avoid. To make room on a miss the pool evicts a page, called the victim. A page is pinned while some code is using it (a counter, so several users can pin the same page), and a pinned page must never be evicted. A page is dirty when it has been changed in memory and not yet written back, so evicting it means writing it first. Finally, scan flooding is what happens when a query reads far more pages than the pool holds, once each, and the pool dutifully evicts everything useful to make room for pages nobody will read again.

One honest limit before we start: the lab is single-threaded and the workload is synthetic (seeded, so you will see the same digits I did). It is a model for learning how the pieces fit, not a drop-in replacement for a database’s buffer manager, and the hit rates are measurements of this workload, not predictions for yours.

Prerequisites

You need Python 3.13 (I ran everything on 3.13.14 on Windows 11; the lab uses only the standard library), pytest for step 9 (I used 9.1.1), a terminal and an empty folder. The whole lab runs in a few seconds. You should be comfortable reading Python classes and dictionaries. Nothing here needs a database server, a cluster or an account. Two earlier posts pair well with this one: How to Build an LRU Cache From Scratch in Python builds the simple cache that the LRU rule comes from, and the B+tree index tutorial builds the page-based index whose access pattern our workload imitates.

mkdir bufpool-lab
cd bufpool-lab
python -m venv .venv
.venv\Scripts\python -m pip install pytest==9.1.1

This creates a private environment and installs pytest into it. On macOS or Linux the interpreter lives at .venv/bin/python instead. Every command below says python, so either activate the environment or call the interpreter by its full path.

Step 1: Build the pool: frames, pins, and dirty pages

The pool has three jobs: find a page quickly, keep it in memory while someone uses it, and make sure changes reach disk. We start with the pieces that do not involve choosing victims. Choosing victims is the job of the policy objects in step 2.

1.1 A fake disk that counts every read and write

Create bufpool.py. The first part is a pretend disk, a dictionary from page id to bytes, which counts every read and write. The count is the whole point: a buffer pool’s hit rate is simply the share of requests that never reach Disk.read.

# bufpool.py - a small buffer pool: frames, pins, dirty pages and a pluggable replacement policy
from collections import Counter, deque
from contextlib import contextmanager


class Disk:
    """A pretend disk: page id -> bytes. It counts every read and write."""

    def __init__(self, page_size=16):
        self.page_size = page_size
        self.pages = {}
        self.reads = 0
        self.writes = 0

    def read(self, page_id):
        self.reads += 1
        return bytearray(self.pages.get(page_id, bytes(self.page_size)))

    def write(self, page_id, data):
        self.writes += 1
        self.pages[page_id] = bytes(data)


class Frame:
    __slots__ = ("page_id", "data", "pins", "dirty")

    def __init__(self):
        self.page_id = None
        self.data = None
        self.pins = 0          # callers currently using the page: a pinned frame is never evicted
        self.dirty = False     # changed in memory, not yet written to disk

A Frame holds one page plus two pieces of bookkeeping. pins counts how many callers are using the page right now, and the pool refuses to evict a frame whose pin count is not zero. dirty says the page was modified in memory and the disk copy is stale. Using __slots__ keeps thousands of frames small, which matters when you replay hundreds of thousands of accesses.

1.2 The pool: a lookup table, a free list, and a place for the policy to plug in

Append the pool class to the same file. This first piece sets up the data structures and the helper that writes a dirty page back before its frame is reused.

# bufpool.py (continued)
class BufferPool:
    def __init__(self, disk, capacity, policy, ring_size=0):
        self.disk = disk
        self.frames = [Frame() for _ in range(capacity)]
        self.policy = policy
        self.table = {}                                    # page id -> frame number
        self.free = list(range(capacity - 1, -1, -1))      # frames that hold nothing yet
        self.ring_size = ring_size                         # frames a bulk scan may recycle
        self.ring = deque()
        self.in_ring = set()
        self.stats = Counter()

    def _evictable(self, f):
        return self.frames[f].pins == 0

    def _empty(self, f):
        fr = self.frames[f]
        if fr.dirty:                                       # write back before the frame is reused
            self.disk.write(fr.page_id, fr.data)
            self.stats["dirty_evictions"] += 1
        del self.table[fr.page_id]
        self.policy.on_evict(f)
        self.stats["evictions"] += 1
        fr.page_id, fr.dirty = None, False

table maps a page id to the number of the frame holding it, so checking for a hit costs one dictionary lookup. free lists frames that hold nothing yet; a cold pool fills these before it evicts anything. policy is the object that will choose victims, and the pool talks to it through only four calls: on_load when a page enters a frame, on_hit when a cached page is used again, on_evict when a frame is emptied, and victim when a frame is needed. _evictable tells the policy which frames are not pinned. In _empty, a dirty page is written to disk before its frame is reused. That is a write-back pool: a changed page waits in memory and costs one disk write when it leaves, however many times it was changed meanwhile. The ring fields are for step 6; with ring_size=0 they never come into play.

1.3 Getting a frame and fetching a page

# bufpool.py (continued)
    def _take_frame(self, bulk):
        """Return an empty frame for a page that is not cached."""
        if bulk and len(self.ring) == self.ring_size:
            f = self.ring.popleft()                        # the oldest frame of the scan's ring
            if self.frames[f].pins == 0:
                self.ring.append(f)
                self._empty(f)
                return f
            self.in_ring.discard(f)                        # pinned: the ring gives it up
        if self.free:
            f = self.free.pop()
        else:
            f = self.policy.victim(self._evictable)
            self._empty(f)
        if bulk:
            self.ring.append(f)
            self.in_ring.add(f)
        return f

    def fetch(self, page_id, scan=False):
        """Pin a page (reading it from disk if needed) and return its frame."""
        bulk = scan and self.ring_size > 0
        f = self.table.get(page_id)
        if f is not None:
            self.stats["hits"] += 1
            if not bulk and f in self.in_ring:             # someone else wants a ring frame
                self.ring.remove(f)
                self.in_ring.discard(f)
            self.policy.on_hit(f, bulk)
        else:
            self.stats["misses"] += 1
            f = self._take_frame(bulk)
            fr = self.frames[f]
            fr.page_id, fr.data, fr.dirty = page_id, self.disk.read(page_id), False
            self.table[page_id] = f
            self.policy.on_load(f, bulk)
        frame = self.frames[f]
        frame.pins += 1
        return frame

fetch is the method the rest of the database would call. On a hit it only tells the policy. On a miss it takes a frame (_take_frame: a free one if any, otherwise whatever the policy picks), reads the page, tells the policy it was loaded and records it in table. Either way the page comes back pinned. The bulk branches are the scan ring, which stays off until step 6 because bulk is true only when the caller says scan=True and the pool was given a ring size.

1.4 Giving the pin back

# bufpool.py (continued)
    def unpin(self, frame, dirty=False):
        if frame.pins <= 0:
            raise RuntimeError("unpin of a page that is not pinned")
        frame.pins -= 1
        frame.dirty = frame.dirty or dirty

    @contextmanager
    def page(self, page_id, write=False, scan=False):
        """Use a page and always give the pin back, even if the caller raises."""
        frame = self.fetch(page_id, scan)
        try:
            yield frame.data
        finally:
            self.unpin(frame, dirty=write)

    def flush_all(self):
        for fr in self.frames:
            if fr.page_id is not None and fr.dirty:
                self.disk.write(fr.page_id, fr.data)
                fr.dirty = False

unpin lowers the pin count and records whether the caller changed the page. page is a context manager that fetches, hands the caller the page’s bytes, and always unpins, even if the caller raises an exception. Use that form everywhere. Step 8 shows what a forgotten unpin does to a pool. flush_all writes every dirty page, which a real engine does at checkpoints and shutdown.

Nothing runs yet, so there is nothing to verify beyond the file parsing. We need a policy before the pool can do anything.

Step 2: Add the first two policies, FIFO and LRU

A policy only has to answer one question, which frame to evict, and it learns what it needs from the four calls above. It never looks at page contents. Create policies.py. FIFO (first in, first out) evicts the page that has been in the pool longest and ignores hits entirely.

# policies.py - replacement policies for the buffer pool in bufpool.py
from collections import OrderedDict


class NoVictim(Exception):
    """Every frame is pinned, so there is nothing to evict."""


class FIFO:
    """Evict the page that has been in the pool longest. Hits change nothing."""

    def __init__(self, n_frames):
        self.n = n_frames
        self.steps = 0                 # frames looked at while hunting for victims
        self.order = OrderedDict()     # first key = next to go
        self.name = "FIFO"

    def on_load(self, f, bulk=False):
        self.order[f] = True

    def on_hit(self, f, bulk=False):
        pass

    def on_evict(self, f):
        del self.order[f]

    def victim(self, evictable):
        for f in self.order:
            self.steps += 1
            if evictable(f):
                return f
        raise NoVictim()

The ordered dictionary is a queue of frame numbers, oldest first. victim walks from the front and returns the first frame the pool says is evictable, so a pinned frame is skipped rather than evicted. If every frame is pinned it raises NoVictim, which the pool lets propagate. steps counts the frames examined while hunting for victims; step 7 uses it.

LRU (least recently used) keeps the same structure and adds one line: a hit moves the frame to the safe end of the queue.

# policies.py (continued)
class LRU(FIFO):
    """Evict the page that was used least recently: a hit moves the page to the safe end."""

    def __init__(self, n_frames):
        super().__init__(n_frames)
        self.name = "LRU"

    def on_hit(self, f, bulk=False):
        self.order.move_to_end(f)

That single move_to_end is the entire difference between FIFO and LRU: FIFO remembers when a page arrived, LRU remembers when it was last used.

2.1 Run six requests by hand

Create try_it.py, a three-frame pool and six requests, so you can follow every decision on paper.

# try_it.py - the smallest possible run of the pool
from bufpool import BufferPool, Disk
from policies import LRU

pool = BufferPool(Disk(), 3, LRU(3))
for page in [1, 2, 3, 1, 4, 2]:
    with pool.page(page):
        pass
print("resident pages:", sorted(pool.table))
print("hits:", pool.stats["hits"], "misses:", pool.stats["misses"], "disk reads:", pool.disk.reads)
python try_it.py
resident pages: [1, 2, 4]
hits: 1 misses: 5 disk reads: 5

Check this against the rules. Pages 1, 2 and 3 fill the pool. The second request for page 1 is the only hit. Page 4 needs a frame and the least recently used page is 2, so 2 is evicted. When page 2 is requested again it is a miss, and now the oldest page is 3, so 3 goes. That gives one hit, five misses, five disk reads, and pages 1, 2 and 4 left in the pool. If your output matches, the pool, the pin handling and the LRU policy all work together.

Step 3: Add the clock, the cheaper cousin of LRU

LRU has a cost that grows with concurrency: every hit must reorder a list, so every reader writes to a shared structure. PostgreSQL’s buffer manager README gives a related reason for not maintaining a strict order: to choose a victim it uses “a simple clock-sweep algorithm, which avoids the need to take system-wide locks during common operations.” The classic clock keeps one reference bit per page and a hand that sweeps round the frames; a general description is that it “keeps a circular list of pages in memory,” and a hit only sets a flag on the frame itself.

PostgreSQL widens the bit into a counter. The README says: “Each buffer header contains a usage counter, which is incremented (up to a small limit value) whenever the buffer is pinned.” The cap is BM_MAX_USAGE_COUNT, which is 5, and the comment above it in buf_internals.h explains the trade-off: “A large value (comparable to NBuffers) would approximate LRU semantics,” but “it can take as many as BM_MAX_USAGE_COUNT+1 complete cycles of clock sweeps to find a free buffer.” Add the class to policies.py.

# policies.py (continued)
class ClockSweep:
    """One counter per frame and a hand that sweeps round the frames.
    A load sets the counter to 1, a hit raises it up to max_usage, the hand lowers it by one per pass
    and evicts the first unpinned frame it finds at 0. With max_usage=1 this is the classic Clock."""

    def __init__(self, n_frames, max_usage=5):
        self.n = n_frames
        self.max_usage = max_usage
        self.usage = [0] * n_frames
        self.hand = 0
        self.steps = 0
        self.name = "Clock" if max_usage == 1 else f"Sweep{max_usage}"

    def on_load(self, f, bulk=False):
        self.usage[f] = 1

    def on_hit(self, f, bulk=False):
        if bulk:       # a bulk scan may keep a page alive at 1 but never raise the count
            self.usage[f] = max(self.usage[f], 1)
        else:
            self.usage[f] = min(self.usage[f] + 1, self.max_usage)

    def on_evict(self, f):
        self.usage[f] = 0

    def victim(self, evictable):
        for _ in range((self.max_usage + 2) * self.n):
            f = self.hand
            self.hand = (self.hand + 1) % self.n
            self.steps += 1
            if not evictable(f):
                continue
            if self.usage[f]:
                self.usage[f] -= 1
                continue
            return f
        raise NoVictim()

Read victim slowly, because it is the heart of the clock. The hand looks at one frame at a time. A pinned frame is skipped without being touched. An unpinned frame with a nonzero counter loses one from its counter and the hand moves on, which is the “second chance”. The first unpinned frame whose counter is already zero is the victim. A hit raises the counter, up to max_usage, so a page that is used often needs several passes of the hand to be forgotten. With max_usage=1 you get the classic one-bit clock, which I call Clock in the tables; with max_usage=5 you get PostgreSQL’s setting, which I call Sweep5. The loop gives up after (max_usage + 2) * n steps, which is more laps than any unpinned frame needs, so only a pool with every frame pinned raises NoVictim.

The bulk flag is a rule we will use in step 6. PostgreSQL’s PinBuffer says in a comment that “Ring buffers shouldn’t evict others from pool,” and its code raises the count of a buffer pinned through a scan strategy only from 0 to 1. The bulk branch above does the same.

3.1 See that the clock is only an approximation

Create try_clock.py, the same six requests with a one-bit clock.

# try_clock.py - the same six requests, now with a one-bit clock
from bufpool import BufferPool, Disk
from policies import ClockSweep

pool = BufferPool(Disk(), 3, ClockSweep(3, 1))
for page in [1, 2, 3, 1, 4, 2]:
    with pool.page(page):
        pass
print("resident pages:", sorted(pool.table))
print("hits:", pool.stats["hits"], "misses:", pool.stats["misses"], "disk reads:", pool.disk.reads)
python try_clock.py
resident pages: [2, 3, 4]
hits: 2 misses: 4 disk reads: 4

The results differ from LRU’s: two hits and four misses, with pages 2, 3 and 4 left. When page 4 arrived every frame had its bit set, so the hand cleared all three bits and then evicted frame 0, which held page 1, even though page 1 had just been hit. LRU would have kept page 1. A clock does not know which page is oldest, only that nobody touched it since the hand last passed, and that is the price of its cheaper hits. The question for the rest of the tutorial is whether the price matters.

Step 4: Generate a workload shaped like a B+tree and measure the policies

Hit rates mean nothing without a realistic stream of requests. An index lookup in a B+tree touches the root, one inner page and one leaf, so the root and the inner pages are always hot, the leaves under popular keys are warm, and the rest are cold. We will model exactly that: one root, 100 inner pages and 20,000 leaves, 20,101 pages in all. Create traces.py.

# traces.py - page-access traces shaped like a B+tree, plus Belady's optimal policy and a runner
import bisect
import heapq
import itertools
import random

from bufpool import BufferPool, Disk

ROOT = 0
INNER = 100                       # inner pages, ids 1..100
LEAVES = 20_000                   # leaf pages, ids 101..20100
PER_INNER = LEAVES // INNER
FIRST_LEAF = 1 + INNER


def lookup_pages(leaf):
    """A point lookup touches the root, the inner page above the leaf, and the leaf."""
    return [ROOT, 1 + leaf // PER_INNER, FIRST_LEAF + leaf]

Page 0 is the root, pages 1 to 100 are inner pages (each one covers 200 leaves), and pages 101 to 20100 are leaves. lookup_pages returns the three pages one lookup touches.

# traces.py (continued)
def make_picker(rng, skew=1.0):
    """Zipf-skewed leaf chooser; the hot leaves are scattered over the key space."""
    cum = list(itertools.accumulate(1 / (r ** skew) for r in range(1, LEAVES + 1)))
    perm = list(range(LEAVES))
    rng.shuffle(perm)
    return lambda: perm[bisect.bisect_left(cum, rng.random() * cum[-1])]

Real key popularity is skewed: a few keys get most of the traffic. make_picker models that with a Zipf distribution, where the leaf of popularity rank r gets a weight proportional to 1/r. The ranks are shuffled over the leaves so hot leaves are scattered through the key space instead of sitting next to each other.

# traces.py (continued)
def workload(seed=7, scan_leaves=6_000, touches=1, updates=0.0, warm=20_000, before=3_000, just_after=1_000, later=11_000):
    """Items are (page, is_scan, phase, is_update).
    phase 0 warm-up, 1 steady state before the scan, 2 the scan, 3 just after it, 4 later.
    The lookups are the same with or without a scan, so a run without one is a fair baseline."""
    rng = random.Random(seed)
    scan_rng = random.Random(seed + 1)
    pick = make_picker(rng)
    trace = []

    def lookups(count, phase):
        for _ in range(count):
            leaf = pick()
            upd = rng.random() < updates
            for page in lookup_pages(leaf):
                trace.append((page, False, phase, upd and page == FIRST_LEAF + leaf))

    lookups(warm - before, 0)
    lookups(before, 1)
    if scan_leaves:
        start = scan_rng.randrange(0, LEAVES - scan_leaves)
        for leaf in range(start, start + scan_leaves):
            for _ in range(touches):
                trace.append((FIRST_LEAF + leaf, True, 2, False))
    lookups(just_after, 3)
    lookups(later, 4)
    return trace

workload builds the whole request stream as a list of tuples: the page, whether it belongs to a scan, a phase number and whether it is an update. The phases are a warm-up, 3,000 lookups of steady state, an optional scan of 6,000 consecutive leaves, 1,000 lookups just after it, and 11,000 later. The scan’s start is chosen by a separate random generator, so the lookups are identical with or without a scan, and a run with no scan is a fair baseline for the damage a scan does.

# traces.py (continued)
def opt_hits(pages, capacity):
    """Belady: when the pool is full, evict the cached page whose next use is farthest away."""
    n = len(pages)
    nxt, last = [0] * n, {}
    for i in range(n - 1, -1, -1):
        nxt[i] = last.get(pages[i], n + 1)
        last[pages[i]] = i
    cached, heap, hits = {}, [], []
    for i, p in enumerate(pages):
        if p in cached:
            hits.append(True)
        else:
            hits.append(False)
            if len(cached) >= capacity:
                while True:
                    neg, q = heapq.heappop(heap)
                    if cached.get(q) == -neg:
                        del cached[q]
                        break
        cached[p] = nxt[i]
        heapq.heappush(heap, (-nxt[i], p))
    return hits

This is Belady’s optimal policy. A general description of it is that when a page must be swapped in, the system swaps out “the page whose next use will occur farthest in the future.” That needs the future, so no real system can run it, but when you replay a recorded trace you know the future, and the result is a ceiling no practical policy can beat. We will print it next to every table.

# traces.py (continued)
def run(trace, capacity, make_policy, ring=0):
    """Replay a trace through a real BufferPool. Returns {(is_scan, phase): [hits, accesses]} and the pool."""
    pool = BufferPool(Disk(), capacity, make_policy(capacity), ring_size=ring)
    out = {}
    stats = pool.stats
    for page, scan, phase, upd in trace:
        before = stats["hits"]
        frame = pool.fetch(page, scan)
        pool.unpin(frame, dirty=upd)
        cell = out.setdefault((scan, phase), [0, 0])
        cell[0] += stats["hits"] - before
        cell[1] += 1
    return out, pool


def opt_by_phase(trace, capacity):
    hits = opt_hits([t[0] for t in trace], capacity)
    out = {}
    for (page, scan, phase, upd), hit in zip(trace, hits):
        cell = out.setdefault((scan, phase), [0, 0])
        cell[0] += hit
        cell[1] += 1
    return out


def rate(cell):
    return 100.0 * cell[0] / cell[1] if cell and cell[1] else float("nan")

run replays a trace through a real BufferPool and counts hits and accesses per (scan, phase) cell. It returns the pool too, so experiments can read the pool’s statistics. Now create run_all.py, starting with its imports and the list of policies to compare.

# run_all.py - experiments that need only FIFO, LRU and the clocks; output is saved under out/
import contextlib
import io
import os
import re
import sys

from bufpool import BufferPool, Disk
from policies import FIFO, LRU, ClockSweep, NoVictim
from traces import opt_by_phase, rate, run, workload

OUT = os.path.join(os.path.dirname(os.path.abspath(__file__)), "out")
POLICIES = [
    ("FIFO", FIFO),
    ("LRU", LRU),
    ("Clock", lambda n: ClockSweep(n, 1)),
    ("Sweep5", lambda n: ClockSweep(n, 5)),
]

Next, a small helper that runs one experiment, prints what the experiment prints, and keeps a copy under out/.

# run_all.py (continued)
def save(name, fn):
    """Run one experiment, print what it prints and keep a copy in out/NAME.txt."""
    buf = io.StringIO()
    with contextlib.redirect_stdout(buf):
        fn()
    os.makedirs(OUT, exist_ok=True)
    with open(os.path.join(OUT, name + ".txt"), "w", encoding="utf-8", newline="\n") as fh:
        fh.write(buf.getvalue())
    print(f"##### {name}")
    print(buf.getvalue(), end="")


def run_experiments(namespace, wanted):
    """Run every function called e<digit>_name in the namespace, or only the ones named on the command line."""
    for name in sorted(namespace):
        if re.fullmatch(r"e\d+[a-z]?_\w+", name) and (not wanted or name in wanted):
            save(name, namespace[name])

Then the first experiment: hit rate against pool size, with no scan.

# run_all.py (continued)
def overall(res):
    return 100.0 * sum(c[0] for c in res.values()) / sum(c[1] for c in res.values())


def e2_capacity():
    trace = workload(scan_leaves=0)
    caps = [500, 1000, 2000, 4000]
    print(f"Hit rate over {len(trace):,} page accesses (B+tree lookups, Zipf skew 1.0, no scan)")
    print(f"{'policy':<10}" + "".join(f"{'pool ' + str(c):>11}" for c in caps))
    for name, make in POLICIES:
        print(f"{name:<10}" + "".join(f"{overall(run(trace, c, make)[0]):>10.1f}%" for c in caps))
    print(f"{'OPT':<10}" + "".join(f"{overall(opt_by_phase(trace, c)):>10.1f}%" for c in caps))
python -c "import run_all; run_all.save('e2_capacity', run_all.e2_capacity)"
Hit rate over 96,000 page accesses (B+tree lookups, Zipf skew 1.0, no scan)
policy       pool 500  pool 1000  pool 2000  pool 4000
FIFO            78.6%      83.7%      87.5%      90.4%
LRU             83.2%      86.5%      89.2%      91.4%
Clock           82.4%      86.1%      88.8%      91.1%
Sweep5          83.8%      86.8%      89.4%      91.5%
OPT             88.8%      90.9%      92.3%      92.4%

The line starting ##### that the script prints in front of the table is just a label; the table is what is saved. Read it column by column. At a pool of 2,000 frames, about a tenth of the 20,101 pages, LRU reaches 89.2%, Sweep5 89.4%, Clock 88.8% and FIFO 87.5%, against 92.3% for the offline optimum. The numbers look high because two of every three accesses are root or inner pages that every policy keeps resident. What matters is that on a skewed read-only workload LRU, Clock and Sweep5 are within 1.4 points of each other at every pool size, and even the unreachable optimum is at most 5 points above the best of them (88.8% against 83.8% at 500 frames) and under 1 point above at 4,000 frames. FIFO trails LRU at every size, by 4.6 points at 500 frames and 1.0 at 4,000. If this were the whole story you could pick any policy and stop. The next step shows why it is not.

Step 5: Break the pool with a loop, then with a table scan

5.1 A loop one page bigger than the pool

Add this experiment to run_all.py, below e2_capacity. It reads 101 pages in a loop, 30 times, through a pool of 100 frames.

# run_all.py (continued)
def e1_cyclic():
    n, rounds = 100, 30
    trace = [(p, False, 0, False) for _ in range(rounds) for p in range(n + 1)]
    print(f"A loop over {n + 1} pages, {rounds} rounds, a pool of {n} frames")
    print(f"{'policy':<10}{'hit rate':>10}")
    for name, make in POLICIES:
        res, _ = run(trace, n, make)
        print(f"{name:<10}{overall(res):>9.1f}%")
    print(f"{'OPT':<10}{overall(opt_by_phase(trace, n)):>9.1f}%")
python -c "import run_all; run_all.save('e1_cyclic', run_all.e1_cyclic)"
A loop over 101 pages, 30 rounds, a pool of 100 frames
policy      hit rate
FIFO            0.0%
LRU             0.0%
Clock           0.0%
Sweep5          0.0%
OPT            95.7%

Every practical policy scores 0.0% while the offline optimum scores 95.7%. The reason is mechanical. When page 100 arrives, the page that was used longest ago is page 0, so it is evicted, and page 0 is exactly the one requested next. Each page is evicted just before it is needed again. It is a toy, but a scan is a loop that never comes back, and the next experiment shows what that does to a pool full of useful pages.

5.2 One table scan between two stretches of lookups

Add misses_after, which counts the lookup misses after the scan, and e3_scan, which runs the scan workload and the same workload without a scan, and reports the difference as extra misses.

# run_all.py (continued)
def misses_after(res):
    return sum(res[(False, p)][1] - res[(False, p)][0] for p in (3, 4))


def e3_scan(rows=None, touches=1):
    rows = rows or [(name, make, 0) for name, make in POLICIES]
    trace = workload(touches=touches)
    base = workload(scan_leaves=0)
    cap = 2000
    print(f"Lookup hit rate in a pool of {cap} frames; a 6,000-page scan (each page touched {touches}x) runs between")
    print("'before' (last 3,000 lookups), 'just after' (next 1,000 lookups) and 'later' (next 11,000)")
    print("'extra misses' = misses in those 12,000 lookups minus the misses of a run that never scanned")
    print(f"{'policy':<19}{'before':>8}{'just after':>12}{'later':>8}{'extra misses':>14}")
    for name, make, ring in rows:
        res, pool = run(trace, cap, make, ring)
        extra = misses_after(res) - misses_after(run(base, cap, make, ring)[0])
        print(f"{name:<19}{rate(res[(False, 1)]):>7.1f}%{rate(res[(False, 3)]):>11.1f}%{rate(res[(False, 4)]):>7.1f}%{extra:>14,}")
    res = opt_by_phase(trace, cap)
    print(f"{'OPT (offline)':<19}{rate(res[(False, 1)]):>7.1f}%{rate(res[(False, 3)]):>11.1f}%{rate(res[(False, 4)]):>7.1f}%{'-':>14}")
python -c "import run_all; run_all.save('e3_scan', run_all.e3_scan)"
Lookup hit rate in a pool of 2000 frames; a 6,000-page scan (each page touched 1x) runs between
'before' (last 3,000 lookups), 'just after' (next 1,000 lookups) and 'later' (next 11,000)
'extra misses' = misses in those 12,000 lookups minus the misses of a run that never scanned
policy               before  just after   later  extra misses
FIFO                  88.7%       79.9%   87.7%           305
LRU                   90.2%       79.9%   89.3%           469
Clock                 90.0%       79.9%   89.1%           406
Sweep5                90.6%       80.0%   89.4%           508
OPT (offline)         93.8%       93.5%   93.9%             -

Look at the LRU row. Before the scan its hit rate is 90.2%. In the 1,000 lookups right after the scan it is 79.9%, and over the next 11,000 lookups it is still a little lower, at 89.3%. The scan read 6,000 leaves, three times the pool’s 2,000 frames, so under LRU it evicted every useful page, and each hot page then had to be read back from disk one miss at a time: 469 extra misses compared with a run that never scanned. Clock (406), Sweep5 (508) and FIFO (305) behave the same way. In absolute terms 469 extra reads in 12,000 lookups is modest, but they arrive in a burst, so the cost is a latency spike right after the scan rather than a permanent loss. The offline optimum is barely affected, because it knows which pages will be used again, so the scan’s one-off pages mostly replace each other instead of pushing out useful ones. The policies cannot know that; the next step gives them a way to find out.

Step 6: Defend the pool against scans

6.1 Defence one: a ring of frames reserved for the scan

The simplest defence is to tell the pool when a request comes from a scan, and let the scan recycle a few frames of its own instead of competing with everyone else. You already wrote it. fetch(page, scan=True) sets bulk when the pool was created with a ring_size, and _take_frame then works like this. While the ring has fewer than ring_size frames, a scan miss takes a frame the normal way and adds it to the ring. Once the ring is full, the next scan miss reuses the oldest ring frame, so the scan keeps cycling through the same few frames. Two safety rules keep this honest: a pinned ring frame is given up rather than reused, and a ring frame that an ordinary reader hits leaves the ring, because somebody else wants that page now.

PostgreSQL does the same thing. Its README describes it this way: “a small ring of buffers is allocated using the normal clock sweep algorithm and those buffers are reused for the whole scan.” The second safety rule has the same logic in freelist.c, where a ring buffer is reused only if its usage count shows that nobody else has used it: “A higher usage_count indicates someone else has touched the buffer, so we shouldn’t re-use it.”

6.2 Defence two: midpoint insertion

The second defence changes where a new page enters the replacement order. InnoDB splits its LRU list into a young part and an old part (its source calls the young end the ‘new’ end). A newly read page enters at the midpoint, the head of the old part, so it has to survive a trip down the old list before it can be evicted, and it only moves to the young part if it is touched again after a delay. The MySQL 8.4 source describes the first variable as “Percentage of the buffer pool to reserve for ‘old’ blocks,” with a default written as 100 * 3 / 8 (an integer percentage, so 37). The second variable, innodb_old_blocks_time, defaults to 1000 milliseconds, and its description says blocks move to the new end of the buffer pool if the first access was at least that many milliseconds ago, with the timeout disabled if it is 0. The delay exists so that a burst of touches in quick succession, which is what a scan produces, does not count as popularity. That is my reading of the setting’s purpose; the source comment gives only the mechanism.

Here is a simplified model of that idea. It is my model of the technique as the source describes it, not InnoDB’s code. Time is counted in ticks, one per load or hit, instead of milliseconds. Add it to policies.py.

# policies.py (continued)
class MidpointLRU:
    """InnoDB style: a new page enters the 'old' list at the midpoint and only joins the 'young'
    list when it is touched again at least old_time ticks after its first access."""

    def __init__(self, n_frames, old_pct=0.375, old_time=100):
        self.n = n_frames
        self.old_target = max(1, int(n_frames * old_pct))
        self.old_time = old_time
        self.young = OrderedDict()     # first key = least recently used end
        self.old = OrderedDict()       # last key = the midpoint end
        self.first = {}                # frame -> tick of its first access
        self.tick = 0
        self.steps = 0
        self.name = f"Midpoint(t={old_time})"

    def _grow_old(self):
        while len(self.old) < self.old_target and self.young:
            f, _ = self.young.popitem(last=False)      # coldest young page crosses the midpoint
            self.old[f] = True

    def on_load(self, f, bulk=False):
        self.tick += 1
        self.first[f] = self.tick
        while len(self.old) >= self.old_target:
            g, _ = self.old.popitem(last=True)         # warmest old page becomes the coldest young page
            self.young[g] = True
            self.young.move_to_end(g, last=False)
        self.old[f] = True

    def on_hit(self, f, bulk=False):
        self.tick += 1
        if f in self.young:
            self.young.move_to_end(f)
        elif self.tick - self.first[f] >= self.old_time:
            del self.old[f]
            self.young[f] = True
            self._grow_old()
        # an old page touched again too soon stays where it is

    def on_evict(self, f):
        self.first.pop(f)
        if f in self.old:
            del self.old[f]
        else:
            del self.young[f]

    def victim(self, evictable):
        for lst in (self.old, self.young):
            for f in lst:
                self.steps += 1
                if evictable(f):
                    return f
        raise NoVictim()

New pages enter the old list at its midpoint end. When the old list is already at its target size, its warmest page is pushed over the boundary into the young list to make room. A hit on a young page just refreshes it. A hit on an old page promotes it to the young list only if at least old_time ticks have passed since its first access; otherwise the page stays where it is. Victims come from the cold end of the old list first, and from the young list only if every old frame is pinned.

6.3 Measure both defences

Create run_defences.py. It reuses the scan experiment with extra rows for the midpoint policy and for rings of 32 and 256 frames (32 frames of 8 kB is the 256 kB that PostgreSQL’s README gives for sequential scans), and adds a second experiment in which the scan touches each page several times.

# run_defences.py - the two scan defences: a ring of frames, and midpoint insertion
import sys

import run_all
from policies import LRU, ClockSweep, MidpointLRU
from traces import run, workload

ROWS = [(name, make, 0) for name, make in run_all.POLICIES] + [
    ("Midpoint", lambda n: MidpointLRU(n, 0.375, 100), 0),
    ("LRU + ring 32", LRU, 32),
    ("Sweep5 + ring 32", lambda n: ClockSweep(n, 5), 32),
    ("Sweep5 + ring 256", lambda n: ClockSweep(n, 5), 256),
]


def e3b_scan_defences():
    run_all.e3_scan(ROWS)


def e4_touches():
    cap = 2000
    makers = [
        ("LRU", LRU, 0), ("Sweep5", lambda n: ClockSweep(n, 5), 0), ("Sweep5 + ring 32", lambda n: ClockSweep(n, 5), 32),
        ("Midpoint t=0", lambda n: MidpointLRU(n, 0.375, 0), 0), ("Midpoint t=1", lambda n: MidpointLRU(n, 0.375, 1), 0),
        ("Midpoint t=10", lambda n: MidpointLRU(n, 0.375, 10), 0), ("Midpoint t=100", lambda n: MidpointLRU(n, 0.375, 100), 0),
    ]
    print(f"Extra lookup misses caused by one scan (pool of {cap}), by how many times the scan touches each page")
    print(f"{'policy':<19}{'1 touch':>9}{'3 touches':>11}{'10 touches':>12}")
    base = workload(scan_leaves=0)
    traces = {t: workload(touches=t) for t in (1, 3, 10)}
    for name, make, ring in makers:
        floor = run_all.misses_after(run(base, cap, make, ring)[0])
        cells = [run_all.misses_after(run(traces[t], cap, make, ring)[0]) - floor for t in (1, 3, 10)]
        print(f"{name:<19}" + "".join(f"{c:>{w},}" for c, w in zip(cells, (9, 11, 12))))


if __name__ == "__main__":
    run_all.run_experiments(globals(), sys.argv[1:])
python run_defences.py
Lookup hit rate in a pool of 2000 frames; a 6,000-page scan (each page touched 1x) runs between
'before' (last 3,000 lookups), 'just after' (next 1,000 lookups) and 'later' (next 11,000)
'extra misses' = misses in those 12,000 lookups minus the misses of a run that never scanned
policy               before  just after   later  extra misses
FIFO                  88.7%       79.9%   87.7%           305
LRU                   90.2%       79.9%   89.3%           469
Clock                 90.0%       79.9%   89.1%           406
Sweep5                90.6%       80.0%   89.4%           508
Midpoint              91.2%       90.7%   90.9%            31
LRU + ring 32         90.2%       90.1%   89.7%            32
Sweep5 + ring 32      90.6%       90.2%   90.0%             3
Sweep5 + ring 256     90.6%       89.8%   89.9%            47
OPT (offline)         93.8%       93.5%   93.9%             -

Compare the “just after” column and the extra misses. Without a defence, LRU, Clock and Sweep5 drop to about 80%. Midpoint stays at 90.7% with 31 extra misses, and its steady-state hit rate before the scan, 91.2%, is the best of the practical policies, which I would attribute to it keeping one-off leaf reads out of the young list, although I did not test that explanation. A ring of 32 frames brings LRU to 90.1% (32 extra misses) and Sweep5 to 90.2% (3 extra misses). The bigger ring of 256 frames costs more, 47 extra misses, because the scan holds 256 frames for its whole run and each of them displaced a page when the ring was filled. A ring is a price you pay for the scan, so the smaller the better, as long as it is large enough for the scan’s pinned pages.

6.4 Break the defences with a scan that touches each page more than once

The second experiment in run_defences.py asks what happens when the scan touches each page one, three and ten times in a row, as a real scan does while it reads the rows on a page.

Extra lookup misses caused by one scan (pool of 2000), by how many times the scan touches each page
policy               1 touch  3 touches  10 touches
LRU                      469        469         469
Sweep5                   508        584         614
Sweep5 + ring 32           3          3           3
Midpoint t=0              30      1,081       1,081
Midpoint t=1              30      1,081       1,081
Midpoint t=10             31         31          31
Midpoint t=100            31         31          31

Three lessons sit in this table. LRU does not care how many times a scan touches a page, because one touch is all it needs to evict someone else. Sweep5 gets worse as touches pile up, 508 then 584 then 614, because each extra touch raises the scan page’s usage count and makes it survive more passes of the hand; that is the problem the PinBuffer comment addresses when it says ring buffers shouldn’t evict others from the pool. The ring is immune: 3 extra misses at every touch count. And midpoint insertion with no delay (t=0, or t=1 tick) collapses to 1,081 extra misses at three touches, worse than LRU, because the second touch of a scan page promotes it into the young list. With a delay of 10 ticks or more it holds at 31. That is the failure the delay in innodb_old_blocks_time is meant to prevent.

Step 7: Count what each eviction costs

The clock’s advantage is cheap hits, but its victim search is not free. Add these two experiments to run_all.py: the average number of frames examined per eviction on the scan workload, and the worst case, in which every frame is hot.

# run_all.py (continued)
def e5_steps():
    cap = 2000
    print(f"Frames examined per eviction (pool of {cap}; the same trace as the scan table, 1 touch)")
    print(f"{'policy':<10}{'evictions':>11}{'steps':>10}{'steps/evict':>13}")
    trace = workload()
    for name, make in [("LRU", LRU), ("Clock", lambda n: ClockSweep(n, 1)), ("Sweep5", lambda n: ClockSweep(n, 5)),
                       ("Sweep15", lambda n: ClockSweep(n, 15))]:
        res, pool = run(trace, cap, make)
        ev = pool.stats["evictions"]
        print(f"{name:<10}{ev:>11,}{pool.policy.steps:>10,}{pool.policy.steps / ev:>13.2f}")


def e5b_worst_sweep():
    n = 2000
    print(f"One eviction when every one of {n} frames is hot (touched 20 times), counted in frames examined")
    print(f"{'policy':<10}{'steps for one victim':>22}{'laps':>8}")
    for name, make in [("Clock", lambda k: ClockSweep(k, 1)), ("Sweep5", lambda k: ClockSweep(k, 5)), ("Sweep15", lambda k: ClockSweep(k, 15))]:
        pool = BufferPool(Disk(), n, make(n))
        for page in range(n):
            pool.unpin(pool.fetch(page))
        for _ in range(20):
            for page in range(n):
                pool.unpin(pool.fetch(page))
        pool.policy.steps = 0
        pool.unpin(pool.fetch(n))                  # one miss: somebody has to go
        print(f"{name:<10}{pool.policy.steps:>22,}{pool.policy.steps / n:>8.2f}")
python -c "import run_all; run_all.save('e5_steps', run_all.e5_steps); run_all.save('e5b_worst_sweep', run_all.e5b_worst_sweep)"
Frames examined per eviction (pool of 2000; the same trace as the scan table, 1 touch)
policy      evictions     steps  steps/evict
LRU            14,721    14,721         1.00
Clock          15,045    35,156         2.34
Sweep5         14,560    38,395         2.64
Sweep15        14,319    38,876         2.71
One eviction when every one of 2000 frames is hot (touched 20 times), counted in frames examined
policy      steps for one victim    laps
Clock                      2,001    1.00
Sweep5                    10,001    5.00
Sweep15                   30,001   15.00

On average the search is short: LRU examines exactly one frame per eviction (nothing is pinned here, so the first candidate is always taken), Clock 2.34, Sweep5 2.64 and Sweep15 2.71. The worst case is far worse. When all 2,000 frames have been touched 20 times, one eviction has to lower every counter before it finds a zero: 2,001 frames examined for Clock, 10,001 for Sweep5 and 30,001 for Sweep15, which is one, five and fifteen laps plus one frame. The comment in buf_internals.h gives the bound as “BM_MAX_USAGE_COUNT+1 complete cycles”; this setup needed five laps and one frame for Sweep5, inside that bound. This is why the cap is small. A higher cap remembers frequency more precisely, but the worst-case sweep grows in proportion.

Step 8: Handle dirty pages and pins

Two more behaviours separate a buffer pool from a plain cache. Both are in the code already, so this step measures them. Add these functions to run_all.py.

# run_all.py (continued)
def e6_writeback():
    trace = workload(scan_leaves=0, updates=0.1)
    updates = sum(1 for t in trace if t[3])
    print(f"{updates:,} page updates in {len(trace):,} accesses (pool of 2000)")
    print(f"{'policy':<22}{'disk writes':>12}")
    print(f"{'write-through':<22}{updates:>12,}")
    for name, make in [("LRU", LRU), ("Sweep5", lambda n: ClockSweep(n, 5))]:
        res, pool = run(trace, 2000, make)
        before_flush = pool.disk.writes
        pool.flush_all()
        print(f"{'write-back, ' + name:<22}{pool.disk.writes:>12,}   ({pool.stats['dirty_evictions']:,} on eviction, {pool.disk.writes - before_flush:,} at the final flush)")


def e7_pin_leak():
    pool = BufferPool(Disk(), 4, LRU(4))

    def buggy(page):
        frame = pool.fetch(page)
        if page % 2 == 0:
            raise ValueError("bad row")          # the unpin below never runs
        pool.unpin(frame)

    leaks = 0
    for page in range(100):
        try:
            buggy(page)
        except ValueError:
            leaks += 1
        except NoVictim:
            pinned = sum(1 for f in pool.frames if f.pins)
            print(f"page {page}: NoVictim after {leaks} failed calls, {pinned} of {len(pool.frames)} frames pinned")
            break

    pool = BufferPool(Disk(), 4, LRU(4))

    def fixed(page):
        with pool.page(page):
            if page % 2 == 0:
                raise ValueError("bad row")

    failed = 0
    for page in range(100):
        try:
            fixed(page)
        except ValueError:
            failed += 1
    print(f"with the context manager: 100 calls, {failed} failed, {sum(1 for f in pool.frames if f.pins)} frames pinned")

The first experiment turns 10% of lookups into updates of the leaf page and compares disk writes. A write-through design writes every update; our write-back pool writes a page once when it leaves the pool, however many updates it took. Finish the file with an entry point that runs every experiment whose name starts with e, a digit and an underscore, or only the ones you name.

# run_all.py (continued)
if __name__ == "__main__":
    run_experiments(globals(), sys.argv[1:])
python run_all.py e6_writeback e7_pin_leak
3,154 page updates in 96,000 accesses (pool of 2000)
policy                 disk writes
write-through                3,154
write-back, LRU              1,506   (1,104 on eviction, 402 at the final flush)
write-back, Sweep5           1,468   (1,028 on eviction, 440 at the final flush)
page 7: NoVictim after 4 failed calls, 4 of 4 frames pinned
with the context manager: 100 calls, 50 failed, 0 frames pinned

The 3,154 updates cost 3,154 disk writes under write-through, and 1,506 under write-back with LRU (1,104 when a dirty page was evicted and 402 at the final flush) or 1,468 with Sweep5. Dirty pages that are updated again before they are evicted are written once, and that is the saving. The second experiment shows the classic pin bug. A function fetches a page and raises before unpinning it. After four such failures the pool of four frames has every frame pinned, and the next request, for page 7, which needs nothing special, fails with NoVictim. With the context manager, a hundred calls with fifty failures leave zero frames pinned. The pin count is the piece of state in the pool that code outside the pool is most likely to leak.

Step 9: Test it, then break it on purpose

Numbers from a simulation are only as good as the code that produced them. The tests below check the pool against a dictionary, check each policy’s rule on a hand-worked example, and check the safety properties. Create test_bufpool.py. The first part holds the helpers and the properties every policy must satisfy: the pool agrees with a dictionary under random reads and writes (and the disk agrees after a flush), a pinned page is never evicted, a pool with every frame pinned raises NoVictim and still works after a pin is released, and the context manager releases pins when the caller raises.

# test_bufpool.py - tests for the buffer pool and its policies (pytest)
import random

import pytest

from bufpool import BufferPool, Disk
from policies import FIFO, LRU, ClockSweep, MidpointLRU, NoVictim

ALL = [FIFO, LRU, lambda n: ClockSweep(n, 1), lambda n: ClockSweep(n, 5), lambda n: MidpointLRU(n, 0.375, 3)]
IDS = ["fifo", "lru", "clock", "sweep5", "midpoint"]


def make(policy, capacity, ring=0):
    return BufferPool(Disk(), capacity, policy(capacity), ring_size=ring)


def touch(pool, page, **kw):
    pool.unpin(pool.fetch(page, **kw))


@pytest.mark.parametrize("policy", ALL, ids=IDS)
def test_matches_a_dictionary_under_random_use(policy):
    """Reads see the latest write and the disk matches after a flush, whatever the policy evicts."""
    rng = random.Random(3)
    pool, model = make(policy, 8), {}
    for _ in range(4000):
        page = rng.randrange(40)
        if rng.random() < 0.4:
            model[page] = model.get(page, 0) + 1
            with pool.page(page, write=True) as data:
                data[0:4] = model[page].to_bytes(4, "big")
        else:
            with pool.page(page) as data:
                assert int.from_bytes(data[0:4], "big") == model.get(page, 0)
    pool.flush_all()
    for page, value in model.items():
        assert int.from_bytes(pool.disk.pages[page][0:4], "big") == value


@pytest.mark.parametrize("policy", ALL, ids=IDS)
def test_a_pinned_page_is_never_evicted(policy):
    pool = make(policy, 3)
    held = pool.fetch(100)
    for page in range(50):
        touch(pool, page)
        assert pool.table[100] == pool.frames.index(held)
    pool.unpin(held)


@pytest.mark.parametrize("policy", ALL, ids=IDS)
def test_all_frames_pinned_raises_and_leaves_the_pool_usable(policy):
    pool = make(policy, 2)
    a, b = pool.fetch(1), pool.fetch(2)
    with pytest.raises(NoVictim):
        pool.fetch(3)
    pool.unpin(a)
    touch(pool, 3)
    assert 3 in pool.table and 2 in pool.table
    pool.unpin(b)


@pytest.mark.parametrize("policy", ALL, ids=IDS)
def test_context_manager_unpins_when_the_caller_raises(policy):
    pool = make(policy, 2)
    for page in range(10):
        with pytest.raises(ValueError):
            with pool.page(page):
                raise ValueError("boom")
    assert all(f.pins == 0 for f in pool.frames)

The next part checks unpinning twice, write-back timing, and the exact rules of LRU, FIFO and the clock on small examples you can verify by hand.

# test_bufpool.py (continued)
def test_unpin_twice_is_an_error():
    pool = make(LRU, 2)
    frame = pool.fetch(1)
    pool.unpin(frame)
    with pytest.raises(RuntimeError):
        pool.unpin(frame)


@pytest.mark.parametrize("policy", ALL, ids=IDS)
def test_a_dirty_page_is_written_once_and_only_later(policy):
    pool = make(policy, 2)
    with pool.page(1, write=True) as data:
        data[0] = 7
    assert pool.disk.writes == 0                       # write-back: nothing yet
    for page in range(2, 12):
        touch(pool, page)
    pool.flush_all()
    assert pool.disk.writes == 1 and pool.disk.pages[1][0] == 7


def test_lru_writes_a_dirty_page_when_it_is_evicted():
    pool = make(LRU, 2)
    with pool.page(1, write=True) as data:
        data[0] = 7
    for page in range(2, 12):
        touch(pool, page)
    assert pool.disk.writes == 1 and pool.stats["dirty_evictions"] == 1


def test_lru_evicts_the_least_recently_used_page():
    pool = make(LRU, 3)
    for page in (1, 2, 3, 1):
        touch(pool, page)
    touch(pool, 4)                                     # 2 is the oldest use
    assert set(pool.table) == {1, 3, 4}


def test_fifo_ignores_hits():
    pool = make(FIFO, 3)
    for page in (1, 2, 3, 1):
        touch(pool, page)
    touch(pool, 4)                                     # 1 arrived first, so it goes despite the hit
    assert set(pool.table) == {2, 3, 4}


def test_clock_gives_a_referenced_page_a_second_chance():
    pool = make(lambda n: ClockSweep(n, 1), 3)
    for page in (1, 2, 3):
        touch(pool, page)
    touch(pool, 4)           # every bit is set: the hand clears them all, then evicts frame 0 (page 1)
    assert set(pool.table) == {2, 3, 4}
    touch(pool, 2)           # sets the bit of page 2 again
    touch(pool, 5)           # hand is at page 2's frame: it is spared, page 3 goes
    assert set(pool.table) == {2, 4, 5}

Then the clock counter: it is capped, the hand lowers it, and a hot page outlives a burst of one-off pages under Sweep5.

# test_bufpool.py (continued)
def test_usage_count_is_capped_and_the_hand_lowers_it():
    policy = ClockSweep(2, 5)
    pool = BufferPool(Disk(), 2, policy)
    for _ in range(20):
        touch(pool, 1)
    assert policy.usage[pool.table[1]] == 5
    touch(pool, 2)
    touch(pool, 3)           # the hand has to lower page 1's count to find a victim
    assert 1 in pool.table and policy.usage[pool.table[1]] < 5


def test_a_hot_page_outlives_a_burst_of_one_off_pages_under_sweep5():
    pool = make(lambda n: ClockSweep(n, 5), 4)
    for _ in range(6):
        touch(pool, 0)
    for page in range(1, 10):
        touch(pool, page)
    assert 0 in pool.table

Finally the scan defences: midpoint keeps quick repeat touches out of the young list and promotes a page touched again after the wait, a ring stops a scan from flushing the pool and loses a frame another reader hits, bulk scans never raise a usage count, and without a ring the same scan flushes everything.

# test_bufpool.py (continued)
def test_midpoint_keeps_scan_pages_out_of_the_young_list():
    policy = MidpointLRU(8, 0.375, 5)
    pool = BufferPool(Disk(), 8, policy)
    for page in range(8):
        touch(pool, page)
    young_before = set(policy.young)
    for page in range(100, 120):
        touch(pool, page)
        touch(pool, page)                              # two quick touches per page, like a scan
    assert set(policy.young) == young_before


def test_midpoint_promotes_a_page_touched_again_after_the_wait():
    policy = MidpointLRU(8, 0.375, 3)
    pool = BufferPool(Disk(), 8, policy)
    touch(pool, 1)
    for page in range(100, 105):
        touch(pool, page)
    touch(pool, 1)
    assert pool.table[1] in policy.young


def test_ring_keeps_a_scan_from_flushing_the_pool():
    pool = make(LRU, 20, ring=4)
    for page in range(10):
        touch(pool, page)
    for page in range(1000, 1100):
        touch(pool, page, scan=True)
    assert all(page in pool.table for page in range(10)) or sum(page in pool.table for page in range(10)) >= 6


def test_ring_frame_hit_by_another_reader_leaves_the_ring():
    pool = make(LRU, 20, ring=4)
    for page in range(1000, 1004):
        touch(pool, page, scan=True)
    frame_of_1000 = pool.table[1000]
    touch(pool, 1000)                                  # a normal reader wants it
    assert frame_of_1000 not in pool.in_ring
    for page in range(2000, 2010):
        touch(pool, page, scan=True)
    assert 1000 in pool.table                          # the ring did not recycle it


def test_without_a_ring_the_same_scan_flushes_everything():
    pool = make(LRU, 20, ring=0)
    for page in range(10):
        touch(pool, page)
    for page in range(1000, 1100):
        touch(pool, page, scan=True)
    assert not any(page in pool.table for page in range(10))


def test_a_bulk_scan_never_raises_a_usage_count():
    policy = ClockSweep(20, 5)
    pool = BufferPool(Disk(), 20, policy, ring_size=4)
    touch(pool, 1)
    for _ in range(10):
        touch(pool, 1, scan=True)
    assert policy.usage[pool.table[1]] == 1
python -m pytest -q
......................................                                   [100%]
38 passed in 0.07s

Thirty-eight tests pass. A passing suite does not prove the tests are any good, so the last file plants one bug at a time in a copy of the code and checks that something fails. Create mutants.py.

# mutants.py - plant one bug at a time in a copy of the lab and check that the tests notice
import pathlib
import re
import shutil
import subprocess
import sys
import tempfile

HERE = pathlib.Path(__file__).resolve().parent
MUTANTS = [
    ("LRU hit does not refresh", "policies.py", "        self.order.move_to_end(f)\n\n\nclass ClockSweep", "        pass\n\n\nclass ClockSweep"),
    ("FIFO hit refreshes the page", "policies.py", "    def on_hit(self, f, bulk=False):\n        pass\n\n    def on_evict(self, f):\n        del self.order[f]",
     "    def on_hit(self, f, bulk=False):\n        self.order.move_to_end(f)\n\n    def on_evict(self, f):\n        del self.order[f]"),
    ("pinned frames can be evicted", "bufpool.py", "return self.frames[f].pins == 0", "return True"),
    ("unpin never marks dirty", "bufpool.py", "frame.dirty = frame.dirty or dirty", "frame.dirty = frame.dirty"),
    ("no write-back on eviction", "bufpool.py", "        if fr.dirty:                                       # write back", "        if False:                                          # write back"),
    ("usage count has no cap", "policies.py", "min(self.usage[f] + 1, self.max_usage)", "self.usage[f] + 1"),
    ("the hand never lowers a count", "policies.py", "                self.usage[f] -= 1\n                continue", "                continue"),
    ("a bulk scan raises usage counts", "policies.py", "        if bulk:       # a bulk scan", "        if False:      # a bulk scan"),
    ("ring keeps a frame another reader hit", "bufpool.py", "if not bulk and f in self.in_ring:", "if False:"),
    ("midpoint ignores old_time", "policies.py", "elif self.tick - self.first[f] >= self.old_time:", "else:"),
    ("double unpin is allowed", "bufpool.py", "        if frame.pins <= 0:", "        if False:"),
]


def main():
    caught = 0
    for label, name, old, new in MUTANTS:
        with tempfile.TemporaryDirectory(dir=HERE.parent) as tmp:
            for f in HERE.glob("*.py"):
                if f.name != "mutants.py":
                    shutil.copy(f, tmp)
            path = pathlib.Path(tmp) / name
            text = path.read_text(encoding="utf-8")
            if text.count(old) != 1:
                print(f"{label:<42} SKIPPED: pattern found {text.count(old)} times")
                continue
            path.write_text(text.replace(old, new), encoding="utf-8", newline="\n")
            run = subprocess.run([sys.executable, "-m", "pytest", "-q", "--tb=no", "-p", "no:cacheprovider"],
                                 cwd=tmp, capture_output=True, text=True)
            m = re.search(r"(\d+) failed", run.stdout)
            ok = run.returncode != 0
            caught += ok
            print(f"{label:<42} {'caught' if ok else 'MISSED':<7} {m.group(1) + ' tests failed' if m else run.stdout.strip().splitlines()[-1]}")
    print(f"{caught} of {len(MUTANTS)} planted bugs caught")


if __name__ == "__main__":
    main()
python mutants.py
LRU hit does not refresh                   caught  1 tests failed
FIFO hit refreshes the page                caught  1 tests failed
pinned frames can be evicted               caught  9 tests failed
unpin never marks dirty                    caught  11 tests failed
no write-back on eviction                  caught  10 tests failed
usage count has no cap                     caught  1 tests failed
the hand never lowers a count              caught  13 tests failed
a bulk scan raises usage counts            caught  1 tests failed
ring keeps a frame another reader hit      caught  1 tests failed
midpoint ignores old_time                  caught  1 tests failed
double unpin is allowed                    caught  1 tests failed
11 of 11 planted bugs caught

All eleven planted bugs are caught, including the ones that matter most for a database: a pinned frame being evicted, a dirty flag that is never set, and no write-back on eviction. One lesson from writing these tests: my first version of the write-back test assumed every policy would eventually evict a page nobody touches again. The midpoint policy did not, because in my model a page that is pushed into the young list during start-up stays there until promotions push it back down, so the test now checks the final flush instead. That is a property of the model you should know about before you trust its numbers.

Step 10: Compare the model with PostgreSQL 18 and InnoDB

The model is only useful if it matches what real systems do, so here is how each piece maps to the sources, which I read in the PostgreSQL 18 tree (the REL_18_STABLE branch) and the MySQL 8.4 source. I did not run either server for this lab.

10.1 Clock sweep with a usage count

PostgreSQL’s buffer manager uses a clock sweep with a usage counter capped at 5, which is ClockSweep(n, 5) in our policies. Hits raise the counter, the hand lowers it, and pinned buffers are skipped. If you run a PostgreSQL 18 server and want to see the counters, the pg_buffercache module documents a function that “returns a set of records, each row describing the number of buffers with a given usage count,” with the columns usage_count, buffers, dirty and pinned. The query below is built from that documentation and I did not run it here; by default the documentation restricts such functions to superusers and roles with privileges of the pg_monitor role.

SELECT usage_count, buffers, dirty, pinned FROM pg_buffercache_usage_counts();

10.2 Which scans get a ring, and how big it is

Not every scan gets a ring. In heapam.c the comment above the decision says: “If the table is large relative to NBuffers, use a bulk-read access strategy,” and the test is scan->rs_nblocks > NBuffers / 4, so a table must be larger than a quarter of the shared buffers. The README says: “For sequential scans, a 256KB ring is used.” In the PostgreSQL 18 branch that sentence is the floor rather than the whole story: GetAccessStrategy in freelist.c starts at 256 kB for bulk reads and then adds room for asynchronous I/O, capping the result at the backend’s pin limit. This is the relevant excerpt with its comments removed:

ring_size_kb = 256;
ring_max_kb = GetPinLimit() * (BLCKSZ / 1024);
ring_max_kb = Max(ring_size_kb, ring_max_kb);
ring_size_kb += (BLCKSZ / 1024) *
	io_combine_limit * effective_io_concurrency;
if (ring_size_kb > ring_max_kb)
	ring_size_kb = ring_max_kb;

The PostgreSQL 18 documentation lists the default of io_combine_limit as 128kB (16 blocks of 8 kB) and says of effective_io_concurrency that “The default is 16.” With those defaults and 8 kB blocks the sum before the cap is 256 + 8 x 16 x 16 = 2,304 kB, and the cap depends on the pin limit of your server, which I did not compute. In short, with the defaults the ring for a large sequential scan can be considerably bigger than the README’s 256 kB, so do not size your own expectations from that sentence alone. Other operations have their own rings. For VACUUM the README says “the size of this ring is controlled by the vacuum_buffer_usage_limit GUC,” and the documentation gives the default as 2MB and adds that “If the specified size would exceed 1/8 the size of shared_buffers, the size is silently capped to that value.” For bulk writes the README says: “For bulk writes we use a ring size of 16MB (but not more than 1/8th of shared_buffers).” The README also warns about a scan that modifies every page: “the buffers in the ring will always be dirtied and the ring strategy effectively degrades to the normal strategy.”

10.3 Midpoint insertion in InnoDB

Our MidpointLRU(n, old_pct=0.375, old_time=100) follows the two InnoDB settings described in step 6.2, with ticks in place of milliseconds and 0.375 in place of the integer 37. In my model, without the delay the protection disappears for scans that touch each page more than once. The InnoDB setting is meant to address that, but I did not test InnoDB itself.

Confirm the whole thing end to end

Run the four commands below from the lab folder. Each prints its tables, and the numbers should match the ones in this article exactly, because the workload is seeded.

python run_all.py
python run_defences.py
python -m pytest -q
python mutants.py

You should see the tables from steps 4 to 8 and 6.3, “38 passed” from pytest (the time will differ), and “11 of 11 planted bugs caught”. If a table differs, check that you copied the seeded constants in traces.py exactly (the seed is 7). If the numbers match, you have a pool whose policies follow the rules described in the PostgreSQL README and the InnoDB settings, and you have seen on your own machine why those rules exist.

Common mistakes and how to spot them

Forgetting to unpin

A leaked pin is a leaked frame. Step 8 showed a pool of four frames locked up after four failed calls. In a real pool the symptom is a request that fails because no frame can be evicted, although the pool is mostly idle; PostgreSQL’s wording for it is “no unpinned buffers available”. Always use the context manager or a try and finally.

Reporting one hit rate for everything

A scan’s own pages are nearly all misses, and they dilute the figure that tells you how your lookups are doing. The experiments report lookups separately from the scan for that reason. When you measure a real system, separate the traffic you want to protect from the traffic you expect to flush through.

Oversizing the ring or the usage cap

With Sweep5, a ring of 256 frames cost 47 extra misses against 3 for 32 frames, and a usage cap of 15 made one eviction examine 30,001 frames against 10,001 for a cap of 5. Both are dials with a cost on each side.

Trusting a delay of zero

Midpoint insertion without a delay looked fine for single-touch scans, with 30 extra misses, and failed badly for scans that touch pages repeatedly, with 1,081. Test your defence with the access pattern of your real scans, not the friendliest one.

Forgetting that this is a model

The lab is single-threaded, one page size, no operating system cache and no read-ahead. Real pools take locks or use atomic counters, share a pool across processes, cooperate with the filesystem cache, and prefetch. The measurements teach the shape of the trade-offs. They do not tell you how fast a given server will go.

Where to go next

Replace the synthetic trace with one recorded from something you run; the run function only needs a list of (page, is_scan, phase, is_update) tuples. Add a policy that remembers pages after they are evicted, such as 2Q or ARC, and see whether it beats midpoint insertion on the multi-touch scan. The PostgreSQL 18 primary key tutorial shows the same machinery from the other side: random UUIDv4 inserts touch pages scattered over the whole index, which is a cache-unfriendly pattern for any pool, while time-ordered keys stay in a few hot pages. To see how a slow query reads buffers in a real server, the PostgreSQL 18 EXPLAIN ANALYZE tutorial is the natural companion. If you want to see a cache protect a backend from a thundering herd instead of a scan, read the cache stampede tutorial.

Sources

PostgreSQL 18 branch, as read for this tutorial: the buffer manager README, freelist.c, buf_internals.h, bufmgr.c and heapam.c; the documentation for resource consumption settings and the pg_buffercache module. InnoDB: the ha_innodb.cc source on the 8.4 branch, where the old-blocks settings are defined (the MySQL manual page for the buffer pool refused automated fetches, so I read the source instead). General descriptions of the clock and of Belady’s optimal policy: Page replacement algorithm on Wikipedia.

Tags:

Buffer PoolCache ReplacementCachingData StructuresDatabasesPostgreSQLPython

Share

A hand holding a clear glass of water with several fingerprints visible on the glass
Previous Post

A Report Turns Model Weights Into a GPU Registry, and It Reproduces in Four Seconds, but the Fingerprint Dates the Starting Weights, Not the Training, and the X Post’s “Conclusive” Covers Six Models Where the Report Claims It for One

Fireworks bursting over a small village at night, a play on the Fireworks AI name
Next Post

Cursor Traces the Tampered Claude Code Extension to a Key Exposed at Fireworks AI and Agent Traces Holding Unredacted Credentials, but Neither Company Says When the Key Leaked, and Fireworks’ Bulletins Never Name Cursor

No Comment! Be the first one.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Latest
16 Nov
How to Stop Ollama From Silently Cutting Your Prompt, Find the Real Context Window, and Set num_ctx Without Running Out of Memory
16 Nov
llama.cpp’s v1.0.0 Promises Major Bumps for API and ABI Breaks, but Its Rule Table Lists Only the C API, libmtmd Shares the Version While Its Header Warns of Breaking Changes, and the Release Page Carries a 7-Byte Pointer to a Nightly Build Instead of Binaries
Trending
November 16, 2026
How to Stop Ollama From Silently Cutting Your Prompt, Find the Real Context Window, and Set num_ctx Without Running Out of Memory
November 16, 2026
llama.cpp’s v1.0.0 Promises Major Bumps for API and ABI Breaks, but Its Rule Table Lists Only the C API, libmtmd Shares the Version While Its Header Warns of Breaking Changes, and the Release Page Carries a 7-Byte Pointer to a Nightly Build Instead of Binaries
November 16, 2026
NoisyTCP Can Crash a Linux Server Over the Network, but the Fix Has Reached Only Three of the Seven Kernel Lines Still Being Released, Red Hat and Ubuntu Have No Update, and the Researcher’s Own Timings Run From 5 Seconds to 14 Hours
November 15, 2026
How to Route Alerts in Alertmanager So Pages Reach the On-Call and Tickets Reach the Queue, and Test Grouping, Inhibition, and Silences Before an Outage Does
November 15, 2026
Ai2’s XYBench Turns the XY Problem Into a Benchmark, but the Model That Drafted Every Rubric Also Judges the Answers, the Human Baseline Is Graded on Rubrics Read Off Its Own Answers, and the Emphasis Judge Disagrees With the Annotators on 20 to 26 Percent of Validation Responses
November 15, 2026
The FBI’s ARTEX Warning Says a Supply Chain Compromise “Enabled Access” to 2,250 Tenants Where Microsoft Counted Sign-In Attempts and Cites “Over 1,600” Consoles Where Censys Counted 1,465, and a Microsoft Post It Cites Mistypes One Indicator in Its Hunting Query

Related Posts

A laptop wrapped in a chain and padlock, illustrating least-privilege controls for AI agents.
Learning Hub

How to Secure Tool-Using AI Agents Before They Touch Production

June 8, 2026
Colorful sticky notes arranged on an office wall, symbolizing governance checklists and planning.
Learning Hub

AI Governance for Agentic Apps: A Practical Checklist for Builders

June 8, 2026
A technician connects green fiber optic cables at a data center, representing a private production inference endpoint.
Learning Hub

How to Deploy a Fine-Tuned LLM Behind a Private Production Inference Endpoint

June 8, 2026
Narrow aisle behind black supercomputer racks in a data center
Learning Hub

Kubernetes SELinux Volume Labeling: What Cluster Operators Should Audit Before v1.37

June 8, 2026
SXZ.io SXZ.io
  • [email protected]

Categories

Articles
Learning Hub
News

All Rights Reserved by SXZ.io ©2026