LRU-K&15445p2

LRU-K页面置换算法

LRU & LRU-K

LRU-least recently used-最近最少使用算法，是一种内存数据淘汰策略，使用常见是当内存不足时，需要淘汰最近最少使用的数据。LRU常用于缓存系统的淘汰策略。

对于固定大小（size）的缓存池，当缓存池满时使用LRU对页面进行驱逐。LRU满足先进先出，使用双向链表+HASH即可维护。

例如：size 为2时

操作 驱逐顺序
1. access(1)
2. access(2)
3. setEvictable(1) 1
4. setEvictable(2) 1 、2
5. access(3) 2
6. setEvictable(3) 2 、3
7. access(2) 3 、2

LRU-K ，它的过程是对于访问次数小于k的页面按照FIFO驱逐，大于等于k的驱逐顺序为具有最大后向k距离访问时间戳的页面

例如：size为2,k为3时
例如：size 为2时有以下操作

操作 驱逐顺序
1. access(1)
2. access(2)
3. setEvictable(1) 1
4. setEvictable(2) 1 、2
5. access(3) 2
6. setEvictable(3) 2 、3
7. access(2) 2 、3
8. access(2) 3 、2

可以看到第7次操作与上述LRU操作的不同，当然当k为1时便是朴素的LRU算法

实现

以15445 2023spring p1为例

对于每个node具有以下定义（省略了set和get）

1
2
3
4
5
6
7
8
class LRUKNode {
 private:
  std::list<size_t> history_;
  size_t k_;
  frame_id_t fid_;
  std::list<std::shared_ptr<LRUKNode>>::iterator pos_;
  bool is_evictable_{false};
};

LRUReplacer定义：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class LRUKReplacer{
public:
auto Evict(frame_id_t *frame_id) -> bool;

void RecordAccess(frame_id_t frame_id, AccessType access_type);

void SetEvictable(frame_id_t frame_id, bool set_evictable);

void Remove(frame_id_t frame_id);

auto Size() -> size_t;

struct Cmp {
    auto operator()(const std::shared_ptr<LRUKNode> &a, const std::shared_ptr<LRUKNode> &b) const -> bool {
      size_t sa = a->Getfront();
      size_t sb = b->Getfront();
      return sa < sb;
    }
  };

 private:
  std::unordered_map<frame_id_t, std::shared_ptr<LRUKNode>> node_store_;
  std::list<std::shared_ptr<LRUKNode>> que_;
  std::set<std::shared_ptr<LRUKNode>, Cmp> lru_;
  size_t current_timestamp_{0};
  size_t curr_size_{0};
  size_t replacer_size_;
  size_t k_;
  std::mutex latch_;

具体可参考spring2023/project1

Evict:
判断当前是否有可驱逐页面，优先从que里面驱逐（FIFO）,其次从lru中驱逐，这里使用Cmp()将具有最小后向k距离的排在前面

RecordAccess：
判断页面是否在缓存池中（nodestore）如果在，更新访问记录（push当前时间戳），如果不在新建一个LRUKNode放在缓存池中，对于可驱逐的点要判断是否要将其从que拿出放进lru。这里要注意更新history并不会更新lru要先将节点拿出再插入

SetEvictable:
修改页面可驱逐状态，对于原本不可驱逐的判断其访问次数将其放进que或者lru中。在que中的可以使用std::lower_bound通过Cmp()比较插入，lru中则直接插入

Remove：
将页面删除使用pos快速删除在que中删除

Buffer Pool Manager

任务2 bpm使用lru-k管理缓存池

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class BufferPoolManager {
public:
    auto NewPage(page_id_t *page_id) -> Page *;
    auto FetchPage(page_id_t page_id, AccessType access_type) -> Page *;
    auto UnpinPage(page_id_t page_id, bool is_dirty, AccessType access_type) -> bool;
    auto FlushPage(page_id_t page_id) -> bool;
    auto DeletePage(page_id_t page_id) -> bool;
private:
    const size_t pool_size_;
    std::atomic<page_id_t> next_page_id_ = 0; 
    Page *pages_;
    DiskManager *disk_manager_ __attribute__((__unused__));
    LogManager *log_manager_ __attribute__((__unused__));
    std::unordered_map<page_id_t, frame_id_t> page_table_;
    std::unique_ptr<LRUKReplacer> replacer_;
    std::list<frame_id_t> free_list_;
    std::mutex latch_;
}

这里只列出几个主要操作

poolsize 缓存池大小
free_list 空闲列表

NewPage：
判断freelist是否为空，不为空时可以直接拿来，为空则通过replacer_驱逐页面，成功驱逐返回驱逐的页面，注意脏页需要写回磁盘

FetchPage：
从读取page_id页面，如果该页面在缓存池中直接返回改页面，否则按照NewPage方式获取空页面，并从磁盘中读取page_id页面。要更新访问记录使得LRU-K工作

UnpinPage：
多线程访问，如果页面的pin_count不为0将其减1，如果此时变为0，则将该页设置为可驱逐。

FlushPage：
将页面写回磁盘（无论是否为脏页）并更新页面不为脏页

DeletePage：
删除页面，如果为脏先写回磁盘，将该页从replacer删除，更新free_list以及nodestore

总结

这个project前后做了一周，主要困难在于没有理解要求，另外实现使用大锁保护，效率较低等有时间会再做优化

附上惨痛的提交记录：