Buffer pool

Deep dive

How it works

Parts:

• frames — fixed array of page-sized memory slots
• page table — hash map page ID → frame
• pin count — number of users of a frame; pinned frames are not evictable
• dirty bit — frame differs from disk and must be written back
• replacer — picks the victim (clock-sweep, midpoint LRU, S3-FIFO)
• background writer and checkpointer — clean dirty frames ahead of demand

page table (hash)         frames                       metadata per frame
 page 17 → 2        [0][1][2][3]...[N-1]         page_id, pin, dirty, ref bit / LRU links
 page 90 → 0              ▲ clock hand sweeps for victims with pin == 0

1. fetch(page): look it up in the page table. On a hit, increment pin and set the reference bit.
2. Miss: choose a victim frame with pin = 0 (CLOCK: skip pinned frames, clear set reference bits, take the first with a clear bit). If the victim is dirty, make sure the log is flushed through its pageLSN, then write it back. Read the new page into the frame and update the page table.
3. Use: take the frame's read or write latch (short-term, a physical lock) to access the bytes.
4. unpin(frame, dirty): decrement pin and OR in the dirty flag.
5. Background writer cleans dirty pages ahead of the clock hand so foreground misses rarely write. The checkpointer writes everything dirty up to a point in the log.

Code

use std::collections::HashMap;
use std::fs::File;
use std::io;
use std::os::unix::fs::FileExt;
use std::sync::{Mutex, RwLock};

pub const PAGE: usize = 8192;

struct Meta { page: Option<u64>, pin: u32, dirty: bool, refbit: bool }
struct Inner { table: HashMap<u64, usize>, meta: Vec<Meta>, hand: usize }

pub struct BufferPool { file: File, inner: Mutex<Inner>, pub frames: Vec<RwLock<Box<[u8]>>> }

impl BufferPool {
    pub fn new(file: File, n: usize) -> Self {
        let meta = (0..n).map(|_| Meta { page: None, pin: 0, dirty: false, refbit: false }).collect();
        let frames = (0..n).map(|_| RwLock::new(vec![0u8; PAGE].into_boxed_slice())).collect();
        BufferPool { file, inner: Mutex::new(Inner { table: HashMap::new(), meta, hand: 0 }), frames }
    }

    /// Pins `page` and returns its frame. Latch `frames[f]` to access it; drop the latch, then `unpin`.
    pub fn fetch(&self, page: u64) -> io::Result<usize> {
        let mut g = self.inner.lock().unwrap();
        if let Some(&f) = g.table.get(&page) {
            let m = &mut g.meta[f];
            m.pin += 1;
            m.refbit = true;
            return Ok(f);
        }
        let f = Self::clock_victim(&mut g).ok_or_else(|| io::Error::other("all frames pinned"))?;
        let mut buf = self.frames[f].write().unwrap(); // pin == 0, so nobody holds this latch
        if let Some(old) = g.meta[f].page {
            if g.meta[f].dirty { // WAL rule: the log must be durable through this page's LSN first
                self.file.write_all_at(&buf, old * PAGE as u64)?;
                g.meta[f].dirty = false;
            }
            g.table.remove(&old);
            g.meta[f].page = None;
        }
        // Simplification: real pools release the pool mutex during I/O and mark the frame "loading".
        self.file.read_exact_at(&mut buf, page * PAGE as u64)?;
        g.meta[f] = Meta { page: Some(page), pin: 1, dirty: false, refbit: true };
        g.table.insert(page, f);
        Ok(f)
    }

    fn clock_victim(g: &mut Inner) -> Option<usize> {
        let n = g.meta.len();
        for _ in 0..2 * n { // first sweep may only clear reference bits
            let f = g.hand;
            g.hand = (g.hand + 1) % n;
            let m = &mut g.meta[f];
            if m.pin > 0 { continue; }
            if m.refbit { m.refbit = false; continue; } // second chance
            return Some(f);
        }
        None
    }

    pub fn unpin(&self, f: usize, dirty: bool) {
        let mut g = self.inner.lock().unwrap();
        let m = &mut g.meta[f];
        m.pin -= 1;
        m.dirty |= dirty;
    }

    pub fn flush_all(&self) -> io::Result<()> {
        let mut g = self.inner.lock().unwrap();
        for f in 0..g.meta.len() {
            if let (Some(p), true) = (g.meta[f].page, g.meta[f].dirty) {
                self.file.write_all_at(&self.frames[f].read().unwrap(), p * PAGE as u64)?;
                g.meta[f].dirty = false;
            }
        }
        self.file.sync_data()
    }
}

Complexity and constants

• Hit path: hash lookup + pin increment + latch: order of 50-200 ns. Under many cores, a single pool mutex caps throughput at a few million fetches/s. Partition it.
• Metadata per frame: order of 50-100 B. For 8 KiB pages that is about 1 % of the pool.
• Miss: one 8-16 KiB random read. NVMe sustains order of 10⁵-10⁶ such reads/s per device with deep queues (io_uring), so the bottleneck is often the miss path's CPU cost, not the device.
• Dirty eviction in the foreground doubles miss latency. Background cleaning keeps a pool of clean victims.

Efficiency

• Cost: a hit is order of 100 ns; a miss is one page read (10-100 µs on NVMe, ms on HDD) plus one write when the victim is dirty. Bound: miss latency, and on hits contention on the pool's shared structures.
• Levers:
  • size the pool to the working set, then a better policy (S3-FIFO, W-TinyLFU) — higher hit rate than plain LRU — random-access workloads
  • small buffer ring (PostgreSQL 256 KiB) or midpoint insertion — scans do not flush the cache — big scans
  • background writer — clean victims ready, foreground misses rarely write — write-heavy loads
  • partitioned pool, atomic pin counts, pointer swizzling (LeanStore), huge pages — cheaper hit path, fewer TLB misses — hot in-memory working sets
  • read-ahead and deep NVMe queues (io_uring), O_DIRECT — hides read latency, no double caching — sequential or cold access
• Naive → standard → state of the art:
  • mmap or OS cache, engine has no control · unpredictable eviction and write order
  • own pool with hash table and clock or midpoint LRU · hit about 100 ns, controlled I/O
  • swizzled pointers, optimistic latching (LeanStore) · in-memory speed on hits

Implementation notes

• Bypass the OS cache: O_DIRECT (InnoDB innodb_flush_method=O_DIRECT) avoids caching each page twice. PostgreSQL uses buffered I/O and relies on the OS cache as a second tier.
• Partitioning: N pool instances (InnoDB innodb_buffer_pool_instances) or a lock-free page table. Pin counts can be atomics in the frame header.
• Scan resistance: midpoint insertion (InnoDB keeps new pages in an "old" sublist for innodb_old_blocks_time ms) or ring buffers for scans and VACUUM. Plain LRU is flushed by one big table scan.
• Pointer swizzling (LeanStore): replace page IDs inside B-tree nodes with direct pointers to hot frames, so a hit needs no hash lookup.
• Huge pages for the frame array cut TLB misses; on Linux 2 MiB pages are often worth it for pools of tens of GB.
• Prefetch: read-ahead on detected sequential access, index-driven prefetch for nested loops.

Pitfalls

• mmap as a buffer pool: no control over eviction or write-back order (it breaks the WAL rule unless you add copies), I/O stalls hit as page faults, TLB shootdowns on eviction, and SIGBUS on I/O errors. Crotty et al. document these failures.
• Pin leaks: an error path forgets to unpin, and the pool eventually runs out of evictable frames. Use RAII guards.
• Holding the pool mutex or a page latch during I/O serializes every thread behind one disk read.
• Evicting a dirty page before its log records are durable. Recovery then cannot undo or redo it.
• Double caching with buffered I/O wastes RAM: a 50 % pool plus the same pages in the OS cache.

Variants and alternatives

In production

• Databases: PostgreSQL shared buffers (clock-sweep), InnoDB buffer pool (midpoint LRU), SQL Server, Oracle buffer cache, WiredTiger cache.
• File systems and operating systems: the Linux page cache; ZFS ARC.
• Key-value stores: the RocksDB block cache (the immutable-file variant).
• Research: LeanStore and Umbra.

Implementations

Sources

• E. O'Neil, P. O'Neil, G. Weikum, The LRU-K Page Replacement Algorithm for Database Disk Buffering, SIGMOD, 1993. paper
• T. Johnson, D. Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, VLDB, 1994. paper
• N. Megiddo, D. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, FAST, 2003. paper
• V. Leis et al., LeanStore: In-Memory Data Management Beyond Main Memory, ICDE, 2018. paper · code
• A. Crotty, V. Leis, A. Pavlo, Are You Sure You Want to Use MMAP in Your Database Management System?, CIDR, 2022. paper
• V. Leis, A. Alhomssi, T. Ziegler, Y. Loeck, C. Dietrich, Virtual-Memory Assisted Buffer Management, SIGMOD, 2023. paper · code