type
status
slug
summary
tags
category
password
date
icon

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个连续页的分配情况。
      notion image
    • 需要实现的函数:
      • 🦄
        与Bitmap Page相关的代码位于src/include/page/bitmap_page.hsrc/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),再通过一个额外的元信息页来记录这些分区的信息。通过这种“套娃”的方式,来使磁盘文件能够维护更多的数据页信息。其主要结构如下图所示:
      notion image
       
  • 缓冲池替换策略
    • LRU替换策略
      • Buffer Pool Replacer负责跟踪Buffer Pool中数据页的使用情况,并在Buffer Pool没有空闲页时决定替换哪一个数据页。在本节中,你需要实现一个基于LRU替换算法的LRUReplacerLRUReplacer类在src/include/buffer/lru_replacer.h中被定义,其扩展了抽象类Replacer(在src/include/buffer/replacer.h中被定义)。LRUReplacer的大小默认与Buffer Pool的大小相同。
         
    • (bonus)CLOCK替换策略
  • 缓冲池管理
 
期末复习索引LLM fintuning
Loading...
fufu酱
fufu酱
一个爱折腾的大学生
公告
👋
欢迎 欢迎来到fufu酱的blog! 💞️我是22级浙江大学竺可桢学院计算机科学与技术专业的学生 一个爱折腾的大学生 🌱我会在这个网站上更新我的笔记和工具分享 🌈目前all in MLLM 📫你可以用下面的方式联系到我
🍀
今後ともよろしくお願いします