实验说明

实验主页https://15445.courses.cs.cmu.edu/spring2023/project1/
本次实验主要完成buffer pool（缓存池）
- 缓存池是用来在主存和磁盘之间移动物理页（physical page）的工具
- 该部分对于数据库管理系统（DBMS）的其他部分来说透明，举例来说，DBMS要求使用一个独有的page_id，buffer pool则帮DBMS获取这个page，不需要知道这个page一开始是否在主存中或者是从disk中取到主存再返回给DBMS的

Task #1 - LRU-K Replacement Policy

Task分析
需要使用LRU-K策略来实现frame的换入和换出。
普通的LRU策略是当replacer的缓存池的大小满了（这里是curr_size == replacer_size）后需要将其中最长时间没有访问的给替换出去。
LRU-K相对于LRU缓解了缓存污染的问题。

LRU缓存污染：偶发性的，周期性的批量操作会导致LRU cache的命中率急剧下降，这时缓存中的数据大部分都不是热点数据
如何确定K？K增大，命中率会更高，但是适应性差（清楚一个缓存需要大量的数据访问，一般选择LRU-2，LRU == LRU-1）

LRU-K Replacer在本次Task中的实现如下

维护一个unordered_map<frame_id_t, std::shared_ptr> node_store_，用来记录全部的节点
维护两个list
- std::list<std::shared_ptr> history_list_; 用来存放访问的节点，但是访问次数小于K次，list的排列顺序按照FIFO的规则，list尾部表示最新访问的数据，头部表示最旧访问的数据
- std::list<std::shared_ptr> cache_list_; 真正需要缓存的节点，访问次数大于等于K次，list的排列顺序遵守LRU-K的规则，参照Node元素中timestamps的头部元素进行排列，按照从小到大的规则，list尾部表示头部元素最大的(最新的)
history_list_.size + cache_list_.size = curr_size
LRUNode表示一个frame在LRUKReplacer中的状态
- 成员变量：frame_id，size k_（最多纪录前k_个访问时间），访问次数ref_count，是否可以evict，timestamps（数组，前k个访问时间）
- 同时每次访问frame时（RecordAccess），ref_count都需要自增

class LRUKNode {
public:
LRUKNode() {
    k_ = 0;
    fid_ = -1;
    // last_seen_timestamp_ = -1;
    is_evictable_ = true;
    ref_count_ = 0;
}

LRUKNode(size_t k, frame_id_t fid, size_t access_time, bool is_evictable, size_t ref_count)
: k_(k), fid_(fid), is_evictable_(is_evictable), ref_count_(ref_count) {
    timestamps_.push_back(access_time);
}

LRUKNode(const LRUKNode &other) {
    k_ = other.k_;
    fid_ = other.fid_;
    // last_seen_timestamp_ = other.last_seen_timestamp_;
    timestamps_ = other.timestamps_;
    is_evictable_ = other.is_evictable_;
    ref_count_ = other.ref_count_;
}

auto GetFrameId() const -> frame_id_t { return fid_; }
auto GetRefCount() const -> size_t { return ref_count_; }
// auto GetLastSeenTimestamp() const -> size_t { return last_seen_timestamp_; }
auto GetFirstTimestamp() const -> size_t { return timestamps_.front(); }
auto IsEvictable() const -> bool { return is_evictable_; }

auto IncRefCount() -> void { ref_count_++; }

auto SetTimestamp(size_t timestamp) -> size_t {
    // last_seen_timestamp_ = timestamp;
    timestamps_.push_back(timestamp);
    auto first_timestamp = timestamps_.front();
    if (timestamps_.size() > k_) {
        timestamps_.erase(timestamps_.begin());
    }
    return first_timestamp;
}
auto SetFrameId(frame_id_t fid) -> void { fid_ = fid; }
auto SetK(size_t k) -> void { k_ = k; }
auto SetEvictable(bool is_evictable) -> bool {
    auto is_same = is_evictable_ == is_evictable;
    is_evictable_ = is_evictable;
    return is_same;
}

private:
/** History of last seen K timestamps of this page. Least recent timestamp stored in front. */
// Remove maybe_unused if you start using them. Feel free to change the member variables as you want.

[[maybe_unused]] size_t k_;
[[maybe_unused]] frame_id_t fid_;
// [[maybe_unused]] size_t last_seen_timestamp_;
std::vector<size_t> timestamps_;
[[maybe_unused]] bool is_evictable_{false};
size_t ref_count_{0};
};

LRU-K的原理

对一个frame访问时(RecordAceess)先搜索全部的节点node_store_
- 如果存在，需要记录当前的current_timestamp，即插入到该LRUK节点的timestamp数组中，如果数组size>k_，则pop掉最前面的元素，这时数组的头部元素就是前第k次访问时间。并将该节点的ref_count++
- 如果不存在，则新建一个LRUKNode，记录到node_store和history中（同时指向这个新建的LRUKNode）
  - 新加入的节点需要考虑当前需要全部元素的个数，如果curr_size == replacer_size，需要Evict掉一个节点
    - Evict逻辑比较简单（只evict一个节点），分别从头到尾遍历history和cache（顺序一定是先history再cache），如果某个节点is_evictable，就把它从对应的list和node_store中erase掉
  - 新节点直接push_back到history尾部即可（history遵循FIFO规则），注意⚠️需要考虑k = = 1的情况，即新节点ref_count = = 1，在移入history之后又要立即移动到cache
如果当前节点ref_count==k，说明该节点现在在history中，达到了k次的访问次数，需要从histroy移动到cache中了
- 因为是将history中的node移动到cache中，不涉及整体size大小的变化，也就不需要Evict cache
- 将该frame_id对应的node从history中erase
- 从cache_list的链表头开始遍历，比较链表节点中timestamps的头部元素和待插入的节点的timestamps的头部元素（前第k次访问时间），找到第一个比待插入节点大的链表节点（比待插入新），插入到该节点之前
- 通过这种操作，保证了cache_list遵循了LRU-K规则，cache最先淘汰的永远是链表头部节点
如果当前节点ref_count>k，说明该节点在访问之前就在cache中了，需要根据该节点的timestamps更新该节点在cache_list中的位置，更新规则同ref_count==k的插入规则

关键点

LRUNode对应每一个frame对应的node
- 比较关键的是其中的timestamps_数组，用来存放每次访问的时间，数组大小最大为k，当访问数refcount>=k时，把这个node从history移动到cache中真正缓存下来
history中按照FIFO替换，cache中按照LRU-K替换
注意k==1的情况
当ref_count==k时不需要考虑size的变化，因为是history和cache之间的交互，不影响整体的size

Task #2 - Buffer Pool Manager

Task分析
Task1中的replacer只是用来记录frame的使用情况，并不做具体的写入写出操作，Task2的buffer pool则需要完成具体的page的写入写出。
一个frame可以理解为一个实际的物理存储空间块，page表示的是逻辑上的存储，在DBMS的一整个生命周期中，page可以对应多个frame（同一时间一个page只能对应一个frame），映射关系通过NewPage构建。

Task2没有添加额外的成员变量，但是增加了一个成员函数FindFrame，各函数实现逻辑如下

构造函数
- 初始化时直接根据pool_size_，初始化Page* pages即缓存池
- page_table_存放是的page_id到frame_id的映射
- free_list_存放的是未使用的frame_id（0<=id<pool size），即未使用的实际上的物理frame
增加了一个辅助函数FindFrame
- 输入参数为frame_id_t *frame_id
- 先搜索free_list_，如果有空余的frame，那么给frame_id赋值并返回
- 如果没有空的frame，用replacer的Evict替换掉其中的一个frame，并将替换的frame的id保存到frame_id中，再从pages取出frame_id对应的page，如果该page dirty，则写入到disk中，然后将该page_id和frame_id的映射从page_table中清除
NewPage
- 找到一个可用的frame_id，使用该frame_id从pages中取出一页，对该页分配page_id，添加table映射，设置pin_count和replacer对于该frame的相关参数
FetchPage
- 从buffer pool中取出page_id对应的page
- 首先搜索page_id到frame_id的映射，保证当前page_id对应一个实际的物理frame
  - 如果有，则取出该frame_id对应的page，并设置pin_count和replacer
  - 如果没有，则FindFrame，找到一个合适的物理frame，从磁盘上将该page_id的数据读取到对应的page中
UnpinPage
- 输入为page_id和该page是否dirty
- 作用是解除page_id对应page的一次引用
- 首先是搜索该page_id是否有分配对应的物理frame，如果没有，返回false
- 如果有对应的frame，查看该page的pin_count
  - 如果小于等于0，说明已经没有数据在引用这个frame，直接返回false
  - 如果大于0，则pin_count–，把dirty写入到page的is_dirty参数，如果解除这次引用后pin_count==0，还需要对replacer SetEvictable
FlushPage
- 输入为page_id
- 将page_id对应的page写入到disk中，并更新dirty位
- 首先判断page_id是否合法
- 在page_table中搜索该page_id，判断是否分配frame
  - 如果没有分配，return false
  - 如有分配，将frame_id对应的page写入到disk，并设置dirty位
FlushAllPages
- 输入为空
- 遍历page_table，将全部的page都写入到disk中即可
DeletePage
- 输入为page_id
- 删除page_id对应的实际的page
- 首先遍历table，确定是否有分配实际的frame
  - 无，返回true
  - 有，判断pin_count是否大于0，如果大于0，说明仍有数据引用这块page，因此不能删除，返回false
- 确定这块page可以删除后
  - 分别在page_table清除映射，replacer清除frame，free_list_添加frame，Deallocate该page_id，Reset该page的memory，重置pin_count和dirty位，最后将该page_id设置为INVALID，return true

Task #3 - Read/Write Page Guards

Task分析
在Task2的条件下，使用DBMS忘记调用UnpinPage可能会导致该page永远不会被Evict掉，会造成page在内存和磁盘之间来回的交换，大大影响系统性能，Task要求实现PageGuard相关成员来完成Page的使用安全性保证。
阅读代码后分析任务，主要是完成类的move的自定义构造函数和自定义操作符，类的Drop函数，类的析构函数，前两个Task实现清楚的话，Task3难度属于简单。

各函数实现细节如下
page_guard