ARC（Adaptive Replacement Cache）是一种适应性Cache算法, 它结合了LRU与LFU。
LRU(Least recently used)
- 其核心思想是:假设刚visit的item,很有可能在未来被revisit
- 丢弃最近最少访问的items
- 通常用双链表实现 tips: redis并没有这样做，因为这样每个key至少会多出两个指针。 redis采用的是一种近似LRU，基本思想是随机取出一些key,形成一个小的POOL，然后在pool中采用LRU策略(相关源码:redis/src/evict.c)
- 缺点:忽略了frequency, 不适合大规模扫描等情况
- LRU有一系列变种，比如LRU2, 2Q, LIRS等。
LFU(Least-frequently used)
- 其核心思想是:假设visit次数越多的item,很有可能在未来被revisit
- 适应大规模扫描
- 对热点友好
- 缺点:忽略了recency, 可能会积累不再使用的数据 tips: redis4.0开始支持了LFU,例如volatile-lfu, allkeys-lfu配置选项
ARC
- 整个Cache分成两部分，起始LRU和LFU各占一半，后续会动态适应调整partion的位置（记为p）
- 除此，LRU和LFU各自有一个ghost list(因此，一共4个list)
- 每次，被淘汰的item放到对应的ghost list中（ghost list只存key）, 例如：如果被evicted的item来自LRU的部分， 则该item对应的key会被放入LRU对应的ghost list
- 第一次cache miss, 则会放入LRU
- 如果cache hit, 如果LFU中没有，则放入LFU
- 如果cache miss, 但在ghost list中命中，这说明对应的cache如果再大一丁点儿就好了： 如果存在于LRU ghost list, 则p=p+1；否则存在于LFU ghost list, p=p-1.
- 也就是说，利用这种适应机制，当系统趋向于访问最近的内容，会更多地命中LRU ghost list，这样会增大LRU的空间； 当系统趋向于访问最频繁的内容，会更多地命中LFU ghost list，这样会增加LFU的空间.
参考
[1] https://linux-mm.org/AdvancedPageReplacement
[2] https://www.usenix.org/legacy/events/fast03/tech/full_papers/megiddo/megiddo.pdf
[3] https://www.youtube.com/watch?v=1Wo3i2gkAIk
[4] https://github.com/antirez/redis/blob/unstable/src/evict.c