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.

  • 也就是说,利用这种适应机制,当系统趋向于访问最近的内容,会更多地命中LRU ghost list,这样会增大LRU的空间; 当系统趋向于访问最频繁的内容,会更多地命中LFU ghost list,这样会增加LFU的空间.