CMU 15-445 2021 Fall Project1 Buffer Pool

CMU 15-445
,

CMU 15-445 的配套项目 BusTub 是一个面向磁盘的 DBMS，所以首先要做的事就是写一个缓存池来管理从磁盘上拉取的页，因为 DBMS 是不能直接在磁盘上的进行修改的，需要通过缓存池。

缓存池负责将磁盘上的页放入内存或反之。缓存池可以让 DBMS 感觉可用内存比实际的内存要大（有点像虚拟内存的概念）。

本次项目有三个任务，分别是：

  1. LRU Replacement Policy：实现 LRU 替换机制。
  2. Buffer Pool Manager Instance：实现缓存池管理器的实例。
  3. Parallel Buffer Pool Manager：实现并行的缓存池管理器。

项目说明书链接：https://15445.courses.cs.cmu.edu/fall2021/project1/

TASK #1 - LRU REPLACEMENT POLICY

任务

实现一个 LRUReplacer 来进行页的调度，需要实现以下方法：

  • Victim(frame_id_t*)：将最近最少使用的页的帧号从 Replacer 中移除并返回。
  • Pin(frame_id_t)：将指定页的帧从 Replacer 中移除。
  • Unpin(frame_id_t)：将指定页的帧添加到 Replacer 中，BufferPoolManager 在调用该方法时，页的 pin_count 必须是 0，即当前没有线程在使用这个页。
  • Size()：返回 Replacer 的长度。

概念

首先要区分帧号和页号的概念，页号指的是磁盘中页存储位置，而帧号是该页的拷贝在缓存池中的位置。所以上述方法实际上操作的都是帧号，BufferPoolManagerInstance 在这些方法返回帧号后，再根据帧号，在缓存池的 pages_ 数组中将真正的页取出来。

img

然后就是 pin 和 unpin 的概念，pin 了某个帧指的是当前有线程在使用这个帧中的页，每有一个线程使用了该页，就会将其 pin_count 加 1，所以 Pin 函数的作用是将其从 Replacer 中移除，这样当有其他线程调用 Victim 函数时，这个被 Pin 的页就不会被替换算法踢出内存。unpin 就是相反的，当线程使用完了该页时，就会将 pin_count 减 1，当 pin_count 变成 0 时，就调用 Unpin 函数将其重新放进 Replacer 中，等待被替换出去。

实现

LRU 的实现有一个很常见的想法就是使用一个队列来实现，最近刚用过的帧会被插到队尾，那么队首就是最近最少使用的帧，所以 Victim 函数就直接将队首元素出队即可，Unpin 函数也只需要将 unpin 的那个帧插入队尾即可。

但问题在于 Pin 函数，因为如果要将一个元素直接移除出队列的话，都需要遍历一遍整个队列，这样就造成了性能的损失。所以我们可以使用一个 unordered_map 来存储每个元素在队列中的位置，C++ 的话可以存储该元素的迭代器，那么就可以直接通过 erase 函数来将该元素移除。

1
2
std::list<frame_id_t> frame_id_list_;
std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> location_map_;

其他需要注意的点就是尽量使用 count 函数代替 find 函数，用 emplace_back 函数取代 push_back函数，可以提高性能。还有就是移除的时候需要判断一下 Replacer 是不是已经空了。

Task #2 - BUFFER POOL MANAGER INSTANCE

任务：

  • FetchPgImp(page_id)：根据 page_id 从磁盘中拉取页并放入缓存池中。
  • UnpinPgImp(page_id, is_dirty)：将指定页的 pin_count 减 1，如果 pin_count 等于 0 了就调用 Unpin 函数将这个帧放入 Replacer 中。
  • FlushPgImp(page_id)：将对应的页刷入磁盘中。
  • NewPgImp(page_id)：创建一个新的页。
  • DeletePgImp(page_id)：删除一个页。
  • FlushAllPagesImpl()：将所有页刷入磁盘中。

概念

操作磁盘的 DiskManager 此次实验已经提供了，不需要自己实现。关于 Page 对象的介绍一定要仔细看项目说明里的内容。

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

每个 Page 对象还维护一个计数器，用于 “pinned” 该页面的线程数。BufferPoolManagerInstance 不允许释放pinned 的页面。 每个 Page 对象还跟踪它是否是 dirty 状态。如果一个页被修改了，那应该将其设置为 dirty 状态。 BufferPoolManagerInstance 必须将脏页的内容写回磁盘，然后才能重用该对象。

实现

这几个函数实现起来还是相对简单的，基本上都给出了详细的步骤，并且可以结合头文件中的注释来写，这里只记录一下碰到的一些坑。

  1. 在 FlushPgImp 函数中，不要去做多余的判断，因为文档注释中已经明确指出只有在页表中找不到该页的时候才返回 false，否则返回 true。并且不管这个页是否是脏页都将其写回磁盘，否则有些测试是无法通过的。

  2. 在 NewPgImp 函数和 FetchPgImp 函数中，需要判断缓存池是否已满和缓存池中的页是否都是 pinned 状态：If all the pages in the buffer pool are pinned, return nullptr。但很容易由于这句话而去循环遍历所有的页来判断，其实并不需要，我的做法是判断空闲列表是否为空且 Replacer 的长度是否为 0。如果空闲列表不为空，那肯定是可以拉取页的；如果空闲列表为空，但是 Replacer 的长度不为 0，就代表可以将 Replacer 中标记的页替换出去，仍旧可以拉取页。if (free_list_.empty() && replacer_->Size() == 0) { return nullptr; }

  3. 使用 NewPgImp 函数创建新页时，一定要先确定是可以创建时再调用 AllocatePage 函数。

  4. UnpinPgImp 函数中，不能直接将 is_dirty 参数设置到属性中，需要判断一下 is_dirty 是否为 true。如果参数是 false，而实际上该页是脏页，那么就可能会丢失数据。

  5. 使用std::lock_guard<std::mutex> guard(latch_)来给函数上锁，在 return 的时候会自动释放锁。

TASK #3 - PARALLEL BUFFER POOL MANAGER

任务

  • ParallelBufferPoolManager(num_instances, pool_size, disk_manager, log_manager)
  • ~ParallelBufferPoolManager()
  • GetPoolSize()
  • GetBufferPoolManager(page_id)：根据 page_id 获取对应的 BufferPoolManagerInstance。
  • FetchPgImp(page_id)
  • UnpinPgImp(page_id, is_dirty)
  • FlushPgImp(page_id)
  • NewPgImp(page_id)
  • DeletePgImp(page_id)
  • FlushAllPagesImpl()

概念

单个 BufferPoolManagerInstance 需要使用锁以保证线程安全，在线程多的情况下会造成大量的竞争，所以该任务的意图就是使用多个 BufferPoolManagerInstance 来解决大量竞争的问题。

实现

Task 3 的实现就比较简单了，基本上方法就是两行代码，首先使用 GetBufferPoolManager 获取 BufferPoolManagerInstance，再调用对应方法即可。可以使用一个数组来存储这些 BufferPoolManagerInstance，在构造函数中对其进行初始化。参数中的 num_instances 是 BufferPoolManagerInstance 的数量，instance_index 是每个 BufferPoolManagerInstance 对应的索引，初始化的时候要注意一下不要写反。

唯一一个不是两行搞定的就是 NewPgImp 函数，该函数的时候使用 round robin 的方式从一个起始位置（一开始设置为 0 ）开始遍历，直到成功返回 page 或者索引又回到了起始位置返回 nullptr，遍历结束后将起始索引顺序移动一位（需要用模运算，因为相当于在一个环中移动）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Page *ParallelBufferPoolManager::NewPgImp(page_id_t *page_id) {
  std::lock_guard<std::mutex> guard(latch_); // 只在该函数中加了锁
  size_t index = next_index_;
  Page *page;
  do {
    page = buffer_pool_manager_instances_[index]->NewPage(page_id);
    if (page != nullptr) {
      break;
    }
    index = (index + 1) % num_instances_;
  } while (index != next_index_);
  next_index_ = (next_index_ + 1) % num_instances_;
  return page;
}

总结

Project 1 虽然比较简单，但通过本次项目对缓存池有了一个更深的理解，代码提交之后 leaderboard 排到 80 多名，等再学一段时间 C++ 尝试优化一下，现在这门语言对我的心智负担太重了。往后有时间的话也可以看一下 DiskManager 具体是怎么实现的，