Project1——Buffer Pool
目标：实现一个缓冲池，对外支持上层取页（上层最常使用的功能）、新建页（支持在其中读写）、删页。
Structure
对下接口：DiskManager，支持向磁盘读写数据。
对上接口：若干的API。
1
2
3
4
5
6
7
8
9
10Page *FetchPgImp(page_id_t page_id) override; // 取页
Page *NewPgImp(page_id_t *page_id) override; // 直接在内存中新建空页，并写入磁盘
bool DeletePgImp(page_id_t page_id) override; // 删页
bool UnpinPgImp(page_id_t page_id, bool is_dirty) override; // 标记某页不再使用
void FlushAllPgsImp() override; // 将缓冲区页全部写入磁盘中内部组件：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17/** Array of buffer pool pages. */
Page *pages_; // 一个个frame，有的是空的
/** Pointer to the disk manager. */
DiskManager *disk_manager_ __attribute__((__unused__));
/** Page table for keeping track of buffer pool pages. */
std::unordered_map<page_id_t, frame_id_t> page_table_; // page_id在那个frame中
/** Replacer to find unpinned pages for replacement. */
Replacer *replacer_; // LRU管理器
/** List of free pages. */
std::list<frame_id_t> free_list_; // 空的frame记录
/** This latch protects shared data structures. We recommend updating this comment to describe what it protects. */
std::mutex latch_;
target 1：LRU_Replacer
LRU的实现还是较为简单，主要思路就是用一个std::list<frame_id_t>维护所有的frame，没有锁住的frame中，越经常使用的frame位置越靠前，为了移动节点位置的时间复杂度为O(1)，则再新增一个std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator>快速定位节点位置。
注意：这里需要搞清楚LRU的对象是谁？不是所有的frame都在LRU中，这里的LRU可以理解成一个“垃圾站”，所有允许置换出的frame才在这里面，然后再按照使用时间进行排序。
主要实现如下三个函数：
1 | bool Victim(frame_id_t *frame_id) override; // 如果能取，则取出一个能够置换的frame |
Buffer pool中如何使用LRU_Repalcer？如何调用这三个函数呢？
Victim较好理解，有需要page时且free_list为空时，则调用它。对于
Pin和Unpin，对于每个page有一个标记量pin_count，它表示有多少个线程正在使用它。显而易见，对于这两个函数，应该是某个frame中的page，pin_count改变为0时，调用Unpin；改变为大于0，则调用Pin。
target 2：Buffer_pool_manager
这里就主要谈谈各个函数内部的一些逻辑：
Page *FetchPgImp(page_id_t page_id)：取page。先判断需要的page是否在内存中，在就pin_count++，PIN，返回；不在的话，先看是否有空的frame，没有的话看看是否有允许置换的frame，有的话则读磁盘，然后记录在frame中，pin_count++，PIN，并返回。Page *NewPgImp(page_id_t *page_id)： 新建page并写入磁盘。先看是否有空的frame，没有的话看看是否有允许置换的frame，有的话直接清空frame并写入磁盘，pin_count=1，PIN，然后返回。这里为什么要写入磁盘一个空页，主要是怕LRU把它置换了，丢失了这个page，也就丢失了这个page的pageid，然后就永远无法从磁盘中得到它了。
bool DeletePgImp(page_id_t page_id)： 删page。先判断需要的页是否在内存中，不在就返回true。在的话判断该page的pin_count，大于0则拒绝删除。等于0就清空page，加入free_list中，并且PIN，这里为什么要PIN，如果该page是unpin状态，不PIN的话就同时存在于freelist和replacer了。—>没考虑到的case。
bool UnpinPgImp(page_id_t page_id, bool is_dirty)：标记某page不再使用。先判断需要的页是否在内存中，不在就返回false，然后pin_count–，如果减为0，则UNPIN。void FlushAllPgsImp()将缓冲区页全部写入磁盘中。补充：如果frame中的页置换出时，page为
dirty，需要写到磁盘后再进行置换，同时一定要清空frame中的相应状态；将page写到磁盘后也要更改isdirty。
总体来说，在各个函数函数中，什么时候可以删可以换，什么时候PIN，什么时候UNPIN，是最重要的。
target 3：Parallel_buffer_pool_manager
为了避免频繁争抢锁, 一个不错的idea是做多个BPM(Buffer Pool Manager), 根据page_id决定由哪个manager来管理, 这样抢锁的程度会低很多。
实验中用的是简单的取模运算, 不是什么复杂的哈希算法, 即根据page_id取模bpm的数量来判断要分配到哪个bpm。
维护多个BPM，调用对应接口即可，较为简单，就不细说了。
Professional terms
C++ syntax
以下代码为什么跑不了？
解释：把copy constructor删除之后，编译器不会定义一个默认的move constructor，emplace back要求的type必须满足move insertable。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
class A{
public:
A(int a):a_(a){}
A() = delete;
A( const A& a) = delete;
//A(A&& a) =default; //添加了又能跑
private:
int a_;
};
int main(){
vector<A> v;
v.emplace_back(2);
return 0;
}
Result
在提交时，最后一个测试案例过不了，显示说超时。主要原因是：寻找某个页在pagetable中是否存在，应该选择find函数，而不是count函数，从原理来说find绝对会比count快，线上的测试案例还是有点严格的😓。