Project #1 - Buffer Pool

Overview

Lecture#05 Buffer Pool

Lecture#06 HashTables

Project1 主要与 Bustub 的 storage manager 相关，分为三个部分：

• Extendible Hash Table
• LRU-K Replacer
• Buffer Pool Manager Instance

Buffer Pool Manager 向系统提供获取 page 的接口，系统通过 page_id 向 Buffer Pool Manager 索要对应的 page，而不关心该 page 具体存放位置。也就是说，系统并不关心（也不可见）获取这个 page 的过程（从 disk 或 memory 上读取），也不关心 page 可能发生的在 disk 和 memory 间的移动。这些内部的操作都交由 Buffer Pool Manager 完成。

Extendible Hash Table 和 LRU-K Replacer 是 Buffer Pool Manager 内部的组件。Extendible Hash Table 用于实现 page table，将 page id 映射为 Buffer Pool 中 frame 的 frame id。 LRU-K Replacer 完成 Buffer Pool 空间不足时 frame 的移除工作。

Disk Manager 已经为我们提供，是实际在 disk 上读写数据的接口。

我们实现结构的类图如下：

Task #1 - Extendible Hash Table

实现 ExtendibleHashTable 类、Bucket 类，涉及文件：

• src/container/hash/extdible_hash_table.cpp
• src/include/Container/hash/extdible_hash_table.h

要求实现一个 extendible hash table，内部不能使用 build-in hash table，如 unordered_map。需要实现对扩容哈希表的支持，而不用实现对缩小/压缩哈希表的支持。该 hash table 在 buffer pool manager 中负责存储 buffer pool 中 page id 到 frame id 的映射关系。

Extendible Hash Table 由一个 directory + 多个 bucket 组成。

• directory: 存放指向 bucket 的指针，是一个数组。用于寻找 key 对应 value 所在的 bucket。
• bucket: 存放 value，是一个链表。一个 bucket 可以至多存放指定数量的 value。

Extendible Hash Table 维护两个值 ——

• global_depth：记录定位到 bucket 指针数组 directory (slot array) 的具体位置，需要取 key 的二进制的多少位
• 各 bucket 的 local_depth：记录定位到该 bucket 需要取 key 的二进制的多少位

Extendible Hash Table ? Chained Hash Table

• Extendible Hash 中，不同的指针可指向同一个 bucket；而 Chained Hash 中每个指针对应一个 bucket。
• 发生冲突时，Chained Hash 简单地将新的 value 追加到其 key 对应 bucket 链表的最后；而 Extendible Hash 中，若 bucket 到达容量上限，则对桶会进行一次 split 操作。

将键值对 (K, V) 插入 Extendible Hash Table 的流程：

1. 用哈希函数计算 K 对应的哈希值 H(K)，用此哈希值计算出索引 (取 H(K) 的低 global_depth 位)，将 V 放入索引对应的 bucket 中。? K 对应的 H(K) = 1010 0010b，此时 global_depth = 4，则对应 index = 0010，因此将 V 放入 directory 中 index 为 2 的指针对应的 bucket 中。
2. 若要插入的 bucket 已满，则对该 bucket 进行 split 操作：
   • 若 global_depth = local_depth，global_depth++，将 dir 容量扩充至2倍，dir 中新的 pointer 依此指向所有旧bucket
   • 创建两个深度为 local_depth + 1 的 bucket
   • 重分配旧 bucket 中所有键值对
   • 重分配dir 中指向旧 bucket 的指针为指向两个新 bucket 的指针
3. bucket 为未满状态，直接插入对应 bucket

Bucket 类

Bucket 类要实现方法：

auto Find(const K &key, V &value) -> bool; 给定 key，在 Bucket 中找到对应的 value。

auto Insert(const K &key, const V &value) -> bool; 若该 key 已在 Bucket 中存在，则更新 value，否则添加 kv pair。

auto Remove(const K &key) -> bool; 给定key，在 Bucket 中删除对应的 kv pair。

这些方法都比较简单，直接遍历 list_ 对象完成对应操作就行，这里不列代码了。

ExtendibleHashTable 类

成员变量

int global_depth_;    // The global depth of the directory
size_t bucket_size_;  // The size of a bucket
int num_buckets_;     // The number of buckets in the hash table
mutable std::mutex latch_;
std::vector<std::shared_ptr<Bucket>> dir_;  // The directory of the hash table

成员函数

初始化

要设置 global_depth = 0，num_buckets = 1，即只有一个 bucket，所有 key 都映射到该 bucket。

template <typename K, typename V>
ExtendibleHashTable<K, V>::ExtendibleHashTable(size_t bucket_size)
    : global_depth_(0), bucket_size_(bucket_size), num_buckets_(1) {
  auto b = std::make_shared<Bucket>(bucket_size_, 0);
  dir_.emplace_back(b);
}

IndexOf

总体功能描述：根据 global_depth 计算 key 对应的 bucket。

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::IndexOf(const K &key) -> size_t {
  int mask = (1 << global_depth_) - 1;  /// mask 表示 global_depth 位 1, 若 global_depth = 2, mask = 11
  return std::hash<K>()(key) & mask;    /// 取 key hash 值的低 mask 位
}

Insert ⭐️

总体功能描述：往 hash table 中加入一个 kv pair。

需要注意的是，要通过while循环判断桶满不满，而不是 if，因为可能一次分裂之后一个桶里的kv还是被分配到同一个桶。如 0=000，4=100，16=10000，在分裂三次之后，桶才有空位。

template <typename K, typename V>
void ExtendibleHashTable<K, V>::Insert(const K &key, const V &value) {
  std::scoped_lock<std::mutex> lock(latch_);
  // 若 bucket 满了，则要先创建桶
  while (dir_[IndexOf(key)]->IsFull()) {
    auto target_bucket = dir_[IndexOf(key)];
    /// 1. 若 global_depth = local_depth: 增加 global_depth, 扩容 dir, 对新的 pointer 指向旧 bucket
    int local_depth = target_bucket->GetDepth();
    if (global_depth_ == local_depth) {
      global_depth_++;
      size_t cap = dir_.size();
      dir_.resize(cap << 1);
      for (size_t i = 0; i < cap; i++) {
        dir_[i + cap] = dir_[i];
      }
    }

    /// 2. 创建两个 local_depth + 1 的 bucket
    int local_high_bit = 1 << local_depth;
    auto new_b0 = std::make_shared<Bucket>(bucket_size_, local_depth + 1);
    auto new_b1 = std::make_shared<Bucket>(bucket_size_, local_depth + 1);
    num_buckets_++;

    /// 3. 重分配旧 bucket 中的键值对
    for (auto &item : target_bucket->GetItems()) {
      if ((std::hash<K>()(item.first) & local_high_bit) != 0U) {
        new_b1->Insert(item.first, item.second);
      } else {
        new_b0->Insert(item.first, item.second);
      }
    }

    /// 4. 重分配 dir 中指向旧 bucket 的指针为指向两个新 bucket 的指针
    for (size_t i = 0; i < dir_.size(); i++) {
      if (dir_[i] == target_bucket) {
        if ((i & local_high_bit) != 0U) {
          dir_[i] = new_b1;
        } else {
          dir_[i] = new_b0;
        }
      }
    }
  }

  // bucket 没满，则直接插入
  dir_[IndexOf(key)]->Insert(key, value);
}

其他函数

还要实现 Find、Remove 方法，根据 key 查找完成对应的操作即可。

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::Find(const K &key, V &value) -> bool {
  std::scoped_lock<std::mutex> lock(latch_);
  return dir_[IndexOf(key)]->Find(key, value);
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::Remove(const K &key) -> bool {
  std::scoped_lock<std::mutex> lock(latch_);
  return dir_[IndexOf(key)]->Remove(key);
}

Task #2 - LRU-K Replacement Policy

缓存替换算法介绍

实现 LRUKReplacer 类，涉及文件：

• src/buffer/lru_k_replacer.cpp
• src/include/buffer/lru_k_replacer.h

LRU-K 算法是实现 Replacer 的一种策略。Replacer 的作用：当 Buffer Pool Manager 中 frame 满时，计算要移除掉哪个 frame。因此 Replacer 只需记录各 frame id，其的容量等于 Buffer Pool Manager 的容量（BPM能 存几个 frame，它就能存几个 frame id）。

LRU-K 基本原理：淘汰第 K 次访问时间距当前时间最大的数据。因此 LRU-K 需维护两个队列：历史队列、缓存队列。

成员变量

设置能不能被驱逐，就像 LRU 中的 pin 和 Unpin，但这里不能像 LRU 中一样直接将 frame 从 list 中删除 or 添加到 list。因为从 list 中增删将失去对该 frame 访问次数的记录。因此这里添加了一个 evictable_ 字段来标识能否被驱逐。

class FrameEntry {
 public:
  bool evictable_{true};  // 能不能被驱逐
  int access_count_{0};   // 访问次数
  std::list<frame_id_t>::iterator pos_;
};

std::list<frame_id_t> lru_k_history_list_;  // 记录未达到 k 次访问的 frame
std::list<frame_id_t> lru_k_cache_list_;    // 记录已达到 k 次访问的 frame
std::unordered_map<frame_id_t, FrameEntry> lru_k_map_;
size_t k_;
size_t cap_;  // Replacer能存的最大容量
size_t curr_size_{0};  // 当前Replacer的容量（指能被驱逐的frame数目）
std::mutex latch_;

成员函数

auto Evict(frame_id_t *frame_id) -> bool;  // 驱逐一个frame
void RecordAccess(frame_id_t frame_id);    // 记录一次对frame的访问
void SetEvictable(frame_id_t frame_id, bool set_evictable);  // 设置一个frame为可驱逐 or 不可驱逐
void Remove(frame_id_t frame_id);  // 删除一个 frame
auto Size() -> size_t;  // 返回当前 Replacer 的容量

初始化

需要对 Replacer 的容量和 K 进行初始化。

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : k_(k), cap_(num_frames) {}

Evict

总体功能描述：移除一个最近 K 次最少使用的 frame, 其 id 存储在输出参数中。若移除成功返回 true；失败（当前容量为空时）返回 false。

编写逻辑：

1. 若 Replacer 当前容量 <= 0，返回 false。
2. 否则，先移出历史链表中的数据，若历史链表中没有数据再移除 cache 队列中的。注意更新对应的数据结构。（移除 frame 前需先判断该 frame 是否能被驱逐 evictable_）
3. 考虑并发：对 Replacer 数据结构进行更改时要获取锁。

auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
  std::scoped_lock<std::mutex> lock(latch_);
  if (curr_size_ <= 0) {
    return false;
  }
  for (auto it = lru_k_history_list_.rbegin(); it != lru_k_history_list_.rend(); it++) {
    if (lru_k_map_[*it].evictable_) {
      *frame_id = *it;
      lru_k_history_list_.erase(lru_k_map_[*frame_id].pos_);
      lru_k_map_.erase(*frame_id);
      curr_size_--;
      return true;
    }
  }
  for (auto it = lru_k_cache_list_.rbegin(); it != lru_k_cache_list_.rend(); it++) {
    if (lru_k_map_[*it].evictable_) {
      *frame_id = *it;
      lru_k_cache_list_.erase(lru_k_map_[*frame_id].pos_);
      lru_k_map_.erase(*frame_id);
      curr_size_--;
      return true;
    }
  }
  return false;
}

RecordAccess

总体功能描述：记录一次对 frame 的访问

编写逻辑：

1. 首先要判断该 frame_id 是否合法。若合法，则进入下一步。
2. 否则，增加该 frame 的访问次数 hist_count。
   • 若增加后 hist_count = 1，证明该 frame 之前不存在，要加入历史队列；
   • 若增加后 hist_count = k，要将该 frame 从历史队列移到 cache 队列；
   • 若增加后 hist_count > k，要将该 frame 从 cache 队列中移到头部；
   • （若增加后 1 < hit_count < k，则不做任何操作，因为本题中要求历史队列 FIFO）。
3. 考虑并发：对 Replacer 数据结构进行更改时要获取锁。

void LRUKReplacer::RecordAccess(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  BUSTUB_ASSERT(frame_id <= static_cast<int>(cap_), " The frame id is invalid.");
  int hit_count = ++lru_k_map_[frame_id].access_count_;
  // new frame，要添加到 history_list
  if (hit_count == 1) {
    lru_k_history_list_.emplace_front(frame_id);
    lru_k_map_[frame_id].pos_ = lru_k_history_list_.begin();
    curr_size_++;
  } else if (hit_count == static_cast<int>(k_)) {  // hit_count = k, frame 从 history_list 转到 cache_list
    lru_k_history_list_.erase(lru_k_map_[frame_id].pos_);
    lru_k_cache_list_.emplace_front(frame_id);
    lru_k_map_[frame_id].pos_ = lru_k_cache_list_.begin();
  } else if (hit_count > static_cast<int>(k_)) {  // hit_count > k, frame 在 cache_list 中变为最新访问的
    lru_k_cache_list_.erase(lru_k_map_[frame_id].pos_);
    lru_k_cache_list_.emplace_front(frame_id);
    lru_k_map_[frame_id].pos_ = lru_k_cache_list_.begin();
  }
  // 1 < hist_count < k, no nothing, 因为 hist_list 中 frame 遵循 FIFO
}

SetEvictable

总体功能描述：设置一个 frame 为可驱逐 or 不可驱逐。类似 LRU 中的 Unpin 和 Pin 的功能。但这里不能像 LRU 中一样直接将 frame 从 list 中删除 or 添加到 list。因为从 list 中增删将失去对该 frame 访问次数的记录。

编写逻辑：

1. 首先要判断该 frame_id 是否合法。若合法，则进入下一步。
2. 若该 frame 不存在，则不做任何操作。
3. 否则找到该 frame，设置它的 evictable_ 字段，更新 curr_size_。
4. 考虑并发：对 Replacer 数据结构进行更改时要获取锁。

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  std::scoped_lock<std::mutex> lock(latch_);
  BUSTUB_ASSERT(frame_id <= static_cast<int>(cap_), " The frame id is invalid.");
  if (lru_k_map_.find(frame_id) == lru_k_map_.end()) {
    return;
  }
  if (lru_k_map_[frame_id].evictable_ != set_evictable) {
    lru_k_map_[frame_id].evictable_ = set_evictable;
    if (set_evictable) {
      curr_size_++;
    } else {
      curr_size_--;
    }
  }
}

Remove

总体功能描述：删除一个指定的 frame

编写逻辑：

1. 首先要判断该 frame_id 是否合法。若合法，则进入下一步。
2. 若该 frame 不存在，则不做任何操作。
3. 若该 frame 存在但不能被驱逐，则报错。若 frame 能被驱逐，则找到它并删除，更新相应的数据结构。
4. 考虑并发：对 Replacer 数据结构进行更改时要获取锁。

void LRUKReplacer::Remove(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  BUSTUB_ASSERT(frame_id <= static_cast<int>(cap_), " The frame id is invalid.");
  if (lru_k_map_.find(frame_id) == lru_k_map_.end()) {
    return;
  }
  BUSTUB_ASSERT(lru_k_map_[frame_id].evictable_, " The frame is non-evictable.");
  //  if (!lru_k_map_[frame_id].evictable_) {
  //    throw std::logic_error("The frame " + std::to_string(frame_id) + "is non-evictable.");
  //  }
  if (lru_k_map_[frame_id].access_count_ < static_cast<int>(k_)) {
    lru_k_history_list_.erase(lru_k_map_[frame_id].pos_);
  } else {
    lru_k_cache_list_.erase(lru_k_map_[frame_id].pos_);
  }
  lru_k_map_.erase(frame_id);
  curr_size_--;
}

Size

总体功能描述：返回 Replacer 当前的容量（指能被驱逐的 frame 数目）。

auto ClockReplacer::Size() -> size_t { return curr_size_; }

Task #3 - Buffer Pool Manager Instance

实现 BufferPoolManagerInstance 类，涉及文件：

• src/buffer/buffer_pool_manager.cpp
• src/include/buffer/buffer_pool_manager.h

BufferPoolManager 类维护一片内存区域 —— BufferPool，这片区域按照 page 的大小划分，称为 frame。采用 frame_id 访问该区域的对应 frame。page table 用于存储 page_id -> frame_id 的映射。Replacer 决定当内存区域满了时，驱逐哪个 frame 空出空间。

BPM 工作流程：上层 execution engine 提供 page_id 给 BPM 要求获取该 page，BPM 先在内存中查找该 page 是否存在【先在 page table 中查找 page_id 对应的 frame_id，若能找到，则根据该 frame_id 在 BufferPool 中找到对应 frame 并返回】。若找不到 frame_id，则该 page 不存在于内存，要从磁盘中读取。此时要先判断 BufferPool 中是否有空位能容纳该 page【若有空闲 frame 则可以容纳；若没有空闲 frame，则需要 Replacer 驱除一个 frame，空出位置；若当前所有 frame 都被 pin 而无法驱逐，则没有空位】若找到了空位就能从磁盘中读取该 page 到 frame，并返回给 execution engine。

代码中 BufferPool（frames）被实现为：存放 Page 类型对象的数组 pages_。空闲 frame_id 存放于链表 free_list_。

page table 被实现为：ExtendibleHashTable 类。Replacer 被实现为 LRUKReplacer 类。

成员变量

/** Array of buffer pool pages. */
Page *pages_;
/** Pointer to the disk manager. */
DiskManager *disk_manager_ __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. */
ExtendibleHashTable<page_id_t, frame_id_t> *page_table_;
/** Replacer to find unpinned pages for replacement. */
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_;

成员函数

易错点：

• NewPgImp() 中，不要一开始就调用 AllocatePage() 分配 pageId，只有当真的有空闲的 page 可以使用时，再调用 AllocatePage()分配一个 pageId 给它。
• 每一次获得一个新的 page，或者删除一个 page 时，请调用 page->ResetMemory() 方法将其数据重置掉，而不是放任不管，想着后面可以直接覆盖。
• UnpinPgImp() 时不要直接 page->is_dirty_ = is_dirty ，而是 入参 is_dirty 为 true 时才更新，不然会把 page 之前的 is_dirty 状态覆盖。
• FlushPgImp() 和 FlushAllPgsImp() 中只要将数据刷到磁盘并更新 is_dirty 状态就行，不要做多余操作，比如删除 page。
• 注意考虑并发，要加锁！

初始化

要创建 pages_、page_table_、replacer_，为 free_list_ 添加所有 frame_id，因为目前所有 frame 都是空闲的。

BufferPoolManagerInstance::BufferPoolManagerInstance(size_t pool_size, DiskManager *disk_manager, size_t replacer_k,
                                                     LogManager *log_manager)
    : pool_size_(pool_size), disk_manager_(disk_manager), log_manager_(log_manager) {
  // we allocate a consecutive memory space for the buffer pool
  pages_ = new Page[pool_size_];
  page_table_ = new ExtendibleHashTable<page_id_t, frame_id_t>(bucket_size_);
  replacer_ = new LRUKReplacer(pool_size, replacer_k);

  // 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));
  }
}

NewPgImp ⭐️

总体功能描述：创建一个新的 page，page_id 存储在输出参数中，page 具体的内容作为返回值。

编写逻辑：

1. 从 free list 或 replacer 中找到一个 replacement frame（总是先从 free list 找）。
2. 创建一个新页，获取其 page_id，重置数据域，设置 metadata。
3. 在哈希表中建立 page_id 到 frame_id 的映射关系。
4. 更新 Replacer（pin 住该 frame，并记录一次访问）。

其中找到一个 replacement frame，我们通过自定义一个辅助函数 GetAvailableFrame 实现，该函数需关注的是，若在 replacer 中找一个 replacement frame，要注意是否需写回脏页，且要在哈希表中删除原 page_id 到该 frame_id 的映射关系。

GetAvailableFrame

auto BufferPoolManagerInstance::GetAvailableFrame(frame_id_t *frame_id) -> bool {
  // 优先使用空闲 frame 作为 replacement frame
  if (!free_list_.empty()) {
    *frame_id = free_list_.front();
    free_list_.pop_front();
    return true;
  }
  // 没有空闲frame，则驱逐一个 frame，使用它的位置
  if (replacer_->Evict(frame_id)) {
    // 若 replacement frame 是个脏页，先写回磁盘
    if (pages_[*frame_id].IsDirty()) {
      disk_manager_->WritePage(pages_[*frame_id].GetPageId(), pages_[*frame_id].GetData());
      pages_[*frame_id].is_dirty_ = false;
    }
    // 删除原映射关系
    page_table_->Remove(pages_[*frame_id].GetPageId());
    return true;
  }
  return false;
}

NewPgImp ⭐️

auto BufferPoolManagerInstance::NewPgImp(page_id_t *page_id) -> Page * {
  std::scoped_lock<std::mutex> lock(latch_);
  frame_id_t frame_id;
  // 从 free list 或 replacer 中找到一个 replacement frame（总是先从 free list 找）
  if (GetAvailableFrame(&frame_id)) {
    // 创建一个新页，获取其 page_id 和 metadata，重置数据域
    *page_id = AllocatePage();
    pages_[frame_id].page_id_ = *page_id;
    pages_[frame_id].ResetMemory();
    pages_[frame_id].pin_count_ = 1;
    pages_[frame_id].is_dirty_ = false;
    // 建立哈希表中的映射关系
    page_table_->Insert(*page_id, frame_id);
    // "Pin"住该 frame 并记录一次访问
    replacer_->RecordAccess(frame_id);
    replacer_->SetEvictable(frame_id, false);
    return &pages_[frame_id];
  }
  return nullptr;
}

FetchPgImp

NewPgImp 和 FetchPgImp 的区别在于，NewPgImp 是要创建一个全新的page，FetchPgImp 是要获取一个已有的 page。

总体功能描述：根据 page_id 获取对应 page，page 具体的内容作为返回值。

编写逻辑：

1. 现在 Buffer Pool 中查找对应 page，若能找到则直接返回。注意更新 pin_count，更新 Replacer（pin 住该 frame，并记录一次访问）。
2. BP 中找不到则去磁盘中找，要先获取一个 replacement frame，再从磁盘中获取 page 数据。注意建立哈希表中的 page_id 到 frame_id 的映射关系，更新 Replacer。
3. 若磁盘中还是找不到，证明该 page 不存在，返回 nullptr。

auto BufferPoolManagerInstance::FetchPgImp(page_id_t page_id) -> Page * {
  BUSTUB_ASSERT(page_id != INVALID_PAGE_ID, " The page id is invalid.");
  std::scoped_lock<std::mutex> lock(latch_);
  frame_id_t frame_id;
  // 可以在 BPM 中找到对应 page，直接返回(注意更新 pin_count 和 replacer)
  if (page_table_->Find(page_id, frame_id)) {
    pages_[frame_id].pin_count_++;
    replacer_->RecordAccess(frame_id);
    replacer_->SetEvictable(frame_id, false);
    return &pages_[frame_id];
  }
  // BPM 中找不到该page，则要从磁盘获取。我们先在 BPM 中腾出空间：从 free list 或 replacer 中找到一个 replacement
  // frame（总是先从 free list 找）
  if (GetAvailableFrame(&frame_id)) {
    // 从磁盘获取 page
    pages_[frame_id].page_id_ = page_id;
    disk_manager_->ReadPage(page_id, pages_[frame_id].data_);
    pages_[frame_id].pin_count_ = 1;
    pages_[frame_id].is_dirty_ = false;
    //  建立哈希表中的映射关系
    page_table_->Insert(page_id, frame_id);
    // "Pin"住该 frame 并记录一次访问
    replacer_->RecordAccess(frame_id);
    replacer_->SetEvictable(frame_id, false);
    return &pages_[frame_id];
  }
  return nullptr;  // 腾不出空间，return nullptr
}

UnpinPgImp

总体功能描述：Unpin 一个 page，若找不到该 page，返回 false；若该 page 的 pin_count 本来就为 0，返回 false；若 pin_count 减少为 0，则设为可驱逐的，若该页是脏页，要更新 is_dirty 状态。

auto BufferPoolManagerInstance::UnpinPgImp(page_id_t page_id, bool is_dirty) -> bool {
  BUSTUB_ASSERT(page_id != INVALID_PAGE_ID, " The page id is invalid.");
  std::scoped_lock<std::mutex> lock(latch_);
  frame_id_t frame_id;
  if (page_table_->Find(page_id, frame_id)) {
    if (pages_[frame_id].GetPinCount() == 0) {
      return false;
    }
    pages_[frame_id].pin_count_--;
    if (pages_[frame_id].GetPinCount() == 0) {
      replacer_->SetEvictable(frame_id, true);
    }
    if (is_dirty) {
      pages_[frame_id].is_dirty_ = true;
    }
    return true;
  }
  return false;
}

FlushPgImp & FlushAllPgsImp

FlushPgImp：将给定 page_id 对应的 page 内容刷到磁盘。

FlushAllPgsImp：将所有 page 内容刷到磁盘。

⚠️ 只要将内容刷到磁盘并更新 is_dirty 状态就行，别做多余的操作。

auto BufferPoolManagerInstance::FlushPgImp(page_id_t page_id) -> bool {
  BUSTUB_ASSERT(page_id != INVALID_PAGE_ID, " The page id is invalid.");
  std::scoped_lock<std::mutex> lock(latch_);
  frame_id_t frame_id;
  if (page_table_->Find(page_id, frame_id)) {
    if (pages_[frame_id].is_dirty_) {
      disk_manager_->WritePage(page_id, pages_[frame_id].GetData());
      pages_[frame_id].is_dirty_ = false;
    }
    return true;
  }
  return false;
}

void BufferPoolManagerInstance::FlushAllPgsImp() {
  std::scoped_lock<std::mutex> lock(latch_);
  for (size_t i = 0; i < pool_size_; i++) {
    if (pages_[i].is_dirty_) {
      disk_manager_->WritePage(pages_[i].GetPageId(), pages_[i].GetData());
      pages_[i].is_dirty_ = false;
    }
  }
}

DeletePgImp

总体功能描述：根据 page_id 在 Buffer Pool 中删除该 page

编写逻辑：

1. 若 Buffer Pool 中找到 page，但其 pin_count > 0，不能驱逐，则返回 false
2. 若该 page 为脏页，则先将其内容刷入磁盘
3. 最后重置该 page 的数据和元数据，删除在哈希表中的映射和 Replacer 中的记录，并将其对应的 frame_id 加入空闲页链表 free_list_

auto BufferPoolManagerInstance::DeletePgImp(page_id_t page_id) -> bool {
  BUSTUB_ASSERT(page_id != INVALID_PAGE_ID, " The page id is invalid.");
  std::scoped_lock<std::mutex> lock(latch_);
  frame_id_t frame_id;
  if (page_table_->Find(page_id, frame_id)) {
    if (pages_[frame_id].GetPinCount() > 0) {
      return false;
    }
    if (pages_[frame_id].is_dirty_) {
      disk_manager_->WritePage(page_id, pages_[frame_id].GetData());
      pages_[frame_id].is_dirty_ = false;
    }
    DeallocatePage(page_id);
    pages_[frame_id].page_id_ = INVALID_PAGE_ID;
    pages_[frame_id].ResetMemory();
    page_table_->Remove(page_id);
    replacer_->Remove(frame_id);
    free_list_.emplace_back(frame_id);
    return true;
  }
  return true;
}

测试提交

参考

https://zhuanlan.zhihu.com/p/571927310

https://www.inlighting.org/archives/cmu-15-445-notes

https://ym9omojhd5.feishu.cn/docx/Fk5MdLNJuopJGaxcDHncC9wZnDg

前几年的project项目部分实现

LRU Replacement Policy

实现 LRUReplacer 类，涉及文件：

• src/buffer/lru_replacer.cpp
• src/include/buffer/lru_replacer.h

LRU 算法是实现 Replacer 的一种策略。Replacer 的作用：当 Buffer Pool Manager 中 frame 满时，计算要移除掉哪个 frame。因此 Replacer 只需记录各 frame id，其的容量等于 Buffer Pool Manager 的容量（BPM能 存几个 frame，它就能存几个 frame id）。

LRU 基本原理：淘汰最后一次访问时间距当前时间最大的数据。

考虑到数据库的特性，本题在最基础的 LRU 之上，还要考虑 Pin 操作。

成员变量

// 锁，对 LRU 进行并发操作时要用到
std::mutex latch_;
// 链表，使插入和删除操作的复杂度达到O(1)
std::list<frame_id_t> lru_list_;
// hash_map，映射key到list结点，使查找的复杂度达到O(1)
std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> lru_map_;
// Replacer能存的最大容量
size_t cap_;

成员函数

// 移除一个frame, 其id存储在输出参数中。若移除成功，返回true；失败（当前容量为空时）返回false
auto Victim(frame_id_t *frame_id) -> bool override;
// pin一个frame，让该frame不能被移除，将要其从list中删除
void Pin(frame_id_t frame_id) override;
// unpin一个frame，则将该frame放入list中
void Unpin(frame_id_t frame_id) override;
// 获取 Replacer 当前的容量
auto Size() -> size_t override;

初始化

需传入 page 的数目，来初始化 Replacer 的最大容量。

LRUReplacer::LRUReplacer(size_t num_pages) : cap_(num_pages) {}
LRUReplacer::~LRUReplacer() = default;

Victim

总体功能描述：移除一个最近最少使用的 frame, 其 id 存储在输出参数中。若移除成功返回 true；失败（当前容量为空时）返回 false。

编写逻辑：

1. 若 Replacer 当前容量 <= 0，返回 false。
2. 否则获取链表中最后一个元素作为要移除的元素。注意更新对应的数据结构。
3. 考虑并发：对 Replacer 数据结构进行更改时要获取锁。

auto LRUReplacer::Victim(frame_id_t *frame_id) -> bool {
  std::scoped_lock<std::mutex> lock(latch_);
  if (Size() <= 0) {
    return false;
  }
  *frame_id = lru_list_.back();
  lru_list_.pop_back();
  lru_map_.erase(*frame_id);
  return true;
}

Pin

总体功能描述：pin 一个 frame，让它不能被移除，则需将其从 list 中删除，这样移除 frame 时就不会考虑到它。

编写逻辑：

1. 通过 map 找该 frame id，若能找到，则将其从 map、list 中移除，更新 curr_size。
2. 考虑并发：对 Replacer 数据结构进行更改时要获取锁。

void LRUReplacer::Pin(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  if (lru_map_.find(frame_id) != lru_map_.end()) {
    lru_list_.erase(lru_map_[frame_id]);
    lru_map_.erase(frame_id);
  }
}

Unpin

总体功能描述：unpin 一个 frame，让它在之后仍能考虑被移除，则需将它添加到 list 中。

编写逻辑：

1. 若 Replacer 中已有该 frame（通过 map 能找到 frame id），则不做任何操作
2. 若 Replacer 中没有该 frame
   • 若 Replacer 满了，则要移除最近最少使用的一个 frame
   • 添加该 frame
3. 考虑并发：对 Replacer 数据结构进行更改时要获取锁

void LRUReplacer::Unpin(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  // 若 lru 中不存在该 frame 且 lru 满了，则要移除最近最少使用的frame
  if (lru_map_.find(frame_id) == lru_map_.end()) {
    if (cap_ == Size()) {
      frame_id_t *temp = nullptr;
      Victim(temp);
    }
    lru_list_.emplace_front(frame_id);
    lru_map_.insert(std::make_pair(frame_id, lru_list_.begin()));
  }
}

Size

总体功能描述：返回 Replacer 当前的容量。

auto LRUReplacer::Size() -> size_t { return lru_list_.size(); }

Clock Replacement Policy

实现 ClockReplacer 类，涉及文件：

• src/buffer/clock_replacer.cpp
• src/include/buffer/clock_replacer.h

Clock 算法也是实现 Replacer 的一种策略。

Clock 基本原理：为每个 page 保存一个标志位 reference bit，它告诉你自从上次检查完该 page 后，此 page 是否被访问了。

• 每当 page 被访问时，ref 设置为 true
• 每当需要移除 page 时，从上次访问的位置开始，按顺序轮询每个 page 的 ref，若为 true，则重置为 false；若为 false，则移除该 page

成员变量

// 锁，对 Replacer 进行并发操作时要用到
std::mutex latch_;
// vector 的序号对应frame_id_t, <该frame是否存在，该frame的ref>
std::vector<std::pair<bool, bool> > clock_list_;
// 当前要访问位置
size_t clock_hand_{0};
// Replacer能存的最大容量
int cap_;
// Replacer当前的容量，因为Clock不像LRU一样能快速获取当前容量，因此在这里记录一下
int curr_size_{0};

本来对于 Clock 想用类似 LRU 的以下数据结构实现，但是 list 只能循序访问，如果通过 clock_pos_添加/删除了元素，通过clock_pos_访问的顺序会乱掉。因此还是采用 vector 实现。

std::mutex latch_;
std::list<std::pair<frame_id_t, bool>> clock_list_;  // <frame_id, ref>
std::unordered_map<frame_id_t, std::list<std::pair<frame_id_t, bool>>::iterator> clock_map_;
std::list<std::pair<frame_id_t, bool>>::iterator clock_pos_;  // 下一次访问的位置
int cap_;

成员函数

要实现的方法与 LRU Replacement Policy 相同

// 移除一个frame, 其id存储在输出参数中。若移除成功，返回true；失败（当前容量为空时）返回false
auto Victim(frame_id_t *frame_id) -> bool override;
// pin一个frame，让该frame不能被移除
void Pin(frame_id_t frame_id) override;
// unpin一个frame，让该frame可以被移除
void Unpin(frame_id_t frame_id) override;
// 获取 Replacer 当前的容量
auto Size() -> size_t override;

初始化

需传入 page 的数目，来初始化 Replacer 的最大容量。

当前 vector 中所有能存放 frame 的位置，都尚未存放 frame，对应的 ref 也是 false。

ClockReplacer::ClockReplacer(size_t num_pages) : cap_(num_pages) {
  for (int i = 0; i < cap_; i++) {
    clock_list_.emplace_back(std::make_pair(false, false));
  }
}

Victim

总体功能描述：移除一个 frame, 其 id 存储在输出参数中。若移除成功返回 true；失败（当前容量为空时）返回 false。

编写逻辑：

1. 若 Replacer 当前容量 <= 0，返回 false。
2. 否则从当前要访问的位置开始访问，按顺序轮询每个 page 的 ref，若为 true，则重置为 false；若为 false，则移除该 page。更新对应的数据结构。
3. 考虑并发：对 LRU 数据结构进行更改时要获取锁。

auto ClockReplacer::Victim(frame_id_t *frame_id) -> bool {
  std::scoped_lock<std::mutex> lock(latch_);
  if (curr_size_ <= 0) {
    return false;
  }
  while (true) {
    std::pair<bool, bool> *temp_frame = &clock_list_[clock_hand_];
    if (temp_frame->first) {
      // ref = true, 设为false
      if (temp_frame->second) {
        temp_frame->second = false;
      } else {  // ref = false, 移除该 frame
        temp_frame->first = false;
        *frame_id = clock_hand_;
        clock_hand_ = (clock_hand_ + 1) % cap_;
        curr_size_--;
        return true;
      }
    }
    clock_hand_ = (clock_hand_ + 1) % cap_;
  }
}

Pin

总体功能描述：pin 一个 frame，让它不能被移除，则需在 vector 中设为不存在，这样移除 frame 时就不会考虑到它。

编写逻辑：

1. 首先要判断该 frame_id 是否合法。若合法，则进入下一步。
2. 若该 frame_id 对应的 frame 存在，则设为不存在，更新对应的数据结构。
3. 考虑并发：对 Replacer 数据结构进行更改时要获取锁。

void ClockReplacer::Pin(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  BUSTUB_ASSERT(frame_id <= static_cast<int>(cap_), " The frame id is invalid.");
  if (clock_list_[frame_id].first) {
    clock_list_[frame_id].first = false;
    clock_list_[frame_id].second = false;
    curr_size_--;
  }
}

Unpin

总体功能描述：unpin 一个 frame，让它在之后仍能考虑被移除，则需将它需在 vector 中设为存在。

编写逻辑：

1. 首先要判断该 frame_id 是否合法。若合法，则进入下一步
2. 若 Replacer 中没有该 frame，将它设为存在（temp_frame->first = true），更新 curr_size
3. 将该 frame 的 ref 设为 true
4. 考虑并发：对 Replacer 数据结构进行更改时要获取锁

void ClockReplacer::Unpin(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  BUSTUB_ASSERT(frame_id <= static_cast<int>(cap_), " The frame id is invalid.");
  std::pair<bool, bool> *temp_frame = &clock_list_[frame_id];
  if (!temp_frame->first) {
    temp_frame->first = true;
    curr_size_++;
  }
  if (!temp_frame->second) {
    temp_frame->second = true;
  }
}

Size

总体功能描述：返回 Replacer 当前的容量。

auto ClockReplacer::Size() -> size_t { return curr_size_; }

本栏目推荐文章
• IDEA项目名称后面出现中括号，模块Modules的名子和文件夹名称不同，可以右键修改名称也可以在File->Project Structure 修改Modules的Name(快捷键ctrl+Shift+Alt+s)
• 多路io复用pool [补档-2023-07-19]
• devicemapper 存储驱动中的 Thin Pool 的可用数据块数量不足
• devmapper: Thin Pool has 162394 free data blocks which is less than minimum required 163840 free data blocks
• PicoCTF_2018_buffer_overflow_2
• Vscode插件Project Manager管理项目器无法显示新建标签的解决方法
• keil 工程编译报错browse infomation of one or more files is not available: ……Doing a project rebuild might fix this.
• PicoCTF_2018_buffer_overflow_1
• 浅谈sql执行流程、innodb架构设计、buffer pool缓存池
• 【Idea・Spring】Maven形のSpringBootのprojectを手動で構築するマニュアル

Project Buffer Poolproject buffer pool buffer_pool project buffer pool buffer_pool innodb_buffer_pool_size buffer mysql pool buffer 15445 pool cmu innodb_buffer_pool_size动态innodb buffer 引擎innodb buffer pool 页面innodb buffer pool project buffer 15445 2020