缓存算法–LRU
这篇讲的是两种经典的缓存淘汰算法：LRU和它的改进版LRU-K。文章开门见山，先解析了LRU（最近最少使用）的核心思想——它用一个巧妙的链表来实现，新数据插入头部，每次访问都把数据提到最前，满了就淘汰尾部那个“最久没碰”的。这种策略在热点数据集中时效率很高，实现也简单。 但文章也指出了LRU的软肋：一旦出现偶发的批量扫描，会挤掉很多热门数据，造成严重的“缓存污染”。为了解决这个问题，文章引入了LRU-K。这里的“K”代表一个访问次数阈值，比如我们常说的LRU-2。它不再因为一次访问就把数据加入缓存，而是让数据在历史队列中先“排队”，只有被访问了K次，证明它确实是热点，才获准进入缓存队列。 这样一来，LRU-K的命中率通常比LRU更高，能有效抵抗缓存污染。但天下没有免费的午餐，它的实现需要维护额外的访问历史队列并进行排序，算法复杂度、内存消耗和CPU开销都比LRU要高。文章最后也点明了选择的关键：LRU胜在简单高效，适合大多数常规场景；而当你面对严重的访问模式波动时，LRU-K（尤其是LRU-2）提供了一个更稳健的选择。