C++ 数据库缓冲池管理：基于 C++ 实现的 LRU-K 页面置换算法在海量数据访问场景下的命中率优化

各位专家、同仁，下午好！

今天我们齐聚一堂，共同探讨一个在数据库核心组件中至关重要的议题：C++ 数据库缓冲池管理：基于 C++ 实现的 LRU-K 页面置换算法在海量数据访问场景下的命中率优化。在当今数据爆炸的时代，无论是OLTP（在线事务处理）还是OLAP（在线分析处理）系统，如何高效地管理内存资源，最大限度地减少昂贵的磁盘I/O，都是决定系统性能的关键。缓冲池（Buffer Pool）正是数据库系统与底层存储交互的核心枢纽，而页面置换算法则是缓冲池的“大脑”，决定了数据的去留。

我们将深入剖析LRU-K算法的原理、设计哲学、C++实现细节，并探讨其在实际海量数据访问场景中如何实现命中率的显著优化。

1. 数据库缓冲池：性能的生命线

1.1 磁盘I/O的瓶颈与内存的优势

数据库系统最主要的性能瓶颈之一是磁盘I/O。与CPU和内存的速度相比，机械硬盘（HDD）的寻道时间以毫秒计，固态硬盘（SSD）虽然快得多，但也远不及内存的纳秒级访问速度。在现代数据库系统中，数据通常以“页”（Page）为单位进行存储和传输，典型大小为4KB、8KB或16KB。每次从磁盘读取或写入一页数据，都会带来显著的延迟。

为了弥补这种巨大的速度差异，数据库系统引入了缓冲池。缓冲池是数据库在主内存中分配的一块区域，用于缓存从磁盘读取的数据页，以及准备写入磁盘的脏页。它的核心目标是：

• 减少磁盘I/O：通过将频繁访问的数据页保留在内存中，避免重复从磁盘读取。
• 加速数据访问：直接从内存访问数据比从磁盘快几个数量级。
• 平滑写入操作：将修改后的数据页（脏页）批量写入磁盘，减少随机写入的频率。

1.2 缓冲池的核心组件

一个典型的数据库缓冲池管理系统（Buffer Pool Manager, BPM）通常包含以下关键组件：

• 缓冲帧（Buffer Frame）：缓冲池中用于存放数据页的实际内存块。每个帧可以容纳一个固定大小的数据页。
• 页（Page）：数据库中数据的最小逻辑单位，通常是4KB、8KB或16KB。
• 页表（Page Table）：一个哈希表，用于快速查找某个逻辑页ID（page_id）当前是否在缓冲池中，以及如果存在，它位于哪个缓冲帧（frame_id）。
• 空闲列表（Free List）：维护当前可用的空闲缓冲帧列表。
• 置换器（Replacer）：当缓冲池满且需要载入新页时，置换器负责选择一个合适的页从缓冲池中淘汰（evict）。这是我们今天讨论的重点。
• 磁盘管理器（Disk Manager）：负责实际的磁盘读写操作，将数据页从磁盘加载到内存或将脏页写回磁盘。
• 页元数据（Page Metadata）：每个缓冲帧通常会关联一些元数据，例如：
  • page_id：当前帧中存储的页的逻辑ID。
  • pin_count：该页当前被多少个线程“钉住”（pinned）。被钉住的页不能被淘汰。
  • is_dirty：该页是否被修改过（脏页）。脏页在淘汰前必须写回磁盘。
  • last_access_time 或其他置换算法所需的统计信息。

1.3 页面置换算法的挑战

当缓冲池没有空闲帧，而又需要加载一个新页时，置换器就必须从现有页中选择一个“牺牲品”将其淘汰。这个选择至关重要，它直接影响到缓冲池的命中率（Hit Rate），即在所有数据访问请求中，有多少比例可以直接从缓冲池中满足，而无需进行磁盘I/O。

理想的置换算法是“最优置换算法”（Bélády’s Optimal Algorithm），它会淘汰将来最长时间内不会被访问的页。但这在实践中是无法实现的，因为它需要预知未来的访问模式。因此，我们寻求的是各种启发式算法，力求在不知道未来访问模式的情况下，尽可能地接近最优性能。

2. LRU：经典但有局限

2.1 LRU算法原理

LRU（Least Recently Used，最近最少使用）是最常用、最直观的页面置换算法之一。它的核心思想是：如果一个数据页最近被访问过，那么它在未来被访问的可能性也比较大；反之，如果一个页很久没有被访问，那么它在未来被访问的可能性也较小。因此，当需要淘汰页时，LRU会选择那个“最近最少使用”的页。

在C++中实现LRU通常使用双向链表（std::list）和哈希表（std::unordered_map）。哈希表将page_id映射到链表中的节点，链表则按访问时间排序。每次访问一个页时，将其对应的节点移到链表头部（表示最近使用）。淘汰时，移除链表尾部的节点。

// LRU 示例数据结构
struct LRUNode {
    page_id_t page_id;
    // ... 其他页元数据
};

class LRUReplacer {
private:
    std::list<page_id_t> lru_list_; // 存储 page_id，按最近使用排序
    std::unordered_map<page_id_t, std::list<page_id_t>::iterator> page_map_; // 映射 page_id 到链表迭代器
    std::unordered_map<page_id_t, int> pin_counts_; // 存储页的 pin_count

public:
    // 访问页时调用
    void RecordAccess(page_id_t page_id) {
        if (page_map_.count(page_id)) {
            lru_list_.erase(page_map_[page_id]); // 从原位置删除
        }
        lru_list_.push_front(page_id); // 移到链表头部
        page_map_[page_id] = lru_list_.begin();
    }

    // 淘汰页时调用
    bool Evict(page_id_t* evicted_page_id) {
        // 查找链表尾部第一个未被钉住的页
        for (auto it = lru_list_.rbegin(); it != lru_list_.rend(); ++it) {
            if (pin_counts_[*it] == 0) { // 检查是否被钉住
                *evicted_page_id = *it;
                lru_list_.erase(std::next(it).base()); // 删除
                page_map_.erase(*it);
                return true;
            }
        }
        return false; // 没有可淘汰的页
    }

    // 设置页是否可淘汰 (基于 pin_count)
    void SetEvictable(page_id_t page_id, bool evictable) {
        if (evictable) {
            pin_counts_[page_id] = 0;
        } else {
            pin_counts_[page_id]++; // 假设 pin_count > 0 表示不可淘汰
        }
    }
    // ... 其他方法
};

2.2 LRU的局限性

尽管LRU简单且在许多场景下表现良好，但在海量数据访问和复杂工作负载下，它暴露出了一些明显的局限性：

1. “扫描攻击”（Scan Resistance Problem）：当数据库进行全表扫描（Full Table Scan）操作时，会按顺序访问大量数据页。这些页通常只被访问一次，然后就不再需要。然而，LRU会将这些页视为“最近使用”，并将它们移到链表头部，从而可能将那些真正频繁访问（但暂时没有被访问）的热点页挤出缓冲池。扫描结束后，下次访问热点数据时又会导致大量缺页中断（Page Fault），性能急剧下降。
2. “一次性访问问题”（One-time Access Problem）：与扫描攻击类似，某些批处理任务或一次性查询可能会访问大量数据，但这些数据在短期内不会再次被访问。LRU无法区分这些“一次性”访问与“持续性”访问，导致缓冲池中充满低价值的页。
3. 缺乏频率信息：LRU只关注页的“最近访问时间”，而忽略了页的“访问频率”。一个页可能在过去被访问了上千次，但如果它最近一次访问是在很久以前，它就会被LRU淘汰。而一个只被访问过一两次的页，如果最近被访问，则会被保留。这显然是不合理的。

这些局限性促使数据库研究者和工程师寻求更智能、更健壮的页面置换算法，其中LRU-K就是一种非常成功的改进方案。

3. LRU-K：兼顾访问频率与近期性

3.1 LRU-K算法的核心思想

LRU-K（Least Recently Used with K-th access）算法由IBM的Patrick O’Neil等人在1993年提出，旨在解决LRU的扫描攻击和一次性访问问题。它的核心思想是：不再仅仅依赖页的最近一次访问时间，而是追溯到页的第K次访问时间（K-th most recent access time）来决定其被淘汰的优先级。

具体来说，LRU-K为每个页维护一个访问历史记录，记录该页最近的K次访问时间戳。当需要淘汰一个页时，LRU-K会选择那个具有最小的第K次访问时间戳的页进行淘汰。这样，一个页必须被访问至少K次才能“站稳脚跟”，进入“稳定”状态。那些只被访问过几次的页（例如全表扫描中的页）将很难达到K次访问，从而更容易被淘汰。

让我们用 rec(p, i) 表示页 p 的第 i 次访问时间戳（从最近到最远排序）。LRU-K的置换原则是：

1. 对于访问次数不足 K 次的页：这些页被认为是“新来的”或“低价值”的页。LRU-K通常会优先淘汰这类页，并且在它们之间，会选择 rec(p, 1)（最近一次访问时间）最小的页进行淘汰。
2. 对于访问次数达到 K 次或更多的页：这些页被认为是“稳定”的页。LRU-K会根据它们的 rec(p, K)（第K次访问时间）来决定淘汰顺序。rec(p, K) 最小的页将被淘汰。

通过这种方式，LRU-K有效地结合了页的访问频率（通过K次访问来判断）和近期性（通过时间戳来判断），从而在很大程度上缓解了LRU的固有缺陷。

3.2 LRU-K的优势

• 强大的扫描抵抗能力：全表扫描中的页通常只被访问一次，它们的访问历史记录长度为1。当缓冲池需要淘汰页时，LRU-K会优先淘汰这些访问次数不足K的页，而不是那些被频繁访问但暂时未被命中的“热点”页。
• 更好的处理混合工作负载：LRU-K能够区分短暂的热点数据和长期稳定的热点数据，对于包含扫描、随机访问和局部性访问的混合工作负载表现更优。
• 可调参数K：K值提供了灵活性。
  • K=1时，LRU-K退化为LRU。
  • K=2是一个常见的选择，能够有效区分一次性访问和至少两次访问的页。
  • 更大的K值可以提供更强的扫描抵抗能力，但也会增加维护成本。

3.3 LRU-K的挑战与权衡

• 更高的复杂度和维护开销：每个页需要存储K个时间戳，这比LRU只存储一个访问时间（隐式在链表位置中）要复杂得多。每次访问页时，都需要更新其访问历史，并可能需要重新评估其在置换列表中的位置。
• 内存开销：存储K个时间戳会增加每个页的元数据开销。
• 参数K的选择：K值不是一成不变的，它依赖于具体的工作负载。选择不当的K值可能会导致性能下降。通常需要通过实验和分析来确定最佳K值。

4. LRU-K缓冲池管理器架构设计

为了实现LRU-K缓冲池管理器，我们需要在LRU的基础上，对数据结构和算法进行精心设计。

4.1 核心组件与数据结构

我们先定义一些基础类型：

using page_id_t = int;       // 页面ID
using frame_id_t = int;      // 缓冲帧ID
using timestamp_t = long long; // 时间戳，通常用 std::chrono::high_resolution_clock::now().time_since_epoch().count()

1. Page 类/结构体

表示内存中的一个数据页。

class Page {
public:
    char data[PAGE_SIZE]; // 实际数据内容
    page_id_t page_id = INVALID_PAGE_ID; // 逻辑页ID
    int pin_count = 0;      // 钉住计数
    bool is_dirty = false;  // 是否为脏页

    Page() { ResetMemory(); }

    void ResetMemory() {
        std::memset(data, 0, PAGE_SIZE);
        page_id = INVALID_PAGE_ID;
        pin_count = 0;
        is_dirty = false;
    }
};

2. BufferPoolManager 类

作为核心协调者，负责与磁盘管理器和置换器交互。

class BufferPoolManager {
public:
    BufferPoolManager(size_t pool_size, DiskManager* disk_manager, LRUKReplacer* replacer);
    ~BufferPoolManager();

    Page* FetchPage(page_id_t page_id);
    bool UnpinPage(page_id_t page_id, bool is_dirty);
    bool FlushPage(page_id_t page_id);
    void FlushAllPages();
    Page* NewPage(page_id_t* page_id);
    bool DeletePage(page_id_t page_id);

private:
    size_t pool_size_;                  // 缓冲池大小（帧数量）
    Page* pages_;                       // 实际的缓冲帧数组
    DiskManager* disk_manager_;         // 磁盘管理器实例
    LRUKReplacer* replacer_;            // LRU-K置换器实例

    std::unordered_map<page_id_t, frame_id_t> page_table_; // 页ID -> 帧ID 映射
    std::list<frame_id_t> free_list_;    // 空闲帧列表

    std::vector<std::mutex> frame_latches_; // 每个帧的互斥锁，用于并发控制
    std::mutex bpm_latch_;               // 缓冲池管理器的全局锁
    // ... 其他必要的计数器或状态
};

3. LRUKReplacer 类

这是我们今天的主角，封装LRU-K逻辑。

class LRUKReplacer {
public:
    LRUKReplacer(size_t buffer_size, size_t k);
    ~LRUKReplacer() = default;

    void RecordAccess(page_id_t page_id);
    void SetEvictable(page_id_t page_id, bool evictable);
    void Remove(page_id_t page_id);
    bool Evict(page_id_t* evicted_page_id);
    size_t Size();

private:
    size_t buffer_size_;
    size_t k_;

    // 每个页的访问历史：page_id -> [t_N, t_{N-1}, ..., t_1] (t_N为最近一次)
    std::unordered_map<page_id_t, std::list<timestamp_t>> page_history_;
    // 存储页的pin_count，0表示可淘汰
    std::unordered_map<page_id_t, int> pin_counts_;
    // 存储页是否可被淘汰的标志
    std::unordered_map<page_id_t, bool> evictable_status_;

    // 核心数据结构：用于高效查找待淘汰页
    // 存储 (K-th_access_time, page_id) 对，按 K-th_access_time 升序排列
    // 如果 K-th_access_time 相同，则按 page_id 升序排列 (作为 tie-breaker，虽然实际中可能需要更复杂的tie-breaker)
    // std::set 自动排序，且查找删除效率高
    std::set<std::pair<timestamp_t, page_id_t>> candidate_k_pages_; // 访问次数 >= K 的页
    // 访问次数 < K 的页，按照 (1st_access_time, page_id) 排序，优先淘汰
    std::set<std::pair<timestamp_t, page_id_t>> candidate_less_k_pages_;

    std::mutex latch_; // 保护内部数据结构
};

4. DiskManager 类

模拟磁盘I/O，通常提供ReadPage和WritePage方法。

class DiskManager {
public:
    DiskManager(const std::string& db_file);
    ~DiskManager();

    void ReadPage(page_id_t page_id, char* page_data);
    void WritePage(page_id_t page_id, const char* page_data);
    page_id_t AllocatePage(); // 分配新的页ID
    void DeallocatePage(page_id_t page_id); // 释放页ID
    // ... 其他文件操作
private:
    std::fstream db_file_;
    int next_page_id_ = 0; // 模拟下一个可用的页ID
    std::mutex latch_;
};

4.2 数据流与操作流程

为了更好地理解各组件之间的协作，我们来看几个核心操作的流程：

1. BufferPoolManager::FetchPage(page_id_t page_id)

获取一个指定page_id的页。

1. 加锁：获取bpm_latch_。
2. 检查页表：在page_table_中查找page_id。
   • 命中（Page Hit）：
     1. 找到对应的frame_id。
     2. 获取frame_latches_[frame_id]。
     3. 增加pages_[frame_id].pin_count。
     4. 调用replacer_->RecordAccess(page_id)更新访问历史。
     5. 如果pin_count从0变为1，通知replacer_->SetEvictable(page_id, false)（该页暂时不可淘汰）。
     6. 释放frame_latches_[frame_id]和bpm_latch_。
     7. 返回&pages_[frame_id]。
   • 未命中（Page Miss）：
     1. 查找空闲帧：
        • 如果free_list_不为空，从其中取出一个frame_id。
        • 否则，调用replacer_->Evict(&evicted_page_id)来选择一个牺牲页。
          • 如果Evict失败（没有可淘汰的页），释放锁，返回nullptr。
          • 如果evicted_page_id是脏页（检查pages_[evicted_frame_id].is_dirty），则调用disk_manager_->WritePage(evicted_page_id, pages_[evicted_frame_id].data)将其写回磁盘。
          • 从page_table_中移除evicted_page_id。
          • 获取被淘汰页的frame_id。
     2. 加载新页：
        • 获取新选定帧的frame_latches_[frame_id]。
        • 调用disk_manager_->ReadPage(page_id, pages_[frame_id].data)将新页数据读入帧。
        • 更新pages_[frame_id]的元数据：page_id，pin_count=1，is_dirty=false。
        • 更新page_table_：page_table_[page_id] = frame_id。
     3. 更新置换器：
        • 调用replacer_->RecordAccess(page_id)记录新页的访问。
        • 调用replacer_->SetEvictable(page_id, false)，因为该页已被钉住。
     4. 释放frame_latches_[frame_id]和bpm_latch_。
     5. 返回&pages_[frame_id]。

2. BufferPoolManager::UnpinPage(page_id_t page_id, bool is_dirty)

解除一个页的钉住状态。

1. 加锁：获取bpm_latch_。
2. 检查页表：在page_table_中查找page_id对应的frame_id。如果未找到，释放锁并返回false。
3. 更新帧状态：
   • 获取frame_latches_[frame_id]。
   • 如果pages_[frame_id].pin_count已为0，说明重复解钉，释放锁并返回false。
   • 递减pages_[frame_id].pin_count。
   • 如果is_dirty为true，设置pages_[frame_id].is_dirty = true。
   • 如果pages_[frame_id].pin_count变为0，通知replacer_->SetEvictable(page_id, true)（该页现在可被淘汰）。
   • 释放frame_latches_[frame_id]和bpm_latch_。
4. 返回true。

5. LRU-K置换器：C++实现细节

现在我们来深入LRU-K置换器的具体实现。

5.1 LRUKReplacer 成员变量与构造函数

#include <chrono>
#include <list>
#include <map>
#include <mutex>
#include <set>
#include <unordered_map>
#include <vector>

// 辅助函数获取当前时间戳
inline timestamp_t GetCurrentTimestamp() {
    return std::chrono::duration_cast<std::chrono::milliseconds>(
               std::chrono::high_resolution_clock::now().time_since_epoch())
        .count();
}

// 假设 INVALID_PAGE_ID 为 -1
const int INVALID_PAGE_ID = -1;

class LRUKReplacer {
public:
    LRUKReplacer(size_t buffer_size, size_t k) : buffer_size_(buffer_size), k_(k) {}

    // ... 其他方法
private:
    size_t buffer_size_; // 缓冲池总帧数
    size_t k_;           // LRU-K中的K值

    // 存储每个页的访问历史。list 确保新时间戳添加到末尾，保持有序
    std::unordered_map<page_id_t, std::list<timestamp_t>> page_history_;
    // 存储每个页的pin_count。0表示可淘汰，>0表示不可淘汰
    std::unordered_map<page_id_t, int> pin_counts_;
    // 存储每个页的evictable状态。true表示可淘汰，false表示不可淘汰
    std::unordered_map<page_id_t, bool> evictable_status_;

    // 用于高效查找 K-th 访问时间最小的页 (访问次数 >= K)
    // 存储 (K-th_access_time, page_id) 对，std::set 自动按 pair 的第一个元素排序，再按第二个元素排序
    std::set<std::pair<timestamp_t, page_id_t>> candidate_k_pages_;

    // 用于高效查找 1st 访问时间最小的页 (访问次数 < K)
    // 存储 (1st_access_time, page_id) 对
    std::set<std::pair<timestamp_t, page_id_t>> candidate_less_k_pages_;

    std::mutex latch_; // 保护replacer内部数据结构的并发访问
};

5.2 RecordAccess(page_id_t page_id)

每次BufferPoolManager访问一个页时，都会调用此方法。

void LRUKReplacer::RecordAccess(page_id_t page_id) {
    std::unique_lock<std::mutex> lock(latch_);

    timestamp_t current_time = GetCurrentTimestamp();

    // 确保页在记录中
    if (page_history_.find(page_id) == page_history_.end()) {
        page_history_[page_id] = {}; // 初始化为空列表
        pin_counts_[page_id] = 0; // 默认pin_count为0
        evictable_status_[page_id] = true; // 默认可淘汰
    }

    // 更新访问历史
    std::list<timestamp_t>& history = page_history_[page_id];
    history.push_back(current_time);

    // 如果历史记录超过K，则移除最旧的（第一个）时间戳
    if (history.size() > k_) {
        history.pop_front();
    }

    // 重新评估页在 candidate_k_pages_ 或 candidate_less_k_pages_ 中的位置
    if (evictable_status_[page_id]) { // 只有可淘汰的页才参与置换
        if (history.size() == k_) {
            // 如果之前是 less_k_pages，需要从那里移除
            if (candidate_less_k_pages_.count({history.front(), page_id})) {
                candidate_less_k_pages_.erase({history.front(), page_id});
            }
            // 如果已经是 k_pages，先移除旧的 K-th 时间戳，再插入新的
            // 注意：这里需要一个机制来获取旧的 K-th 时间戳，通常是在插入新K-th之前记录
            // 更简单的处理是：每次RecordAccess，如果达到了K，就先尝试从两个set中移除旧的，再插入新的
            // 确保在插入新值之前移除旧值，避免重复

            // 尝试移除旧的 K-th entry (如果存在的话)
            auto old_k_time_it = history.begin();
            std::advance(old_k_time_it, history.size() - 2); // 倒数第二个，即旧的K-th
            if (history.size() > k_) { // 如果是 K+1 个元素，旧的 K-th 在 pop_front 之后就是第一个
                candidate_k_pages_.erase({*old_k_time_it, page_id});
            } else if (history.size() == k_ && history.size() > 1){ // 如果刚刚达到K，且之前是 < K 的，不需要移除旧的Kth
                // 此时已经从 less_k_pages 移除
            }

            // 插入新的 K-th entry
            candidate_k_pages_.insert({history.front(), page_id}); // history.front() 现在是 K-th access time
        } else if (history.size() < k_) {
            // 如果之前是 k_pages，需要从那里移除
            if (candidate_k_pages_.count({history.front(), page_id})) {
                candidate_k_pages_.erase({history.front(), page_id});
            }
            // 尝试移除旧的 1st entry (如果存在的话)
            if (history.size() > 1) { // 避免空历史记录
                // 需要记录之前的 1st access time，这里简化为直接移除
                // 实际中可能需要维护一个 map<page_id, timestamp> 来记录每个页的当前 1st/Kth time
                // 这里我们假设每次RecordAccess都会导致其位置变化，所以直接移除再插入
                auto old_1st_time_it = history.begin();
                std::advance(old_1st_time_it, history.size() - 2); // 倒数第二个，即旧的1st
                if (history.size() > 1) { // 如果历史记录有多个，移除旧的1st
                    candidate_less_k_pages_.erase({*old_1st_time_it, page_id});
                }
            }
            candidate_less_k_pages_.insert({history.back(), page_id}); // history.back() 是 1st access time
        }
    }
}

修订RecordAccess逻辑：

上述RecordAccess逻辑在处理candidate_k_pages_和candidate_less_k_pages_的更新时，略显复杂且容易出错。更健壮的模式是：每次RecordAccess时，如果页是可淘汰的，就从两个std::set中无条件移除旧的条目（如果存在），然后根据当前的访问历史长度重新插入正确的条目。这避免了复杂的条件判断。

为了实现这个，我们需要在page_history_中保存的timestamp_t列表，其front()是K-th，back()是1st。

void LRUKReplacer::RecordAccess(page_id_t page_id) {
    std::unique_lock<std::mutex> lock(latch_);

    timestamp_t current_time = GetCurrentTimestamp();

    // 确保页在记录中
    if (page_history_.find(page_id) == page_history_.end()) {
        page_history_[page_id] = {}; // 初始化为空列表
        pin_counts_[page_id] = 0;    // 默认pin_count为0
        evictable_status_[page_id] = true; // 默认可淘汰
    }

    // 获取页的历史记录
    std::list<timestamp_t>& history = page_history_[page_id];

    // 如果页当前是可淘汰的，并且在某个 set 中，先移除旧的条目
    if (evictable_status_[page_id]) {
        if (history.size() >= k_) {
            candidate_k_pages_.erase({history.front(), page_id});
        } else if (history.size() > 0) { // 访问次数 < K, 且历史不为空
            candidate_less_k_pages_.erase({history.back(), page_id});
        }
    }

    // 添加新的访问时间戳
    history.push_back(current_time);

    // 如果历史记录超过K，则移除最旧的（第一个）时间戳
    if (history.size() > k_) {
        history.pop_front();
    }

    // 如果页当前是可淘汰的，重新插入新的条目
    if (evictable_status_[page_id]) {
        if (history.size() >= k_) {
            candidate_k_pages_.insert({history.front(), page_id}); // history.front() 是 K-th access time
        } else { // 访问次数 < K
            candidate_less_k_pages_.insert({history.back(), page_id}); // history.back() 是 1st access time
        }
    }
}

5.3 SetEvictable(page_id_t page_id, bool evictable)

当页的pin_count变为0时（可淘汰），或从0变为>0时（不可淘汰），调用此方法。

void LRUKReplacer::SetEvictable(page_id_t page_id, bool evictable) {
    std::unique_lock<std::mutex> lock(latch_);

    if (page_history_.find(page_id) == page_history_.end()) {
        return; // 页不在replacer中
    }

    bool old_evictable_status = evictable_status_[page_id];
    evictable_status_[page_id] = evictable;

    // 如果状态没有变化，无需操作
    if (old_evictable_status == evictable) {
        return;
    }

    std::list<timestamp_t>& history = page_history_[page_id];

    if (evictable) { // 从不可淘汰变为可淘汰，需要加入到置换候选集
        if (history.size() >= k_) {
            candidate_k_pages_.insert({history.front(), page_id});
        } else {
            candidate_less_k_pages_.insert({history.back(), page_id});
        }
    } else { // 从可淘汰变为不可淘汰，需要从置换候选集中移除
        if (history.size() >= k_) {
            candidate_k_pages_.erase({history.front(), page_id});
        } else {
            candidate_less_k_pages_.erase({history.back(), page_id});
        }
    }
}

5.4 Evict(page_id_t* evicted_page_id)

选择一个页进行淘汰。这是LRU-K的核心逻辑所在。

bool LRUKReplacer::Evict(page_id_t* evicted_page_id) {
    std::unique_lock<std::mutex> lock(latch_);

    // 优先淘汰访问次数 < K 且 1st_access_time 最小的页
    if (!candidate_less_k_pages_.empty()) {
        auto it = candidate_less_k_pages_.begin();
        *evicted_page_id = it->second;

        // 移除相关记录
        candidate_less_k_pages_.erase(it);
        page_history_.erase(*evicted_page_id);
        pin_counts_.erase(*evicted_page_id);
        evictable_status_.erase(*evicted_page_id);
        return true;
    }

    // 如果没有访问次数 < K 的页，则淘汰访问次数 >= K 且 K-th_access_time 最小的页
    if (!candidate_k_pages_.empty()) {
        auto it = candidate_k_pages_.begin();
        *evicted_page_id = it->second;

        // 移除相关记录
        candidate_k_pages_.erase(it);
        page_history_.erase(*evicted_page_id);
        pin_counts_.erase(*evicted_page_id);
        evictable_status_.erase(*evicted_page_id);
        return true;
    }

    // 没有可淘汰的页
    *evicted_page_id = INVALID_PAGE_ID;
    return false;
}

5.5 Remove(page_id_t page_id)

当一个页从缓冲池中彻底删除时（例如DeletePage操作），需要将其从置换器中移除。

void LRUKReplacer::Remove(page_id_t page_id) {
    std::unique_lock<std::mutex> lock(latch_);

    if (page_history_.find(page_id) == page_history_.end()) {
        return; // 页不在replacer中
    }

    // 确保被移除的页没有被钉住
    if (pin_counts_[page_id] > 0) {
        // 这是一个错误，被钉住的页不应该被删除
        // 实际场景中可能需要抛出异常或记录错误
        return; 
    }

    // 从两个候选集中移除
    if (evictable_status_[page_id]) { // 只有可淘汰的页才会在候选集中
        std::list<timestamp_t>& history = page_history_[page_id];
        if (history.size() >= k_) {
            candidate_k_pages_.erase({history.front(), page_id});
        } else {
            candidate_less_k_pages_.erase({history.back(), page_id});
        }
    }

    // 从所有记录中移除
    page_history_.erase(page_id);
    pin_counts_.erase(page_id);
    evictable_status_.erase(page_id);
}

5.6 Size()

返回当前可淘汰页的数量。

size_t LRUKReplacer::Size() {
    std::unique_lock<std::mutex> lock(latch_);
    return candidate_k_pages_.size() + candidate_less_k_pages_.size();
}

6. 并发控制与性能考量

在多线程环境下，数据库缓冲池管理器必须是线程安全的。我们已经看到在BufferPoolManager和LRUKReplacer中使用了std::mutex和std::unique_lock进行并发控制。

6.1 并发策略

• 全局锁（bpm_latch_）：保护page_table_和free_list_等核心数据结构，以及缓冲池层面的操作（如FetchPage、NewPage）。
• 帧锁（frame_latches_）：每个缓冲帧有自己的锁，用于保护该帧内部的元数据（pin_count、is_dirty）和实际数据。这允许不同线程同时访问不同的帧。
• 置换器锁（replacer_->latch_）：保护LRUKReplacer内部的所有数据结构（page_history_、pin_counts_、evictable_status_以及两个std::set）。

锁的粒度与顺序：
为了避免死锁，必须遵循一致的锁获取顺序。一个常见且有效的顺序是：

1. 首先获取bpm_latch_（如果需要访问全局数据）。
2. 然后获取目标帧的frame_latches_（如果需要访问特定帧）。
3. 在需要与replacer_交互时，获取replacer_->latch_。
   始终在完成操作后以相反的顺序释放锁。

6.2 K值选择对性能的影响

K值是LRU-K算法的关键参数。

• K=1：退化为LRU。最简单，开销最小，但对扫描攻击和一次性访问最脆弱。
• K=2：一个非常常见的选择。它能有效区分只访问一次的页和至少访问两次的页。对于许多混合工作负载，K=2能提供不错的性能提升，且额外开销相对可控。
• 更大的K值（例如 K=3, K=4）：
  • 优点：对扫描攻击的抵抗力更强，能更好地识别长期热点数据。
  • 缺点：
    • 内存开销增加：每个页需要存储更多的历史时间戳。
    • CPU开销增加：RecordAccess和Evict操作需要处理更多的历史数据，尤其是std::list的操作。std::set的查找和插入/删除操作也更耗时。
    • 缓冲池利用率下降：一个页需要被访问更多次才能“站稳脚跟”，这可能导致一些短期的热点页在达到K次访问之前就被淘汰，从而降低缓冲池的效率。

如何选择K？
最佳的K值通常需要通过对实际工作负载的模拟和基准测试来确定。可以尝试不同的K值，并观察缓冲池的命中率、磁盘I/O量和CPU利用率。

6.3 数据结构选择的考量

• std::list<timestamp_t> for page_history_：std::list在两端插入和删除（push_back, pop_front）是O(1)操作，这非常适合维护固定长度的访问历史。
• std::set<std::pair<timestamp_t, page_id_t>> for candidate_k_pages_ and candidate_less_k_pages_：
  • std::set自动保持元素有序，使得begin()指向最小值，从而Evict操作非常高效（O(logN)）。
  • 插入和删除也是O(logN)。
  • 使用std::pair作为键，可以利用其默认的字典序比较规则，实现 (K-th_access_time, page_id) 的排序，其中page_id作为tie-breaker。
• std::unordered_map for page_table_, page_history_, pin_counts_, evictable_status_：提供平均O(1)的查找性能，对于通过page_id快速访问页元数据至关重要。

6.4 模拟工作负载与命中率评估

为了评估LRU-K的性能提升，我们需要设计不同的数据访问模式进行模拟：

• 随机访问：模拟完全无序的访问，此时任何算法命中率都可能不高。
• 顺序扫描：模拟全表扫描，LRU-K应在此场景下展现出优于LRU的扫描抵抗能力。
• 局部性访问：模拟热点数据集中在小范围内的场景，LRU和LRU-K都应表现良好。
• 混合工作负载：结合上述多种模式，最能体现LRU-K的综合优势。例如，模拟一个OLTP系统，同时进行大量随机读写和偶尔的全表分析查询。

通过记录每次FetchPage操作是否导致磁盘I/O（即是否命中缓冲池），我们可以计算出缓冲池的命中率。

// 简单的命中率统计
struct BufferPoolStats {
    long long total_fetches = 0;
    long long cache_hits = 0;
    long long disk_reads = 0; // cache_misses
    long long disk_writes = 0; // for dirty pages eviction
};

// 在 BufferPoolManager 中
// ...
// FetchPage 逻辑
    // If found: cache_hits++;
    // If not found: disk_reads++;
// UnpinPage 逻辑
    // If is_dirty and page is evicted: disk_writes++;
// ...

7. LRU-K在海量数据访问场景下的应用与优化

在海量数据访问场景下，LRU-K的优势尤为明显。考虑一个拥有数TB甚至PB级数据的数据库，其缓冲池通常只有几十GB到几百GB。在这种内存与磁盘容量严重不匹配的情况下，高效的页面置换策略是维持性能的关键。

7.1 应用场景举例

• 数据仓库/OLAP系统：经常需要执行复杂的分析查询，这些查询可能涉及大表的扫描，但也会频繁访问一些维度表或聚合结果。LRU-K能够确保扫描不会轻易淘汰掉这些重要的辅助数据。
• 混合型数据库系统：如HTAP（Hybrid Transactional/Analytical Processing）系统，既要处理高并发的事务，又要兼顾实时的分析查询。LRU-K能够平衡这两类工作负载对缓冲池的需求。
• 缓存层：在数据库之上构建的通用缓存层，如果数据访问模式复杂，LRU-K也能提供更稳定的性能。

7.2 进一步的优化方向

1. 自适应 K 值：不是所有工作负载都适合同一个K值。可以通过监控缓冲池的命中率和页的访问模式，动态调整K值。例如，如果命中率下降且观察到大量扫描，可以尝试增加K。
2. LRU-K与分区（Partitioning）结合：将缓冲池划分为不同的区域，每个区域使用独立的LRU-K或不同的K值，以适应不同类型的数据（例如，系统表、用户数据、索引等）。
3. 结合其他置换算法：例如，DB2的LRU-2Q（Two Queues）或ARC（Adaptive Replacement Cache）。这些算法在LRU-K的基础上，引入了更多的队列或更复杂的策略，试图进一步优化命中率。
4. Numa Aware Buffer Pool：在多NUMA架构的服务器上，将缓冲池页分配到与CPU核心距离最近的内存节点，可以减少内存访问延迟。
5. 异步I/O：将磁盘I/O操作放入单独的线程池中异步执行，避免阻塞主线程，提高吞吐量。
6. 预取（Prefetching）：根据访问模式（例如顺序访问），在数据被实际请求之前，提前将后续数据页加载到缓冲池中。这可以进一步减少I/O延迟。

8. 一些思考与展望

LRU-K算法是LRU系列算法中一个非常成功的改进，它通过引入访问频率的概念，有效地解决了LRU在复杂工作负载下的局限性。在海量数据访问场景下，其对扫描攻击的强大抵抗能力和对混合工作负载的良好适应性，使其成为数据库缓冲池置换策略的重要选择。

尽管LRU-K带来了更高的复杂度和一定的性能开销，但对于那些对性能和稳定性有极高要求的数据库系统而言，这种投入是值得的。通过精心的C++实现、合理的并发控制、以及对K值的细致调优，我们可以构建出高效、健壮的数据库缓冲池管理器，为上层应用提供卓越的性能支撑。

未来，随着硬件技术的发展（如持久内存、更高带宽的NVMe SSD）和数据库工作负载的日益复杂，页面置换算法的研究将继续演进，向着更智能、更自适应的方向发展。理解并掌握LRU-K这样的经典算法，将为我们探索这些前沿领域奠定坚实的基础。