缓存淘汰策略：怎么淘汰缓存命中率才不会下降？

为什么要淘汰？

用缓存肯定要控制住缓存的内存使用量。而这就会引出一个问题，万一达到了内存使用上限，但是又需要加入新的键值对，怎么办？最保守的做法就是直接报错，那么你就没有办法缓存新的数据了。后续如果缓存中已有的数据过期了，你就能缓存新的数据了。

淘汰算法

LRU

LRU（Least Recently Used）是指最近最少使用算法。也就是说，缓存容量不足的时候，就从所有的 key 里面挑出一个最近一段时间最长时间未使用的 key。

只需要把 key 用额外的链表连起来，然后每次被访问到的 key 都挪到队尾，那么队首就是最近最长时间未访问过的 key。也可以反过来，每次访问过的挪到队首，那么队尾就是最近最久未访问过的 key。

LFU

LFU（Least Frequently Used）是最不经常使用算法，它是根据对象的使用次数来确定淘汰对象的，每次都是将使用次数最低的淘汰掉。所以基本的思路就是按照访问频率来给所有的对象排序。每次要淘汰的时候，就从使用次数最少的对象里面找出一个淘汰掉。

如果有好几个对象的访问频次恰好相等，而且又是最低的，那么可以自由决策如何淘汰。标准做法是淘汰最先插入的，不过也有一些实现就是随机删一个，又或者删掉排序位置最小的那个。实现的基本思路就是每次读写的时候，对象上面的次数都加 1，然后调整位置。

小结

在实践中，一般是优先考虑 LRU。这主要是因为 LRU 对时间局部性突出的应用非常友好，而大多数的应用场景都满足时间局部性的要求。

Redis 支持的淘汰算法

Redis 支持很多淘汰算法，可以通过 maxmemory 选项来控制 Redis 整个内存使用量，还可以通过指定 maxmemory_policy 设置淘汰算法