CMU15-445 Lab1.Buffer Pool
于2022年5月30日2022年5月30日由Sukuna发布
这是CMU数据库系列的第一个实验,第一个实验需要我们完成关于Buffer的一些功能.在完善Buffer的功能之前,我们先了解一下buffer的一些基本知识.
buffer在这里面和操作系统很像,是主存和辅存的缓冲地带,我们需要完成的是两个特别重要的数据结构,一个是Disk Manager,用我的话说就是页表,一个是LRU Replacer,这个数据结构研究,在缓冲地带满的时候我们应该替换谁进入到辅存.这两个数据结构所存储的信息单位量是一样的(也就是说这两个数据结构都存储了n个块[你也可以认为是“页”]的信息).两个数据结构通过Pin和Unpin来互相作用.
实验1.1 LRU REPLACEMENT
实验提示:修改src/include/buffer/lru_replacer.h和src/buffer/lru_replacer.cpp.
首先我们知道LRU Replacer是一个依赖LRU算法进行替换的一个结构体,我们在操作系统和组成原理的课程中已经知道,模拟LRU算法一般使用堆栈,我们现在使用堆栈来进行模拟:
首先在头文件中添加有关堆栈的一些信息;
代码语言：javascript复制 size_t capacity; //容量
size_t size; //当前大小
std::list<frame_id_t> lists; //存储帧的栈,用list实现
std::unordered_map<frame_id_t , int> maps; //哈希映射,映射帧和是否在LRU Replacer里面.
std::mutex locks;定义了这么多成员,我们可以实现类的方法了:
1、构造函数.(略)
代码语言：javascript复制LRUReplacer::LRUReplacer(size_t num_pages) {
capacity = num_pages;
maps.clear();
lists.clear();
size = lists.size();
}2、Victim函数:
这个函数选择一个帧来被替换.返回值是是否成功输出.具体的做法是从栈中选择栈顶返回即可.然后在maps中删除掉这个帧即可.
代码语言：javascript复制bool LRUReplacer::Victim(frame_id_t *frame_id) {
if(lists.empty()) return false;
locks.lock();
frame_id_t lasts = lists.back();
maps.erase(lasts);
lists.pop_back();
*frame_id = lasts;
locks.unlock();
return true;
}3、Pin函数
Pin的意思就是固定,这个意思就是Disk Manager固定了某一个页,希望这个页不会被LRU Replacer选中然后被替换掉.那么首先调用maps,看看LRU Replacer中是否存在这个帧,存在的话就删除,不存在的话就不作任何处理.
代码语言：javascript复制void LRUReplacer::Pin(frame_id_t frame_id) {
if(maps.count(frame_id) == 0) return;
locks.lock();
lists.remove(frame_id);
maps.erase(frame_id);
locks.unlock();
}4、UnPin函数
UnPin函数的意思是解除固定,这个意思就是Disk Manager解除固定某一个页,表示Disk Manager最近不需要使用这个页了,LRU Replacer最近可以对其进行替换操作.首先第一步就是查看这个帧是否存在于LRU Replacer中.如果没有就需要放进LRU Replacer中,那么就会存在问题,问题就是,万一我LRU Replacer满了怎么办?满了的话就可以选择一个元素替换下去,然后在插入.(跟我们在操作系统课程上面学习的一样,从栈顶取一个元素,然后把它放入栈底)
代码语言：javascript复制void LRUReplacer::Unpin(frame_id_t frame_id) {
if(maps.count(frame_id) != 0) return;
locks.lock();
//如果已经满了,则需要淘汰一个然后放入 LRUReplacer 中
if (lists.size() == capacity) {
frame_id_t last_frame = lists.back();
maps.erase(last_frame);
lists.pop_back();
}
lists.push_front(frame_id);
maps[frame_id] = 1;
locks.unlock();
}
先看实验的最后怎么make的吧,一开始太智障直接cd进目录调gcc,这下丑大了,重写了一份…
实验1.2 BUFFER POOL MANAGER INSTANCE
提示:修改src/include/buffer/buffer_pool_manager_instance.h和src/buffer/buffer_pool_manager_instance.cpp
首先我们先来了解一下BUFFER POOL的一些成员(这个实验不需要我们添加成员),一个是存储每个页的指针的指针数组,在后面我们会使用这个结构来给定页的id获得一个页的指针,接着就是页表成员,将物理帧和页的id进行对应,接着就是空闲物理帧以及之前做的替换器元素.(其实页和物理帧是相互统一的概念,物理帧是一个物理概念,代表了一块空闲的内存空间,页就是记录数据的单位,当物理帧被赋值,被填入数据的时候,它就变成了一个页.**当然,页表的id某种程度上反映了辅存的位置**)
代码语言：javascript复制 /** Array of buffer pool pages. */
Page *pages_;
/** Pointer to the disk manager. */
DiskManager *disk_manager_ __attribute__((__unused__));
/** Pointer to the log manager. */
LogManager *log_manager_ __attribute__((__unused__));
/** Page table for keeping track of buffer pool pages. */
std::unordered_map<page_id_t, frame_id_t> page_table_;
/** Replacer to find unpinned pages for replacement. */
Replacer *replacer_;
/** List of free pages. */
std::list<frame_id_t> free_list_;
/** This latch protects shared data structures. We recommend updating this comment to describe what it protects. */
std::mutex latch_;1、NewPgImp函数
这个函数主要让我们申请一个新的Page,然后把Page的ID放入到page_id中,然后返回这个Page的指针.关于这个函数,提示已经说明地很明显了:
首先第一步,遍历一遍pool_size_,看看是不是所有的Page都被Pin了,如果是,那么就返回空指针,代表找不到可以申请的页.
第二步就是从freelist中获取一个新的帧,如果freelist为空,就代表我们不得不得替换一个页下来,这个页可以调用Replacer的Victim函数获得.如果要替换的页是脏的,我们要把这个页写进磁盘中.(脏块,参考组成原理)
第三步就是从给这个页一些初始数据,比如说引用数为1,页的id是page_id,存储的内容为空,最后Pin一下这个页,返回即可.然后把这个页填入到物理帧中然后加入到页表中.
代码略
2、FetchPgImp函数
这个函数主要根据页面的id来获取一个页的指针,这个提示说明的也很明显了
首先第一步,在页表中寻找page_id,看这个页是否真正存在,如果存在就跳过,如果不存在,按照第一个函数的方式申请一个页,然后把页号加载一下,把辅存的内容加载到p->data_里面,Pin一下即可.
代码如下:
代码语言：javascript复制Page *BufferPoolManagerInstance::FetchPgImp(page_id_t page_id) {
// 1. Search the page table for the requested page (P).
// 1.1 If P exists, pin it and return it immediately.
// 1.2 If P does not exist, find a replacement page (R) from either the free list or the replacer.
// Note that pages are always found from the free list first.
// 2. If R is dirty, write it back to the disk.
// 3. Delete R from the page table and insert P.
// 4. Update P's metadata, read in the page content from disk, and then return a pointer to P.
frame_id_t fid;
Page* p = nullptr;
// step 1.1.
if(page_table_.find(page_id) != page_table_.end()){
fid = page_table_[page_id];
pages_[fid].pin_count_ ;
// pin it.
replacer_->Pin(fid);
return &pages_[fid];
}
latch_.lock();
// step 1.2.
if (free_list_.empty()) { // pick from free list first.
//can't find a page that can be flushed.
if (!replacer_->Victim(&fid)) {
return nullptr;
} else {
// the page placed in the lrureplacer need to be flushed.
// send it to the disk
p = &pages_[fid];
if (p->is_dirty_) {
disk_manager_->WritePage(p->page_id_, p->data_);
p->is_dirty_ = false;
}
// erase the pagetable_.
page_table_.erase(p->page_id_);
}
} else {
//found:
fid = free_list_.front();
free_list_.pop_front();
p = &pages_[fid];
}
// Step 3.
page_table_[page_id] = fid;
replacer_->Pin(fid);
// Step 4.
p->page_id_ = page_id;
p->pin_count_ = 1;
disk_manager_->ReadPage(page_id, p->data_);
latch_.unlock();
return p;
}3、DeletePgImp函数
这个函数要求我们删除某个页.当然,代码的注释也给出了很详细的说明.
首先判断要删除的那个页到底存不存在,如果不存在的话就跳过,然后判断被删除的那个页到底有没有被Pin,如果被Pin了的话也是不能删除的,接着判断这个页是不是为脏,如果是脏页就要写回,最后把这个页的一些信息初始化,然后把这个页的信息加入到freelist里面.
代码语言：javascript复制bool BufferPoolManagerInstance::DeletePgImp(page_id_t page_id) {
// 0. Make sure you call DeallocatePage!
// 1. Search the page table for the requested page (P).
// 1. If P does not exist, return true.
// 2. If P exists, but has a non-zero pin-count, return false. Someone is using the page.
// 3. Otherwise, P can be deleted. Remove P from the page table, reset its metadata and return it to the free list.
if (page_table_.find(page_id) == page_table_.end()) {
return true;
}
// P does exists.
frame_id_t fid = page_table_[page_id];
Page* deletepage = &pages_[fid];
// P is pinned
if (deletepage->pin_count_ != 0) {
return false;
}
// if dirty rewrite:
// flush the page before deallocate it.
latch_.lock();
if (deletepage->is_dirty_) {
disk_manager_->WritePage(page_id, deletepage->data_);
deletepage->is_dirty_ = false;
}
DeallocatePage(page_id);
// remove P from the page table.
page_table_.erase(page_id);
// reset its metadata.
// the page returned to freelist does not stores any page.
deletepage->page_id_ = INVALID_PAGE_ID;
deletepage->is_dirty_ = false;
deletepage->pin_count_ = 0;
// return it to free_list_.
free_list_.push_back(fid);
latch_.unlock();
return true;
}好了,最难的几个函数我们都做完了,剩下的几个都比较简单.
4、FlushPgImp函数
刷新一个页,把这个页里面的数据写入磁盘.
找到这个页,然后调用WritePage就可以了.
代码语言：javascript复制bool BufferPoolManagerInstance::FlushPgImp(page_id_t page_id) {
// Make sure you call DiskManager::WritePage!
std::lock_guard<std::mutex> lock(latch_);
if (page_table_.find(page_id) == page_table_.end() || page_id == INVALID_PAGE_ID)
return false;
disk_manager_->WritePage(page_id, pages_[page_table_[page_id]].data_);
return true;
}5、UnpinPgImp函数
让一个页的pin数减1.
找到一个页,首先置脏位,然后让pin数-1,如果减为0就调用Replacer的Unpin函数.
代码语言：javascript复制bool BufferPoolManagerInstance::UnpinPgImp(page_id_t page_id, bool is_dirty) {
std::lock_guard<std::mutex> lock(latch_);
frame_id_t fid = page_table_[page_id];
Page* p = &pages_[fid];
p->is_dirty_ = is_dirty; // hold the state until victim.
if (p->pin_count_ <= 0)
return false;
--p->pin_count_;
if (p->pin_count_ == 0) {
replacer_->Unpin(fid);
return true;
}
return false;
}
实验1.3 PARALLEL BUFFER POOL MANAGER
并行的manager,先前是一个manager工作,现在是多个manager工作,具体的思路大同小异,就是先选择究竟是哪一个manager,然后再调用这个manager的函数.
选择的方式比较淳朴,假设有N个manager,那个调用manager的序号就是id % N.
这一部分的函数,除了创建新页面这个不确定初始页面id的情况下,其他的都一模一样.
1、NewPgImp函数.
遍历一遍所有的Manager,然后调用所有的Manager的NewPgImp函数,找得到就返回,找不到就算了,返回空指针吧.
代码语言：javascript复制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 = 0; i < num_instances_; i ){
BufferPoolManager* one_manager_instance = manager_[next_instacnce_];
Page *page = one_manager_instance->NewPage(page_id);
if(page != nullptr){
return page;
}
next_instacnce_ = (next_instacnce_ 1) % num_instances_;
}
return nullptr;
}当然,有小伙伴就问了,你这样子做,有没有这样一种可能,就是生成这个页的时候是由i号Manager生成的,但是调用这个页的时候是由j号Manager管理,这个可以说应该是不可能的,因为next_instacnce_可以认为是和page_id同步的(起码模 N是一样的),各位做实验可以验证这个结论.
2、其他函数.
先选Manager,再调用,没啥好说的.
代码语言：javascript复制BufferPoolManager *ParallelBufferPoolManager::GetBufferPoolManager(page_id_t page_id) {
// Get BufferPoolManager responsible for handling given page id. You can use this method in your other methods.
return manager_[page_id % num_instances_];
}
Page *ParallelBufferPoolManager::FetchPgImp(page_id_t page_id) {
// Fetch page for page_id from responsible BufferPoolManagerInstance
return GetBufferPoolManager(page_id)->FetchPage(page_id);
}
bool ParallelBufferPoolManager::UnpinPgImp(page_id_t page_id, bool is_dirty) {
// Unpin page_id from responsible BufferPoolManagerInstance
return GetBufferPoolManager(page_id)->UnpinPage(page_id,is_dirty);
}
bool ParallelBufferPoolManager::FlushPgImp(page_id_t page_id) {
// Flush page_id from responsible BufferPoolManagerInstance
return GetBufferPoolManager(page_id)->FlushPage(page_id);
}
实验二再见!
