解析 ‘Database Buffer Pool’：如何利用 C++ 实现一个具备 LRU-K 淘汰算法的高性能页管理系统

各位编程专家、数据库系统设计爱好者们：

今天，我们将深入探讨一个数据库核心组件——数据库缓冲池（Database Buffer Pool）的实现。它在高性能数据库系统中扮演着至关重要的角色，是连接高速内存与低速持久化存储之间的桥梁。我们将聚焦于如何利用 C++ 构建一个具备先进的 LRU-K 淘汰算法的页管理系统，并确保其高性能和逻辑严谨性。

1. 数据库缓冲池：核心概念与重要性

数据库系统的数据主要存储在磁盘上，而 CPU 访问数据首先需要将其加载到内存中。磁盘 I/O 的速度远低于内存访问速度，这之间的巨大性能鸿沟是数据库系统面临的主要挑战之一。缓冲池正是为了弥补这一鸿沟而生。

什么是缓冲池？
缓冲池是数据库系统在主内存中维护的一块区域，用于缓存从磁盘读取的数据页（或称块、Page）。当数据库需要访问某个数据页时，它首先检查该页是否已存在于缓冲池中。如果存在（缓存命中），则直接从内存中读取，避免了昂贵的磁盘 I/O；如果不存在（缓存未命中），则从磁盘读取该页并将其加载到缓冲池中，同时可能需要根据某种策略淘汰掉缓冲池中已有的某个页。

为什么缓冲池如此重要？

1. 降低磁盘 I/O： 这是最主要的目的。通过缓存常用数据页，显著减少了物理磁盘的读写操作。
2. 提高数据访问速度： 内存访问速度远超磁盘，缓存命中可以大幅提升查询和事务处理的速度。
3. 支持并发控制与恢复： 缓冲池中的页通常带有“脏页”标志，记录了数据页是否被修改但尚未写入磁盘。这对于事务的持久性（Durability）和恢复机制至关重要。
4. 管理页面生命周期： 缓冲池负责页面的载入、固定（pin）、解固定（unpin）、刷新（flush）和淘汰（evict）。

缓冲池的核心功能：

• FetchPage(PageId page_id)： 从缓冲池获取指定页。如果页不在缓冲池中，则从磁盘加载。
• UnpinPage(PageId page_id, bool is_dirty)： 解固定指定页，并标记其是否为脏页。
• NewPage(PageId& page_id)： 在缓冲池中创建一个新页，并分配一个唯一 PageId。
• DeletePage(PageId page_id)： 从缓冲池中删除指定页。
• FlushPage(PageId page_id)： 将指定脏页强制写入磁盘。
• FlushAllPages()： 将缓冲池中所有脏页强制写入磁盘。

2. 页淘汰算法：LRU-K 的选择与原理

当缓冲池满时，需要加载新页，就必须选择一个旧页将其淘汰出去，以腾出空间。这个选择过程由页淘汰算法（Page Eviction Policy）决定。一个好的淘汰算法能够最大化缓存命中率，减少不必要的磁盘 I/O。

常见的淘汰算法：	算法名称	原理	优点	缺点	适用场景
FIFO	先进先出，淘汰最先进入缓冲池的页。	实现简单。	与页的使用频率无关，可能淘汰常用页。	简单场景，对性能要求不高。
LRU	最近最少使用，淘汰最长时间未被访问的页。	通常命中率较高，符合局部性原理。	无法抵御全表扫描（导致缓存污染）。	局部性好的工作负载。
LFU	最不经常使用，淘汰访问频率最低的页。	能够识别长期热点页。	实现较复杂，无法适应访问模式变化（旧热点页可能长期不被淘汰）。	长期稳定热点数据。
Clock	LRU 的近似实现，使用一个循环队列和引用位。	兼顾 LRU 效果和实现开销。	依然可能受到全表扫描影响。	多数通用数据库系统。
LRU-K	记录每个页的 K 次访问历史，淘汰 K 次访问时间最久的页。	更好地识别热点页，抵御全表扫描，适应性强。	实现复杂，开销较大。	高性能、复杂工作负载。

为什么选择 LRU-K？
简单的 LRU 算法在面对全表扫描（Sequential Scan）时表现不佳。例如，如果缓冲池只能容纳 N 个页，而一个表有 N+1 个页，进行全表扫描会导致每个页被加载一次，然后立即被淘汰，缓存命中率为零。这种现象称为缓存污染（Cache Pollution）。

LRU-K 算法通过记录每个页的 K 次历史访问时间戳，有效地解决了 LRU 的这一痛点。

• LRU-K 的核心思想： 对于每个页，我们不仅关注它最近一次的访问时间，而是关注它第 K 次访问的时间。当需要淘汰页时，我们选择那些第 K 次访问时间最久远的页进行淘汰。如果一个页的访问历史不足 K 次，则可以将其视为“新页”或“不够热”的页，并使用其第一次访问时间作为 K-th 访问时间进行比较。
• 抵御全表扫描： 假设 K=2。一个页只有在被访问过两次之后，才有可能进入 LRU-K 的“稳定”状态，其 K-th 访问时间才具有参考价值。对于扫描操作，一个页可能只被访问一次，其 K-th 访问时间（即第一次访问时间）会相对较新，因此不会轻易被淘汰。只有那些频繁（至少 K 次）访问的页才能在缓冲池中长期驻留。
• 更好的热点识别： LRU-K 能够区分出“偶尔访问”的页和“持续热门”的页，从而更准确地保留真正重要的热点数据。

LRU-K 的挑战：

• 实现复杂性： 需要维护每个页的访问历史，管理时间戳列表。
• 内存开销： 存储访问历史需要额外的内存。K 值越大，开销越大。
• 计算开销： 淘汰时需要比较 K-th 访问时间，可能涉及排序或遍历。

尽管存在这些挑战，LRU-K 在现代数据库系统中因其卓越的性能表现而被广泛采用。我们将实现一个 LRU-K 淘汰器作为我们缓冲池的核心组件。

3. 核心组件设计

一个高性能的数据库缓冲池通常由以下几个核心组件构成：

1. Page (数据页)： 封装了实际的数据内容，以及页的元数据（PageId, pin_count, is_dirty）。
2. DiskManager (磁盘管理器)： 模拟磁盘 I/O 操作，负责从磁盘读写数据页。
3. Replacer (淘汰器)： 实现页淘汰算法，负责选择待淘汰的页。我们将实现 LRU-K Replacer。
4. BufferPoolManager (缓冲池管理器)： 协调所有组件，提供对外接口，管理缓冲池中的所有页。
5. FreeList (空闲帧列表)： 记录缓冲池中可用的空闲内存帧（frame）。
6. Latch (锁)： 用于并发控制，确保多个线程访问缓冲池时的数据一致性。

下面我们逐一深入实现这些组件。

3.1 Page 类

Page 类是缓冲池中数据页的抽象。每个 Page 对象对应缓冲池中的一个内存帧。

#include <atomic>
#include <array>

// 定义 PageId 和 FrameId 类型
using PageId = int;
using FrameId = int;

// 定义页大小 (例如 4KB)
const int PAGE_SIZE = 4096;

/**
 * @brief Page 类表示缓冲池中的一个数据页。
 *        它包含页的实际数据、元数据（ID、固定计数、脏页标志）。
 */
class Page {
public:
    Page() {
        ResetMemory();
    }

    ~Page() = default;

    // 获取页的数据指针
    char* GetData() {
        return data_;
    }

    // 获取页的 ID
    PageId GetPageId() const {
        return page_id_;
    }

    // 获取页的固定计数
    int GetPinCount() const {
        return pin_count_;
    }

    // 判断页是否为脏页 (被修改但未写入磁盘)
    bool IsDirty() const {
        return is_dirty_;
    }

    // 增加固定计数
    void IncPinCount() {
        pin_count_++;
    }

    // 减少固定计数
    void DecPinCount() {
        if (pin_count_ > 0) {
            pin_count_--;
        }
    }

    // 设置脏页标志
    void SetDirty(bool dirty) {
        is_dirty_ = dirty;
    }

    // 设置页 ID
    void SetPageId(PageId page_id) {
        page_id_ = page_id;
    }

    // 重置页的所有状态和数据
    void ResetMemory() {
        page_id_ = -1; // -1 表示无效页
        pin_count_ = 0;
        is_dirty_ = false;
        std::fill(data_.begin(), data_.end(), 0); // 清空数据
    }

private:
    std::array<char, PAGE_SIZE> data_; // 页的实际数据
    PageId page_id_;                   // 页的唯一标识符
    int pin_count_;                    // 固定计数：表示有多少个线程或组件正在使用此页。
                                       // 当 pin_count > 0 时，此页不能被淘汰。
    bool is_dirty_;                    // 脏页标志：如果页数据被修改过，则为 true。
                                       // 脏页在被淘汰前必须写入磁盘。
};

3.2 DiskManager 类 (模拟实现)

DiskManager 负责模拟磁盘的读写操作。在实际系统中，它会与文件系统交互。为了简化，我们使用 std::map 来模拟磁盘上的数据存储。

#include <string>
#include <map>
#include <fstream> // 真实磁盘管理器可能需要
#include <iostream>

/**
 * @brief DiskManager 类模拟磁盘的读写操作。
 *        在实际数据库中，这将与文件系统进行交互。
 */
class DiskManager {
public:
    DiskManager() : next_page_id_(0) {
        // 可以在构造函数中初始化文件等
        // For simulation, we just use an in-memory map
    }

    // 从磁盘读取一个页的数据
    void ReadPage(PageId page_id, char* data) {
        if (disk_data_.count(page_id)) {
            // 模拟从磁盘读取数据
            std::copy(disk_data_[page_id].begin(), disk_data_[page_id].end(), data);
            // std::cout << "DiskManager: Read page " << page_id << " from disk." << std::endl;
        } else {
            // std::cerr << "DiskManager: Page " << page_id << " not found on disk." << std::endl;
            // 如果页不存在，填充空数据
            std::fill(data, data + PAGE_SIZE, 0);
        }
    }

    // 将一个页的数据写入磁盘
    void WritePage(PageId page_id, const char* data) {
        // 模拟写入磁盘
        disk_data_[page_id].assign(data, data + PAGE_SIZE);
        // std::cout << "DiskManager: Write page " << page_id << " to disk." << std::endl;
    }

    // 分配一个新的页 ID
    PageId AllocatePage() {
        return next_page_id_++;
    }

    // 解分配一个页 (模拟删除磁盘上的页)
    void DeallocatePage(PageId page_id) {
        disk_data_.erase(page_id);
        // std::cout << "DiskManager: Deallocate page " << page_id << " from disk." << std::endl;
    }

    // 获取当前已分配的最大页 ID
    PageId GetNextPageId() const {
        return next_page_id_;
    }

private:
    PageId next_page_id_; // 下一个可分配的页 ID
    // 模拟磁盘上的数据存储，实际中会是文件 I/O
    std::map<PageId, std::vector<char>> disk_data_;
};

3.3 LRUKReplacer 类 (LRU-K 淘汰器)

这是我们实现的核心。LRUKReplacer 负责根据 LRU-K 策略选择一个合适的页进行淘汰。

#include <list>
#include <set>
#include <chrono>
#include <algorithm> // for std::min, std::find

/**
 * @brief LRUKReplacer 类实现了 LRU-K 页淘汰算法。
 *        它维护每个帧的 K 次访问历史，并根据这些历史信息来决定淘汰哪个帧。
 */
class LRUKReplacer {
public:
    /**
     * @brief 构造函数。
     * @param buffer_size 缓冲池的总帧数。
     * @param k LRU-K 算法的参数 K。
     */
    LRUKReplacer(size_t buffer_size, size_t k) :
        buffer_size_(buffer_size), k_(k), current_timestamp_(0) {
    }

    ~LRUKReplacer() = default;

    // 记录一个帧的访问。
    // 每当一个帧被访问时，调用此方法来更新其访问历史。
    void RecordAccess(FrameId frame_id) {
        // 确保帧 ID 有效
        if (frame_id < 0 || static_cast<size_t>(frame_id) >= buffer_size_) {
            return;
        }

        current_timestamp_++; // 每次访问都增加全局时间戳

        // 如果帧是新的，初始化其历史记录
        if (history_timestamps_.find(frame_id) == history_timestamps_.end()) {
            history_timestamps_[frame_id] = std::list<long long>();
        }

        // 添加当前时间戳到历史记录
        history_timestamps_[frame_id].push_back(current_timestamp_);

        // 如果历史记录超过 K，移除最旧的访问时间
        if (history_timestamps_[frame_id].size() > k_) {
            history_timestamps_[frame_id].pop_front();
        }
    }

    // 标记一个帧为已固定 (pinned)，它将不能被淘汰。
    void Pin(FrameId frame_id) {
        // 确保帧 ID 有效
        if (frame_id < 0 || static_cast<size_t>(frame_id) >= buffer_size_) {
            return;
        }

        // 从 unpinned 集合中移除
        unpinned_frames_.erase(frame_id);

        // 清除历史记录，因为 pinned 的帧通常不参与淘汰，且其历史记录在 Unpin 后可能会重新计算
        // 也可以选择保留历史记录，这取决于具体设计，但清除可以简化逻辑
        // history_timestamps_.erase(frame_id);
    }

    // 标记一个帧为未固定 (unpinned)，它现在可以被淘汰。
    void Unpin(FrameId frame_id) {
        // 确保帧 ID 有效
        if (frame_id < 0 || static_cast<size_t>(frame_id) >= buffer_size_) {
            return;
        }

        // 如果该帧之前没有历史记录，初始化一个空的
        if (history_timestamps_.find(frame_id) == history_timestamps_.end()) {
             history_timestamps_[frame_id] = std::list<long long>();
        }

        // 将帧添加到 unpinned 集合中
        unpinned_frames_.insert(frame_id);
    }

    // 选择一个帧进行淘汰，并返回其 FrameId。
    // 如果没有可淘汰的帧，返回 false。
    bool Evict(FrameId* frame_id) {
        if (unpinned_frames_.empty()) {
            return false; // 没有可淘汰的帧
        }

        long long min_k_timestamp = -1; // 记录最小的 K-th 访问时间
        long long min_first_timestamp = -1; // 用于 K-th 访问时间相同时的 LRU 规则
        FrameId candidate_frame_id = -1; // 待淘汰的帧 ID

        // 遍历所有未固定的帧
        for (FrameId current_frame_id : unpinned_frames_) {
            auto it = history_timestamps_.find(current_frame_id);
            if (it == history_timestamps_.end() || it->second.empty()) {
                // 这个帧没有访问历史，通常意味着它是一个新帧，或者在Pin后没有RecordAccess
                // 暂时不考虑这种边缘情况，或者默认其K-th访问时间为0 (最老)
                // 更严谨的做法是，如果K-th访问时间不存在，则使用一个特殊值或视为最旧
                // 这里我们假设所有unpinned帧都有至少一个访问记录（在Unpin之前会RecordAccess）
                continue; 
            }

            const auto& timestamps = it->second;
            long long current_k_timestamp;
            long long current_first_timestamp;

            if (timestamps.size() < k_) {
                // 如果历史记录不足 K 次，使用第一次访问时间作为 K-th 访问时间
                current_k_timestamp = timestamps.front();
            } else {
                // 否则，使用第 K 次访问时间 (即列表中的第一个元素，因为我们只保留 K 个)
                current_k_timestamp = timestamps.front();
            }
            current_first_timestamp = timestamps.front(); // 总是取列表的第一个作为 LRU 规则的依据

            // 初始化第一个候选帧
            if (candidate_frame_id == -1) {
                min_k_timestamp = current_k_timestamp;
                min_first_timestamp = current_first_timestamp;
                candidate_frame_id = current_frame_id;
                continue;
            }

            // 比较 K-th 访问时间
            if (current_k_timestamp < min_k_timestamp) {
                min_k_timestamp = current_k_timestamp;
                min_first_timestamp = current_first_timestamp;
                candidate_frame_id = current_frame_id;
            } else if (current_k_timestamp == min_k_timestamp) {
                // 如果 K-th 访问时间相同，则使用 LRU 规则 (第一次访问时间最久远的) 作为 tie-breaker
                if (current_first_timestamp < min_first_timestamp) {
                    min_first_timestamp = current_first_timestamp;
                    candidate_frame_id = current_frame_id;
                }
            }
        }

        if (candidate_frame_id != -1) {
            *frame_id = candidate_frame_id;
            // 从内部数据结构中移除被淘汰的帧
            unpinned_frames_.erase(candidate_frame_id);
            history_timestamps_.erase(candidate_frame_id);
            return true;
        }

        return false;
    }

    // 获取当前可淘汰的帧数量。
    size_t Size() const {
        return unpinned_frames_.size();
    }

private:
    size_t buffer_size_; // 缓冲池总大小 (帧数量)
    size_t k_;           // LRU-K 算法的参数 K
    long long current_timestamp_; // 全局时间戳，用于记录访问时间

    // 存储每个帧的 K 次访问时间戳历史。
    // map: FrameId -> list of timestamps (list按时间顺序存储，front是最旧的，back是最近的)
    std::map<FrameId, std::list<long long>> history_timestamps_;

    // 存储所有当前未固定 (unpinned) 且可供淘汰的帧 ID。
    std::set<FrameId> unpinned_frames_;
};

LRUKReplacer 核心逻辑解释：

• history_timestamps_: 这是一个 std::map<FrameId, std::list<long long>>，其中 key 是 FrameId，value 是一个 std::list，存储了该帧最近 K 次的访问时间戳。list 的 front() 始终是该帧的第 K 次（或更少）最旧的访问时间，而 back() 则是最近一次访问时间。
• RecordAccess(FrameId frame_id): 每次访问页时，增加全局时间戳 current_timestamp_，并将其添加到对应 frame_id 的 list 末尾。如果 list 大小超过 k_，则移除 list 的 front() 元素，确保只保留 K 个最新访问记录。
• Pin(FrameId frame_id): 将帧从 unpinned_frames_ 集合中移除，使其不能被淘汰。
• Unpin(FrameId frame_id): 将帧添加到 unpinned_frames_ 集合中，使其可以被淘汰。
• Evict(FrameId* frame_id): 这是淘汰算法的核心。
  1. 遍历 unpinned_frames_ 集合中的所有帧。
  2. 对于每个帧，获取其 history_timestamps_。
  3. 如果 timestamps.size() < k_，说明该帧的访问历史不足 K 次，我们将其 K-th 访问时间视为其第一次访问时间（即 timestamps.front()）。
  4. 如果 timestamps.size() >= k_，则其 K-th 访问时间就是 timestamps.front()。
  5. 我们寻找具有最小 K-th 访问时间的帧作为候选。
  6. Tie-breaker (破局规则): 如果有多个帧具有相同的最小 K-th 访问时间，我们进一步比较它们的第一次访问时间（即 timestamps.front()），选择第一次访问时间更早的帧（即更符合 LRU 规则）进行淘汰。
  7. 一旦找到最佳候选帧，将其从 unpinned_frames_ 和 history_timestamps_ 中移除，并返回其 FrameId。

3.4 BufferPoolManager 类

BufferPoolManager 是缓冲池的核心控制器，它将上述所有组件整合起来，提供完整的页管理功能。

#include <mutex>
#include <vector>
#include <deque> // 用于 FreeList
#include <unordered_map> // 替代 map 提高查找效率

/**
 * @brief BufferPoolManager 类负责管理缓冲池中的所有页面。
 *        它协调 DiskManager 和 Replacer 来实现页面的加载、固定、淘汰等操作。
 */
class BufferPoolManager {
public:
    /**
     * @brief 构造函数。
     * @param pool_size 缓冲池中的帧数量。
     * @param k LRU-K 算法的参数 K。
     * @param disk_manager_ptr 磁盘管理器指针。
     */
    BufferPoolManager(size_t pool_size, size_t k, DiskManager* disk_manager_ptr)
        : pool_size_(pool_size),
          disk_manager_(disk_manager_ptr),
          replacer_(pool_size, k),
          next_page_id_(0) { // 从 DiskManager 获取初始 next_page_id

        // 初始化缓冲池中的所有 Page 对象
        pages_ = new Page[pool_size_];

        // 将所有帧添加到空闲列表中
        for (size_t i = 0; i < pool_size_; ++i) {
            free_list_.push_back(static_cast<FrameId>(i));
            pages_[i].SetPageId(INVALID_PAGE_ID); // 初始化为无效页
        }
    }

    ~BufferPoolManager() {
        // 确保所有脏页都被刷回磁盘
        FlushAllPages();
        delete[] pages_;
    }

    // 从缓冲池获取一个页。如果页不在缓冲池中，则从磁盘加载。
    // 如果缓冲池已满且没有可淘汰的页，返回 nullptr。
    Page* FetchPage(PageId page_id) {
        std::unique_lock<std::mutex> lock(latch_); // 保护共享资源

        // 1. 检查页是否已在缓冲池中
        if (page_table_.count(page_id)) {
            FrameId frame_id = page_table_[page_id];
            Page* page = &pages_[frame_id];
            page->IncPinCount(); // 增加固定计数
            replacer_.RecordAccess(frame_id); // 记录访问
            replacer_.Pin(frame_id); // 确保 pinned 的页不被淘汰
            return page;
        }

        // 2. 页不在缓冲池中，需要从磁盘加载
        FrameId frame_id = -1;

        // 尝试从空闲列表获取一个帧
        if (!free_list_.empty()) {
            frame_id = free_list_.front();
            free_list_.pop_front();
        } else {
            // 空闲列表为空，需要淘汰一个页
            if (!replacer_.Evict(&frame_id)) {
                // 没有可淘汰的页，缓冲池已满且所有页都被固定
                return nullptr;
            }

            // 淘汰的页可能是一个脏页，需要先写回磁盘
            Page* evicted_page = &pages_[frame_id];
            if (evicted_page->IsDirty()) {
                disk_manager_->WritePage(evicted_page->GetPageId(), evicted_page->GetData());
                evicted_page->SetDirty(false); // 刷盘后不再是脏页
            }
            // 从页表中移除被淘汰的页
            page_table_.erase(evicted_page->GetPageId());
        }

        // 3. 将新页加载到选定的帧中
        Page* new_page = &pages_[frame_id];
        new_page->ResetMemory(); // 重置帧的内存和元数据
        new_page->SetPageId(page_id);
        new_page->IncPinCount(); // 新加载的页默认固定
        new_page->SetDirty(false); // 从磁盘加载的页不是脏页

        disk_manager_->ReadPage(page_id, new_page->GetData()); // 从磁盘读取数据
        page_table_[page_id] = frame_id; // 更新页表

        replacer_.RecordAccess(frame_id); // 记录访问
        replacer_.Pin(frame_id); // 确保新加载的页被固定

        return new_page;
    }

    // 解固定一个页。
    // 如果 is_dirty 为 true，则标记页为脏页。
    void UnpinPage(PageId page_id, bool is_dirty) {
        std::unique_lock<std::mutex> lock(latch_);

        if (page_table_.count(page_id)) {
            FrameId frame_id = page_table_[page_id];
            Page* page = &pages_[frame_id];

            if (page->GetPinCount() <= 0) {
                // 尝试解固定一个未固定的页，可能表示逻辑错误
                // std::cerr << "Warning: Unpinning an already unpinned page " << page_id << std::endl;
                return;
            }

            page->DecPinCount();
            if (is_dirty) {
                page->SetDirty(true);
            }

            // 如果固定计数变为 0，则通知 replacer 该页现在可以被淘汰了
            if (page->GetPinCount() == 0) {
                replacer_.Unpin(frame_id);
            }
        }
    }

    // 在缓冲池中创建一个新页。
    // 如果缓冲池已满且没有可淘汰的页，返回 nullptr。
    Page* NewPage(PageId& page_id) {
        std::unique_lock<std::mutex> lock(latch_);

        FrameId frame_id = -1;

        // 尝试从空闲列表获取一个帧
        if (!free_list_.empty()) {
            frame_id = free_list_.front();
            free_list_.pop_front();
        } else {
            // 空闲列表为空，需要淘汰一个页
            if (!replacer_.Evict(&frame_id)) {
                return nullptr; // 没有可淘汰的页
            }

            // 淘汰的页可能是一个脏页，需要先写回磁盘
            Page* evicted_page = &pages_[frame_id];
            if (evicted_page->IsDirty()) {
                disk_manager_->WritePage(evicted_page->GetPageId(), evicted_page->GetData());
                evicted_page->SetDirty(false);
            }
            // 从页表中移除被淘汰的页
            page_table_.erase(evicted_page->GetPageId());
        }

        // 分配一个新的 PageId
        page_id = disk_manager_->AllocatePage();
        next_page_id_ = page_id + 1; // 更新下一个可用 PageId

        // 初始化新页
        Page* new_page = &pages_[frame_id];
        new_page->ResetMemory();
        new_page->SetPageId(page_id);
        new_page->IncPinCount(); // 新创建的页默认固定
        new_page->SetDirty(true); // 新创建的页默认是脏页

        page_table_[page_id] = frame_id; // 更新页表

        replacer_.RecordAccess(frame_id); // 记录访问
        replacer_.Pin(frame_id); // 确保新创建的页被固定

        return new_page;
    }

    // 从缓冲池中删除一个页。
    // 如果页当前被固定，则无法删除。
    void DeletePage(PageId page_id) {
        std::unique_lock<std::mutex> lock(latch_);

        if (!page_table_.count(page_id)) {
            return; // 页不在缓冲池中
        }

        FrameId frame_id = page_table_[page_id];
        Page* page = &pages_[frame_id];

        if (page->GetPinCount() > 0) {
            // std::cerr << "Error: Cannot delete pinned page " << page_id << std::endl;
            return; // 无法删除被固定的页
        }

        // 如果是脏页，先刷回磁盘 (尽管删除通常意味着不需要刷回，但为安全起见)
        if (page->IsDirty()) {
            disk_manager_->WritePage(page_id, page->GetData());
        }

        // 从页表中移除
        page_table_.erase(page_id);
        // 将帧标记为空闲，并重置其状态
        page->ResetMemory();
        free_list_.push_back(frame_id);

        // 通知 replacer 该帧现在是空闲的 (不再参与淘汰，可以清除其历史记录)
        // replacer_.Pin(frame_id); // 逻辑上，被删除的页应该从replacer中完全移除
        // LRUKReplacer 的 Evict 逻辑已经将其从 history_timestamps_ 中移除，这里只需确保它不再参与。
        // 由于它被放回 free_list_，在下次分配时会重新初始化并 RecordAccess。
        // 如果想更彻底，可以增加 replacer.Remove(frame_id) 方法。
        // 对于当前实现，当帧被 ResetMemory 并放回 free_list_ 时，其旧的 page_id 历史记录
        // 已经不重要了，因为下次分配时会赋予新的 page_id 和新的 history。
        disk_manager_->DeallocatePage(page_id); // 通知磁盘管理器释放该页 ID
    }

    // 将指定页强制写入磁盘。
    void FlushPage(PageId page_id) {
        std::unique_lock<std::mutex> lock(latch_);

        if (page_table_.count(page_id)) {
            FrameId frame_id = page_table_[page_id];
            Page* page = &pages_[frame_id];

            if (page->IsDirty()) {
                disk_manager_->WritePage(page_id, page->GetData());
                page->SetDirty(false);
                // std::cout << "BufferPoolManager: Flushed page " << page_id << " to disk." << std::endl;
            }
        }
    }

    // 将缓冲池中所有脏页强制写入磁盘。
    void FlushAllPages() {
        std::unique_lock<std::mutex> lock(latch_);

        for (size_t i = 0; i < pool_size_; ++i) {
            Page* page = &pages_[i];
            if (page->GetPageId() != INVALID_PAGE_ID && page->IsDirty()) {
                disk_manager_->WritePage(page->GetPageId(), page->GetData());
                page->SetDirty(false);
                // std::cout << "BufferPoolManager: Flushed all page " << page->GetPageId() << " to disk." << std::endl;
            }
        }
    }

    // 获取缓冲池大小
    size_t GetPoolSize() const {
        return pool_size_;
    }

    // 获取当前缓冲池中活跃的页数量
    size_t GetNumActivePages() const {
        return page_table_.size();
    }

private:
    static constexpr PageId INVALID_PAGE_ID = -1; // 无效页 ID

    size_t pool_size_; // 缓冲池中的帧数量
    Page* pages_;      // 实际存储 Page 对象的内存数组 (即缓冲池)

    // 页表：PageId 到 FrameId 的映射，用于快速查找页在缓冲池中的位置
    std::unordered_map<PageId, FrameId> page_table_; 

    DiskManager* disk_manager_; // 磁盘管理器
    LRUKReplacer replacer_;     // LRU-K 淘汰器

    // 空闲帧列表：存储当前可用的帧 ID
    std::deque<FrameId> free_list_; 

    PageId next_page_id_; // 用于分配新页 ID 的计数器

    std::mutex latch_; // 用于并发访问缓冲池的互斥锁
};

BufferPoolManager 核心逻辑解释：

• 内存管理： pages_ 是一个 Page 对象的数组，代表缓冲池中的所有内存帧。free_list_ 维护当前可用的帧 ID。
• 页表 (page_table_)： std::unordered_map<PageId, FrameId> 提供了 PageId 到 FrameId 的快速映射，是查找页是否在缓冲池中的关键。
• FetchPage：
  1. 首先检查 page_table_，如果命中，则增加 pin_count，记录访问，并通知 replacer 该帧被 Pin (因为 pin_count > 0)。
  2. 如果未命中，尝试从 free_list_ 获取空闲帧。
  3. 如果没有空闲帧，则调用 replacer_.Evict() 淘汰一个页。如果被淘汰的页是脏页，先将其刷回磁盘。然后将旧页从 page_table_ 中移除。
  4. 将新页从 disk_manager_ 读取到选定的帧中，更新 page_id、pin_count 等元数据，并添加到 page_table_。记录访问并 Pin 该帧。
• UnpinPage： 减少 pin_count。如果 pin_count 降为 0，则通知 replacer 该帧现在可以被淘汰 (Unpin)。同时根据 is_dirty 参数更新页的脏页标志。
• NewPage： 逻辑与 FetchPage 类似，但它首先从 disk_manager_ 获取一个新的 PageId，然后初始化帧为脏页。
• DeletePage： 检查 pin_count，如果页被固定，则无法删除。否则，将其从 page_table_ 移除，重置帧状态，并将其帧 ID 返回 free_list_。通知 disk_manager_ 释放该 PageId。
• FlushPage / FlushAllPages： 将脏页数据通过 disk_manager_ 写入磁盘，并清除脏页标志。
• 并发控制： std::mutex latch_ 用于保护缓冲池的内部状态，所有关键操作都通过 std::unique_lock 获取锁，确保线程安全。

4. 完整的示例与使用

现在，我们将所有组件整合到一个简单的 main 函数中，演示缓冲池的基本操作和 LRU-K 淘汰算法的行为。

#include <iostream>
#include <thread>
#include <vector>
#include <random> // 用于模拟随机访问

// 包含所有头文件
// Page.hpp
// DiskManager.hpp
// LRUKReplacer.hpp
// BufferPoolManager.hpp

// 为了演示，我们将所有类定义放在同一个文件，实际项目中应分开
// ... (前面定义的 Page, DiskManager, LRUKReplacer, BufferPoolManager 类定义) ...

int main() {
    std::cout << "Starting Buffer Pool Manager Demo with LRU-K Replacer..." << std::endl;

    // 1. 初始化 DiskManager
    DiskManager disk_manager;

    // 2. 初始化 BufferPoolManager
    // 缓冲池大小为 10 个页，LRU-K 参数 K=2
    size_t pool_size = 10;
    size_t lru_k_param = 2; 
    BufferPoolManager bpm(pool_size, lru_k_param, &disk_manager);

    std::cout << "n--- Step 1: Create some new pages ---" << std::endl;
    std::vector<PageId> page_ids;
    for (int i = 0; i < pool_size + 2; ++i) { // 创建比缓冲池大的页数
        PageId new_page_id;
        Page* page = bpm.NewPage(new_page_id);
        if (page) {
            std::string content = "Hello from page " + std::to_string(new_page_id);
            std::copy(content.begin(), content.end(), page->GetData());
            page_ids.push_back(new_page_id);
            bpm.UnpinPage(new_page_id, true); // 解固定新页，并标记为脏页
            std::cout << "Created and unpinned page: " << new_page_id << std::endl;
        } else {
            std::cout << "Failed to create new page. Buffer pool full and no evictable pages." << std::endl;
        }
    }
    std::cout << "Total pages created: " << page_ids.size() << std::endl;
    std::cout << "Buffer pool active pages: " << bpm.GetNumActivePages() << "/" << pool_size << std::endl;

    // 此时，缓冲池应该满了，并且包含了 page_ids 中最后 pool_size 个页。
    // 由于 K=2，前几个页可能因为访问历史不足 K 次而被淘汰。
    // 但是我们新创建的页，在NewPage时被pin，然后Unpin，所以都会有至少一次RecordAccess。

    std::cout << "n--- Step 2: Fetch and access pages to demonstrate LRU-K ---" << std::endl;
    // 假设 page_ids 包含了 0, 1, ..., 11。缓冲池大小为 10。
    // 那么最初缓冲池中应该有 page_ids[2] 到 page_ids[11] (如果前面的页被淘汰了)

    // 访问 page_ids[0] (假设它已被淘汰)
    std::cout << "nAccessing page " << page_ids[0] << " (likely to be fetched from disk)..." << std::endl;
    Page* p0 = bpm.FetchPage(page_ids[0]);
    if (p0) {
        std::cout << "Fetched page " << p0->GetPageId() << ". Content: " << std::string(p0->GetData(), 20) << std::endl;
        bpm.UnpinPage(page_ids[0], false);
    }

    // 访问 page_ids[1] (假设它已被淘汰)
    std::cout << "nAccessing page " << page_ids[1] << " (likely to be fetched from disk)..." << std::endl;
    Page* p1 = bpm.FetchPage(page_ids[1]);
    if (p1) {
        std::cout << "Fetched page " << p1->GetPageId() << ". Content: " << std::string(p1->GetData(), 20) << std::endl;
        bpm.UnpinPage(page_ids[1], false);
    }
    std::cout << "Buffer pool active pages: " << bpm.GetNumActivePages() << "/" << pool_size << std::endl;

    // 现在，p0 和 p1 已经被访问了一次。它们在 LRU-K 中属于 "新" 的页，K-th 访问时间就是第一次访问时间。
    // 它们应该比那些只被访问过一次且访问时间更早的页更不容易被淘汰。

    // 频繁访问一些页，使其成为 LRU-K 意义上的热点
    std::cout << "n--- Step 3: Create 'hot' pages with K=2 accesses ---" << std::endl;
    std::vector<PageId> hot_pages = {page_ids[0], page_ids[1], page_ids[2]};
    for (int i = 0; i < 3; ++i) {
        for (PageId id : hot_pages) {
            Page* page = bpm.FetchPage(id);
            if (page) {
                // std::cout << "Accessed hot page " << id << std::endl;
                bpm.UnpinPage(id, false);
            }
        }
    }
    std::cout << "Pages " << hot_pages[0] << ", " << hot_pages[1] << ", " << hot_pages[2] << " now have multiple accesses." << std::endl;

    // 模拟一次全表扫描，观察 LRU-K 的抗扫描能力
    std::cout << "n--- Step 4: Simulate a sequential scan (should not evict hot pages) ---" << std::endl;
    // 访问所有页，每次访问后立即 unpin。这将触发多次淘汰。
    // 理论上，hot_pages 应该更难被淘汰，因为它们的 K-th 访问时间相对较新。
    for (PageId id : page_ids) {
        Page* page = bpm.FetchPage(id);
        if (page) {
            // std::cout << "Scanning page " << id << ". Content: " << std::string(page->GetData(), 20) << std::endl;
            // 每次访问后，立即 unpin，但由于是扫描，不会标记为脏
            bpm.UnpinPage(id, false);
        } else {
            // std::cout << "Page " << id << " not found or could not be fetched during scan." << std::endl;
        }
    }
    std::cout << "Finished sequential scan. Hot pages (" << hot_pages[0] << ", " << hot_pages[1] << ", " << hot_pages[2] << ") should ideally still be in cache." << std::endl;

    // 检查热点页是否仍在缓冲池中
    std::cout << "n--- Step 5: Verify hot pages are still in cache ---" << std::endl;
    for (PageId id : hot_pages) {
        Page* page = bpm.FetchPage(id); // 再次固定，以便检查
        if (page) {
            std::cout << "Page " << id << " is still in buffer pool. PinCount: " << page->GetPinCount() << ". Content: " << std::string(page->GetData(), 20) << std::endl;
            // 重要：用完后记得解固定
            bpm.UnpinPage(id, false);
        } else {
            std::cout << "Page " << id << " was unexpectedly evicted from buffer pool!" << std::endl;
        }
    }

    std::cout << "n--- Step 6: Modify a page and flush ---" << std::endl;
    PageId modify_page_id = page_ids[3]; // 选择一个页进行修改
    Page* mod_page = bpm.FetchPage(modify_page_id);
    if (mod_page) {
        std::string new_content = "MODIFIED content for page " + std::to_string(modify_page_id);
        std::copy(new_content.begin(), new_content.end(), mod_page->GetData());
        std::cout << "Modified page " << modify_page_id << ". New content: " << std::string(mod_page->GetData(), 20) << std::endl;
        bpm.UnpinPage(modify_page_id, true); // 标记为脏页
        bpm.FlushPage(modify_page_id); // 强制刷回磁盘
        std::cout << "Flushed page " << modify_page_id << " to disk." << std::endl;
    }

    std::cout << "n--- Step 7: Delete a page ---" << std::endl;
    PageId delete_page_id = page_ids[4];
    std::cout << "Attempting to delete page " << delete_page_id << std::endl;
    bpm.DeletePage(delete_page_id);
    // 尝试再次获取被删除的页，应该会失败
    Page* deleted_page_check = bpm.FetchPage(delete_page_id);
    if (deleted_page_check == nullptr) {
        std::cout << "Successfully deleted page " << delete_page_id << " (not found in buffer pool after deletion)." << std::endl;
    } else {
        std::cout << "Failed to delete page " << delete_page_id << " (still found in buffer pool)." << std::endl;
        bpm.UnpinPage(delete_page_id, false);
    }

    std::cout << "n--- Step 8: Flush all remaining dirty pages ---" << std::endl;
    bpm.FlushAllPages();
    std::cout << "All dirty pages flushed during shutdown." << std::endl;

    std::cout << "nBuffer Pool Manager Demo Finished." << std::endl;

    return 0;
}

运行示例的预期行为：

1. 创建新页： 会创建超过缓冲池容量的页。较早创建的页会被淘汰。
2. LRU-K 演示： 访问 page_ids[0] 和 page_ids[1] 会将它们带入缓冲池。
3. 创建热点页： hot_pages 数组中的页被多次访问，其 K-th 访问时间会被更新，使其在 LRU-K 策略下更不容易被淘汰。
4. 模拟全表扫描： 此时会遍历并 Fetch/Unpin 所有页。由于 hot_pages 有足够多的访问历史，它们应该能够抵抗住这次扫描带来的缓存污染，继续留在缓冲池中。
5. 验证热点页： 再次尝试 Fetch hot_pages，它们应该仍然在缓冲池中，证明 LRU-K 的有效性。
6. 修改和刷新： 演示页面的修改和强制刷盘。
7. 删除页面： 演示页面的删除操作。
8. FlushAllPages： 在程序结束时，缓冲池管理器会自动调用 FlushAllPages，确保所有修改过但未刷盘的页都被持久化。

5. 高级考量与优化

我们实现的缓冲池是一个功能完备的 LRU-K 页面管理系统，但作为真实数据库系统的一部分，它还需要考虑更多高级功能和优化：

• 页级并发控制： 当前实现使用一个全局锁 latch_ 保护整个缓冲池。在高并发场景下，这会成为性能瓶颈。更精细的并发控制是使用页级锁（Page Latch）。即每个 Page 对象都有自己的 std::mutex。当访问特定页时，只锁定该页，而不是整个缓冲池。但 BufferPoolManager 仍然需要一个锁来管理元数据（如 page_table_、free_list_）。
• 后台刷新线程： 脏页的刷新操作是磁盘 I/O 密集型任务，会阻塞前端操作。可以引入一个后台线程，周期性地扫描缓冲池，将脏页异步刷新到磁盘，以减轻 FetchPage 和 NewPage 等操作的负担。
• 检查点与恢复： 数据库需要崩溃恢复机制。缓冲池的状态（哪些页是脏的，哪些页被固定）是恢复的关键。检查点操作会强制将所有脏页写入磁盘，并记录当前事务日志的 LSN (Log Sequence Number)，以便在恢复时从最近的检查点开始。
• 预取（Pre-fetching）： 数据库系统可以预测用户接下来可能访问的页，提前将其从磁盘加载到缓冲池中，进一步减少延迟。这通常与查询优化器和执行器结合。
• 多个缓冲池： 对于某些特殊用途（如索引页、数据页），可以维护不同的缓冲池，使用不同的淘汰策略或大小，以优化性能。
• NUMA 架构优化： 在 NUMA（Non-Uniform Memory Access）架构下，将缓冲池分配在与 CPU 核心相近的内存节点上，可以减少内存访问延迟。
• 更灵活的 K 值： LRU-K 的 K 值可以根据不同的工作负载进行调整，甚至可以为不同的数据类型或访问模式设置不同的 K 值。

结语

通过本次深入探讨，我们不仅理解了数据库缓冲池在高性能系统中的关键作用，更亲手构建了一个具备 LRU-K 淘汰算法的页管理系统。从核心的 Page 数据结构，到模拟磁盘交互的 DiskManager，再到精妙的 LRUKReplacer 和统筹全局的 BufferPoolManager，每个组件都经过精心设计。尽管这只是一个基础实现，但它为我们理解和进一步优化复杂的数据库内存管理机制奠定了坚实的基础。希望这次讲座能启发您在数据库系统设计与实现领域的更多探索。