• 对

    缓存穿透、缓存雪崩、缓存击穿 问题解决思路

    缓存来由随着互联网系统发展的逐步完善，提高系统的qps，目前的绝大部分系统都增加了缓存机 制从 而避免请求过多...
    这篇文章中提到的LRU、LRU-K算法做一个附加介绍。

    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：September 20, 2020
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏