缓存是有空间的限制的，不同的情况下会采取不同的缓存淘汰策略应对缓存满载。常见的缓存淘汰策略有三种：

• 先进先出策略 FIFO（First In，First Out）
• 最少使用策略 LFU（Least Frequently Used）
• 最近最少使用策略 LRU（Least Recently Used）

FIFO

先进先出，如果缓存容量满，则优先移出最早加入缓存的数据；其内部可以使用队列实现。

简单理解其实就是：如果一个数据最先进入缓存中，则应该最早淘汰掉。

LFU

根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。

所以 LFU 的淘汰策略其实就是：如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小，所以优先淘汰。

LRU

least recently used，是目前最常用的缓存算法和设计方案之一，其移除策略为“当缓存（页）满时，优先移除最近最久未使用的数据”，优点是易于设计和使用，适用场景广泛。

乍一看好像和 LFU 的区别不是很大，其实 LFU 和 LRU 的区别主要是判断的依据不一样，LFU 依据的是访问次数、LRU 依据的是多少时间没被访问。

举个例子：

1. 比如有数据：1，2，3，4

2. 缓存大小为2：[]

3. 我依次访问了1，2，1

4. 缓存现在应该是 [1(2), 2(1)] (括号里面是访问的次数)

5. 我现在又要访问3，这个时候就需要缓存淘汰策略了

6. 对于 FIFO 应该很好理解，先进先出，我先访问的1，后访问的2，所以缓存变为[3(1).2(1)]

7. 对于 LFU 淘汰访问次数最少的就可以了，缓存变成[3(1),1(2)]

8. LRU 我们要看哪个数据没被访问的时间最长，因为我最新一次访问的是1，所以淘汰2，缓存变成[3(1),1(2)]