CMU-15445-BusTub 笔记 - Lab 1: Buffer Pool Manager

第一个编程项目是在storage manager中实现缓冲池。

实验指导书

缓冲池负责将物理页从主内存来回移动到磁盘。它允许DBMS支持大于系统可用内存量的数据库。缓冲池的操作对系统中的其他部分是透明的。例如，系统使用其唯一标识符（page_id_t）向缓冲池请求页面，但不知道该页面是否已在内存中，或者系统是否必须从磁盘检索该页面。

您的实现需要是线程安全的。多个线程将同时访问内部数据结构，因此您需要确保它们的临界区受到闩锁（在操作系统中称为“锁”）的保护。

一、LRU替换策略

该组件负责跟踪缓冲池中的页面使用情况。将在 src/include/buffer/lru_replacer.h中实现一个新的子类LRUReplacer，它相应的实现文件在src/buffer/lru_replacer.cpp。LRUReplacer继承了抽象类 Replacer（src/include/buffer/replacer.h）。

LRUReplacer中的最大页数与Buffer Pool相同，因为BufferPoolManager中包含所有frames的占位符。然而，在任何可能的时候，并非所有frames都会在LRUReplacer中。LRUReplacer应当被初始化为不包含任何frames。然后，只有新被unpinnded的才会被包含在LRUReplace中。

我们将实现课程中讨论的LRU策略。需要实现以下方法：

1. Victim(frame_id_t*)：Replacer跟踪与所有元素相比最近访问次数最少的对象并删除，将其删除页号存储在输出参数中，并返回 True。如果 Replacer 为空则返回 False。
2. Pin(frame_id_t)：在将page固定到BufferPoolManager中的frame后，应调用此方法。它应该从LRUReplacer中删除包含固定page的frame。
3. Unpin(frame_id_t)：当页面的引用计数变为 0 时，应该调用此方法。这个方法应该将未包含固定 page 的 frame 添加到 LRUReplacer。（注意，需要判断是否超出了内存大小，如果超过了，则删除较新的页面，然后再添加。）
4. Size()：此方法返回当前在LRUReplacer中的页面数

二、缓冲池管理器实例

接下来，需要在系统中实现缓冲池管理器 ( BufferPoolManagerInstance)。该BufferPoolManagerInstance负责从DiskManager中读取数据库页并将它们存储在内存中。该BufferPoolManagerInstance也可以写脏页到磁盘，仅当它被要求这样做或当他需要回收一个页面为新页面提供空间时。

为了确保你的代码能与系统其他部分一起正常工作，我们将为你提供一些已经完成的函数。同样，你也不需要完成读写磁盘的代码（这部门被叫做DiskManager）。

系统中所有内存中的页都被表示为Page对象，BufferPoolManagerInstance不需要知道每个页的内容。但是，作为系统开发人员，你必须理解Page对象只是缓冲池中的内存容器，因此并不特定于唯一的页面。也就是说，每个Page对象包含一个内存块，DiskManager将使用该内存块作为一个位置，以复制它从磁盘读取的物理页的内容。当BufferPoolManagerInstance在磁盘中移动的时候，它将重用相同的Page对象来存储数据，这意味着在系统的整个生命周期内，相同的Page对象可能包含不同的物理页。Page对象的标识符(page_id)跟踪它包含的物理页面，如果Page对象不包含物理页面，那么它的page_id必须设置为INVALID_PAGE_ID。

每个Page对象还维护一个计数器，以表示“pin”过该页面的线程数。您的BufferPoolManagerInstance不能释放被固定的页面。此外，每个Page对象还跟踪它是否是脏的。您的工作是记录页面在“Unpin”之前是否被修改。在重用该对象之前，您的BufferPoolManagerInstance必须将脏Page的内容写回磁盘。

您的BufferPoolManagerInstance将使用您在之前创建的LRUReplacer类。它将使用LRUReplacer跟踪访问Page对象的时间，以便当它必须释放一个帧来为从磁盘复制一个新的物理页腾出空间时，它可以决定删除哪个。

您将实现以下方法：

FetchPgImp(page_id)
UnpinPgImp(page_id, is_dirty)
FlushPgImp(page_id)
NewPgImp(page_id)
DeletePgImp(page_id)
FlushAllPagesImpl()

在FetchPgImp中，如果空闲列表中没有可用的页面，并且所有其他页面当前都被固定，则应该返回NULL。
FlushPgImp应该刷新页面，不管其pin状态如何。
在UnpinPgImp中，is_dirty参数跟踪页面在被固定时是否被修改。

有关如何实现这些函数的详细信息，请参阅函数文档。不要碰非impl版本，我们需要它们来给你的代码评分。

注意:LRUReplacer和BufferPoolManagerInstance上下文中的Pin和Unpin有相反的含义。在LRUReplacer上下文中，Pin页面意味着我们不应该因为页面正在使用而删除它。这意味着我们应该将它从LRUReplacer中移除。然而，将页面Pin在BufferPoolManagerInstance中意味着我们希望使用页面，并且不应该将其从缓冲池中删除。

三、并行缓冲池管理器

正如上个任务中看到的，每一个缓冲池都有一个锁来保证线程安全。这可能导致性能问题，因为每个线程在与缓冲池交互时都会争夺该锁。一个可行的解决方案是同时维护多个缓冲池，每个缓冲池都有独立的锁。

ParallelBufferPoolManager是一个包含多个bufferpoolmanagerinstance的类。对于每个操作，其都会选择一个实例并调用该实例。

我们使用给定的page_id来确实使用哪个特定的实例。如果我们有多个实例，则需要某种方法将page_id映射到[0, num_instances)中。对于本项目，我们将使用模运算，即page_id mod num_instances来将给定的page_id映射到正确的范围。

当ParallelBufferPoolManager初始化的时候，他的起始索引应该是0.此后每创建一个新的页面，都应从起始索引开始尝试每个实例直到某个成功。然后将起始指数加1。

确保当你创建单独的BufferPoolManagerInstances时，你调用的构造函数应使用uint32_t num_instances和uint32_t instance_index，来保证页面id被正确地创建。

您将实现以下方法：

ParallelBufferPoolManager(num_instances, pool_size, disk_manager, log_manager)
~ParallelBufferPoolManager()
GetPoolSize()
GetBufferPoolManager(page_id)
FetchPgImp(page_id)
UnpinPgImp(page_id, is_dirty)
FlushPgImp(page_id)
NewPgImp(page_id)
DeletePgImp(page_id)
FlushAllPagesImpl()

实验过程

一、LRU替换策略

// include/buffer/lru_replacer.h
 private:
  // TODO(student): implement me!
  std::mutex mutex_;
  std::list<frame_id_t> lru_list_;                                            // 双向链表，存放frame_id_t
  std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> lru_hash_;  // 哈希表，value存储一个迭代器
  size_t max_size_;                                                           // 最大容量

// buffer/lru_replacer.cpp
LRUReplacer::LRUReplacer(size_t num_pages) { max_size_ = num_pages; }

LRUReplacer::~LRUReplacer() = default;

// 使用LRU策略删除一个victim frame，这个函数能得到frame_id
// @param[out] *frame_id 在指针中写入被删除的id
// @return 如果删除成功返回true，否则返回false
bool LRUReplacer::Victim(frame_id_t *frame_id) {
  std::scoped_lock lock{mutex_};
  if (lru_list_.empty()) {
    return false;
  }
  *frame_id = lru_list_.back();
  lru_hash_.erase(lru_list_.back());
  lru_list_.pop_back();
  return true;
}

// 固定一个frame, 表明它不应该成为victim（即在replacer中移除该frame_id）
// @param frame_id 被固定的ID
void LRUReplacer::Pin(frame_id_t frame_id) {
  std::scoped_lock lock{mutex_};
  auto iter = lru_hash_.find(frame_id);
  if (iter == lru_hash_.end()) {
    return;
  }

  lru_list_.erase(iter->second);
  lru_hash_.erase(iter);
}

void LRUReplacer::Unpin(frame_id_t frame_id) {
  std::scoped_lock lock{mutex_};
  // 避免重复添加
  if (lru_hash_.count(frame_id) != 0) {
    return;
  }
  // 超容量了
  if (lru_list_.size() >= max_size_) {
    return;
  }
  // 添加到链表头
  lru_list_.push_front(frame_id);
  lru_hash_[frame_id] = lru_list_.begin();
}

// 返回replacer中能够victim的数量
size_t LRUReplacer::Size() {
  std::scoped_lock lock{mutex_};
  return lru_list_.size();
}

二、缓冲池管理器实例

直接实现各个函数，每个函数的作用及步骤见注释

// buffer/buffer_pool_manager_instance.cpp
BufferPoolManagerInstance::BufferPoolManagerInstance(size_t pool_size, DiskManager *disk_manager,
                                                     LogManager *log_manager)
    : BufferPoolManagerInstance(pool_size, 1, 0, disk_manager, log_manager) {}

BufferPoolManagerInstance::BufferPoolManagerInstance(size_t pool_size, uint32_t num_instances, uint32_t instance_index,
                                                     DiskManager *disk_manager, LogManager *log_manager)
    : pool_size_(pool_size),
      num_instances_(num_instances),
      instance_index_(instance_index),
      next_page_id_(static_cast<page_id_t>(instance_index)),
      disk_manager_(disk_manager),
      log_manager_(log_manager) {
  BUSTUB_ASSERT(num_instances > 0, "If BPI is not part of a pool, then the pool size should just be 1");
  BUSTUB_ASSERT(
      instance_index < num_instances,
      "BPI index cannot be greater than the number of BPIs in the pool. In non-parallel case, index should just be 1.");
  // We allocate a consecutive memory space for the buffer pool.
  pages_ = new Page[pool_size_];
  replacer_ = new LRUReplacer(pool_size);

  // Initially, every page is in the free list.
  for (size_t i = 0; i < pool_size_; ++i) {
    free_list_.emplace_back(static_cast<int>(i));
  }
}

BufferPoolManagerInstance::~BufferPoolManagerInstance() {
  delete[] pages_;
  delete replacer_;
}

/**
 * Flushes the target page to disk.
 * 刷新目标页到磁盘
 * @param page_id id of page to be flushed, cannot be INVALID_PAGE_ID
 * @return false if the page could not be found in the page table, true otherwise
 */
bool BufferPoolManagerInstance::FlushPgImp(page_id_t page_id) {
  // Make sure you call DiskManager::WritePage!
  std::scoped_lock lock{latch_};
  if (page_id == INVALID_PAGE_ID) {
    return false;
  }
  auto iter = page_table_.find(page_id);
  // 如果page不在页表中
  if (iter == page_table_.end()) {
    return false;
  }
  // 在页表中找到frameid，然后根据他获取Page对象
  frame_id_t frame_id = iter->second;
  Page *page = &pages_[frame_id];
  disk_manager_->WritePage(page_id, page->GetData());
  page->is_dirty_ = false;  // 刷新之后重置dirty状态
  return true;
}

/**
 * Flushes all the pages in the buffer pool to disk.
 * 刷新buffer pool中的所有页到磁盘
 */
void BufferPoolManagerInstance::FlushAllPgsImp() {
  // You can do it!
  std::scoped_lock lock{latch_};
  auto iter = page_table_.begin();
  while (iter != page_table_.end()) {
    page_id_t page_id = iter->first;
    frame_id_t frame_id = iter->second;
    Page *page = &pages_[frame_id];
    disk_manager_->WritePage(page_id, page->GetData());
    iter++;
  }
}

/**
 * Creates a new page in the buffer pool.
 * 在缓冲池中创建一个新页面
 * @param[out] page_id id of created page
 * @return nullptr if no new pages could be created, otherwise pointer to new page
 */
Page *BufferPoolManagerInstance::NewPgImp(page_id_t *page_id) {
  // 0.   Make sure you call AllocatePage!
  // 1.   If all the pages in the buffer pool are pinned, return nullptr.
  // 2.   Pick a victim page P from either the free list or the replacer. Always pick from the free list first.
  // 3.   Update P's metadata, zero out memory and add P to the page table.
  // 4.   Set the page ID output parameter. Return a pointer to P.
  std::scoped_lock lock{latch_};
  // 优先从freelist里获取空页，没有就去replacer中找一个，如果都找不到就返回nullptr
  frame_id_t frame_id = -1;
  Page *page = nullptr;
  if (!free_list_.empty()) {
    frame_id = free_list_.front();
    free_list_.pop_front();
    page = &pages_[frame_id];
  } else if (replacer_->Victim(&frame_id)) {
    page = &pages_[frame_id];
    // 从replacer中找到的页面要从pagetable中先删除
    if (page->IsDirty()) {
      disk_manager_->WritePage(page->GetPageId(), page->GetData());
    }
    page_table_.erase(page->GetPageId());
  } else {
    return nullptr;
  }

  // 重置状态，清空内存
  page_id_t new_page_id = AllocatePage();
  page->page_id_ = new_page_id;
  page->pin_count_ = 1;
  page->is_dirty_ = false;
  page->ResetMemory();

  // 添加到pagetable，Pin该页面并返回数据
  page_table_[new_page_id] = frame_id;
  *page_id = new_page_id;
  replacer_->Pin(frame_id);
  return page;
}

/**
 * Fetch the requested page from the buffer pool.
 * 从缓冲池中获取请求的页面
 * @param page_id id of page to be fetched
 * @return the requested page
 */
Page *BufferPoolManagerInstance::FetchPgImp(page_id_t page_id) {
  // 1.     Search the page table for the requested page (P).
  // 1.1    If P exists, pin it and return it immediately.
  // 1.2    If P does not exist, find a replacement page (R) from either the free list or the replacer.
  //        Note that pages are always found from the free list first.
  // 2.     If R is dirty, write it back to the disk.
  // 3.     Delete R from the page table and insert P.
  // 4.     Update P's metadata, read in the page content from disk, and then return a pointer to P.
  std::scoped_lock lock{latch_};
  auto iter = page_table_.find(page_id);
  // 如果存在，即Page在缓冲池中
  if (iter != page_table_.end()) {
    // 找到这个页面，Pin它并返回它
    frame_id_t frame_id = iter->second;
    Page *page = &pages_[frame_id];
    page->pin_count_++;
    replacer_->Pin(frame_id);
    return page;
  }
  // 不存在，即Page在磁盘中
  // 优先从freelist里获取空页，没有就去replacer中找一个，如果都找不到就返回nullptr
  frame_id_t frame_id = -1;
  Page *page = nullptr;
  if (!free_list_.empty()) {
    frame_id = free_list_.front();
    free_list_.pop_front();
    page = &pages_[frame_id];
  } else if (replacer_->Victim(&frame_id)) {
    page = &pages_[frame_id];
    // 从replacer中找到的页面要从pagetable中先删除
    if (page->IsDirty()) {
      disk_manager_->WritePage(page->GetPageId(), page->GetData());
    }
    page_table_.erase(page->GetPageId());
  } else {
    return nullptr;
  }

  // 重置状态
  page->page_id_ = page_id;
  page->pin_count_ = 1;
  page->is_dirty_ = false;
  // 填充Page内容
  disk_manager_->ReadPage(page_id, page->GetData());
  // 添加到pagetable，Pin该页面并返回数据
  page_table_[page_id] = frame_id;
  replacer_->Pin(frame_id);
  return page;
}

/**
 * Deletes a page from the buffer pool.
 * 从缓冲池中删除一个页面
 * @param page_id id of page to be deleted
 * @return false if the page exists but could not be deleted, true if the page didn't exist or deletion succeeded
 */
bool BufferPoolManagerInstance::DeletePgImp(page_id_t page_id) {
  // 0.   Make sure you call DeallocatePage!
  // 1.   Search the page table for the requested page (P).
  // 1.   If P does not exist, return true.
  // 2.   If P exists, but has a non-zero pin-count, return false. Someone is using the page.
  // 3.   Otherwise, P can be deleted. Remove P from the page table, reset its metadata and return it to the free list.
  std::scoped_lock lock{latch_};
  DeallocatePage(page_id);
  auto iter = page_table_.find(page_id);
  // 如果不存在，即Page在磁盘中，直接返回成功
  if (iter == page_table_.end()) {
    // DeallocatePage(page_id);
    return true;
  }
  // 如果存在，即Page在缓冲池中
  frame_id_t frame_id = iter->second;
  Page *page = &pages_[frame_id];
  // 如果PinCount不为0，则说明有人在用，返回失败
  if (page->GetPinCount() > 0) {
    return false;
  }
  // 清理，更新元数据，删除pagetable，返还至freelist
  if (page->IsDirty()) {
    disk_manager_->WritePage(page->GetPageId(), page->GetData());
  }
  replacer_->Pin(frame_id);
  page_table_.erase(page->page_id_);
  page->is_dirty_ = false;
  page->pin_count_ = 0;
  page->page_id_ = INVALID_PAGE_ID;
  page->ResetMemory();
  free_list_.push_back(frame_id);
  // DeallocatePage(page_id);
  return true;
}

/**
 * Unpin the target page from the buffer pool.
 * 在缓冲池中Unpin一个页面
 * @param page_id id of page to be unpinned
 * @param is_dirty true if the page should be marked as dirty, false otherwise
 * @return false if the page pin count is <= 0 before this call, true otherwise
 */
bool BufferPoolManagerInstance::UnpinPgImp(page_id_t page_id, bool is_dirty) {
  std::scoped_lock lock{latch_};
  auto iter = page_table_.find(page_id);
  // 如果不存在，即Page在磁盘中，直接返回true
  if (iter == page_table_.end()) {
    return false;
  }
  // 如果存在，即Page在缓冲池中
  frame_id_t frame_id = iter->second;
  Page *page = &pages_[frame_id];
  if (page->GetPinCount() <= 0) {  // 如果没被pin过，直接返回false
    return false;
  }
  page->pin_count_--;
  if (is_dirty) {  // 判断而非直接赋值是为了避免覆盖以前的状态
    page->is_dirty_ = true;
  }
  if (page->GetPinCount() <= 0) {
    replacer_->Unpin(frame_id);
  }
  return true;
}

三、并行缓冲池管理器

先回到BufferPoolManagerInstances中，看下它的代码：

page_id_t BufferPoolManagerInstance::AllocatePage() {
  const page_id_t next_page_id = next_page_id_;
  next_page_id_ += num_instances_;
  ValidatePageId(next_page_id);
  return next_page_id;
}

这里可以看出，关于pageid的逻辑已经实现了，不需要我们重新实现一遍。而且pageid和每个Instance的对应关系就是简单的取模即可，并且pageid可以原样传给Instance，不需要其他处理。
那么我们先修改下头文件，增加一些类内的变量：

// include/buffer/parallel_buffer_pool_manager.h
  /** 实例的数量 */
  size_t num_instances_;
  /** 每个实例的容量 */
  size_t pool_size_;
  /** RR法插入页面时，下一个要插入的位置*/
  size_t next_instance_;
  /** 锁 */
  std::mutex latch_;
  /** 实例s */
  std::vector<BufferPoolManagerInstance *> managers_;

然后对这个类进行初始化：

// buffer/parallel_buffer_pool_manager.cpp
ParallelBufferPoolManager::ParallelBufferPoolManager(size_t num_instances, size_t pool_size, DiskManager *disk_manager,
                                                     LogManager *log_manager) {
  // Allocate and create individual BufferPoolManagerInstances
  num_instances_ = num_instances;
  pool_size_ = pool_size;
  next_instance_ = 0;
  for (size_t i = 0; i < num_instances_; i++) {
    managers_.push_back(new BufferPoolManagerInstance(pool_size, num_instances_, i, disk_manager, log_manager));
  }
}

析构函数要记得删除这些对象

// buffer/parallel_buffer_pool_manager.cpp
ParallelBufferPoolManager::~ParallelBufferPoolManager() {
  for (size_t i = 0; i < num_instances_; i++) {
    delete managers_[i];
  }
}

然后需要关注下GetBufferPoolManager这个函数，其实就是直接取模即可：

// buffer/parallel_buffer_pool_manager.cpp
BufferPoolManager *ParallelBufferPoolManager::GetBufferPoolManager(page_id_t page_id) {
  // Get BufferPoolManager responsible for handling given page id. You can use this method in your other methods.
  return managers_[page_id % num_instances_];
}

还有NewPgImp，这里由于要轮询各个Instance，故要加锁处理：

// buffer/parallel_buffer_pool_manager.cpp
Page *ParallelBufferPoolManager::NewPgImp(page_id_t *page_id) {
  std::scoped_lock lock{latch_};
  for (size_t i = 0; i < num_instances_; i++) {
    BufferPoolManager *manager = managers_[next_instance_];
    Page *page = manager->NewPage(page_id);
    next_instance_ = (next_instance_ + 1) % num_instances_;
    if (page != nullptr) {
      return page;
    }
  }
  return nullptr;
}

其他就没什么难度了，基本都是一行代码解决，这里贴个示例：

// buffer/parallel_buffer_pool_manager.cpp
Page *ParallelBufferPoolManager::FetchPgImp(page_id_t page_id) {
  // Fetch page for page_id from responsible BufferPoolManagerInstance
  return GetBufferPoolManager(page_id)->FetchPage(page_id);
}

总结

本实验总的来说是实现了一个缓冲池管理器。在BusTub中，所有的数据都是以页为单位存储的，所有页都会存在硬盘中。在其中有一些页，他们正在被使用或者经常被使用，故会缓存到内存中。在被缓存的页面中，有一些页被Pin在了内存中，即无论如何他们都不会被替换出去，而还有一些页是Unpin状态，这些页在内存不足的时候会被替换出去。我们要做的就是管理这些页。

1. LRU替换策略与Leetcode上面的题不太一样，这里的LRU替换器中记录的是可以被删除的页，而不是全部的页。Pin的过程是从LRU替换器中删除该页面，这样该页面就不会被替换器删除了。Unpin则是在替换器中加入该页面，这样该页面就可能被替换器删除。
2. 我们实现了一个BufferPoolManagerInstance，这是一个缓冲池管理器。他主要是负责将页加载到内存中、读取页的内容、从内存中删除该页等。
3. 由于页的管理必须上锁，为了提高性能，我们使用了一种简单的办法来减少等待锁的可能，即将页面均匀的分配到各个Instance中。这样只有当要操纵的两个页面在同一个Instance中的时候才需要等待锁释放。ID一致性问题是通过为每个Instance设置自增步长来解决的，插入过程则需要通过轮询各个Instance这种简单的方式来尽量使负载均衡。
4. 坑：一定要通过make -j check-clang-tidy该检查，不然可能会报超时。

参考

https://www.inlighting.org/archives/cmu-15-445-notes/
https://www.qtmuniao.com/2021/02/10/cmu15445-project1-buffer-pool/