Minisql | fufu酱のNoteBook

type

status

slug

summary

1 DISK AND BUFFER POOL MANAGER

涉及的代码有：

src/include/page/bitmap_page.h

src/page/bitmap_page.cpp

src/include/storage/disk_manager.h

src/storage/disk_manager.cpp

src/include/buffer/lru_replacer.h

src/buffer/lru_replacer.cpp

src/include/buffer/buffer_pool_manager.h

src/buffer/buffer_pool_manager.cpp

test/buffer/buffer_pool_manager_test.cpp

test/buffer/lru_replacer_test.cpp

test/storage/disk_manager_test.cpp

这一个部分主要包含四个模块：

实现一个简单的位图页

实现一个简单的位图页（Bitmap Page），位图页是Disk Manager模块中的一部分，是实现磁盘页分配与回收工作的必要功能组件。位图页与数据页一样，占用PAGE_SIZE（4KB）的空间，标记一段连续页的分配情况。

Bitmap由两部分组成

用于加速Bitmap内部查找的元信息（Bitmap Page Meta）

包含当前已经分配的页的数量（page_allocated_）
下一个空闲的数据页(next_free_page_)

页中剩余的部分就是Bitmap存储的具体数据

大小BITMAP_CONTENT_SIZE可以通过PAGE_SIZE - BITMAP_PAGE_META_SIZE来计算
这个Bitmap Page能够支持最多纪录BITMAP_CONTENT_SIZE * 8个连续页的分配情况。

需要实现的函数：

🦄

与Bitmap Page相关的代码位于src/include/page/bitmap_page.h和src/page/bitmap_page.cpp中

BitmapPage::AllocatePage(&page_offset)：分配一个空闲页，并通过page_offset返回所分配的空闲页位于该段中的下标（从0开始）；
BitmapPage::DeAllocatePage(page_offset)：回收已经被分配的页；
BitmapPage::IsPageFree(page_offset)：判断给定的页是否是空闲（未分配）的。

与该模块相关的测试代码位于test/storage/disk_manager_test.cpp中。

磁盘数据页管理

在实现了基本的位图页后，我们就可以通过一个位图页加上一段连续的数据页（数据页的数量取决于位图页最大能够支持的比特数）来对磁盘文件（DB File）中数据页进行分配和回收。但实际上，这样的设计还存在着一点点的小问题，假设数据页的大小为4KB，一个位图页中的每个字节都用于记录，那么这个位图页最多能够管理32768个数据页，也就是说，这个文件最多只能存储4K * 8 * 4KB = 128MB的数据，这实际上很容易发生数据溢出的情况。

为了应对上述问题，一个简单的解决思路是，把上面说的一个位图页加一段连续的数据页看成数据库文件中的一个分区（Extent），再通过一个额外的元信息页来记录这些分区的信息。通过这种“套娃”的方式，来使磁盘文件能够维护更多的数据页信息。其主要结构如下图所示：

缓冲池替换策略

LRU替换策略

Buffer Pool Replacer负责跟踪Buffer Pool中数据页的使用情况，并在Buffer Pool没有空闲页时决定替换哪一个数据页。在本节中，你需要实现一个基于LRU替换算法的LRUReplacer，LRUReplacer类在src/include/buffer/lru_replacer.h中被定义，其扩展了抽象类Replacer（在src/include/buffer/replacer.h中被定义）。LRUReplacer的大小默认与Buffer Pool的大小相同。

（bonus）CLOCK替换策略

缓冲池管理