一、缓存
缓存（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 的淘汰却不是给予全局的策略，执行步骤如下：
- 判断是否超过最大容量限制
- 在缓存中随机取出不超过 30 个元素作为样本
- 根据淘汰策略确定需要淘汰的元素
- 在缓存中移除元素
3.2 redis 中的缓存淘汰
在 redis 中可以配置 6 中淘汰机制：
- noeviction：不删除策略, 达到最大内存限制时, 如果需要更多内存, 直接返回错误信息。
- allkeys-lru：所有 key 通用，优先删除最近最少使用 (LRU) 的 key。
- volatile-lru：只限于设置了 expire 的部分; 优先删除最近最少使用 (LRU) 的 key。
- allkeys-random：所有 key 通用; 随机删除一部分 key。
- volatile-random：只限于设置了 expire 的部分; 随机删除一部分 key。
- volatile-ttl：只限于设置了 expire 的部分; 优先删除剩余时间 (time to live,TTL) 短的key。
详细介绍可以参考 官方文档 。
3.3 Guava 中的缓存淘汰
Guava 在维护缓存数据的同时，还维护了 WirteQueue 和 AccessQueue，分别用来记录写入的记录和访问的记录。总体来说有 4 种淘汰策略：
- Size-base Eviction：基于使用量的淘汰策略。
- Timed Eviction：基于时间驱逐，提供了根据访问时间（expireAfterAccess）和根据写入时间（expireAfterWrite）。
- Reference-based Eviction：基于引用驱逐（通过 java 的软、弱引用实现）。
- Explicit Removals：显示移除。
详细介绍可以参考 官方文档。