CMU15445数据库系统实验一：缓冲池管理器

本文转载自微信公众号《分布式比特》，作者Munio。转载本文请联系分布式滴公众号。本文为实验一，管理文件系统页面在内存中的缓存——bufferpoolmanager。概述实验BusTub的目标系统是一个面向磁盘的DBMS，但是磁盘上的数据不支持字节粒度的访问。这需要一个管理页面的中间层，但是AndyPavlo教授坚持不使用mmap将页面管理权力转移给操作系统。因此，实验一的目标是在内存中主动管理磁盘上页面的缓存。因此，最大限度地减少磁盘访问次数（在时间上），并最大限度地提高相关数据的连续性（在空间上）。本实验可以分解为两个相对独立的子任务：维护替换策略：LRU替换策略管理缓冲池：缓冲池管理器两个组件都需要线程安全。本文首先从基本概念和核心数据流两个方面对实验内容进行分析，然后分别对两个子任务进行梳理。作者：青藤木鸟https://www.qtmuniao.com/2021/02/10/cmu15445-project1-buffer-pool/，转载请注明出处实验分析刚开始写实验代码的时候，感觉有很多细节，以及实现的时候很容易忘记。但随着实施和思考的深入，我逐渐摸清了全貌，发现只要理清几个基本概念和核心数据流，就可以勾勒出轮廓。基本概念缓冲池操作的基本单位是逻辑上连续的字节数组，在磁盘上表示为页（page），有唯一标识page_id；它在内存中表示为一个帧（frame），并有一个唯一的标识符frame_id。为了记录哪些页存储在哪些帧中，需要用到页表（pagetable）。下面的文字可能会把page和frame混在一起，因为这两个概念是bufferpool管理数据的基本单位，一般都是4k，区别如下：pageid是这个数据单位的全局标识，frameid只在内存池（framearray）indexapagesubscriptpage在文件系统中是一个逻辑上连续的字节数组；在内存中，我们会给它添加一些元信息：pin_count_,is_dirty_基本概念和管理frame的内存池一般来说，size比磁盘小很多，所以内存池满了之后，再加载从磁盘到内存池的新页面，需要一些替换策略（replacer）将一些未使用的页面踢出内存池以腾出空间。空间不足。核心数据流从结论开始。缓冲池管理器的核心在于对内存池中所有帧的状态进行管理。因此，如果我们能够梳理好框架的状态机，就可以掌握核心的数据流向。缓冲池维护一个frame数组，每个frame有三种状态：free：初始状态，不存储pagepinned：存储线程正在使用的pageunpinned：存储page，但不再使用page通过任意线程实现的函数：FetchPageImpl(page_id)NewPageImpl(page_id)UnpinPageImpl(page_id,is_dirty)DeletePageImpl(page_id)是驱动状态机中改变上述状态的动作（action），状态机如下：frame状态机对应实现时的数据结构上：保存page数据的frame数组为pages_，所有freeframeindex（frame_id）存储在free_list_中，所有unpinnedframeindex存储在replacer_中，所有pinnedframeindex和unpinnedframeindex存储在page_table_中，通过pagepin_count_字段来区分两种状态。上图中NewPage1和NewPage2表示在NewPage函数中，每获取一个空闲帧，就会先去空闲列表（freelist_）中获取一个空闲帧，如果没有，就去replacer_中获取驱逐未固定的框架。使用。这反映了bufferpoolmanager实现的一个目标：最小化磁盘访问，后面会分析原因。实验组成在掌握本实验的基本概念和核心数据流程后，分析两个子任务。TASK#1-LRUREPLACEMENTPOLICY之前在LeetCode上写过相关的实现，所以很自然的把之前的经验带进来，但是后来发现这两个接口有些不同。LeetCode提供了kvstore接口，完成get/set时新旧顺序的维护，当内存池满时自动替换最旧的KV。但是本实验提供了replacer接口，维护一个unpinned的frame_id列表，调用Unpin时将frame_id加入列表并保持新旧顺序，调用Pin时从列表中移除frame_id，调用Victim时替换最旧的frame_id是回。当然本质还是一样的，所以我在本次实验中同样使用了unordered_map和双向链表的数据结构，实现细节不再赘述。需要注意的是，如果发现Unpin时frame_id已经在replacer中，则直接返回，不改变列表的新旧顺序。因为从逻辑上讲，同一个frame_id是不能多次Unpinned的，所以我们只需要考虑frame_id的第一个Unpin。在更大的范围内，replacer本质上是一个维护回收顺序的回收站，即我们不直接从内存中删除所有pin_count_=0的页面，而是将其放入回收站。根据数据访问的时间局部性原则，刚刚被访问过的页面很可能会被再次访问，所以当我们要真正从回收站中删除（Victim）一帧时，我们需要删除最旧的帧。当我们后面要访问一个刚刚加入回收站的数据时，只需要将页面拉出回收站即可，这样就省去了一次磁盘访问，也达到了最小化磁盘访问的目的。TASK#2-BUFFERPOOLMANAGER几乎已经解释了实验分析部分的核心逻辑。这里简单罗列一下我在实现过程中遇到的问题。page_table_的范围。在最初的实现中，绘制了frame的状态机后，感觉只把pinned的frameid放到page_table_中就完美了：frameid可以根据状态分布在free_list_、replacer_和page_table_中，互斥。但是后来发现如果unpinnedframeid没有保存在page_table_中，那么pin_count_=0的page就不能很好的复用，replacer也没有意义。清理脏页的时机。有两种策略，一种是每次Unpin都要刷一次，这样会刷的更频繁，但是可以保证异常掉电重启后内容不会丢失；另一种是在替代者受害时偷懒滑动，可以保证滑动次数最少。这是性能和可靠性之间的权衡。仅考虑这个实验，两者肯定都会通过。NewPage不读取磁盘。这是我写的错误。毕竟创建NewPage时，磁盘上并没有对应的页面内容，所以会报如下错误：2021-02-1816:53:47[autograder/bustub/src/storage/disk/disk_manager.cpp:121:ReadPage]DEBUG-Readlessthanapage2021-02-1816:53:47[autograder/bustub/src/storage/disk/disk_manager.cpp:108:ReadPage]DEBUG-I/Oerrorreadingpastenofffile在复用帧时清除元数据。在重新使用从替换器中驱逐的帧时要特别注意，一定要在使用前清除pin_count_\is_dirty_字段。当然，在删除Page时，还需要注意将page_id_设置为INVALID_PAGE_ID，并清空以上字段。否则再次使用时，如果Unpin后pin_count_的值不为0，则执行DeletePage时无法删除页面。锁的粒度。最粗暴的就是在每个函数范围的粒度上加锁。如果后期需要优化，锁的粒度会更细。实验代码以FetchPageImpl为例，强调一些实现细节。注意，实验已经通过注释给出了实现框架。我用中文注释来标注一些我认为需要注意的地方。Page*BufferPoolManager::FetchPageImpl(page_id_tpage_id){//a.使用自动获取和释放锁std::scoped_locklock(latch_);//1.Searchthepagetablefortherequestedpage(P).//1.1IfPexists,pinitandreturnitmediately.autotarget=page_table_.find(page_id);//b.判断存在和访问数据只需要一次查找if(target!=page_table_.end()){frame_id_tframe_id=target->second;//c.通过指针操作得到frame_id处存放的Page结构Page*p=pages_+frame_id;p->pin_count_++;replacer_->Pin(frame_id);//d。从“回收站”returnp;}//1.2IfPdoesnotexist,findareplacementpage(R)fromeitherthefreelistorthereplacer.//Notthatpagesarealwaysfoundfromthefreelistfirst.frame_id_tframe_id=-1;Page*p=nullptr;if(!free_list_.empty()){frame_id=free_list_.back.at运行结束;/效率更高free_list_.pop_back();assert(frame_id>=0&&frame_id(pool_size_));p=pages_+frame_id;//f.从freelist获取的dirtypage在delete的时候已经写回了}else{boolvictimized=replacer_->Victim(&frame_id);if(!victimized){returnnullptr;}assert(frame_id>=0&&frame_id(pool_size_));p=pages_+frame_id;//2.IfRisdirty,writeitbacktothedisk.if(p->IsDirty()){disk_manager_->WritePage(p->GetPageId(),p->GetData());p->is_dirty_=false;}p->pin_count_=0;//g.清除元信息pin_count_}//3.DeleteRfromthepagetableandinsertP.page_table_.erase(p->GetPageId());//h.时刻注意区分p->GetPageId()是否等于page_id，不要混用page_table_[page_id]=frame_id;//4.UpdateP的元数据，从磁盘读取pagecontent，然后返回指向P.p->page_id_=page_id;p->ResetMemory();disk_manager_->ReadPage(page_id,p->GetData());p->pin_count_++;returnp;}实验相关的autograder可以在FAQ中找到注册地址和邀请码，提交时最好代码不要提交github仓库地址，会有很多格式问题，可以每次按照实验页面的提示，将相关文件按照目录结构打成zip包提交。投稿事项仔细阅读实验说明，投稿前注意事项：运行build目录下的makeformat，自动格式化。在构建目录中运行makecheck-lint以检查一些语法问题。为每个函数在本地设计一些测试，写入相关文件（本次实验buffer_pool_manager_test.cpp），并打开测试开关，在build文件夹下编译makebuffer_pool_manager_test，运行./test/buffer_pool_manager_test，粘贴一个project1autograder实验结果：autograderresultssummary这是cmu15445的第一个实验，实现了按需在磁盘和内存之间移动页（page）的bufferpoolmanager。本次实验的重点是掌握基本概念，梳理核心数据流，并在此基础上关注一些实现细节。