Project #1 - Buffer Pool
Task #1 - LRU-K Replacement Policy
需要实现一个 LRU-K 替换策略，看了知乎上的推荐，可以先写一下这道题：Leetcode 146. LRU 缓存
这道题要求实现一个 LRU 缓存，即当缓存满时访问次数少的，时间久的数据会优先被淘汰。
而 LRU-K 与 LRU 的区别就是，LRU-K 会考虑最近 K 次访问的情况，而不是只考虑最近一次访问。
先看实验指导：
The LRU-K algorithm evicts a frame whose backward k-distance is maximum of all frames in the replacer. Backward k-distance is computed as the difference in time between current timestamp and the timestamp of kth previous access. A frame with fewer than k historical accesses is given +inf as its backward k-distance. When multiple frames have +inf backward k-distance, the replacer evicts the frame with the earliest overall timestamp (i.e., the frame whose least-recent recorded access is the overall least recent access, overall, out of all frames). 翻译 LRU-K 算法会淘汰一个 backward k-distance 最大的 frame。backward k-distance 是当前时间戳和第 k 次访问的时间戳的差值。如果一个 frame 的历史访问次数少于 k，那么它的 backward k-distance 为 +inf。当有多个 frame 的 backward k-distance 为 +inf 时，淘汰最早访问的 frame。
可以得知 LRU-K 的 frame 分两种情况：
- 历史访问次数少于 k，backward k-distance 为 +inf，这种情况下，优先淘汰最早访问的 frame，即先进先出，FIFO
- 历史访问次数大于等于 k，backward k-distance 为当前时间戳和第 k 次访问的时间戳的差值，优先淘汰 backward k-distance 最大的 frame，即优先淘汰第 k 次访问时间最久远的 frame，这个第 k 次指的是从当前时间往前数的第 k 次访问。即 LRU
这样考虑的话，时间戳这个东西就不那么重要了。
我的做法是使用两个哈希链表，一个存 fifo,一个存 lru。
为了减少内存泄漏，我最开始使用的是智能指针，shared_ptr，但是写完才发现，像双向链表这种不适用 shared_ptr，会导致循环引用，内存泄漏。如果使用 unique_ptr, 又无法避免的要用到裸指针，所以最后还是使用裸指针。
记得在类析构和逐出页面时清理内存即可。
在测试是要将 DISABLED_SampleTest 的前缀 DISABLED_ 去掉，才能运行测试。
可以使用std::lock_guard，使用 RAII 的方式来管理锁。std::lock_guard 会在构造时锁住 mutex，在析构时释放 mutex。
实验要求实现 latch, 我没太明白 latch 和 lock 的区别，直接锁住有写操作的函数就行了。实际上都是写操作，所有这样加锁相当于将所有操作串行化了。
优化点：
- fifo 和 lru 两个链表可以合并成一个链表，新增一个中间节点隔开就像，可以简化一些操作。