15445 的 project 是要学生实现一个名为 Bustub 的关系型数据库。该数据库的主要框架已经为我们实现好了，我们需要做的就是在这个框架上实现一些核心功能。
第一个 project 是实现一个buffer pool Manager。 在开始 P1 之前，我们先来简要回顾一下 buffer pool 的一些基本概念。
Buffer Pool
缓冲池是内存的一个分区，它的主要目标之一是最小化磁盘和内存之间的块传输次数。
DBMS 在需要数据时会向缓冲管理器发起一个请求：
- 如果该数据块已经在缓冲中，缓冲管理器会将内存中块的地址传递给请求者。
- 如果缓冲池中没有该数据块，缓冲管理器
- 首先在缓冲池中为该块分配空间，如果缓冲池已满了，会淘汰掉一些其他块以为新块腾出空间。被淘汰的块只有在自上次写入磁盘以来被修改后才会被写回磁盘。
- 然后，缓冲管理器从磁盘读取请求的块到缓冲中，并将主内存中块的地址传递给请求者。
另外，一旦一个数据块被加载到缓冲区，数据库进程可以从缓冲内存中读写块的内容。然而，在读或写块的同时，如果一个并发进程将该块驱逐并替换为不同的块，那么正在操作旧块内容的进程将会产生致命的错误。
因此，在进程从缓冲块读取数据之前，确保该块不会被驱逐是非常重要的。为此，进程在块上执行一个 pin 操作；缓冲管理器永远不会淘汰被 pin 住的块。当进程完成数据读取后，应该执行一个 unpin 操作，允许在需要时将块驱逐。
在实际的数据库系统中，同时会有多个进程可以从缓冲区中的块中读取数据。每个进程在访问数据之前都需要执行 pin 操作，并在完成访问后执行 unpin 操作。只有在执行 pin 操作的所有进程都执行了 unpin 操作后，块才能被淘汰。确保这一属性的一种简单方法是为每个缓冲块保留一个类似于 C++中 shared_ptr 引用计数 的 pin 计数。每次 pin 操作会增加计数，而 unpin 操作会减少计数。只有当 pin 计数等于 0 时，才能淘汰页面。
Task #1 - LRU-K Replacement Policy
Task 1 要让我们实现一个 LRU-K 替换策略。LRU-K 是 LRU 的一种变种。它会淘汰 backward k-distance 最大的页面。
该算法在 《The LRU-K Page Replacement Algorithm For Database Disk Buffering》 这篇论文中第一次提出。在论文中，backward k-distance的定义为：
也就是指当前时间戳与上 k 次访问的时间戳之差。如果某个块的访问次数小于 k，那么它的 backward k-distance 就是+inf。
例如缓冲池中某一个块被访问了 5 次，这 5 次访问的时间戳分别为[3,8,12,20,28],当前时间戳为 30，那么这个块的 backward 3-distance 就是 30-12=18。LRU-1 就是普通的 LRU，而 LRU-2 则根据页面倒数第二次访问的时间来淘汰页面。相对于 LRU，LRU-K 在时间局部性方面有显著改进。
在 Task 1 中，我们需要实现以下函数：
-
Evict(frame_id_t* frame_id)：淘汰具有与替换器跟踪的所有其他可淘汰帧相比最大后向 k 距离的帧。将帧 ID 存储在输出参数中并返回 True。如果没有可淘汰帧，则返回 False。
-
RecordAccess(frame_id_t frame_id)：记录给定帧 ID 在当前时间戳下的访问。在 BufferPoolManager 中将页面固定后，应调用此方法。
-
Remove(frame_id_t frame_id)：清除与帧关联的所有访问历史。仅当在 BufferPoolManager 中删除页面时才应调用此方法。
-
SetEvictable(frame_id_t frame_id, bool set_evictable)：此方法控制帧是否可淘汰。它还控制 LRUKReplacer 的大小。当页面的固定计数达到 0 时，应调用此函数，将相应的帧标记为可淘汰，并增加替换器的大小。
-
Size()：此方法返回当前 LRUKReplacer 中可淘汰帧的数量。