CMU15-445数据库系统(Spring Lab)lab笔记

发表于 本文字数： 1.8k 阅读时长 ≈ 2 分钟

题图：TNO经济面板

剧透警告

在ACM败犬群里听说人均cmu15 445，想补一补缺少的数据库知识（题主在某普通一本，数据库课程很垃圾），就来做做cmu15445。

学cmu15-445前：数据库不就是std::map

学cmu15-445后：存储模型，事务控制，内存装不下

Project #1 - Buffer Pool Manager

Project #1 - Buffer Pool - CMU 15-445/645 :: Intro to Database Systems (Spring 2023)

先上AC图～

总的来说还是比较难的，隔着Page和DiskManager头一次写中层代码，需要考虑一堆细节问题。

然后莫名其妙上了rk9，没做啥特别的优化啊

Task #1 - LRU-K Replacement Policy

写一个独立的LRU-K置换策略，有几点需要注意的

  1. 一般的LRU置换器会遇到sqeuential flooding(简单的顺序for可占用过多的可能不会继续用的缓存导致缓存命中率降低)，LRU-K根据第k访问的时间戳进行LRU，这样强制访问次数大于等于k次才能够保留在缓存中，能够缓解这一问题。
  2. LRU-K置换器内部与具体的Page和Buffer Pool Manager无关。
  3. 还需要实现SetEvict接口，因为当一个页面被占用时我们不希望被逐出缓存。
  4. 线程安全
  5. Size返回的是可逐出页的数量而不是缓存中页的总数。

我的思路简单来说就是维护一个std::map<size_t, std::deque<frame_id_t>>的distance->frame_id_t的数据结构，每一次访问/更新可逐出状态时更新。这样这个数据结构的第一个frame_id_t就是我们期望的下一个逐出的frame。distance由节点的GetDis函数计算，用一个队列保存访问时间戳，访问次数小于k时distance为0。

实现线程安全直接给每一个成员函数上一把成员锁就行了，简单方便（逃

Task #2 - Buffer Pool Manager

Buffer Pool Manager(以下简称BPM)是本次project最难的了，它基于DiskManager/Page/我们刚写的LRUKReplacer向上提供一个以Page为基本单位的内存池。有几点需要注意的

  1. 分清楚page/page id和frame/frame id的概念。page是物理存在的一页内存空间，存在于DiskManager/BufferPoolManager中（分别是一页内存的磁盘状态和内存状态）；frame是容纳page的一个逻辑概念，存在于BufferPoolManager和LRUKReplacer中。DiskManager根据page id管理磁盘上海量的页；BufferPoolManager内部才有frame id，是BufferPoolManager内部内存中的少数page的索引。
  2. 对于NewPage和如果内存中没有对应page的FetchPage函数，找frame_id要先在free_list_中找（空闲frame），然后再尝试逐出现有page，逐出前别忘了写回。我在FetchPage时找frame_id顺序搞反了花一个多小时才发现（。
  3. UnpinPage时对页面置dirty时记得要用逻辑或，不然一个clean的unpin会清除之前dirty的unpin状态。
  4. 一些函数的返回值，UnpinPage返回0除了在内存中找不到页时还有pin_count已经小于等于0；DeletePage在pin_count>0时返回false；NewPage(page_id_t *page_id)返回nullptr前还要把*page_id置0，
  5. Guarded系列函数要在返回前给页上锁
  6. 线程安全

Task #3 - Read/Write Page Guards

实现一个类似unique_ptr的page guard，析构时自动Unpin。有几点需要注意的

  1. ReadGuard/WriteGuard析构还得解读/写锁
  2. 移动构造函数/移动赋值函数移动后别忘了设置nullptr
  3. 移动赋值函数移动前别忘了Drop自己
  4. Drop时要检查是否有效

也是实现C++ RAII类的老生常谈的东西了。不过好像不需要考虑a=std::move(a)这种问题，看来测试代码还是蛮规范的。