CMU 15-445/645 Database System/Fall2021 #Project1_BufferPoolManager
CMU 15-445是一门数据库系统课程——官方主页CMU-15445。由于官方网站提示不能在公开网络张贴答案，所以本文不会有全面详细的代码，但是会有详细的解析。
一、LRU Replacement Policy
第一个任务是实现缓冲池的LRU算法，这里的LRU算法提供的接口和日常在LeetCode刷题中遇到的接口不一样：
/**
* 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;
我们需要实现的是LRUReplacer的构造函数，析构函数，Victim淘汰函数，Pin函数，Unpin函数。LRUReplacer中装的是，frame_id，也可以理解为页框号，这里Victim函数需要做的事情就是淘汰LRUReplacer（头进尾出）中末尾的frame_id。
Pin函数的逻辑需要注意一下，这里的Pin是指某一页被钉住了，不会从BufferPool中被换出，而所有被换出的页对应的页框号frame_id都需要Victim接口来提供。所以这里Pin的逻辑是将该页对应的页框号从LRUReplacer中踢出，这样Victim函数就用于无法得到该页的页框号，从而达到“钉住”的效果。
Unpin相反，需要我们将某页对应的页框号加入到LRUReplacer之中，这样Victim函数就能得到该页框号，从而进行页换出处理。
这里lru的实现就是采用经典的双向链表加哈希表的方式，不过多赘述，但是这里LRU算法有一个奇怪的地方，在第二次将同一个frame_id放入LRUReplacer时，不能将其移动到队头，这么做了反而测试会不通过。
二、Buffer Pool Manager Instance
这个任务算是Project1中的核心任务，需要实现以下6个函数：
/**
* Fetch the requested page from the buffer pool.
* @param page_id id of page to be fetched
* @return the requested page
*/
Page *FetchPgImp(page_id_t page_id) override;
/**
* Unpin the target page from the buffer pool.
* @param page_id id of page to be unpinned
* @param is_dirty true if the page should be marked as dirty, false otherwise
* @return false if the page pin count is <= 0 before this call, true otherwise
*/
bool UnpinPgImp(page_id_t page_id, bool is_dirty) override;
/**
* Flushes the target page to disk.
* @param page_id id of page to be flushed, cannot be INVALID_PAGE_ID
* @return false if the page could not be found in the page table, true otherwise
*/
bool FlushPgImp(page_id_t page_id) override;
/**
* Creates a new page in the buffer pool.
* @param[out] page_id id of created page
* @return nullptr if no new pages could be created, otherwise pointer to new page
*/
Page *NewPgImp(page_id_t *page_id) override;
/**
* Deletes a page from the buffer pool.
* @param page_id id of page to be deleted
* @return false if the page exists but could not be deleted, true if the page didn't exist or deletion succeeded
*/
bool DeletePgImp(page_id_t page_id) override;
/**
* Flushes all the pages in the buffer pool to disk.
*/
void FlushAllPgsImp() override;
在实现函数之前，需要对一些关键概念进行理解，如下图：
这个图就很好的表示了Page，page_id，frame_id的关系。Page是一个类，其中的data_数据成员保存了数据页中的内容，
通过page_id_数据成员来区分保存的是哪个页，在Page的生命周期中，可能会保存多个不同的数据页。通过page_table_可以找到当前page_id和frame_id的对应关系，也就是找到当前页所在的页框。
在进行页换出的时候，通过LRUReplacer的Victim函数可以找到应该被换出的页所对应的页框号，然后将页框中的内容也就是Page的元数据清空，再放入新换入的页并更新元数据即可。在这个任务中Pin和Unpin的逻辑与上个任务相反：
这里UnpinPgImp函数是将该页的引用计数减一，当减到0的时候，将该页对应的页框号加入到LRUReplacer，参与淘汰。
在这些函数中都需要对考虑线程安全，这里使用粗粒度的互斥锁实现，为了简洁方便，可以使用unique_lock。
FlushPgImp函数需要将参数指定的page_id对应的页刷盘，通过page_id在page_table_中查到对应的页框号，然后访问Page数组page_就可得到Page对象，FlushAllPgImp直接对page_table中的page_id挨个调用FlushPgImp即可，注意该函数不用加锁，否则重复对同一个互斥量加锁会造成死锁。
如上图所示，无论是pin还是unpin的页，都能在page_table_中找到所对应的页框号。free_list中的页框没有装数据页，获取新页框先从free_list中获取，取不到再去replacer中使用Victim函数获取淘汰页占用的页框的页框号，从而得到页框。
NewPgImp函数返回一个新的页框，实现的时候需要注意第三步，需要在更新P的元数据之前将其原来的page_id从page_table_中移除,然后插入新的{page_id，frame_id}到page_table_。另外新的Page的pin_count_应该为1。
FetchPgImp函数将指定page_id的页从Disk中读入到BufferPool，如果page_table_中已经存在该页，对应的pin_count++，并调用replacer的Pin函数，将该页对应的页框号从LRUReplacer中移除，然后是获取页框，和NewPgImp类似，具体实现按照注释步骤来即可。
DeletePgImp函数负责删除参数page_id指定的页占用的页框，清空其元数据后归还到free_list中，这里需要注意在清空元数据后需要调用replacer->Pin()函数，防止删除后页框号同时在replacer和free_list中，其他实现根据注释提示来即可。
UnpinPgImp函数还需要注意，只有当参数is_dirty为true的时候才能将Page的数据成员is_dirty_置为true，不能直接赋值，如果原来该page的is_dirty_是true，这里传入is_dirty_为false，就会导致错误。
三、Parallel Buffer Pool Manager
在单个BufferPool Instance的情况下，多个线程会争抢一个互斥量，一个潜在的解决方法是一个系统中有多个BufferPool Instance，他们每一个都拥有一个自己的互斥量(mutex/latch)。
这里要求实现下列10个函数，大部分只需调用上个任务的方法即可，下面贴出部分函数实现。
部分自己添加的数据成员：
/** How many instances are in the parallel BPM (if present, otherwise just 1 BPI) */
const uint32_t num_instances_ = 1;
/** Number of pages in the single buffer pool instance. */
const size_t pool_size_ = 0;
/*start search at a different BPMI each time by start_index_*/
int start_index_ = 0;
/*bufferpool instances container*/
BufferPoolManager **bufferpool_instances_;
ParallelBufferPoolManager::ParallelBufferPoolManager(size_t num_instances, size_t pool_size, DiskManager *disk_manager,
LogManager *log_manager)
: num_instances_(num_instances), pool_size_(pool_size) {
// Allocate and create individual BufferPoolManagerInstances
bufferpool_instances_ = new BufferPoolManager *[num_instances];
for (size_t i = 0; i < num_instances; i++) {
bufferpool_instances_[i] = new BufferPoolManagerInstance(pool_size, num_instances, i, disk_manager, log_manager);
}
}
// Update constructor to destruct all BufferPoolManagerInstances and deallocate any associated memory
ParallelBufferPoolManager::~ParallelBufferPoolManager() {
for (size_t i = 0; i < num_instances_; i++) {
delete bufferpool_instances_[i];
}
delete[] bufferpool_instances_;
}
Page *ParallelBufferPoolManager::NewPgImp(page_id_t *page_id) {
// create new page. We will request page allocation in a round robin manner from the underlying
// BufferPoolManagerInstances
// 1. From a starting index of the BPMIs, call NewPageImpl until either 1) success and return 2) looped around to
// starting index and return nullptr
// 2. Bump the starting index (mod number of instances) to start search at a different BPMI each time this function
// is called
for (size_t i = start_index_; i < start_index_ + num_instances_; i++) {
Page *page =
dynamic_cast<BufferPoolManagerInstance *>(bufferpool_instances_[i % num_instances_])->NewPgImp(page_id);
if (page != nullptr) {
start_index_ = i % num_instances_;
return page;
}
}
return nullptr;
}
