本周主要跟着代码随想录学习了LRU, LFU, 以及ARC三种缓存替换算法的原理和C++实现。

1. LRU

LRU是Least Recently Used的缩写，即淘汰最近最少使用的元素。

缓存的实现使用了一个哈希表和一个双向链表。哈希表用于快速查找缓存中的元素，双向链表用于维护缓存中的元素顺序。

每当涉及一个元素的key时，将该元素移动到双向链表的头部。当缓存满时，将双向链表的尾部元素删除。同时将该元素从哈希表中删除。

1.1 改进

以上的LRU存在着缓存污染、锁的粒度过大的问题。

缓存污染：当新加进来的一次性的数据很多，导致缓存满时，传统的LRU会直接删除尾部元素。但是，尾部元素可能是热门数据。
锁的粒度大：一把大锁锁全局。多线程高并发的访问下，同步等待将是一笔极大的时间开销。

故考虑以下改进：

1.1.1 LRU-K

LRU-K在普通的LRU的基础上，新增加了一个小的LRU副缓存。当数据进入时，它会先进入副缓存，并访问计数加一。只有当它的访问计数大于等于K时，才会移出副缓存，进入主缓存。

当主副缓存满时，淘汰机制与普通LRU一致。

这样就可以避免缓存污染的问题。使得大量进入的一次性数据不会挤出热门数据。

1.1.2 LRU-Hash

与2024-xv6-labs-2中2.2 Buffer cache的思想一致，既然一个链表配全局大锁效率低，那就把链表分成多个小链表，每个小链表即是一个小的lru缓存，各自配置最大容量，并通过一个哈希表（vector即可）统一管理，每个哈希桶配一个锁。每个新来的元素根据key的哈希值插入对应的小链表中。若容量在这之前已满，则同理删除这个小链表的尾部元素。

2. LFU

LFU是Least Frequently Used的缩写，即淘汰使用次数最少的元素。

缓存的实现使用了一个记录键-值对<key, value>的哈希表a和一个记录频率-列表对<freq, linklist>的哈希表b。哈希表a用于快速查找缓存中的元素，哈希表b用于根据频率高效地维护缓存中的元素。

每当涉及一个元素的key时，将该元素的频率增加1，并将该元素移动到哈希表b中对应频率的链表头部。移动后若原链表为空则删去。当缓存满时，将哈希表b中频率最低的链表的尾部元素删除。同时将该元素从哈希表a中删除。

2.1 改进

普通LFU存在着新来的元素容易被移出（即使是未来的热门数据）、而过时的热门数据很难被移出的问题，而且访问次数若一直增长，可能会导致上溢。

同时与普通LRU一样，存在锁的粒度过大的问题。

改进如下：

2.1.1 最大平均访问次数限制

首先设置一个阈值。当数据访问/插入发生时，不仅需要记录当前最小访问次数，还需要计算平均访问次数。然后当平均访问次数超过阈值时，就需要对记录的访问次数进行调整。所有的元素的访问次数减去阈值的一半，操作后小于0者设为1。然后更新记录<freq-linklist>的哈希表，将元素插入对应频率的链表中。

这样的方式不仅可以避免访问次数的上溢，还可以加快数据的更新，让旧的热点数据”老化”，缓解挤占未来的热点数据空间的问题。

2.1.2 LFU-Hash

同LRU-Hash的思想，分成多个记录<freq-linklist>的小哈希表，每个表即是一个小的lfu缓存，各自配置最大容量，并通过一个哈希表（vector即可）统一管理，每个哈希桶配一个锁。每个新来的元素根据key的哈希值插入对应的小链表中。若容量在这之前已满，则同理删除频率最低的链表的尾部元素。

3. ARC

ARC是Adaptive Replacement Cache的缩写，即自适应替换缓存。

当访问的数据趋向于访问最近的内容，会更多地命中LRU list；当系统趋向于访问频繁访问的内容时，会更多地命中LFU list。

LRU和LFU各有优劣，而实际应用环境更为复杂，需要将两种混合，取长补短。于是就有了结合LRU和LFU的缓存替换算法，即ARC。

基本思想是，将缓存分成两个部分，一部分是LRU缓存，一部分是LFU缓存，然后每个缓存有一个自己的ghost缓存。

当新数据进入时，先进入LRU list，并访问次数设为一。当再次访问这个数据时，访问次数增加1。当访问次数达到阈值后，LFU list里也插入这个元素。于是，该数据块不仅仅只保存在LRU的缓存目录中，也将保存到LFU中。所以一个最近的热门数据若有更新应该是两个表同时进行的。

这样，那些真正被频繁访问的页面将一直呆在缓存中，不会被冷数据的加入而误淘汰，不经常访问的数据会向链表头部移动，最终被淘汰出去。

当缓存满时，需要淘汰一个元素。淘汰的逻辑与对应的普通LRU和普通LFU一致，只是淘汰出的元素要插入对应的ghost缓存中。ghost缓存的淘汰模式就是简单的FIFO即可。

这样，访问元素在哪一边ghost中找到，就说明那一边的容量小了而对面的容量大了。对面的容量如果不为0则减一，然后这边的容量加一。否则跳过。