ARC Cache算法

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….