【数据库】cmu15445-project1 实验报告与知识扩展-526互联

cmu 15445 是一门面向本科生的数据库开发课程。得益于前几年TiDB这样的开源先驱，以及国内对各种数据库没有止境的稳定性和性能要求，数据库内核开发成为很多程序员追求的开发方向，cmu 15445及MIT 6.824等项目成为了所谓的"标配。但是从dashboard的提交可以看出来，实际上很多人还是比较浮躁，并没有真的学透，甚至lab都没有真的完成，也不用说扩展的知识点了。

实验准备

课程主页 https://15445.courses.cs.cmu.edu/fall2022/schedule.html

课程仓库 https://github.com/cmu-db/bustub

自动测评网站 GradeScope，course entry code: PXWVR5 https://www.gradescope.com/

注意课程每年都有更新，项目的代码也有些许的差别。直接fork仓库到自己的github，然后在本地自己开发。如果要看以往2022的项目，clone后用切换到v20221128-2022fall对应tag。

实验要求

project-1要实现：

extendible_hash，实现一个动态的哈希表，防止一开始就占用了很大的空间。跟一般的哈希差别比较大，要弄清楚它的扩容方式。

lru_k_replacer：LRU内存置换算法的实现，跟普通的LRU区别不大。

buffer_pool_manager：缓存池。作用就是负责申请、回收页面。注意到缓存池的大小是有限的，也就意味着在使用的时候需要对可能需要驻留的页的数量级有一定的概念。

实验前提

1.不要上来就看project-1的实验文档。需要先了解extendible hash table的设计和buffer_pool_manager的内容。参见配套的slides和homework。

extendible_hash

extendible hash table的插入过程和概念参考

https://blog.csdn.net/MelroseLbt/article/details/129329316

其中，hash(key)得到的值与掩码做与运算，掩码为 (1 << global_depth) – 1，如

global_depth	mask	directory数
0	0	1
1	1	2
2	11	4

即directory数=global_depth。

注意到单个桶的容量不变，变的只有global_depth和directory数。

而local_depth是每个桶的性质，用来表示该桶掩码的位长。

可扩展哈希表的性质

索引项dir_index指向的桶内hash(key) & mask =dir_index。

global_depth=max{local_depth(i), 1<=i<=max_bucket}

插入过程正是保持哈希表性质不变的过程

算法流程

对参考文章中的流程重新组织语言。

step 1.

　　掩码global_mask = (1 << global_depth) – 1，即global_depth个1的二进制。

step2.

　　如果计算得到的桶内(=hash(key) & local_mask)未满，则完成插入。

　　否则要进行扩容。此时插入的桶记为bucket1，新加一个桶为bucket2。同时还要记录当前dir_index，对应bucket1的索引。local_depth加1，计算local_mask=(1<<local_depth)-1。

step3.

　　如果local_depth>global_depth, 则需扩容directory，按照二倍的容量对其扩容，均摊复杂度仍是O(1)。由于此时global_depth=n，对于n-1的低位，其所指的桶是一样的。另外新增一个桶bucket2，暂时保持为空。bucket1，2对应local_mask的最高位分别为0，1，其余相同。

step 4.

　　由于local_mask已经变化，hash(key)&local_mask也会发生变化，之前在旧桶bucket1中的元素不一定再满足性质。需要依次求元素的hash(key)&local_mask，若与dir_index&local_mask相等，则保留在旧桶，否则将元素迁移到新桶bucket2。

step 5.

　　如果按照新的mask分配仍然空间不够，（例如插入1110，1111，10111，1011），则必须要对bucket2重新分裂。但是在此之前要先将directory项对应的指针重定向。因为directory中，必然只有bucket1的指针而没有bucket2的指针，而global_depth>=local_depth,所以必然有与local_mask掩码与bucket2相同的项，需要按其重新定向。

step 6.

　　重定向完成，则以bucket2为旧桶，重新执行step1，直至完成插入并分配好相应的桶。

lru_k_replacer

LRU类提供Evict，Remove和RecordAccess接口。

核心接口是Evict，即淘汰内存页。对于每一个页，用frame_id表示，每次遍历访问历史表，用计数表示的时间戳（不能用真实时间戳）来表示。这里当然可以考虑用优先队列优化，当然这不是重点。

buffer_pool_manager

实现接口：

FetchPgImp(page_id)

UnpinPgImp(page_id, is_dirty)

FlushPgImp(page_id)

NewPgImp(page_id)

DeletePgImp(page_id)

FlushAllPagesImpl()

这里的思想是操作系统中常用的，缓存到页面中，并且一旦修改页面则置为脏页。利用前面的lru_k_replacer和extendible_hash，实现页面的动态替换，目的是利用程序的空间局部性提高性能。

buffer_pool_manager用文件实现页面的读写，注意已有的实现接口disk_manager->WritePage。

每次FetchPage都要pin页面，代表已被程序使用。

实验注意事项

可扩展哈希表的directory中的项跟桶就是数组跟指针的关系，它的指针形态跟数据插入流程高度相关，不要被图解的指针弄晕。
pin和unpin有什么用？其实就是告诉管理器页面此时被使用，在每次fetch页面之后都要有对应的pin，必须有与之成对的unpin操作，否则在后续的实验会出现问题。最简单的就是缓存不够用了，本质上就是该释放的内存垃圾一直占用着内存。所以这个是一个类似引用计数的标记。
为什么buffer_pool_manager的具体类要使用NewPgImp而不是更直接的NewPage？从代码可以看出来，应该是为了实现AOP切面编程。
buffer_pool_manager，lru的容量是静态的，而hash表的容量是动态的。