CMU15-445-P1 Buffer Pool Manager

[CMU15-445] P1 Buffer Pool Manager

Task #1 - LRU-K Replacement Policy

任务要求

This component is responsible for tracking page usage in the buffer pool. You will implement a new class called LRUKReplacer in src/include/buffer/lru_k_replacer.h and its corresponding implementation file in src/buffer/lru_k_replacer.cpp. Note that LRUKReplacer is a stand-alone class and is not related to any of the other Replacer classes. You are expected to implement only the LRU-K replacement policy. You don’t have to implement LRU or a clock replacement policy, even if there is a corresponding file for it.

The LRU-K algorithm evicts a frame whose backward k-distance is maximum of all frames in the replacer. Backward k-distance is computed as the difference in time between current timestamp and the timestamp of kth previous access. A frame with fewer than k historical accesses is given +inf as its backward k-distance.

When multiple frames have +inf backward k-distance, the replacer evicts the frame with the earliest overall timestamp (i.e., the frame whose least-recent recorded access is the overall least recent access, overall, out of all frames).

LRU-K算法会淘汰在替换器中所有帧中，后向k距离最大的帧，即backward k-distance

后向k距离是当前时间戳和第k次以前访问的时间戳之间的差值。

历史访问次数少于k的帧被赋予+inf作为其后向k距离。

当多个帧具有+inf的后向k距离时，替换器将淘汰具有最早整体时间戳（即最近记录的访问，是所有帧中最近的访问）的帧。

总结：

优先淘汰距离最大的frame (Backward k-distance)
少于K次访问，距离是无穷大inf，优先被淘汰。
当有多个无穷大时，优先淘汰整体时间戳最早的，FIFO策略

The maximum size for the LRUKReplacer is the same as the size of the buffer pool since it contains placeholders for all of the frames in the BufferPoolManager. However, at any given moment, not all the frames in the replacer are considered to be evictable. The size of LRUKReplacer is represented by the number of evictable frames. The LRUKReplacer is initialized to have no frames in it. Then, only when a frame is marked as evictable, replacer’s size will increase.

LRUK替换器的最大大小与缓冲池的大小相同，因为它包含缓冲池管理器中所有帧的占位符。然而，在任何时刻，替换器中的并非所有帧都被视为可驱逐的。

LRU-K替换器的大小由可驱逐帧的数量表示。LRUK替换器被初始化为空，只有在标记某个帧为可驱逐时，替换器的大小才会增加。

总结：

只有被标记为可驱逐的frame 并且传入是要驱逐时，才能被驱逐，替换器的大小才会增加

要求实现以下5个API,

You will need to implement the LRU-K policy discussed in this course. You will need to implement the following methods as defined in the header file (src/include/buffer/lru_k_replacer.h) and in the source file (src/buffer/lru_k_replacer.cpp):

Evict(frame_id_t* frame_id) : Evict the frame with largest backward k-distance compared to all other evictable frames being tracked by the Replacer. Store the frame id in the output parameter and return True. If there are no evictable frames return False.

淘汰：淘汰具有与替换器跟踪的所有其他可淘汰帧，相比最大后向k距离的帧。

将frame id存储在输出参数中并返回True。

如果没有可淘汰的帧，则返回False。
RecordAccess(frame_id_t frame_id) : Record that given frame id is accessed at current timestamp. This method should be called after a page is pinned in the BufferPoolManager.

访问帧：记录给定的帧ID在当前时间戳被访问。

此方法应在页面在BufferPoolManager中固定之后调用。
Remove(frame_id_t frame_id) : Clear all access history associated with a frame. This method should be called only when a page is deleted in the BufferPoolManager.

移除帧：清除与帧相关联的所有访问历史记录。

此方法仅在BufferPoolManager中删除页面时调用。
SetEvictable(frame_id_t frame_id, bool set_evictable) : This method controls whether a frame is evictable or not. It also controls LRUKReplacer‘s size. You’ll know when to call this function when you implement the BufferPoolManager. To be specific, when pin count of a page reaches 0, its corresponding frame is marked evictable and replacer’s size is incremented.

设置为可驱逐：此方法控制帧是否可淘汰。它还控制LRUKReplacer的大小。

当您实现BufferPoolManager时，将会知道何时调用此函数。

具体而言，当页面的固定计数达到0时，其对应的帧将被标记为可淘汰，并增加替换器的大小。
Size() : This method returns the number of evictable frames that are currently in the LRUKReplacer.

容量大小：此方法返回当前在LRUKReplacer中可淘汰的帧数，即LRU-K替换器的大小。

The implementation details are up to you. You are allowed to use built-in STL containers. You may assume that you will not run out of memory, but you must make sure that your implementation is thread-safe.

前置知识

通用的lab分析流程

从测试代码入手（TDD：测试驱动开发）

分析类的成员函数（实现5个API）

根据要求或提示，实现每个函数具体的细节

调试时格式化代码

这部分需要我们完成该组件中，负责跟踪缓冲池中的页面使用情况的实现，即LRU-K替换策略的实现

先要理清LRU-K的原理，这里使用两个队列来实现
相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。

只有当数据的访问次数达到K次的时候，才会将数据放入缓存队列。

当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。

【参考文档 LRU-K相关原理介绍】

【题解 LeetCode 146. LRU缓存机制】
01.历史队列
- 历史队列中的数据为第一次访问时的位置，只要未达到k次访问频率，位置一直保持不变。
- 实现数据结构：双向链表+哈希表
- 淘汰策略：FIFO
02.缓存队列
- 大于等于k次的访问频率，需要根据最近的访问时间切换元素在队列中的位置，类似于LRU。
- 实现数据结构：双向链表+哈希表
- 淘汰策略：LRU

实现5个API

每个frame_id都唯一对应一个Page_Table中的一个page_id, 可以理解为放入队列中槽的具体位置

每次缓冲池的新建页表或者取出一个页表，都要进行LRU-K的策略(淘汰不常用的内存页面，来保证读写的高效性)

注意事项:

构造函数要补充完整，给自定义成员变量完成初始化操作;

同时要保证多线程情况下是线程安全的;

考虑边界情况，进行入参判断。

具体处理逻辑:

RecordAccess(frame_id_t frame_id)

访问帧操作，(考虑把帧放入历史队列还是缓存队列)

利用哈希表，每次访问统计frame_id的出现频次

01.到达LRU-K的K次时，放入缓存队列

02.超过K次时，表明它已经在缓存队列里了，需要更新它在缓存队列的位置（放在队头）

03.小于K次时，只对于第一次访问时，放入历史队列（放在队头）
SetEvictable(frame_id_t frame_id, bool set_evictable)

通过传入的参数set_evictable，来设置当前frame_id是否可以淘汰/驱逐；

根据原先的is_accessible_[frame_id] 和当前set_evictable的状态，更新当前替换器的大小；

同时更新标记当前帧是否可驱逐掉的状态。
Evict(frame_id_t* frame_id) FIFO策略 + LRU策略

开始进行淘汰操作，返回的是实际被淘汰掉的帧id, 并且返回给frame_id

从两个队列的尾部开始遍历，找到一个可驱逐的帧id；

需要注意以下两个操作的实现步骤区别；

注意，这里先要移除hash表中的值，再从队列里的链表移除对应的指针（防止访问已经被释放的内存，防止出现内存泄漏）；

01.驱逐前先要将已有的帧信息清空(包括从哈希表中移除，*it才可得到帧id)

02.后面才从队列移除it，并更新替换器的大小，让缓存池容量减1
Remove(frame_id_t frame_id)

移除/删除操作，清理两个队列中的数据，清除与帧相关联的所有访问历史记录。

未到K，在历史队列中，否则在缓存队列中，都要完成哈希表和对应队列的数据移除。

Size()

返回当前替换器的容量/缓存池的容量。

代码实现

balabala…

Task #2 - Buffer Pool Manager

任务要求

Next, implement the buffer pool manager (BufferPoolManager). The BufferPoolManager is responsible for fetching database pages from the DiskManager and storing them in memory. The BufferPoolManager can also write dirty pages out to disk when it is either explicitly instructed to do so or when it needs to evict a page to make space for a new page.

// 负责实现从BufferPoolManager中获取数据库页面DiskManager并将其存储在内存中。

// BufferPoolManager当明确指示这样做或需要逐出页面以为新页面腾出空间时，也可以将脏页面写入磁盘。

// 刷脏的时机是什么？从缓冲池中淘汰掉一个帧页面；刷新内存页面到磁盘时；

To make sure that your implementation works correctly with the rest of the system, we will provide you with some functions already filled in. You will also not need to implement the code that actually reads and writes data to disk (this is called the DiskManager in our implementation). We will provide that functionality.

All in-memory pages in the system are represented by Page objects. The BufferPoolManager does not need to understand the contents of these pages. But it is important for you as the system developer to understand that Page objects are just containers for memory in the buffer pool and thus are not specific to a unique page. That is, each Page object contains a block of memory that the DiskManager will use as a location to copy the contents of a physical page that it reads from disk. The BufferPoolManager will reuse the same Page object to store data as it moves back and forth to disk. This means that the same Page object may contain a different physical page throughout the life of the system. The Page object’s identifer (page_id) keeps track of what physical page it contains; if a Page object does not contain a physical page, then its page_id must be set to INVALID_PAGE_ID.

// 如果Page对象不包含物理页，则page_id必须将其设置为INVALID_PAGE_ID。

Each Page object also maintains a counter for the number of threads that have “pinned” that page.

// 每个Page对象还维护一个计数器，用于记录“固定”该页面的线程数量。

// 引用计数是用来跟踪页面当前被多少个操作或线程引用的的一个机制。

Your BufferPoolManager is not allowed to free a Page that is pinned. Each Page object also keeps track of whether it is dirty or not. It is your job to record whether a page was modified before it is unpinned. Your BufferPoolManager must write the contents of a dirty Page back to disk before that object can be reused.

Your BufferPoolManager implementation will use the LRUKReplacer class that you created in the previous steps of this assignment. The LRUKReplacer will keep track of when Page objects are accessed so that it can decide which one to evict when it must free a frame to make room for copying a new physical page from disk. When mapping page_id to frame_id in the BufferPoolManager, again be warned that STL containers are not thread-safe.

You will need to implement the following functions defined in the header file (src/include/buffer/buffer_pool_manager.h) and in the source file (src/buffer/buffer_pool_manager.cpp):

FetchPage(page_id_t page_id)
UnpinPage(page_id_t page_id, bool is_dirty)
FlushPage(page_id_t page_id)
NewPage(page_id_t* page_id)
DeletePage(page_id_t page_id)
FlushAllPages()

For FetchPage, you should return nullptr if no page is available in the free list and all other pages are currently pinned. FlushPage should flush a page regardless of its pin status.

// FlushPage无论其引脚状态如何，都应该刷新页面。

For UnpinPage, the is_dirty parameter keeps track of whether a page was modified while it was pinned.

// 对于UnpinPage，is_dirty 参数跟踪页面在固定时是否被修改。

The AllocatePage private method provides the BufferPoolManager a unique new page id when you want to create a new page in NewPage(). On the other hand, the DeallocatePage() method is a no-op that imitates freeing a page on the disk and you should call this in your DeletePage() implementation.

// DeallocatePage()该方法是模拟释放磁盘上页面的操作。

Disk Manager

The Disk Manager class (src/include/storage/disk/disk_manager.h) reads and writes the page data from and to the disk. Your buffer pool manager will use DiskManager::ReadPage() and DiskManager::WritePage() whenever it needs to fetch a page to the buffer pool or flush a page to the disk.

概念理解

BufferPoolManager，几个重要的成员变量信息

const size_t pool_size_; // 缓冲池的容量

Page *pages_; // 从磁盘读取数据放入内存中，带有(meta-data元数据 + 磁盘读取的Data)

std::unique_ptr replacer_; // Task#1的LRU-K替换策略类

std::unordered_map<page_id_t, frame_id_t> page_table_; // 内存页表，用来绑定page_id和frame_id间的映射关系

std::list free_list_; // 管理空闲帧的列表，大小受pool_size影响

std::mutex latch_; // 底层的锁(用于给配置加锁)

内存Page: 以数组形式记录每个内存Page的信息（meta-data + 磁盘中读到的数据）

成员变量pin_count引用计数的含义和作用，

“pin_count” 表示页面当前被固定（正在被使用）的次数，以确保在页面上进行操作时数据的一致性和可靠性。

利用ChatGpt进行辅助理解，

一些问题的理解：

01.内存Page和磁盘Page有什么区别？

page_table是内存池上的索引，用于表示每个内存页面的page_id对应在缓冲池中的槽的位置frame_id，

page_directory是磁盘上的数据文件索引，标识page_id对应的数据文件位置。

区别：

内存Page的容量更小，可以提供快速的数据访问；

磁盘Page通常是帮助内存Page从磁盘找到对应的页表数据的位置；

再从磁盘读到内存中，放入一个成员变量data中(磁盘Page中包含的实际数据)

【面向磁盘的关系型数据库输入读取过程】

据库系统倾向于将热门数据或索引保留在内存中，以提高性能。

下图展示了，当用户读取数据库中数据的一个流程，

**(SQL执行)执行器 —-> 缓冲池 (找到，返回给执行器) **

(SQL执行)执行器 —-> 缓冲池（没找到）在对应磁盘Page中取 —-> 载入缓冲池(free_list检测 + LRU替换策略) —-> 返回给执行器

02.NewPage()和FetchPage()操作的区别是什么？

NewPage是在缓冲池中新创建一个只在内存中的页面，磁盘上没有该页面，得到一个新初始化的新页面并返回；

FetchPage是这个页面已经在缓冲池中存在了，我只需要取出来，并返回这个页面的信息；

03.刷脏的时机是什么？

从缓冲池中淘汰掉一个帧页面时；刷新内存页面到磁盘时；

实现6个API

实现缓冲池管理器（BufferPoolManager）,负责BufferPoolManager从中获取数据库页面DiskManager并将其存储在内存中。

构造函数如下：

1 2	BufferPoolManager(size_t pool_size, DiskManager disk_manager, size_t replacer_k = LRUK_REPLACER_K, LogManager log_manager = nullptr);

初始时，利用缓冲池容量大小pool_size初始化了空闲链表free_list的大小，用来表示当前空闲着的帧列表

注意：

FetchPage操作没在缓存池中找到信息，需要从磁盘读取信息到内存，

Flush操作不需要reset数据。

具体处理逻辑:

NewPage(page_id_t* page_id)

新建页面操作

获取一个可用的frame_id；
- 空闲链表里非空，还有帧id可用，直接从free_list末尾拿一个帧页面就行
- 空闲链表里没有空闲的帧时，需要从缓冲池中淘汰掉一个帧页面，得到可用的帧id（Task#1 Evict()淘汰机制）
  
  注意：若当前页面是脏状态，需要先进行刷脏，将数据写入磁盘再继续操作
  
  然后，删除每个页表对应的帧id的索引，解除映射关系
与申请到的新的new_page_id和frame_id，建立一对新映射关系；

对于page_table_数组进行数据初始化meta-data，并reset清空Data信息；

同步也要在，在LRU-K的替换器中进行访问帧和驱逐帧的操作

返回这个新的pages_

FetchPage(page_id_t page_id)

从缓冲池中取出一个内存页，操作过程类似NewPage

若page_id能在缓冲池找到，
- 更新页面的引用计数
- 在LRU-K的替换器中进行访问帧和驱逐帧的操作
缓冲池中没有找到，在磁盘中读取，
- 先获取一个可用的frame_id
- 初始化meta-data信息，从磁盘中读数据存入pages_的data成员变量中
- 要在LRU-K的替换器中进行访问帧和驱逐帧的操作
返回当前拿到的pages_
UnpinPage(page_id_t page_id, bool is_dirty)

用于将目标页面从缓冲池中解除固定, 同时传入该内存页面的脏状态

先是入参判断，传入的page_id要有效，并且可以在内存页表里找到

获取page_id对应的frame_id

通过按位或来，更新页面的脏状态（将传入的 is_dirty 参数的状态合并到页面的脏状态中）

（按位或：这样的做的目的，确保在更新页面状态时不会丢失页面的脏状态信息）

当前页面的引用计数大于0，每次解除固定操作只会让pin_count_减1
- 只有引用计数为零时，页面才可以被置换(驱逐)出缓冲池（Task#1 Evict()淘汰机制）
返回解除操作是否成功
FlushPage(page_id_t page_id)

刷新一个内存页面到磁盘，写入数据操作

注意FlushPage, 只管刷新页面不管其pin的状态，内存页面也不必清空

该页面能够在page_table_中找到时，获取对应的frame_id

进行刷脏，利用disk_manager_写入数据到磁盘中，并且更新页面的脏状态

FlushAllPages()

刷新所有内存页面到磁盘

当前页面是脏状态，并且page_id是有效的，就可以满足刷脏操作

利用disk_manager_写入数据到磁盘中，并且更新页面的脏状态

DeletePage(page_id_t page_id)

删除缓冲池的内存页面

边界考虑，

要删除的page_id并不存在，即不在缓冲池中，返回true，

该页面正在被使用时，不能删；

删除前，页面数据还没写入磁盘时，需要先刷脏

然后要清空页面中的meta-data信息，

注意reset清空data, 标记page_id为无效IDINVALID_PAGE_ID(Page对象不包含物理页);

最后在page_table、replacer、free_list中进行清除，

然后DeallocatePage()释放磁盘页面

代码实现

注意：

开始实现代码时，需要将throw NotImplementedException()的代码移除，以便于后续可以正常完成GTest.

balabala…

Task #3 - Read/Write Page Guards

任务要求

In the Buffer Pool Manager, FetchPage and NewPage functions return pointers to pages that are already pinned. The pinning mechanism ensures that the pages are not evicted until there are no more reads and writes on the page. To indicate that the page is no longer needed in memory, the programmer has to manually call UnpinPage.

On the other hand, if the programmer forgets to call UnpinPage, the page will never be evicted out of the buffer pool. As the buffer pool operates with an effectively smaller number of frames, there will be more swapping of pages in and out of the disk. Not only the performance takes a hit, the bug is also difficult to be detected.

You will implement BasicPageGuard which store the pointers to BufferPoolManager and Page objects.

// 你将实现BasicPageGuard存储指向BufferPoolManager和Page对象的指针，进行读/写页面的防护

A page guard ensures that UnpinPage is called on the corresponding Page object as soon as it goes out of scope. Note that it should still expose a method for a programmer to manually unpin the page.

As BasicPageGuard hides the underlying Page pointer, it can also provide read-only/write data APIs that provide compile-time checks to ensure that the is_dirty flag is set correctly for each use case.

In the future projects, multiple threads will be reading and writing from the same pages, thus reader-writer latches are required to ensure the correctness of the data. Note that in the Page class, there are relevant latching methods for this purpose. Similar to unpinning of a page, a programmer can forget to unlatch a page after use. To mitigate the problem, you will implement ReadPageGuard and WritePageGuard which automatically unlatch the pages as soon as they go out of scope.

You will need to implement the following functions for all BasicPageGuard, ReadPageGuard and WritePageGuard.

PageGuard(PageGuard &&that) : Move constructor. // 移动构造函数
operator=(PageGuard &&that) : Move operator. // 移动操作符
Drop() : Unpin and/or unlatch. // 取消固定和或解锁
~PageGuard() : Destructor.

With the new page guards, implement the following wrappers in BufferPoolManager.

FetchPageBasic(page_id_t page_id)
FetchPageRead(page_id_t page_id)
FetchPageWrite(page_id_t page_id)
NewPageGuarded(page_id_t *page_id)

Please refer to the header files (lru_k_replacer.h, buffer_pool_manager.h, page_guard.h) for more detailed specs and documentations.

代码实现

balabala…

CMU15-445-P1 Buffer Pool Manager