CMU 15-445 Project 1：Buffer Pool Manager 踩坑实录

花了大概一周时间把 Project 1 搞定了。这个项目要实现数据库的 Buffer Pool Manager，说人话就是：管理内存和磁盘之间的数据搬运工作，顺便决定内存不够用的时候踢谁出去。

做完最大的感受是——并发这玩意，真的能把人绕晕。

---

先搞清楚几个概念

开始写代码之前，有几个概念必须分清楚，不然后面会很懵：

Frame vs Page

这俩中文都叫"页"，但完全不是一回事：

• Page：磁盘上的数据块，有个 page_id 作为身份证
• Frame：内存里的槽位，有个 frame_id 作为编号

打个比方：Page 是人，Frame 是酒店房间。同一个人（Page）今天住 101（Frame 0），明天可能住 202（Frame 1）。Buffer Pool Manager 就是酒店前台，负责安排谁住哪个房间。

为什么需要 Buffer Pool？

磁盘读写太慢了，比内存慢好几个数量级。数据库不可能每次查数据都去磁盘读，所以在内存里开辟一块区域当缓存。问题是内存有限，满了就得踢人，踢谁？这就是 Replacement Policy 要解决的事。

---

子任务 1：LRU-K Replacer

为什么不用普通 LRU？

最简单的 LRU（Least Recently Used）策略是：谁最久没被访问就踢谁。但这在数据库场景下有个大坑——缓存污染。

想象一下：你执行了一个全表扫描，把整张表几万个 Page 都读了一遍。这些 Page 可能就用这一次，但它们会把 Buffer Pool 里那些真正常用的"热数据"全挤出去。一次扫描，缓存全废。

LRU-K 的思路是：光看"最近一次"访问不够，得看"最近 K 次"。一个 Page 要被访问至少 K 次，才算真正的热数据。

核心数据结构

class LRUKNode {
 private:
  std::list<size_t> history_;  // 最近 K 次访问的时间戳
  size_t k_;
  frame_id_t fid_;
  bool is_evictable_{false};
};

history_ 用链表存最近 K 次访问时间。为啥用链表？因为我们需要：

• 尾部插入新时间戳
• 头部删除最老的时间戳
• 访问头部算 k-distance

全是 O(1) 操作，链表刚好合适。Java 程序员可以理解成 LinkedList。

驱逐逻辑

auto LRUKReplacer::Evict() -> std::optional<frame_id_t> {
  std::scoped_lock lock(latch_);
  
  frame_id_t victim = -1;
  size_t max_k_distance = 0;
  bool found_inf = false;
  size_t earliest_timestamp = std::numeric_limits<size_t>::max();
  
  for (auto &[fid, node] : node_store_) {
    if (!node.is_evictable_) continue;

    if (node.history_.size() < k_) {
      // 访问不足 K 次，k-distance = 无穷大，优先踢
      found_inf = true;
      if (node.history_.front() < earliest_timestamp) {
        earliest_timestamp = node.history_.front();
        victim = fid;
      }
    } else if (!found_inf) {
      // 访问 >= K 次，算真正的 k-distance
      size_t k_distance = current_timestamp_ - node.history_.front();
      if (k_distance > max_k_distance) {
        max_k_distance = k_distance;
        victim = fid;
      }
    }
  }
  // ...
}

逻辑分两档：

1. 访问不足 K 次的，k-distance 视为无穷大，优先被踢
2. 多个无穷大之间，选最早被访问的（退化成普通 LRU）
3. 都访问了 K 次以上，选 k-distance 最大的

我这里实现得比较暴力，每次 Evict 都遍历所有 Node。其实可以用两个链表分别维护"访问不足 K 次"和"访问够 K 次"的节点，但测试数据量不大，暴力也能过。

---

子任务 2：Disk Scheduler

这个相对简单。DiskScheduler 就是对 DiskManager 的一层封装，用一个后台线程处理磁盘读写请求。

void DiskScheduler::StartWorkerThread() {
  while (true) {
    auto request_opt = request_queue_.Get();  // 阻塞等待
    if (!request_opt.has_value()) break;      // 收到 nullopt 就退出
    
    if (request_opt->is_write_) {
      disk_manager_->WritePage(request_opt->page_id_, request_opt->data_);
    } else {
      disk_manager_->ReadPage(request_opt->page_id_, request_opt->data_);
    }
    request_opt->callback_.set_value(true);  // 通知调用方完成了
  }
}

这里用了 std::promise 和 std::future 做异步通知。调用方 Schedule 一个请求后，可以通过 future.get() 阻塞等待结果。

Java 类比：std::promise/future 就像 Java 的 CompletableFuture，一边 complete()，另一边 get() 等待。

---

子任务 3：Page Guard（RAII 的精髓）

这是今年 Project 1 和往年最大的区别，也是我觉得设计最精妙的部分。

为什么需要 Page Guard？

C++ 没有 GC，资源管理全靠程序员。如果每次访问 Page 都要手动 Pin/Unpin、加锁/解锁，迟早会忘，然后内存泄漏或者死锁。

RAII（Resource Acquisition Is Initialization）的思路是：把资源生命周期绑定到对象生命周期。对象创建时获取资源，销毁时释放资源。

Java 类比：就像 try-with-resources

// Java
try (FileInputStream fis = new FileInputStream("file.txt")) {
    // 用 fis
}  // 自动 close()

// C++
{
    WritePageGuard guard = bpm->WritePage(page_id);
    // 用 guard
}  // 离开作用域，自动调用析构函数，释放锁 + unpin

移动语义：为什么禁止拷贝？

ReadPageGuard(const ReadPageGuard &) = delete;  // 禁止拷贝
ReadPageGuard(ReadPageGuard &&that) noexcept;   // 只允许移动

PageGuard 持有锁和引用计数。如果允许拷贝，两个 Guard 指向同一个 Frame，析构时会释放两次锁——直接崩。

移动语义的意思是"转移所有权"，移动后原对象变成空壳：

ReadPageGuard guard1 = bpm->ReadPage(page_id);
ReadPageGuard guard2 = std::move(guard1);  
// 现在 guard1.is_valid_ == false，guard2 拥有一切

Java 没有移动语义，但可以这样理解：

// 伪代码
MyObject obj1 = new MyObject();
MyObject obj2 = obj1;
obj1 = null;  // 手动置空，模拟"移动"

移动构造 vs 移动赋值

这俩容易搞混：

// 移动构造：guard2 之前不存在
ReadPageGuard guard2(std::move(guard1));

// 移动赋值：guard2 之前已经存在，可能持有资源
ReadPageGuard guard2 = ...;
guard2 = std::move(guard1);  // 要先释放 guard2 原来的资源！

移动赋值要多一步：先 Drop() 掉自己原来的资源，再接管别人的。

auto ReadPageGuard::operator=(ReadPageGuard &&that) noexcept -> ReadPageGuard & {
  if (this == &that) return *this;  // 自己赋值给自己，啥也不干
  
  Drop();  // 先释放自己原来的资源！
  
  // 再接管 that 的资源
  this->frame_ = std::move(that.frame_);
  // ... 其他字段 ...
  this->is_valid_ = that.is_valid_;
  that.is_valid_ = false;
  
  return *this;
}

---

子任务 4：Buffer Pool Manager

核心函数：GetFrame

我把获取 Frame 的逻辑封装成了一个 helper，CheckedReadPage 和 CheckedWritePage 都调用它：

auto BufferPoolManager::GetFrame(page_id_t page_id, AccessType access_type)
    -> std::optional<std::pair<frame_id_t, bool>> {
  
  // 情况 1：Page 已经在内存里
  auto it = page_table_.find(page_id);
  if (it != page_table_.end()) {
    frame_id_t frame_id = it->second;
    frames_[frame_id]->pin_count_.fetch_add(1);
    replacer_->SetEvictable(frame_id, false);
    replacer_->RecordAccess(frame_id, access_type);
    return std::make_pair(frame_id, false);
  }

  frame_id_t frame_id;

  // 情况 2：有空闲 Frame
  if (!free_frames_.empty()) {
    frame_id = free_frames_.front();
    free_frames_.pop_front();
  } else {
    // 情况 3：需要驱逐
    auto evicted = replacer_->Evict();
    if (!evicted.has_value()) {
      return std::nullopt;  // 所有 Frame 都被 pin 住了
    }
    frame_id = evicted.value();
    // 脏页要先写回磁盘...
  }

  // 从磁盘读数据到 Frame
  // ...
  
  return std::make_pair(frame_id, true);
}

pin_count 是什么？

pin_count 表示"有多少人正在使用这个 Page"。

类比：你在图书馆借了一本书，这本书就被你 pin 住了，图书馆不能下架。只有所有人都还书（pin_count 降到 0），才能被移到仓库（驱逐）。

---

重头戏：并发控制与死锁

这部分是整个 Project 最烧脑的地方。

系统里有哪些锁？

1. bpm_latch_：Buffer Pool Manager 的大锁，保护 page_table_、free_frames_ 等共享数据
2. frame->rwlatch_：每个 Frame 的读写锁，保护 Frame 里的数据
3. replacer 内部的 latch_：保护 LRU-K 的数据结构

锁的层级关系

这是理解死锁的关键。从持有时间来看：

• rwlatch_：高级锁，持有时间长（整个 PageGuard 生命周期）
• bpm_latch_：低级锁，持有时间短（只在函数调用期间）

正常情况（单次申请）：

rwlatch:  [申请]━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━[释放]
bpm锁:    [申请][释放]                                        [申请][释放]
           ↑ 拿完就放                                          ↑ 更新 pin_count

规则：拿 rwlatch 的时候，bpm 锁必须是解锁状态。

死锁是怎么发生的？

如果你在持有一个 PageGuard（即持有 rwlatch1）的情况下，又去申请另一个 Page：

死锁场景：

线程 A（持有 rwlatch1，想申请 rwlatch2）：
rwlatch1: [申请]━━━━━━━━━━━━━━━━━━━━━━━[想释放，但要先拿bpm锁]
bpm锁:    [申请][释放]    [申请]━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━→ 卡住！
rwlatch2:                       [申请]━━━━━━━━━━━━━━━━━━━━━→ 等 rwlatch1

线程 B（想申请 rwlatch1）：
bpm锁:                          [申请]━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━→ 持有
rwlatch1:                              [申请]━━━━━━━━━━━━━━━━━━━━━→ 卡住！

• 线程 A 持有 rwlatch1，想拿 bpm 锁去申请 rwlatch2
• 线程 B 持有 bpm 锁，想拿 rwlatch1
• 循环等待，死锁！

我的代码怎么处理的？

关键在 CheckedWritePage：

auto BufferPoolManager::CheckedWritePage(...) {
  std::unique_lock<std::mutex> latch(*bpm_latch_);
  auto result = GetFrame(page_id, access_type);
  // ...
  latch.unlock();  // ← 先释放 bpm 锁！
  frame->rwlatch_.lock();  // ← 再拿 rwlatch
  return WritePageGuard(...);
}

还有 Drop()：

void ReadPageGuard::Drop() {
  if (!is_valid_) return;

  frame_->rwlatch_.unlock_shared();  // ← 先释放 rwlatch！
  {
    std::scoped_lock lock(*bpm_latch_);  // ← 再拿 bpm 锁
    size_t old = frame_->pin_count_.fetch_sub(1);
    if (old == 1) {
      replacer_->SetEvictable(frame_->frame_id_, true);
    }
  }
  // ...
}

核心原则：拿 rwlatch 时不持有 bpm 锁，释放 rwlatch 后才拿 bpm 锁。

但这并没有完全解决问题

上面的代码只保证单次申请/释放不会死锁。如果用户这样写：

auto guard1 = bpm->WritePage(page1);  // 持有 page1 的 rwlatch
auto guard2 = bpm->WritePage(page2);  // 想拿 bpm 锁 → 可能卡住

这时候 guard1 的 rwlatch 还没释放，你又去拿 bpm 锁，就可能和另一个线程形成死锁。

这是使用层面的问题，BusTub 的解决方案是文档约定：不要在持有 PageGuard 时再请求其他 Page。

---

C++ 知识点补课

std::optional

std::optional<T> 表示"可能有值，也可能没有"。

auto result = replacer_->Evict();
if (!result.has_value()) {
  return std::nullopt;  // 没有可驱逐的
}
frame_id_t fid = result.value();

Java 类比：就是 Optional<T>，用法几乎一样。

std::scoped_lock vs std::unique_lock

// scoped_lock：简单粗暴，构造加锁，析构解锁，不能中途解锁
{
  std::scoped_lock lock(mutex);
  // ...
}  // 自动解锁

// unique_lock：更灵活，可以手动 lock/unlock
std::unique_lock<std::mutex> lock(mutex);
// ...
lock.unlock();  // 手动解锁
// 做一些不需要锁的操作
lock.lock();    // 再加锁

什么时候用 unique_lock？当你需要中途释放锁的时候，比如释放锁后再做 I/O。

std::atomic

std::atomic<T> 保证读写是原子的，不需要额外加锁。

std::atomic<size_t> pin_count_;

pin_count_.fetch_add(1);  // 原子 +1，返回旧值
pin_count_.fetch_sub(1);  // 原子 -1，返回旧值
pin_count_.load();        // 原子读
pin_count_.store(0);      // 原子写

Java 类比：AtomicInteger、AtomicLong。

std::shared_mutex（读写锁）

std::shared_mutex rwlatch_;

// 写锁（独占）
rwlatch_.lock();
rwlatch_.unlock();

// 读锁（共享）
rwlatch_.lock_shared();
rwlatch_.unlock_shared();

多个线程可以同时持有读锁，但写锁是独占的。

Java 类比：ReentrantReadWriteLock。

---

踩坑记录

坑 1：忘记设置 is_valid_ = false

移动构造/赋值后，原对象的 is_valid_ 必须设为 false，否则析构时会 double free：

ReadPageGuard::ReadPageGuard(ReadPageGuard &&that) noexcept {
  // ... 转移字段 ...
  this->is_valid_ = that.is_valid_;
  that.is_valid_ = false;  // 别忘了这行！
}

坑 2：Drop() 里锁的顺序

一开始我写成了先拿 bpm 锁再释放 rwlatch，结果死锁。正确顺序是：先释放 rwlatch，再拿 bpm 锁。

坑 3：新 Page 的处理

NewPage() 只分配一个 page_id，不会把数据放到内存里。第一次 WritePage 这个新 Page 时，不能从磁盘读（磁盘上还没有），要特殊处理。

我用了一个 new_pages_ 集合记录哪些是新分配的 Page：

if (new_pages_.count(page_id) > 0) {
  // 新 page：写空白数据到磁盘
  DiskRequest req{true, frame->GetDataMut(), page_id, ...};
  // ...
  new_pages_.erase(page_id);
} else {
  // 已存在的 page：从磁盘读
  DiskRequest req{false, frame->GetDataMut(), page_id, ...};
  // ...
}

坑 4：pin_count 和 SetEvictable 的原子性

8 个线程同时读写同一个 Frame，pin_count 的增减和 SetEvictable 必须是原子的。我用 bpm 锁保护这两个操作：

{
  std::scoped_lock lock(*bpm_latch_);
  size_t old = frame_->pin_count_.fetch_sub(1);
  if (old == 1) {
    replacer_->SetEvictable(frame_->frame_id_, true);
  }
}

---

做完这个 Project，对数据库的内存管理、RAII 设计模式、并发控制都有了更深的理解。下一个是 B+ Tree，听说更难，希望不要被并发搞死（flag 已立）。