CMU15-445 Project #1 Buffer Pool

Lab内容

Lab的总体目标是构建一个buffer pool manager用于管理page写入写出buffer pool。本质上就是实现slides中的下图，维护一个page_id到frame_id的映射，并且根据不同状态执行不同的操作。

project分为两个部分，LRU REPLACEMENT POLICY以及BUFFER POOL MANAGER，LRU REPLACEMENT POLICY是为 BUFFER POOL MANAGER服务的

TASK #1 - LRU REPLACEMENT POLICY

这部分就是实现LRU算法,经典面试题，实现一下Leetcode 146. LRU 缓存机制，与Leetcode不同的是，Leetcode实现的是一个KV，而Lab中所给出的接口略有不同

为了实现LRU功能新增了如下数据结构

std::list<frame_id_t> cache

用于存储所以可被换出的frame_id，也就是unpined状态下的frame_id集合，同时维护了frame的最后访问时间顺序，从头到尾访问时间从近到远，所以需要找到page换出时会从尾部取，而插入从头部插入

std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> frameid2node

维护了frame_id到std::list<frame_id_t>::iterator的映射，用于O(1)找到对应frame_id在cache中的地址

int maxframes

cache大小上限，也就是buffer pool的大小

std::mutex lru_lock

锁，用于互斥访问

需要实现如下接口：

bool LRUReplacer::Victim(frame_id_t *frame_id)

该函数找到一个页换出，并且将换出的frame_id存在参数*frame_id中，需要满足优先换出最远访问的page

void Pin(frame_id_t frame_id) override;

用于将frame_id锁定，转换成pinned状态，该状态的frame不会被换出，在本实现中也就是从cache中删除，这里注意不要重复删除

void Unpin(frame_id_t frame_id) override;

用于将frame_id解除锁定，转换成unpinned状态，该状态的frame有可能被换出，本实现就是插入cache中，注意不要重复unpinned

TASK #2 - BUFFER POOL MANAGER

该部分是配合上一个task的lru_replacer实现一个buffer pool manager，主要实现以下接口。

Page *BufferPoolManager::FetchPageImpl(page_id_t page_id)

该接口实现的是将参数page_id换入buffer pool中，需要注意的点有如下几个：

1.如果page_id在page_table_里，需要pin_count++，因为此时可能还有其他线程使用该page_id

2.如果page_id在page_table_里，需要replacer_->Pin(frame_id)，确保该page_id对应的frame_id处于pinned状态



bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty)

该接口实现的是将对应page_id 从Buffer pool 中Unpin，并且给page赋is_dirty，需要注意的有如下几点:

1.page_table_中找不到page_id，需要return true，虽然接口说明写清楚了true otherwise，但是一般第一次写都会return false吧。。。

2.unpined的时候需要判断pin_count 每次调用UnpinPageImpl,--pin_count,只有pin_count调用前等于1，也就是--pin_count=0的时候才调用replacer_->Unpin(page_table_[page_id])

3.设置is_dirty需要Pageptr->is_dirty_ = Pageptr->is_dirty_ || is_dirty;防止本来page是dirty的，用is_dirty=false刷成false，导致出错

bool BufferPoolManager::FlushPageImpl(page_id_t page_id)

该接口实现的是将page_id的内容刷入disk中，实现比较简单但是有个坑，这个函数要加锁，因为测试的时候会调用这个函数，如果不加锁，当作一个函数在需要刷新的地方调用，那么测试的时候会导致多个线程写同一个page造成错误，所以我发现了这个问题时在原本调用无锁FlushPageImpl的地方改成了FlushPageImplWithoutLock。


Page *BufferPoolManager::NewPageImpl(page_id_t *page_id)

该接口实现的是新建一个page，这里有一个坑点，就是新建page 不能将dirty设置成true等换出的时候flush,因为有测试是类似check(0,newpage->data())，需要将初始化的内容马上刷进disk，不然就过不了测试

bool BufferPoolManager::DeletePageImpl(page_id_t page_id)

该接口实现的是将page_id从buffer_pool删除，加入free_list_中，这里有个坑点是删除的时候需要Pin(page_id)，如果不调用，假设该page_id原先是unpinned的，在replacer中，那么就会导致该page_id同时出replacer和free_list_中。

void BufferPoolManager::FlushAllPagesImpl()

把所有page_id刷盘，这个没什么好说的。。

换出策略

以上所有实现涉及到需要换出旧page，换入新page的时候，首先是需要从free_list_中，如果free_list_没有空闲，再从replacer中找，因为从free_list_中可以直接得到空闲的frame，不涉及换出，而从replacer中需要换出unppined的frame,即使使用了lazy write机制，还是从free_List_中获取frame访问disk和内存的次数小。是否将淘汰页刷入disk则需要通过Page的dirty标记判断。