CMU15445-2024fall-project1踩坑经历

p1目录：

lRU\_K替换策略
- LRU
- LRU\_K
- 大体思路
- - SetEvictable
  - RecordAccess
  - Size
  - Evict
  - Remove
Disk Scheduler
BufferPool
- NewPage
- DeletePage
- FlashPage/FlashAllPage
- CheckReadPage/CheckWritePage
- - PageGuard
  - 并发设计
  - 主逻辑

感谢CMU的教授们给我们分享了如此精彩的一门课程，希望您能尊重教授们和TAs的劳动成果！

本篇文章记录本人对实验中各个板块的理解以及踩坑，如果您发现我过多的涉及到了实验的内容，有违学术诚信，请告诉我！

正文：

Project1要实现的是一个Buffer pool Manager。 Buffer pool Manager的作用是能够对磁盘中的数据进行预缓存。数据库的数据是保存在磁盘中的，要对其中的数据进行处理，就要将磁盘的数据加载到内存中，但是如果当每次要用这个数据的时候再从磁盘中取出，那么就会消耗大量的时间。 Buffer Pool Manager的作用就是预先从磁盘中将数据取出来，当需要使用到时候再把数据从内存中直接提取使用。

在本project中，我们要实现三个组件：

lru_k替换策略
Disk Scheduler 磁盘管理器
Buffer pool Manager 缓冲池管理器。

lRU_K替换策略

Buffer pool manager通过lru_k的替换策略来替换掉缓冲池中的不常用页面。这个lru_k的替换策略类似于操作系统中的三大调度算法 —— 进程替换、页面置换、磁盘调度算法。

为了解释lru_k，这里用lru进行辅助理解。下面是两者的执行策略和思想：

LRU

执行策略：选择最长时间没有被使用过的页面进行替换。
思想：过去访问频繁的页面，未来也会频繁访问；过去访问最少的页面，未来也会很少访问。

如果两个数据的访问次数相同，那么删除访问时间最早的那一个。或者说是访问时间距离现在最远的那一个。

LRU_K

执行策略：设置一个k，然后规定一个后向距离k，删除后向距离k最大的节点。
- ```
后向距离k的计算方式为（除红框框外的论述）：
```
- 当节点被访问的次数大于等于k：k = 当前时间戳 - 第前k次访问该节点时的时间;
  - 比如当前时间戳为1000， k为3。有节点1、节点2。其中节点1的访问次数为4，访问时间戳依次为：100， 200， 300， 400; 节点2的访问次数为5，访问时间戳依次为:10, 20, 50, 800, 900。那么对于节点1的后向k为: 1000 - 200 = 800。节点2的后向k为: 1000 - 50 = 950。所以删除节点2。
- 当节点被访问的次数小于k：k = +inf，如果两个节点的访问次数均小于k，那么会删除第一次时间戳距离当前时间戳最久的节点。
  - - 对于当访问次数小于k的时候我之前也有过疑问，文档中写的意思按照我的理解是：删除节点中最近访问的时间戳最小的节点，但是我这么写线上测试没过。所以这里的节点访问次数小于k应该是对于最早的一次访问的时间戳与当前时间戳的比较。
- 综上lru_k的策略其实很简单：就是如果有访问次数小于k的节点，优先删除访问节点小于k的，如果存在多个这样的节点，那么就删除第一次访问的时间戳最早的节点。如果没有访问次数小于k的节点，那么计算后向k距离，删除后向k距离最大的节点。

大体思路

LRU_K的代码集中在了lru_k_replacer.h和cpp文件中。您可以阅读lru_k_replacer.h中的注释和类的定义来获取实现所需要的各种信息。

在这里插入图片描述

（上图为官方仓库）LRUKNode是lru_k中的节点。根据注释的描述， histroy_用来存储访问的timestamps(时间戳）、k_为规定的k、 fid_为与当前节点绑定的缓冲池中的页面id、is_evicatable_为当前页面是否可以被删除。

另外，在该项目中，我们的变量如果定义后没有使用，编译是会报错的，所以请将不使用的变量删掉或者不确定使用可以加[[maybe_unused]]修饰。

在这里插入图片描述

（上图为官方仓库）LRUKReplacer是lru_k数据结构，作为移除器使用。这里面可能有一些我们可能需要的属性以及要实现的方法。

SetEvictable

修改指定的lru_k节点是否可以删除。可以为true，否则为false。需要注意同时修改lru_k移除器中的可移除节点的数量。

RecordAccess

页面被访问时调用，更新页面对应节点的使用情况。先查找lru_k移除器有没有维护该页面。如果没有，则添加维护信息；如果已经维护，添加时间戳，同时全局时间戳要增加。

Size

返回移除器中可移除节点的数量。

Evict

lru_k板块的核心。找出要移除的节点。大体思路就是设置一个指向删除节点的标记位。遍历所有可移除节点，计算后向k距离，与被标记的节点对比。如果两个后向k都为inf，标记两者中最小时间戳更小的那一个；如果其中一个inf，标记该节点。如果两个都不为inf，标记后向k更大的。

Remove

Remove也是移除某个节点。不同的是，它是指定某个可移除帧，确定该帧要被删除。而Evict是从可以出帧中选出一个不常用的删除。 Remove面向外部的 “我要删除特定的帧”； Evict面向外部的"我需要一个帧”。

Disk Scheduler

这部分记不太清了，印象中实现起来很简单。难点是要使用C++17的语法promise 和 future，学习一下新语法就可以通过了。

BufferPool

实现BufferPool，其实就是实现PageGuard的创建和删除，在该组件中，核心的功能就是 创建新页面、从磁盘读取页面、删除页面，将页面刷新到磁盘。

NewPage

NewPage，即创建新页面。就是在磁盘中创建新的页面。注意！不是将页面放到缓冲池的frames中，而是直接在磁盘上创建一个页面，无需读取到frames。利用DiskScheduler的函数。

DeletePage

删除页面的操作，这个删除是在磁盘中删除，而不是只从缓冲池中删除。如果目标页面在缓冲池的帧中，那么刷新到磁盘，再从磁盘中删除。注意：只从缓冲池删除p1不会测试出现问题，但是在p3的外排序任务中需要检测磁盘的刷新和加载。

FlashPage/FlashAllPage

将页面刷新到磁盘。（刷新磁盘的操作都是使用Disk Scheduler中的刷新函数)

CheckReadPage/CheckWritePage

p1的核心，最难的地方。需要理解pin_count的增加和减少的时机、SetEvict的时机；以及大锁（整个BufferPool的锁）和小锁（单个页面的读写锁) 的获取与释放的时机。

我们下面就先讨论并发设计：

PageGuard

对于CheckReadPage和CheckWritePage, 他们两个获取的是指定page_id的PageGuard。这个PageGuard，可以理解为BufferPool内frame帧的RAII管理器。创建ReadPageGuard的时候，会增加帧的引用计数，修改帧的lru_k属性, 同时也会获取帧的读锁，此时如果获取了读锁，那么别的线程再获取写锁，即WritePageGuard, 就会阻塞；创建WritePageGuard的时候，同样也会增加帧的引用计数，修改帧的lru_k属性，同时也会获取帧的写锁，此时如果获取了写锁，那么别的线程再获取ReadPageGuard或者WritePageGuard，就会阻塞。

当ReadPageGuard释放的时候，会减少帧的引用计数，修改帧的lru_k属性，同时会释放读锁，销毁资源；当WritePageGuard释放的时候，同样会减少帧的引用计数，修改帧的lru_k属性，同时会释放写锁。

以上就是PageGuard的理解。

并发设计

并发设计要保证三个顺序：

当获取和释放PageGuard的时候，对于读写锁和pin_count，我们要保证一个顺序：pin->lock->unlock->unpin。
- 大概的主要原因是因为如果lock->pin，那么在线程获取小锁被锁住后，该页面的pin_count只有1，如果持有页面的线程释放该页面，在lock -> pin + SetEvict()中间的空挡，该页面可能会被设置为可移除，进而被刷新回磁盘。那么线程再lock， lock的是什么？我们要知道， lock是frame帧里面的成员，作用是锁住该帧。而如果原本的页面被替换成别的页面，那么此时lock，锁住的就不是原本的页面，而是新替换来的页面了，与预期结果不符，程序出错。（TODO。这里不太懂，可能就是先 lock再pin会导致页面被刷新替换，导致lock了自己不想要的页面，导致逻辑错误。）
保证获取小锁之前要将大锁释放掉。在本地测试的DeadLockTest有下面这种情况:
- 线程TA想要获取页面A，所以进入CheckPage函数，获取了大锁，然后创建页面A的PageGuard获取页面A的小锁。退出CheckPage函数释放大锁。
- 此时线程TB也想要获取页面A，所以进入CheckPage函数，获取了大锁，然后创建页面A的PageGuard时因为A的锁被占用，所以阻塞。此时TB占据着大锁阻塞。
- 如果此时TA想要再获取任何一个页面，都要进入CheckPage函数获取大锁，但是大锁被TB占用，就形成了一种情况：TA占据着页面A的小锁，想要获取TB占用的的大锁； TB占据着大锁，想要获取TA占用的小锁。形成死锁。
- 所以我们要确保TB在阻塞之前把大锁释放掉。但是这样我们必须说服自己一件事，就是这样做可能导致插队，此时执行会不会不符合预期？
- 如果TA和TB两个获取不同的页面PageGuard那么不会造成插队情况， TA获取页面A的PageGuard之前释放大锁， TB进入获取TB的PageGuard。两个线程针对不同的frame，即BufferPool中不同的内存块。互相不干预，而且因为减少了锁粒度，可以让并发更快。
- 如果TA和TB获取相同的页面， TA获取页面A的PageGuard，在获取小锁之前释放大锁；TA刚刚释放大锁，此时一个TB速度极快，迅速获取大锁，然后抢在TA之前获取小锁。
- 如果TA和TB获取的都是读锁，那么不冲突，两者都可以获取到页面A的小锁。
- 如果TA获取读锁， TB获取写锁。或者TA获取写锁， TB获取读锁。那么TA会被插队， TB会成功获取到页面A。此时的结果相当于TB获取到页面A后，TA才执行。页面A此时pin_count为二，TBpin了一次， TApin了一次，并且页面A的可移除状态为false。结果在可接受范围之内。
保证pin/unpin和SetEvictable()被绑定为原子。即两个操作一定是在一起，原子的。所以要保证pin和SetEvictable()以及unpin 和SetEvictable()是在大锁的保护下。因为如果pin和SetEvictable不被绑定为原子操作，就会出现以下这种情况：
- 对于页面A，线程A本来持有该页面。然后线程Aunlock->unpin->pin_count == 0。线程A想要进入SetEvictable。
- 此时另一个线程B在正在获取页面A，并且执行速度非常快。很快就pin->pin_count == 1了。然后比线程A更快进入SetEvictable，修改了页面的状态变成”不可移除“。
- 最后线程A才进入SetEvictable修改页面变成”可移除“。程序出错。