LRU-K模型设计

LRU算法介绍
  • Least recently used(LRU,最近最少使用):根据数据的历史访问记录淘汰数据。
  • 核心思想

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

    • 当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。
  • LRU算法模型如下图:
    1.png

    • 新数据插入到链表头部;
    • 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
    • 当链表满的时候,将链表尾部的数据丢弃。

LRU-K算法设计

LRU-K中的K代表最近使用的次数。
  • 主要目的

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

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

    • LRU-K降低了“缓存污染”带来的问题,命中率比LRU要高。
  • LRU-K模型如下图:
    2.png

    • 数据第一次被访问,加入到访问历史记录表(简称记录表);在记录表中对应的K单元中设置最后访问时间=new(),且设置访问次数为1;
    • 如果数据访问次数没有达到K次,则访问次数+1。最后访问时间与当前时间间隔超过预设的值(如30秒),访问次数清0并加1;
    • 当数据访问计数超过(>=)K次后,则访问次数+1。将数据保存到LRU缓存队列中,缓存队列重新按照时间排序;
    • LRU缓存队列中数据被再次访问后,重新排序;
    • LRU缓存队列需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第K次访问离现在最久”的数据。
Last modification:November 12th, 2019 at 09:32 am
如果觉得我的文章对你有用,请随意赞赏