Database Buffer Pool Management: Bridging In-Memory Speed and Disk Persistence

Database storage engines cannot operate on data directly from disk; data pages must first be copied into volatile memory (RAM) before query execution engines can read, scan, or modify them. Because available system RAM is strictly smaller than total database size, engines manage an in-memory memory region known as the **Buffer Pool** (or Buffer Cache).

Rather than relying on the operating system's unified page cache—which lacks domain knowledge of database transaction boundaries, query execution semantics, and Write-Ahead Logging (WAL) dependencies—database engines implement custom buffer managers. The buffer pool controls page allocation, concurrency pinning, replacement eviction policies, and asynchronous dirty-page flushes to minimize expensive disk I/O operations.

Buffer Pool Architecture & Frame Descriptors

The Buffer Pool is allocated as a contiguous array of fixed-size memory blocks called **Page Frames** (matching the on-disk page size, typically 8 KB or 16 KB). The buffer manager maintains two core components to coordinate these frames:

1. Page Table (Frame Hash Map)

An in-memory concurrent hash table that maps a physical page identifier (`page_id` = file descriptor + block offset) to the specific in-memory frame index currently holding that page.

2. Frame Descriptors (Page Metadata)

Every memory frame has an associated metadata descriptor storing its operational status:

• Pin Count (Reference / Fix Count): Tracks how many active worker threads are currently reading or writing to the page. A page with `pin_count > 0` is pinned and cannot be evicted from RAM.
• Dirty Bit: Set to true whenever a transaction modifies the page contents in RAM, signaling that the page must be flushed to disk before the frame can be repurposed.
• Page LSN (Log Sequence Number): Records the LSN of the latest WAL record modifying this page, enforcing the WAL invariant before disk writes.
• Frame Latches (Read/Write Locks): Lightweight in-memory synchronization locks (shared for readers, exclusive for writers) preventing race conditions while mutating page bytes.

Page Request Lifecycle: Pinning and Unpinning

When an execution operator requires access to page $P$:

1. Lookup: Query the Page Table for $P$. If found (Cache Hit), increment $P$'s `pin_count`, acquire the appropriate frame latch (Shared/Exclusive), and return the memory pointer.
2. Cache Miss Allocation: If $P$ is not in RAM, select a candidate frame for eviction using the replacement policy (filtering out pinned pages where `pin_count > 0`).
3. Eviction & Flush: If the victim page is dirty, flush its preceding WAL records to disk, flush the dirty page to its table file, remove the victim from the Page Table, and clear the frame.
4. Disk Read: Read page $P$ from persistent storage into the freed frame, register $P$ in the Page Table, set `pin_count = 1`, and return the frame pointer.
5. Unpinning: Once the query operator finishes with the page, it releases its frame latch and decrements `pin_count`. When `pin_count` reaches 0, the page becomes eligible for future eviction.

Page Replacement Policies: Beyond Basic LRU

While standard Least Recently Used (LRU) performs well for random access, it fails catastrophically during sequential table scans: scanning a large table flushes out frequently accessed hot pages (known as 'buffer pool pollution' or scan resistance).

1. CLOCK (Second-Chance Algorithm)

Maintains a circular array of unpinned frames with a sweeping 'clock hand'. Each frame has a usage bit (set to 1 on access). When looking for an eviction candidate, if the hand encounters a bit of 1, it resets the bit to 0 and advances. If it encounters a bit of 0, that frame is chosen for eviction. Operates in $O(1)$ without linked list mutex bottlenecks.

2. LRU-K (O'Neil et al.)

Tracks the timestamp of the last $K$ accesses for every page (commonly LRU-2). Pages are prioritized based on the time elapsed since their $K$-th backward reference rather than their most recent access. Infrequently scanned pages have an infinite $K$-distance, making them candidates for immediate eviction while protecting repeatedly accessed index pages.

3. 2Q (Two-Queue) & Clock-Pro

Divides the buffer pool into two separate queues: a probationary FIFO queue for single-access pages (capturing sequential scans) and a main LRU queue for frequently referenced pages. Pages only graduate to the main queue after receiving a second access within a sliding time window.

C++ Conceptual Simulation Blueprint (CLOCK Page Replacement Buffer Manager)

#include <iostream>
#include <vector>
#include <unordered_map>

struct FrameDescriptor {
    int pageId = -1;
    int pinCount = 0;
    bool isDirty = false;
    bool usageBit = false;
};

class BufferPoolManager {
private:
    size_t poolSize;
    std::vector<FrameDescriptor> frames;
    std::unordered_map<int, size_t> pageTable; // pageId -> frameIndex
    size_t clockHand = 0;

    int findVictimFrame() {
        size_t scans = 0;
        while (scans < 2 * poolSize) {
            auto& frame = frames[clockHand];
            if (frame.pinCount == 0) {
                if (frame.usageBit) {
                    frame.usageBit = false;
                } else {
                    int victim = clockHand;
                    clockHand = (clockHand + 1) % poolSize;
                    return victim;
                }
            }
            clockHand = (clockHand + 1) % poolSize;
            scans++;
        }
        return -1; // All pages are pinned
    }

public:
    BufferPoolManager(size_t size) : poolSize(size), frames(size) {}

    int fetchPage(int pageId) {
        // 1. Cache Hit
        if (pageTable.count(pageId)) {
            size_t frameIdx = pageTable[pageId];
            frames[frameIdx].pinCount++;
            frames[frameIdx].usageBit = true;
            return frameIdx;
        }

        // 2. Cache Miss: Find victim
        int frameIdx = findVictimFrame();
        if (frameIdx == -1) return -1; // Buffer pool full of pinned pages

        auto& victimFrame = frames[frameIdx];
        if (victimFrame.pageId != -1) {
            if (victimFrame.isDirty) {
                // In production: flush WAL and write dirty page to disk
            }
            pageTable.erase(victimFrame.pageId);
        }

        // 3. Load requested page into frame
        victimFrame.pageId = pageId;
        victimFrame.pinCount = 1;
        victimFrame.isDirty = false;
        victimFrame.usageBit = true;
        pageTable[pageId] = frameIdx;

        return frameIdx;
    }

    void unpinPage(int pageId, bool isDirty) {
        if (!pageTable.count(pageId)) return;
        size_t frameIdx = pageTable[pageId];
        if (isDirty) frames[frameIdx].isDirty = true;
        if (frames[frameIdx].pinCount > 0) {
            frames[frameIdx].pinCount--;
        }
    }
};

Real-World Database Implementations

1. PostgreSQL Shared Buffers: Uses the CLOCK sweep algorithm combined with a private backend buffer ring for sequential scans to prevent table-scan pollution.
2. MySQL InnoDB Buffer Pool: Implements a midpoint-insertion modified LRU list (dividing the list into 5/8 old sublist and 3/8 young sublist) alongside dedicated page-cleaner background flush threads.
3. SQLite Pcache: Modular page cache subsystem supporting both LRU and customized OS memory allocation configurations across embedded devices.
4. Modern Vectorized OLAP Engines: Bypassing OS page buffers entirely via direct I/O (`O_DIRECT`) to execute explicit columnar memory staging and asynchronous NVMe prefetching.