GreenHatHG の Blog

https://15445.courses.cs.cmu.edu/fall2022/project1/

DB 的 Buffer Replacement Policies 中的 LRU 和 Clock 算法都容易受到 sequential flooding 的影响，对于 LRU 来讲，使用 LRU-K 算法能够缓解这个问题。

LRU-K

• This component is responsible for tracking page usage in the buffer pool.
• 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 less than k historical accesses is given +inf as its backward k-distance.
  • When multipe frames have +inf backward k-distance, the replacer evicts the frame with the earliest timestamp.

Backward k-distance

这个数据很关键，也很容易被理解错，下面举例说明，当 k=3 时候

由上面的定义可知，Backward k-distance 为 current_timestamp 和倒数第 k 次访问的时间之差，故 k=3 时候如上面所示

因为每次 current_timestamp 都是一样的，所以其实直接看第 k 次访问的时间点就好，这里可以不用记下每次访问的时间戳，直接记录访问对应的 index 就好了，也就说记住某个数在第几次出现就好了。

• 每次都选择最大的 Backward k-distance 驱除 (evit)，这里存在两种情况:

  1. 某个数已经有了 k 次访问记录，那么 Backward k-distance 就是上图所示

  2. 如果不够 k 次访问，那么 Backward k-distance 就是正无穷大

• 那么每次 evit 时候肯定都是优先选择第二种情况，因为是正无穷大

  • 如果有多个无穷大，则按照 FIFO 的顺序 evit
    比如访问顺序如下（从左到右依次访问），假设 k=3
    1 2 3 4 1 2 3 1 2
    这里无限大的数有 3 和 4，按照 FIFO 顺序，3 第一次出现的时间点和 4 还早，所以第一次 evit 时候选择 3
• 第二种情况没有了的话，则按照第一种情况，这里直接看哪个数倒数第 k 次最早出现就好了，那么就是 Backward k-distance 最大的

SetEvictable

需要注意的是某个数是 evitable 才能被 evit，也就是 ` 这个函数的作用，因为此时某个数据正在被访问，不能 evit

有一种情况是 SetEvictable 时候，但是这个数还没有被访问过或者是被 evit 了，那么这个函数直接 return 就好了

Implementation

我是使用了两个顺序容器和一个 map

• map 记录了某个数第 n 次访问的 index，比如 hist (1, 3)，代表 1 这个数第 3 次访问的 index

• 当某个数还没有访问 k 次时候，就放到第一个容器，保证容器内的顺序是 FIFO 的，这样每次从队首或者队尾出队就好了，因为某些数可能不是 Evictable 的，实际上需要遍历一下容器，找到第一个能够 Evictable 的。

• 如果达到 k 次，那么把这个数从第一个容器挪到第二个容器

• evit 时候，如果第一个容器已经是 empty 的，那么代表没有正无穷的数，需要从第二个容器拿，此时因为 map 记录了每次容器出现的时间点，按照 map 对容器排序后直接取好了。这里没有想到一个方法类似第一个容器那么维护状态，考虑一下访问顺序：

  1 1 1 2 2 2 1 X
  

  虽然 1 是最后 evit 的，但是按照 Backward 3-distance 来看，1 才是要 evit，不能每次访问就更新那个数在第二个容器的位置。

  看了下 discord 的讨论，有比这个更快的方法，应该使用了堆之类的容器维护

维护某个数是否已经出现，以及其状态：

struct LruEntry {
    bool evictable_{false};
    size_t access_count_{0};
  };
std::unordered_map<frame_id_t, LruEntry> lru_entry_hash_;

第一个容器：

std::list<frame_id_t> less_than_k_frames_;

第二个容器：

std::vector<frame_id_t> more_than_k_frames_;

记录每个数每次出现的时间点：

struct PairHash {
    auto operator()(const std::pair<frame_id_t, size_t> &p) const -> std::size_t {
      // 使用 std::hash 计算哈希值
      std::size_t h1 = std::hash<frame_id_t>{}(p.first);
      std::size_t h2 = std::hash<size_t>{}(p.second);
      return h1 ^ (h2 << 1);  // 可以使用异或和位移等运算来组合哈希值
    }
  };
std::unordered_map<std::pair<frame_id_t, size_t>, size_t, PairHash> hist_;

获取某个数第 k 次出现的时间：

auto GetLastKAccessTime(const frame_id_t x) const -> size_t {
	const auto last_k = lru_entry_hash_.at(x).access_count_ - k_ + 1;
	return hist_.at(std::make_pair(x, last_k));
}

按照 Backward k-distance 对第二个容器排序：

std::sort(more_than_k_frames_.begin(), more_than_k_frames_.end(),
            [&](frame_id_t a, frame_id_t b) { return GetLastKAccessTime(a) < GetLastKAccessTime(b); });