CMU 15445 2023fall Project1 Buffer Pool Manager

前言

实验要求

通过本地测试大概花了三天，第一次提交线上测试只有45分😭😭😭。后来又陆陆续续修改，又花了两天时间终于过了。不过这个实现基本毫无性能可言，bpm的每个函数都是简单粗暴地直接上scope lock锁住整个函数作用域，所以QPS rank排在200靠后了，后面再做优化吧。

Buffer Pool

对Buffer Pool做一个简单的介绍

更详细的可以看揭开 Buffer Pool 的面纱

温故知新——虚拟内存

首先复习一下操作系统的知识。在每个进程创建加载的时候，会被分配一定的内存和一个连续的虚拟地址空间。与实际的内存空间不同，虚拟内存地址空间在物理上是不存在的，仅仅是每个进程在逻辑层面上拥有的内存，他的真实位置位于磁盘中。等到进程真正运行的时候，需要某些数据但是数据不在物理内存中，就会触发缺页异常，然后进行数据拷贝，将数据从磁盘中拷贝到内存中。

在虚拟存储机制中，系统将虚拟地址空间划分为固定大小的虚拟页（Virtual Page，VP），而物理内存则划分为相同大小的物理页（Physical Page，PP），也被称为页帧（Page Frame）。每个虚拟页和物理页的大小通常是相等的，并且由系统设置。常见的页大小为4KB、2MB或4MB。虚拟页和物理页之间的映射关系由操作系统的内存管理单元（Memory Management Unit，MMU）进行管理。MMU中包含页表（Page Table），用于存储虚拟页和物理页之间的映射信息，当进程访问虚拟地址时，MMU根据页表的映射信息将虚拟页转换为对应的物理页。如果虚拟页已经在物理内存中，那么访问将直接转向物理页。如果虚拟页不在物理内存中（即发生了缺页异常），操作系统将负责将该虚拟页从磁盘加载到物理内存中，并更新页表的映射关系。

当物理内存的页已满时，OS使用页面置换算法来选择哪些物理页将被逐出并加载新的虚拟页。页面置换算法的目标是尽量减少页面置换的次数，同时尽量减少对性能的影响。一些常见的置换算法如下：

1. 最佳(Optimal)算法：理想情况下，最佳算法会选择最长时间内不会被访问的物理页进行置换。然而，最佳算法需要预先知道未来访问模式，因此在实际中无法实现，仅被用作评估其他算法的性能上限。
2. 先进先出(FIFO)算法：FIFO算法简单地选择最早进入物理内存的物理页进行置换。它维护一个页队列，当需要逐出页时，选择队列中最前面的页面进行置换。然而，FIFO算法可能会导致”Belady’s Anomaly”问题，即物理页数增加时，缺页率反而增加。
3. 最近最久未使用(LRU)算法：LRU算法基于页面最近的访问情况进行置换。它将物理页按照最近访问的时间顺序排列，当需要逐出页时，选择最久未被访问的物理页进行置换。LRU算法的实现较为复杂，包括硬件和软件支持。
4. 时钟(Clock)算法：时钟算法使用一个类似于时钟的数据结构来维护物理页的访问情况。每个物理页都有一个访问位（或称为引用位），当页面被访问时，访问位被设置为1。当需要逐出页时，算法从时钟的当前位置开始扫描物理页，如果访问位为0，则选择该页进行置换；如果访问位为1，则将访问位置为0，继续扫描。这样，算法会尽量保留最近被访问的物理页。
5. 最近未使用(NRU)算法：NRU算法将物理页分为多个类别，根据页的访问位和修改位进行分类。然后，从最低优先级的类别中选择一个物理页进行置换。这样，算法会优先选择长时间未被访问且未被修改的物理页进行置换。

引入了虚拟内存机制后，在逻辑上拓展了计算机的物理内存。一个仅有4GB物理内存的计算机，可能能够运行8GB的应用程序，而仅仅只需要付出维护页表和进行缺页中断时的磁盘I/O的较小的代价。

InnoDB的Buffer Pool

数据库系统的Buffer Pool和虚拟内存机制相似，但是目标却不同。因为数据库系统的数据本身就是存储在磁盘中，虚拟内存机制是为了在逻辑层面扩展计算机的计算资源，而Buffer Pool机制则是为了减少磁盘的I/O操作。（注意，Buffer Pool位于InnoDB存储引擎层，与MySQL 8.0 版本摒弃的查询缓存不是同一个东西）

下面的结构图中展示了Buffer Pool是InnoDB内存结构的四大组件之一，不属于MySQL的Server层，是InnoDB存储引擎层的缓冲池。

参考小林coding的图解MySQL

InnoDB存储引擎的逻辑存储结构大致如下图：

在DBMS中，记录是按照行来存储的，但是数据库的读取并不是以行为单位的，否则一次读取（也就是一次 I/O 操作）只能处理一行数据，效率会非常低。因此，InnoDB 的数据是按「页」为单位来读写的，也就是说，当需要读一条记录的时候，并不是将这个行记录从磁盘读出来，而是以页为单位，将其整体读入内存。InnoDB 默认每个页的大小为 16KB，也就是最多能保证 16KB 的连续存储空间。页是 InnoDB 存储引擎磁盘管理的最小单元，意味着数据库每次读写都是以 16KB 为单位的，一次最少从磁盘中读取 16K 的内容到内存中，一次最少把内存中的 16K 内容刷新到磁盘中。

为了减少磁盘I/O操作，Buffer Pool的作用就是把最热的数据页缓存在内存中，下次需要这个数据页时可以直接从内存读取，而不是进行一次磁盘I/O。当需要读取或写入数据时，存储引擎首先检查缓冲池中是否已经存在所需的数据页。如果数据页在缓冲池中，DBMS可以直接从内存中读取或写入数据，避免了磁盘IO的开销。如果数据页不在缓冲池中，DBMS就需要从磁盘加载数据页到缓冲池，并进行相应的操作。

相应的，缓冲池的管理也涉及到数据页的替换策略。当缓冲池已满时，需要替换一些数据页以腾出空间来存储新的数据页。常见的数据页替换策略包括最近最少使用（LRU）和时钟（Clock）算法。

在接下来的实现中，page表示在磁盘，frame表示在内存

Task #1 – LRU-K Replacement Policy

第一步实现一个LRU-K的页置换策略。与一般的LRU算法不同。K表示历史访问的数量。该算法选择一个具有最大的后向K距离的页面进行替换。后向K距离是指当前时间戳与第K次之前访问的时间戳之间的差异。如果一个页面的历史访问次数少于K次，则将其后向K距离设为正无穷。当有多个页面的后向K距离都为正无穷时，算法会选择具有最早整体时间戳（即最早一次的访问时间最早）的页面进行替换。这种算法的目标是增加对最近访问的页面的优先级，同时考虑到页面的历史访问模式。通过调整K的值，可以控制算法对历史访问的敏感程度。较小的K值更关注最近的访问，而较大的K值更平衡最近和历史访问的影响。

首先让每个frame都关联一个LRUKNode数据结构如下。std::list<size_t> history_记录该节点的历史访问记录、k_为策略设置的K值、fid_为关联的frame id、is_evictable_记录当前节点关联的页是否可以驱逐。

为该结构实现了几个关键函数，比如获取最近的一次访问时间戳、最早的一次访问时间戳、清空历史记录、计算后向K距离等。

class LRUKNode {
 public:
  LRUKNode() = default;
  LRUKNode(size_t id, size_t k) : k_(k), fid_(id) {}
  auto GetEvictable() -> bool { return is_evictable_; }
  void SetEvictable(bool evictable) { is_evictable_ = evictable; }
  auto GetHistory() { return history_; }
  void AddHistory(size_t timestamp) { history_.push_front(timestamp); }
  void RemoveHistory() {
    while (!history_.empty()) {
      history_.pop_back();
    }
  }
  auto GetFid() { return fid_; }
  void SetK(size_t k) { k_ = k; }
  auto GetKDistance(size_t cur) -> uint64_t {
    // 如果一个帧的历史访问次数少于k次，则将其后向k距离设置为正无穷大（+inf）
    if (history_.size() < k_) {
      return UINT32_MAX;
    }
    // 获取k次前访问的时间戳
    size_t k_distance;
    auto it = history_.begin();
    std::advance(it, k_ - 1);
    k_distance = *it;
    return cur - k_distance;
  }
  auto GetLastAccess() -> size_t {
    if (history_.empty()) {
      return UINT32_MAX;
    }
    return history_.front();
  }
  auto GetBackAccess() -> size_t {
    if (history_.empty()) {
      return UINT32_MAX;
    }
    return history_.back();
  }

 private:
  /** History of last seen K timestamps of this page. Least recent timestamp stored in front. */
  // Remove maybe_unused if you start using them. Feel free to change the member variables as you want.

  // 访问历史——时间戳链表，最近的访问时间戳在头部
  [[maybe_unused]] std::list<size_t> history_;
  // k距离
  [[maybe_unused]] size_t k_;
  // 帧id
  [[maybe_unused]] frame_id_t fid_;
  // 是否可驱逐
  [[maybe_unused]] bool is_evictable_{false};
};

LRUKReplacer结构如下，node_store_维护的frame id与LRUKNode节点的映射关系、current_timestamp_记录当前的时间戳、curr_size_表示当前可以驱逐的frame数量、replacer_size_表示维护的frame数量、k_为策略设置的K大小、latch_用于实现并发安全。

class LRUKReplacer {
 public:
  explicit LRUKReplacer(size_t num_frames, size_t k);

  DISALLOW_COPY_AND_MOVE(LRUKReplacer);

  ~LRUKReplacer() = default;
  // need to implement
  auto Evict(frame_id_t *frame_id) -> bool;
  void RecordAccess(frame_id_t frame_id, AccessType access_type = AccessType::Unknown);
  void SetEvictable(frame_id_t frame_id, bool set_evictable);
  void Remove(frame_id_t frame_id);

  auto Size() -> size_t;

 private:
  [[maybe_unused]] std::unordered_map<frame_id_t, LRUKNode> node_store_;
  [[maybe_unused]] size_t current_timestamp_{0};
  // 当前维护的页个数
  [[maybe_unused]] size_t curr_size_{0};
  [[maybe_unused]] size_t replacer_size_;
  [[maybe_unused]] size_t k_;
  [[maybe_unused]] std::mutex latch_;
};

接下来实现 LRUKReplacer结构的四个函数

• LRUKReplacer::Evict

驱逐Replacer中的一个元素。首先一把大锁先加上（先最大化锁的粒度，保证逻辑正确再来优化）。然后遍历一下frame id对应的LRUKNode，如果目标元素可驱逐，获取其后向K距离，如果为正无穷，则放入数组中，如果不为正无穷更新最大的后向K距离frame id。

如果有后向K距离为正无穷的节点，则遍历数组驱逐其中最早一次的访问时间最早的frame，否则驱逐刚刚遍历得到的拥有最大的后向K距离frame id。

/*******************************************************
 * @brief 淘汰一个元素
 *
 * @param frame_id
 * @return true
 * @return false
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-20
 *******************************************************/
auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
  // 加锁
  std::lock_guard<std::mutex> access_lock(latch_);
  bool find = false;
  // k距离为无穷的页id
  std::vector<size_t> inf_k_d_frame_id;
  // 记录最大的k距离
  size_t max_k_d = 0;

  // 记录最大的k距离页id
  frame_id_t max_k_d_id = replacer_size_;
  //   遍历存储的node
  for (auto &node : node_store_) {
    // 该节点是否可淘汰
    if (!node.second.GetEvictable()) {
      continue;
    }
    size_t tmp = node.second.GetKDistance(current_timestamp_);
    // 如果当前节点的k距离更大，更新页id
    if (tmp > max_k_d) {
      find = true;
      max_k_d = tmp;
      max_k_d_id = node.first;
    }

    // 如果k距离为无穷
    if (tmp == UINT32_MAX) {
      inf_k_d_frame_id.push_back(node.first);
    }
  }

  *frame_id = max_k_d_id;

  //   如果有inf
  size_t min_k_d = UINT32_MAX;
  for (size_t &i : inf_k_d_frame_id) {
    // 可淘汰且最近访问时间小
    if (node_store_[i].GetBackAccess() < min_k_d) {
      min_k_d = node_store_[i].GetBackAccess();
      *frame_id = i;
    }
  }
  // 清空历史记录
  if (find) {
    node_store_[*frame_id].RemoveHistory();
    node_store_[*frame_id].SetEvictable(false);
    curr_size_--;
    // node_store_.erase(*frame_id);
    return true;
  }

  return false;
}

• LRUKReplacer::RecordAccess

给一个frame添加一个访问记录。如果frame_id存在，则直接更新历史记录并移动时间戳。如果frame_id不存在且合法，初始化一个frame_id对应的LRUKNode。

/*******************************************************
 * @brief 访问一页
 *
 * @param frame_id
 * @param access_type
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-20
 *******************************************************/
void LRUKReplacer::RecordAccess(frame_id_t frame_id, [[maybe_unused]] AccessType access_type) {
  // 加锁
  std::lock_guard<std::mutex> access_lock(latch_);
  // 如果页id不合法
  if (static_cast<size_t>(frame_id) > replacer_size_) {
    throw Exception("LRUKReplacer::RecordAccess: frame_id is invalid");
  }
  if (node_store_.find(frame_id) == node_store_.end()) {
    // 节点已满
    if (node_store_.size() == replacer_size_) {
      return;
    }
    // 如果不存在，则添加
    node_store_[frame_id] = LRUKNode(frame_id, k_);
  }
  // 给当前页添加访问历史
  node_store_[frame_id].AddHistory(current_timestamp_);
  // 时间自增
  current_timestamp_++;
}

• LRUKReplacer::SetEvictable

frame_id的is_evictable_属性，这个没啥说的，注意更新 cur_size_。

/*******************************************************
 * @brief 设置是否可淘汰
 *
 * @param frame_id
 * @param set_evictable
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-20
 *******************************************************/
void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  // 加锁
  std::lock_guard<std::mutex> access_lock(latch_);
  // 如果页id不合法
  if (node_store_.find(frame_id) == node_store_.end()) {
    throw Exception("LRUKReplacer::RecordAccess: frame_id is invalid");
  }
  if (!set_evictable && node_store_[frame_id].GetEvictable()) {
    curr_size_--;
  } else if (set_evictable && !node_store_[frame_id].GetEvictable()) {
    curr_size_++;
  }
  node_store_[frame_id].SetEvictable(set_evictable);
}

• LRUKReplacer::Remove

不管后向K距离，直接驱逐一个frame（如果frame存在且可驱逐）。注意更新 curr_size_。

/*******************************************************
 * @brief 移除
 *
 * @param frame_id
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-20
 *******************************************************/
void LRUKReplacer::Remove(frame_id_t frame_id) {
  // 加锁
  std::lock_guard<std::mutex> access_lock(latch_);
  if (node_store_.find(frame_id) == node_store_.end()) {
    return;
  }
  // 如果页id不合法或不可驱逐
  if (!node_store_[frame_id].GetEvictable()) {
    throw Exception("LRUKReplacer::Remove: frame_id can not be remove");
  }
  //   移除
  node_store_[frame_id].RemoveHistory();
  node_store_[frame_id].SetEvictable(false);
  node_store_.erase(frame_id);
  curr_size_--;
}

• LRUKReplacer::Size()

直接return cur_size_即可。

Task #2 – Disk Scheduler

第二个任务是实现一个磁盘调度程序。磁盘管理程序已经给出了，不需要我们自己实现，完成了对磁盘的读取与写入，

稍微看看DiskManager的部分实现吧。（GPT阅读）

1、构造函数，用于打开或创建数据库文件和日志文件。首先根据提供的数据库文件名确定日志文件名，然后打开或创建日志文件。接着在互斥锁的保护下打开或创建数据库文件。

/**
 * Constructor: open/create a single database file & log file
 * @input db_file: database file name
 */
DiskManager::DiskManager(const std::string &db_file) : file_name_(db_file) {
  std::string::size_type n = file_name_.rfind('.');
  if (n == std::string::npos) {
    LOG_DEBUG("wrong file format");
    return;
  }
  log_name_ = file_name_.substr(0, n) + ".log";

  log_io_.open(log_name_, std::ios::binary | std::ios::in | std::ios::app | std::ios::out);
  // directory or file does not exist
  if (!log_io_.is_open()) {
    log_io_.clear();
    // create a new file
    log_io_.open(log_name_, std::ios::binary | std::ios::trunc | std::ios::out | std::ios::in);
    if (!log_io_.is_open()) {
      throw Exception("can't open dblog file");
    }
  }

  std::scoped_lock scoped_db_io_latch(db_io_latch_);
  db_io_.open(db_file, std::ios::binary | std::ios::in | std::ios::out);
  // directory or file does not exist
  if (!db_io_.is_open()) {
    db_io_.clear();
    // create a new file
    db_io_.open(db_file, std::ios::binary | std::ios::trunc | std::ios::out | std::ios::in);
    if (!db_io_.is_open()) {
      throw Exception("can't open db file");
    }
  }
  buffer_used = nullptr;
}

2、DiskManager::ShutDown(): 关闭所有文件流，即关闭数据库文件和日志文件。

/**
 * Close all file streams
 */
void DiskManager::ShutDown() {
  {
    std::scoped_lock scoped_db_io_latch(db_io_latch_);
    db_io_.close();
  }
  log_io_.close();
}

3、DiskManager::WritePage(page_id_t page_id, const char *page_data): 将指定页面的内容写入磁盘文件。函数首先获取页面在文件中的偏移量，然后将写入游标定位到该偏移量处，并写入指定大小的页面数据。最后，将文件内容刷新到磁盘。

/**
 * Write the contents of the specified page into disk file
 */
void DiskManager::WritePage(page_id_t page_id, const char *page_data) {
  std::scoped_lock scoped_db_io_latch(db_io_latch_);
  size_t offset = static_cast<size_t>(page_id) * BUSTUB_PAGE_SIZE;
  // set write cursor to offset
  num_writes_ += 1;
  db_io_.seekp(offset);
  db_io_.write(page_data, BUSTUB_PAGE_SIZE);
  // check for I/O error
  if (db_io_.bad()) {
    // std::cout << "write bad" << std::endl;
    LOG_DEBUG("I/O error while writing");
    return;
  }
  // std::cout << "write" << page_data << std::endl;
  // needs to flush to keep disk file in sync
  db_io_.flush();
}

4、DiskManager::ReadPage(page_id_t page_id, char *page_data): 将指定页面的内容读取到给定的内存区域中。函数首先获取页面在文件中的偏移量，然后将读取游标定位到该偏移量处，并读取指定大小的页面数据。如果读取过程中发生错误，函数会进行相应的错误处理。

/**
 * Read the contents of the specified page into the given memory area
 */
void DiskManager::ReadPage(page_id_t page_id, char *page_data) {
  std::scoped_lock scoped_db_io_latch(db_io_latch_);
  int offset = page_id * BUSTUB_PAGE_SIZE;
  // check if read beyond file length
  if (offset > GetFileSize(file_name_)) {
    LOG_DEBUG("I/O error reading past end of file");
    // std::cerr << "I/O error while reading" << std::endl;
  } else {
    // std::cout << page_id << " " << strlen(page_data) << std::endl;
    // set read cursor to offset
    db_io_.seekp(offset);
    db_io_.read(page_data, BUSTUB_PAGE_SIZE);
    if (db_io_.bad()) {
      // std::cout << "read bad" << std::endl;
      LOG_DEBUG("I/O error while reading");
      return;
    }
    // if file ends before reading BUSTUB_PAGE_SIZE
    int read_count = db_io_.gcount();
    if (read_count < BUSTUB_PAGE_SIZE) {
      LOG_DEBUG("Read less than a page");
      db_io_.clear();
      // std::cerr << "Read less than a page" << std::endl;
      memset(page_data + read_count, 0, BUSTUB_PAGE_SIZE - read_count);
    }
  }
}

日志操作目前不关注。

• DiskScheduler::Schedule

该函数的作用仅仅把DiskRequest放入请求队列。

void DiskScheduler::Schedule(DiskRequest r) { request_queue_.Put(std::move(r)); }

• DiskScheduler::ProcessDiskRequest

自己实现一个函数用于处理DiskRequest（调用disk_manager_完成读写操作）

void DiskScheduler::ProcessDiskRequest(DiskRequest r) {
  // 写请求
  if (r.is_write_) {
    disk_manager_->WritePage(r.page_id_, r.data_);
  } else {
    // 读请求
    disk_manager_->ReadPage(r.page_id_, r.data_);
  }
  r.callback_.set_value(true);
}

• DiskScheduler::StartWorkerThread

磁盘调度后台进程的函数。不断从request_queue_请求队列中取出DiskRequest，然后创建一个线程进行处理，使用join串行等待。

void DiskScheduler::StartWorkerThread() {
  std::optional<DiskRequest> r;
  while ((r = request_queue_.Get()) != std::nullopt) {
    std::thread t = std::thread(&DiskScheduler::ProcessDiskRequest, this, std::move(r.value()));
    t.join();
  }
}

观察DiskScheduler的析构函数，向请求队列中放入 std::nullopt，并等待后台处理线程结束来实现优雅的退出。因此 DiskScheduler::StartWorkerThread函数的结束条件是 (r = request_queue_.Get()) != std::nullopt。

DiskScheduler::~DiskScheduler() {
  // Put a `std::nullopt` in the queue to signal to exit the loop
  request_queue_.Put(std::nullopt);
  if (background_thread_.has_value()) {
    background_thread_->join();
  }
}

Task #3 – Buffer Pool Manager

先看一下这些数据的作用吧。

/**
 * BufferPoolManager reads disk pages to and from its internal buffer pool.
 */
class BufferPoolManager {
 public:
  /**
   * @brief Creates a new BufferPoolManager.
   * @param pool_size the size of the buffer pool
   * @param disk_manager the disk manager
   * @param replacer_k the LookBack constant k for the LRU-K replacer
   * @param log_manager the log manager (for testing only: nullptr = disable logging). Please ignore this for P1.
   */
  BufferPoolManager(size_t pool_size, DiskManager *disk_manager, size_t replacer_k = LRUK_REPLACER_K,
                    LogManager *log_manager = nullptr);

  /**
   * @brief Destroy an existing BufferPoolManager.
   */
  ~BufferPoolManager();

  auto GetPoolSize() -> size_t { return pool_size_; }
  auto GetPages() -> Page * { return pages_; }

  auto NewPage(page_id_t *page_id) -> Page *;
  auto NewPageGuarded(page_id_t *page_id) -> BasicPageGuard;
  auto FetchPage(page_id_t page_id, AccessType access_type = AccessType::Unknown) -> Page *;

  auto FetchPageBasic(page_id_t page_id) -> BasicPageGuard;
  auto FetchPageRead(page_id_t page_id) -> ReadPageGuard;
  auto FetchPageWrite(page_id_t page_id) -> WritePageGuard;

  auto UnpinPage(page_id_t page_id, bool is_dirty, AccessType access_type = AccessType::Unknown) -> bool;
  auto FlushPage(page_id_t page_id) -> bool;
  void FlushAllPages();
  auto DeletePage(page_id_t page_id) -> bool;

 private:
  /** Number of pages in the buffer pool. */
  const size_t pool_size_;
  /** The next page id to be allocated  */
  std::atomic<page_id_t> next_page_id_ = 0;

  /** Array of buffer pool pages. */
  Page *pages_;
  /** Pointer to the disk sheduler. */
  std::unique_ptr<DiskScheduler> disk_scheduler_ __attribute__((__unused__));
  /** Pointer to the log manager. Please ignore this for P1. */
  LogManager *log_manager_ __attribute__((__unused__));
  /** Page table for keeping track of buffer pool pages. */
  std::unordered_map<page_id_t, frame_id_t> page_table_;
  /** Replacer to find unpinned pages for replacement. */
  std::unique_ptr<LRUKReplacer> replacer_;
  /** List of free frames that don't have any pages on them. */
  std::list<frame_id_t> free_list_;
  /** This latch protects shared data structures. We recommend updating this comment to describe what it protects. */
  std::mutex latch_;

  /**
   * @brief Allocate a page on disk. Caller should acquire the latch before calling this function.
   * @return the id of the allocated page
   */
  auto AllocatePage() -> page_id_t;
  void DeallocatePage(__attribute__((unused)) page_id_t page_id) {
    // This is a no-nop right now without a more complex data structure to track deallocated pages
  }
};

成员变量的描述：

• pool_size_：Buffer Pool缓存的frame容量

• next_page_id_：分配的下一page id（使用atomic保证原子性）

• pages_：Buffer Pool缓存page数组

• disk_scheduler_：磁盘调度器

• log_manager_：日志管理器（不关注）

• page_table_：维护page id到frame id的映射

• replacer_：页置换策略

• free_list_：可用的frame id链表

• latch_：用于保证并发安全

需要实现的函数描述：

• NewPage：创建一个空的page

• FetchPage：从Buffer Pool取出一个frame，如果没有则从磁盘读取

• UnpinPage：减少对frame的引用

• FlushPage：将page写回磁盘

• FlushAllPages：将所有page写回磁盘

• DeletePage：删除一个frame

frame id数量是固定的，Buffer Pool中只能维护1~n的frame id，这些frame id映射到不固定的page id

来一个一个实现

1、BufferPoolManager::NewPage

先从free_list_取出一个可用的frame id，如果没有可用的则使用replacer_驱逐一个frame，如果也没有可驱逐的直接返回nullptr。

找到可用的frame id之后，如果之前为脏页，先将脏页写回到磁盘，然后重新分配该frame的内存和引用计数并更新replacer_的记录。

/*******************************************************
 * @brief 新建一页
 *
 * @param page_id
 * @return Page*
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-24
 *******************************************************/
auto BufferPoolManager::NewPage(page_id_t *page_id) -> Page * {
  Page *page;
  frame_id_t frame_id = -1;
  std::scoped_lock lock(latch_);
  if (!free_list_.empty()) {
    // ! get frame id from free list
    frame_id = free_list_.back();
    free_list_.pop_back();
    page = pages_ + frame_id;
  } else {
    // ! get frame id from replacer
    if (!replacer_->Evict(&frame_id)) {
      return nullptr;
    }
    page = pages_ + frame_id;
  }
  // ! write back dirty page
  if (page->IsDirty()) {
    auto promise = disk_scheduler_->CreatePromise();
    auto future = promise.get_future();
    disk_scheduler_->Schedule({true, page->GetData(), page->GetPageId(), std::move(promise)});
    future.get();
    // ! clean
    page->is_dirty_ = false;
  }
  // ! alloc a page id
  *page_id = AllocatePage();
  // ! delete old map
  page_table_.erase(page->GetPageId());
  // ! add new map
  page_table_.emplace(*page_id, frame_id);
  // ! set page id
  page->page_id_ = *page_id;
  page->pin_count_ = 1;
  page->ResetMemory();
  // ! update replacer
  replacer_->RecordAccess(frame_id);
  replacer_->SetEvictable(frame_id, false);
  return page;
}

2、BufferPoolManager::FetchPage

从Buffer Pool取出一页，如果page不在Buffer Pool中，和NewPage的逻辑类似，找到可用的frame id后，如果之前为脏页，先将脏页写回到磁盘，然后重新分配该frame的内存（与NewPage不同，这里是发起一个磁盘读取请求来更新frame的内存）和引用计数并更新replacer_的记录。如果page在Buffer Pool中，直接更新引用计数并更新replacer_的记录。

/*******************************************************
 * @brief 取出一页，如果 buffer pool 没有则从磁盘读取
 *
 * @param page_id
 * @param access_type
 * @return Page*
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-24
 *******************************************************/
auto BufferPoolManager::FetchPage(page_id_t page_id, [[maybe_unused]] AccessType access_type) -> Page * {
  if (page_id == INVALID_PAGE_ID) {
    return nullptr;
  }
  // ! if exist
  std::scoped_lock lock(latch_);
  if (page_table_.find(page_id) != page_table_.end()) {
    // ! get page
    auto frame_id = page_table_[page_id];
    auto page = pages_ + frame_id;
    // ! uodate replacer
    replacer_->RecordAccess(frame_id);
    replacer_->SetEvictable(frame_id, false);
    // ! update pin count
    page->pin_count_ += 1;
    return page;
  }
  // ! if not exist
  Page *page;
  frame_id_t frame_id = -1;
  if (!free_list_.empty()) {
    // ! get frame id from free list
    frame_id = free_list_.back();
    free_list_.pop_back();
    page = pages_ + frame_id;
  } else {
    // ! get frame id from replacer
    if (!replacer_->Evict(&frame_id)) {
      return nullptr;
    }
    page = pages_ + frame_id;
  }
  // ! write back dirty page
  if (page->IsDirty()) {
    auto promise = disk_scheduler_->CreatePromise();
    auto future = promise.get_future();
    disk_scheduler_->Schedule({true, page->GetData(), page->GetPageId(), std::move(promise)});
    future.get();
    // ! clean
    page->is_dirty_ = false;
  }
  // ! erase old map
  page_table_.erase(page->GetPageId());
  // ! add new map
  page_table_.emplace(page_id, frame_id);
  // ! update page
  page->page_id_ = page_id;
  page->pin_count_ = 1;
  page->ResetMemory();
  // ! update replacer
  replacer_->RecordAccess(frame_id);
  replacer_->SetEvictable(frame_id, false);
  // ! read page from disk
  auto promise = disk_scheduler_->CreatePromise();
  auto future = promise.get_future();
  disk_scheduler_->Schedule({false, page->GetData(), page->GetPageId(), std::move(promise)});
  future.get();
  return page;
}

3、BufferPoolManager::UnpinPage

如果page不在Buffer Pool中，直接返回false。否则先检查引用计数，如果为0，直接返回false，如果不为0，设置脏位为 is_dirty同时减少引用计数，如果减为0，将该frame设为可驱逐。

/*******************************************************
 * @brief 减少对一页的引用
 *
 * @param page_id
 * @param is_dirty
 * @param access_type
 * @return true
 * @return false
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-24
 *******************************************************/
auto BufferPoolManager::UnpinPage(page_id_t page_id, bool is_dirty, [[maybe_unused]] AccessType access_type) -> bool {
  if (page_id == INVALID_PAGE_ID) {
    return false;
  }
  // ! if exist
  std::scoped_lock lock(latch_);
  if (page_table_.find(page_id) != page_table_.end()) {
    // ! get page
    auto frame_id = page_table_[page_id];
    auto page = pages_ + frame_id;
    // ! set dirty
    if (is_dirty) {
      page->is_dirty_ = is_dirty;
    }
    // ! if pin count is 0
    if (page->GetPinCount() == 0) {
      return false;
    }
    // ! decrement pin count
    page->pin_count_ -= 1;
    if (page->GetPinCount() == 0) {
      replacer_->SetEvictable(frame_id, true);
    }
    return true;
  }
  return false;
}

4、BufferPoolManager::FlushPage和BufferPoolManager::FlushAllPages

这个就是把对应的page写回磁盘即可，注意设置脏位为false。

/*******************************************************
 * @brief 将一页写回
 *
 * @param page_id
 * @return true
 * @return false
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-24
 *******************************************************/
auto BufferPoolManager::FlushPage(page_id_t page_id) -> bool {
  if (page_id == INVALID_PAGE_ID) {
    return false;
  }
  std::scoped_lock lock(latch_);
  if (page_table_.find(page_id) == page_table_.end()) {
    return false;
  }
  // ! get page
  auto page = pages_ + page_table_[page_id];
  // ! write back
  auto promise = disk_scheduler_->CreatePromise();
  auto future = promise.get_future();
  disk_scheduler_->Schedule({true, page->GetData(), page->GetPageId(), std::move(promise)});
  future.get();
  // ! clean
  page->is_dirty_ = false;
  return true;
}

/*******************************************************
 * @brief 将所有页写回
 *
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-24
 *******************************************************/
void BufferPoolManager::FlushAllPages() {
  std::scoped_lock lock(latch_);
  for (size_t i = 0; i < pool_size_; i++) {
    auto page = pages_ + i;
    if (page->GetPageId() == INVALID_PAGE_ID) {
      continue;
    }
    // ! write back
    auto promise = disk_scheduler_->CreatePromise();
    auto future = promise.get_future();
    disk_scheduler_->Schedule({true, page->GetData(), page->GetPageId(), std::move(promise)});
    future.get();
    page->is_dirty_ = false;
  }
}

5、BufferPoolManager::DeletePage

从Buffer Pool中移除一页。如果page在Buffer Pool中，引用计数大于0，无法删除返回false，否则更新bpm的page_table_、free_list_、replacer_成员变量并重置page。如果不在Buffer Pool中或者page id不合法，直接返回true。

/*******************************************************
 * @brief 删除页
 *
 * @param page_id
 * @return true
 * @return false
 * @author Andromeda (ech0uname@qq.com)
 * @date 2024-01-24
 *******************************************************/
auto BufferPoolManager::DeletePage(page_id_t page_id) -> bool {
  if (page_id == INVALID_PAGE_ID) {
    return true;
  }
  // ! page exist
  std::scoped_lock lock(latch_);
  if (page_table_.find(page_id) != page_table_.end()) {
    // ! get page
    auto frame_id = page_table_[page_id];
    auto page = pages_ + frame_id;
    // ! if can not delete
    if (page->GetPinCount() > 0) {
      return false;
    }
    // ! delete page
    page_table_.erase(page_id);
    free_list_.push_back(frame_id);
    replacer_->Remove(frame_id);
    // ! reset page memory
    page->ResetMemory();
    page->page_id_ = INVALID_PAGE_ID;
    page->is_dirty_ = false;
    page->pin_count_ = 0;
  }
  DeallocatePage(page_id);
  return true;
}

性能优化

从头到尾都是直接上一把大锁，后面还是要针对锁的粒度进行一些优化的。