基于LRU、LRU-K算法的简单总结

- 如果数据最近被访问过，那么将来被访问的几率更高。命中率

- 当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。LRU算法模型
    - 新数据插入到链表头部；
    - 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
    - 当链表满的时候，将链表尾部的数据丢弃。
LRU-K算法设计
LRU-K中的K代表最近使用的次数。主要目的

- 解决LRU算法“缓存污染”的问题。核心思想

- “最近使用过1次”的判断标准扩展为“最近使用过K次”。命中率

- LRU-K降低了“缓存污染”带来的问题，命中率比LRU要高。LRU-K模型数据第一次被访问，加入到访问历史记录表（简称记录表）；在记录表中对应的K单元中设置最后访问时间=new()，且设置访问次数为1；如果数据访问次数没有达到K次，则访问次数+1。最后访问时间与当前时间间隔超过预设的值(如30秒)，访问次数清0并加1；当数据访问计数超过(>=)K次后，则访问次数+1。将数据保存到LRU缓存队列中，缓存队列重新按照时间排序；LRU缓存队列中数据被再次访问后，重新排序；LRU缓存队列需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。