常见缓存淘汰算法

2019/01/26 algorithm

一、缓存

缓存(Cache) 一词来源于 1967 年的一篇电子工程期刊论文。其作者将法语词 “cache” 赋予 “safekeeping storage” 的涵义,用于计算机工程领域。
最早是因为 CPU 与内存之间运算和读写速度不一致,在 CPU 添加一块空间用于提前将内存中数据加载进来,提高 整体的速度,这块空间被称为 缓存(Cache)。如今缓存的概念已被扩充,在内存和硬盘之间也有 Cache(磁盘缓存),乃至在硬盘与网络之间也有某种意义上的 Cache ──称为 Internet 临时文件夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间,用于协调两者数据传输速度差异的结构,均可称之为 Cache。
但是缓存的空间是宝贵的,所以我们不会将所有的数据都缓存起来,必须依赖一定的规则淘汰掉一部分数据。这个规则就是我们讨论的缓存淘汰算法。

二、缓存淘汰

2.1 FIFO(先入先出)

FIFO (First In FIrst Out) 是最简单的算法,原理跟名字一样,“如果一个数据最先进入缓存中,则应该最早淘汰掉”。把缓存中的数据看成一个队列,最先加入的数据位于队列的头部,最后加入位于队列的尾部。当缓存空间不足需要执行缓存淘汰操作时,从队列的头部开始淘汰。 如下所示,假设我们的缓存可以缓存 3 对数据,1 加入时处于队列的头部,2 和 3 加入时缓存空间充足。当 4 加入时,执行缓存淘汰,由于 1 处于队列的头部,所以被淘汰。同理 5 加入时,2 被淘汰。
Java 中有单独的队列 Queue ,可以使用 LinkedList

1 2 3 4 5
    3=c 4=e 5=f
  2=b 2=b 3=c 4=e
1=a 1=a 1=a 2=b 3=c

2.2 LRU(最近最少被使用)

LRU (Least Recently Used) 的核心思想是基于“如果数据最近被访问过,它在未来也极有可能访问过”。同样把缓存看成一个队列,访问一个数据时,如果缓存中不存在,则插入到队列尾部;如果缓存中存在,则把该数据移动到队列尾部。当执行淘汰操作时,同样从队列的头部开始淘汰。 如下所示,1、2、3 加入时缓存空间充足,接下来 1 又被访问了一次,所以 1 被移动到队列尾部。当 4 加入时,执行缓存淘汰,2 位于队列头部被淘汰。 Java 中可以直接使用 LinkedHashMap 来实现。

1 2 3 1 4
    3=c 1=a 4=e
  2=b 2=b 3=c 1=a
1=a 1=a 1=a 2=b 3=c

2.3 LFU(最不经常使用)

LFU (Least Frequently Used)的核心思想是“如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小”,会记录数据访问的次数,当需要进行淘汰操作时,淘汰掉访问次数最少的数据。 如下所示,一开始 1 被连续访问了两次,接下来 2 被访问一次,3 被访问一次,按照访问次数排序,访问次数少的处于队列头部。当 4 加入时,执行缓存淘汰,2 位于队列头部被淘汰。

1 1 2 3 4
      1=a (2) 1=a (2)
    1=a (2) 3=c (1) 4=e(1)
1=a (1) 1=a (2) 2=b (1) 2=b (1) 3=c (1)

2.4 其他

还有一些其他的淘汰算法:

  • 2Q(Two Queues):同时采用 FIFO 和 LRU 两个队列,首次访问数据时加入到 FIFO 队列中,如果数据在 FIFO 队列移除之前被再次访问,数据会被移动到 LRU 队列中。
  • LRU-K :是一种 LRU 算法的增强版,在 LRU 维护队列的基础上,再添加一个队列维护数据访问的次数,由原来访问 1 次会被添加到缓存中,改为访问 K 次才会被加入到缓存中。
  • ARC:在IBM Almaden研究中心开发,这个缓存算法同时跟踪记录LFU和LRU,以及驱逐缓存条目,来获得可用缓存的最佳使用。

三、常见示例

3.1 Ehcache 中的缓存淘汰

Ehcache 提供了 3 种淘汰机制(驱逐策略),分别是 LRU(默认),LFU,FIFO。但是 Ehcache 的淘汰却不是给予全局的策略,执行步骤如下:

  1. 判断是否超过最大容量限制
  2. 在缓存中随机取出不超过 30 个元素作为样本
  3. 根据淘汰策略确定需要淘汰的元素
  4. 在缓存中移除元素

3.2 redis 中的缓存淘汰

在 redis 中可以配置 6 中淘汰机制:

  1. noeviction:不删除策略, 达到最大内存限制时, 如果需要更多内存, 直接返回错误信息。
  2. allkeys-lru:所有 key 通用,优先删除最近最少使用 (LRU) 的 key。
  3. volatile-lru:只限于设置了 expire 的部分; 优先删除最近最少使用 (LRU) 的 key。
  4. allkeys-random:所有 key 通用; 随机删除一部分 key。
  5. volatile-random:只限于设置了 expire 的部分; 随机删除一部分 key。
  6. volatile-ttl:只限于设置了 expire 的部分; 优先删除剩余时间 (time to live,TTL) 短的key。

详细介绍可以参考 官方文档

3.3 Guava 中的缓存淘汰

Guava 在维护缓存数据的同时,还维护了 WirteQueue 和 AccessQueue,分别用来记录写入的记录和访问的记录。总体来说有 4 种淘汰策略:

  1. Size-base Eviction:基于使用量的淘汰策略。
  2. Timed Eviction:基于时间驱逐,提供了根据访问时间(expireAfterAccess)和根据写入时间(expireAfterWrite)。
  3. Reference-based Eviction:基于引用驱逐(通过 java 的软、弱引用实现)。
  4. Explicit Removals:显示移除。

详细介绍可以参考 官方文档

Search

    Table of Contents