CMU15-445-Spring-2023-Project #1 - Buffer Pool

在存储管理器中实现缓冲池。缓冲池负责将物理页从主内存来回移动到磁盘。它允许 DBMS 支持大于系统可用内存量的数据库。缓冲池的操作对系统中的其他部分是透明的。例如，系统使用page唯一标识符（page_id_t）向缓冲池请求一个页面，但系统并不知道该页面是否已在内存中，也不知道系统是否需要从磁盘中获取该页面。
实现必须是线程安全的。

Task #1 - LRU-K Replacement Policy

这部分负责追踪缓冲池中的页面使用。
Impl：
src/include/buffer/lru_k_replacer.h
src/buffer/lru_k_replacer.cpp

LRU-K算法的基本思想是维护一个大小为K的历史记录，记录最近K次访问的信息。当需要替换缓存中的数据时，LRU-K会根据这个历史记录来判断哪些数据是最近最少使用的，然后将其替换出去。

与LRU相比，LRU-K增加了对历史访问的考量，因此更加灵活，能够更好地适应不同访问模式下的缓存需求。
LRU-K 算法驱逐的帧的后向 k 距离是替换器中所有帧的最大值。后向 k 距离计算为**当前时间戳（指当前时间而不是history中最近时间戳）**与前第 k 次访问时间戳之间的时间差。历史访问次数少于 k 次的帧的后向 k 距离为 +inf。当多个帧的后向 k 距离为 +inf 时，替换者会驱逐history中最末时间戳最小的帧。

• Evict(frame_id_t* frame_id)：驱逐与所有其他可驱逐帧相比后向 k-distance 最大的帧。在输出参数中存储帧 ID 并返回 True。如果没有可驱逐帧，则返回 False。驱逐不同于remove，区别在于只需要将is_evictable_置为false即可。
• RecordAccess(frame_id_t frame_id)：记录给定帧 ID 在当前时间戳被访问，没有存储该帧则新建一个node，此方法应在页面被固定在 BufferPoolManager 中后调用。
• Remove(frame_id_t frame_id)：清除指定帧的所有访问历史记录，并从node_store_中删除。只有在 BufferPoolManager 中删除页面时才调用此方法。
• SetEvictable(frame_id_t frame_id, bool set_evictable)：该方法控制帧是否可驱逐。它还控制 LRUKReplacer 的大小。具体来说，当某个页面的引用计数达到 0 时（pageGuard进行drop->bpm进行unpin），其对应的帧就会被标记为可驱逐，替换器的大小也会随之增加。
• Size()：该方法返回当前 LRUKReplacer 中可驱逐帧的数量。

Task #2 - Buffer Pool Manager

实现缓冲池管理器（BufferPoolManager）。BufferPoolManager 负责从 DiskManager 抓取数据库页面并将其存储到内存中。BufferPoolManager 还可以在收到明确指示或需要删除页面以便为新页面腾出空间时，将脏页面写出到磁盘。

系统中的所有内存页面都由 Page 对象表示。缓冲池管理器无需了解这些页面的内容。Page 对象只是缓冲池中内存的容器，也就是说，每个页面对象都包含一个内存块，DiskManager 将把它用作从磁盘读取物理页面内容的复制位置。缓冲池管理器（BufferPoolManager）会重复使用同一个页面对象来存储数据，因为数据会在磁盘上来回移动。这意味着，在系统的整个生命周期中，同一个页面对象可能包含不同的物理页面。页面对象的标识符（page_id）可追踪其包含的物理页面；如果页面对象不包含物理页面，则其 page_id 必须设置为 INVALID_PAGE_ID。

每个页面对象还维护一个计数器（pincount），用于记录 “固定” 该页面的线程数。缓冲池管理器不允许释放被钉住的页面。每个页面对象也会记录它是否变脏（write过）。需要记录页面在解除固定前是否被修改过。BufferPoolManager 必须先将脏页面的内容写回磁盘，然后才能重新使用该对象。

BufferPoolManager 实现将使用 LRUKReplacer 类。LRUKReplacer 将跟踪页面对象被访问的时间，以便在必须释放帧以腾出空间从磁盘复制新的物理页面时，决定驱逐哪个页面对象。在 BufferPoolManager 中将 page_id 映射到 frame_id 时，请再次注意 STL 容器不是线程安全的。
Impl：
src/include/buffer/buffer_pool_manager.h
src/buffer/buffer_pool_manager.cpp

• FetchPage(page_id_t page_id)：从缓冲池中获取指定page，此时增加pincount，且无法被驱逐；如果page不在缓冲池中，从空闲列表或替换器中选择一个frame（总是先从空闲列表中查找），通过调用 disk_manager_->ReadPage() 从磁盘读取页面，然后替换frame中的旧页面。如果空闲列表中没有可用页面，且所有其他页面当前都被固定（evictable），则应返回 nullptr。如果旧页面is dirty，需要先写入磁盘。
• UnpinPage(page_id_t page_id, bool is_dirty)：is_dirty 参数会跟踪页面在固定期间是否被修改，如果页面之前is_dirty就为true，但是还没有写入磁盘，这时就不能置为false。如果pincount减为0了，需要将驱逐标记设为true。
• FlushPage(page_id_t page_id)：刷新页面，将页面写入磁盘，而不管其固定状态如何。
• NewPage(page_id_t* page_id)：在缓冲池中创建一个新的page，AllocatePage() 私有方法会为 BufferPoolManager 提供一个唯一的新页面 ID。
• DeletePage(page_id_t page_id)：删除缓冲池中的指定page，DeallocatePage() 方法是一个无操作的方法，它模仿释放磁盘上的页面。
• FlushAllPages()

DiskManager::WritePage() 函数需要在获取的页面为脏时，或者刷新页面时调用。不要忘记unset页面的is dirty标记。

Task #3 - Read/Write Page Guards

在缓冲池管理器中，FetchPage 和 NewPage 函数返回的指针指向已被钉住的页面。钉住机制确保在页面上没有更多读写之前，页面不会被驱逐。要表明内存中不再需要该页面，必须手动调用 UnpinPage。

实现用于存储 BufferPoolManager 和 Page 对象指针的 BasicPageGuard。页面防护确保一旦相应的页面对象退出作用域（析构），就会调用 UnpinPage。

由于 BasicPageGuard 隐藏了底层的页面指针，因此它还可以提供 read-only/write API，这些 API 可提供编译时检查，以确保为每个用例正确设置 is_dirty 标志。

在未来的项目中，多个线程将读写同一页面，因此需要读写器锁存来确保数据的正确性。请注意，在页面类中，有相关的锁定方法用于此目的。与取消页面锁定类似，在使用页面后可能会忘记取消锁定。为了缓解这一问题，将实现 ReadPageGuard 和 WritePageGuard，一旦页面超出范围，它们就会自动解除锁定。

Impl：
src/storage/page/page_guard.cpp
src/buffer/buffer_pool_manager.cpp

实验结果

优化方面，减少stl的使用会明显增加qps。