ARC算法

ARC（Adjustable Replacement Cache）是一个缓存优化策略，ARC内部将缓存分为两类，分别是LRU（最近最多使用缓存）和LFU（最近最频繁使用），一般情况缓存根据时间进行优化或者根据频率进行优化，但是ARC可以自动调整优化策略。

首先说结论：
ARC是一种平衡访问时间优先和访问频率优先的策略，当缓存倾向于访问最近访问过的缓存（LRU）时，ARC会增加LRU链表的空间（同时减少LFU链表的空间）；当缓存倾向于访问最近频繁访问的文件时，ARC会增加LFU链表的空间（同时减少LRU链表的空间）。

ARC的做法：
假设总容量固定为n，初始状态我们需要容量为2n的管理表，分为四个链表。

• 最近最多使用的缓存链表，LRU链表
• 最近最频繁使用的缓存链表，LFU链表
• 最近从LRU表中淘汰的缓存链表，ghost LRU链表
• 最近从LFU表中淘汰的缓存链表，ghost LFU链表

所有数据首次进入缓存都会被放在LRU链表中，当被访问第二次时会进入LFU链表，且越是最近访问的数据越靠近头部。
当两个缓存都满了以后，一个新的数据进入缓存：

• LRU链表满了，链表尾部页面被淘汰到ghost LRU链表中
• 当命中ghost LRU链表，说明LRU缓存太小了，LRU链表的长度将会被加1，LFU链表的长度将会被减1
• LFU同理， 当数据从ghost链表中被淘汰，就是真正的被淘汰了。