Category: 算法

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