1. 缓存简介

缓存进化史

缓存的淘汰策略

由于本地缓存是将计算结果缓存到内存中，所以需要设置一个最大容量来防止出现内存溢出的情况。这个容量可以是缓存对象的数量，也可以是一个具体的内存大小。

当缓存数量逼近或大于所设置的最大容量时，为了将缓存数量控制在所设定的阈值内，就需要丢弃掉一些数据。由于缓存的最大容量恒定，为了提高缓存的命中率，需要尽量丢弃那些之后不再经常访问的数据，保留那些即将被访问的数据。为了达到以上目的，往往会制定一些缓存淘汰策略，常用的缓存淘汰算法有以下几种：

FIFO：First In First Out，先进先出。一般采用队列的方式实现。这种淘汰策略仅仅是保证了缓存数量不超过所设置的阈值，而完全没有考虑缓存的命中率。所以在这种策略极少被使用。
LRU：Least Recently Used，最近最少使用；该算法其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。所以该算法是淘汰最后一次使用时间离当前最久的缓存数据，保留最近访问的数据。所以该种算法非常适合缓存“热点数据”。但是该算法在缓存周期性数据时，就会出现缓存污染，也就是淘汰了即将访问的数据，反而把不常用的数据读取到缓存中。为了解决这个问题，后续也出现了如LRU-K，Two queues，Multi Queue等进阶算法。
LFU：Least Frequently Used，最不经常使用。该算法的核心思想是“如果数据在以前被访问的次数最多，那么将来被访问的几率就会更高”。所以该算法淘汰的是历史访问次数最少的数据。一般情况下，LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录，一旦数据访问模式改变，LFU需要更长时间来适用新的访问模式，即：LFU存在历史数据影响将来数据的“缓存污染”效用。后续也出现LFU*，LFU-Aging，Window-LFU等改进算法。

合理的使用淘汰算法能够很明显的提升缓存命中率，但是也不应该一味的追求命中率，而是应在命中率和资源消耗中找到一个平衡。