Project1：Buffer Pool Manager

1 基本介绍

缓冲池作为物理页面在主内存和磁盘的移动介质。这使得DBMS操作大于系统可用内存量的数据库。

我们只需要实现提供的API即可

2 实验内容

2.1 LRU Replacement Policy

该部分需要完成跟踪缓冲池中页面的使用情况。

需要实现LRUReplacer in src/include/buffer/lru_replacer.h和它对应的cpp文件src/buffer/lru_replacer.cpp

LRUReplacer的大小和缓冲池相同，因为包含了BufferPoolManager的所有frames。但并不是所有frames都被认为在LRUReplacer，LRUReplacer被初始化为没有frame。然后，在 LRUReplacer 中只会考虑新未固定的那些。

需要实现以下方法：

Victim(T*)：删除与Replacer跟踪的所有元素相比最近被访问次数最少的对象，将其内容存储在输出参数中并返回True。如果Replacer是空的，则返回False。
Pin(T)：这个方法应该在一个页面被pin在BufferPoolManager的一个frame上之后被调用。它应该从LRUReplacer中删除包含pin的页面的frame。
Unpin(T)：当一个页面的pin_count变成0的时候，这个方法应该被调用。这个方法应该把包含unpin的页面的frame添加到LRUReplacer。
Size()：该方法返回当前在LRUReplacer中的frame的数量。

理解pin和unpin：pin是指取走特定页，unpin是指添加page，这里注意实现的重复添加时后一次添加是不起作用的

2.2 Buffer Pool Manager

实现一个缓冲池管理器，负责从DiskManager中获取数据库页面并存储到内存中。要注意将旧页面逐出，将脏页写入磁盘，为新页腾出空间。

lab已经实现了实际读取和写入磁盘的代码（DiskManager），我们要实现要注意以下几点：

所有内存页面通过Page对象表示，每个Page对象包含一块内存，而且Page只是相当于一个内存容器，可以重用相同的Page来存储数据。也就是说，同一个Page对象可能包含不同的物理页面。
Page对象的标识符 (page_id) 跟踪它包含的物理页面；如果 Page对象不包含物理页面，则其 page_id必须设置为 INVALID_PAGE_ID。
每个 Page 对象还维护一个计数器，用于“固定”该页面的线程数。不允许BufferPoolManager释放已固定的页面。
每个 Page 对象要跟踪它是否脏。要记录页面在取消固定之前是否被修改。BufferPoolManager必须将脏页的内容写回磁盘，然后才能重用该对象。
对于FetchPageImpl，如果空闲列表中没有可用的页面，并且所有其他的页面都被钉住了，你应该返回NULL。FlushPageImpl应该刷新一个页面，不管它的引脚状态如何。

BufferPoolManager实现将使用前面步骤中创建的 LRUReplacer类。它将使用 LRUReplacer来跟踪访问 Page对象的时间，以便在必须释放帧以腾出空间从磁盘复制新物理页面时决定驱逐哪个对象。

在源文件 (src/buffer/buffer_pool_manager.cpp) 中实现头文件 (src/include/buffer/buffer_pool_manager.h) 中定义的以下函数：

FetchPageImpl(page_id)：从缓冲池中获取请求的页面
NewPageImpl(page_id)：在缓冲池中创建一个新页面
UnpinPageImpl(page_id, is_dirty)：从缓冲池中取消固定（unpin）目标页面
FlushPageImpl(page_id)：将目标页刷入磁盘
DeletePageImpl(page_id)：从缓冲池中删除某页
FlushAllPagesImpl()：将缓冲池中的所有页面刷新到磁盘

2.3 PARALLEL BUFFER POOL MANAGER

实现一个并行缓冲池管理器（ParallelBufferPoolManager），它包含多个``BufferPoolManagerInstances。对于每个操作，ParallelBufferPoolManager选择一个 BufferPoolManagerInstance`并委托给该实例。

使用模运算来映射到对应的实例，实现以下函数：

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()

3 实验思路

3.1 Task1

设计一个LRUReplacer，里面维护着unpinned page，指的是那些不被使用但任有意义的page。

LeetCode上有类似的题146. LRU 缓存 - 力扣（LeetCode） (leetcode-cn.com)

class LRUReplacer : public Replacer {
 public:
  /**
   * Create a new LRUReplacer.
   * @param num_pages the maximum number of pages the LRUReplacer will be required to store
   */
  explicit LRUReplacer(size_t num_pages);

  /**
   * Destroys the LRUReplacer.
   */
  ~LRUReplacer() override;

  bool Victim(frame_id_t *frame_id) override;

  void Pin(frame_id_t frame_id) override;

  void Unpin(frame_id_t frame_id) override;

  size_t Size() override;

 private:
  // TODO(student): implement me!
  std::mutex latch_;
  std::list<frame_id_t> list_unpinned_;
  std::unordered_map<frame_id_t , std::list<frame_id_t>::iterator> map_frames_;
  size_t pages_num;
};

这里放.h就好了。

3.2 Task2

设计时要先弄清楚以下数据结构：

Page

DiskManager

以下变量：

pages_：保存Buffer Pool中存在的page

page_table_：维护page_id与frame_id的映射

replacer_：可以理解为一个查找器，查找unpinned的页面并进行替换，实现的是LRU方式则用哈希表+链表维护对应的页表（frame）号

free_list_：记录Buffer Pool中哪些缓存页是可用的，里面的页数据都是无意义的，没有线程在使用

注意frame与page：两者其实是一个东西，在Buffer Pool通常称为frame，在磁盘中称为Page

譬如page_id和frame_id：前者指的是某一个page编号，比如disk上第十个page；后者指的是BufferPoolManager中的页框号码。

4 自问自答

为什么有了replacer还要有free_list？

replacer里维护的是没有线程操作，但还存在内存中的页，也就是unpinned的页，它们随时可能会被delete进入free_list；free_list中维护的已经刷入磁盘的页，它们在缓冲池的页框已经空了。可以认为unpinned里的随时可以回收，free的已经回收。

frame和page究竟有什么区别？

buffer pool 的操作的基本单位为一段逻辑连续的字节数组，在磁盘上表现为页（page），有唯一的标识 page_id；在内存中表现为帧（frame），有唯一的标识 frame_id。通过page table来记录哪些frame存的哪些page

为什么需要替换策略？

管理帧的内存池大小一般来说是远小于磁盘的，因此在内存池满了后，再从磁盘加载新的页到内存池，需要某种替换策略（replacer）将一些不再使用的页踢出内存池以腾出空间。

为什么DBMS要设计一个BPM来管理内存，而不要OS来管理内存？

OS会将Page当作一个临时数据，当查询结束就会删除Page；使用DBMS可以设计更多的方案，例如选择替换策略

Buffer pool的作用，为什么要用Buffer Pool，和操作系统的虚拟内存有什么区别？

Buffer Pool是数据库内部分配的一个大的内存区域，用来存储从磁盘中获取的页面（在MySQL中，默认大小为128MB）