缓存

最近在狂补优化方面的知识,缓存也是优化的一大方向。之前关于缓存只是知道它的功能,再多不知道了,这里整理缓存相关的知识,算是优化入门吧。

相关概念

  • 缓存

    是“存贮使用频繁的数据的临时地方,因为取原始数据的代价太大了,所以我可以取得快一些。”

    缓存可以认为是数据的池,这些数据是从数据库里的真实数据复制出来的,并且为了能别取回,被标上了标签(键 ID)。

  • 缓存分类

    • 硬件缓存

      它指的是一块芯片,可以被集成到硬盘或者是CPU上。它的作用就是充当硬盘(CPU)与外界接口(通常是内存)之间的暂存器。利用缓存可以减轻系统的负荷,同时提高数据的传输速率,如硬盘缓存和CPU缓存。

    • 客户端缓存

      某些应用,如浏览器,手机淘宝等,为了实现能够快速响应用户的请求,会把用户之前浏览的东西(如图片等)存在本地。在下次访问时,如果本地的缓存里有请求的内容,那么就直接展示出来,不用再次向服务器请求。

    • 服务端缓存

      它与客户端缓存目的相同,只不过是站在服务器这边考虑的。如果每次接到客户端请求都要连接一次数据库,当用户请求多的时候,负载过大。这时可以把一些经常被请求的数据存放在内存中,当有请求时直接返回,不用经过数据库。这样就可以减轻数据库的负担。

  • 缓存的工作原理

    当客户端向服务器请求一个资源时,服务器首先在缓存中找,如果在缓存中,那么直接返回,不需要连接数据库;如果请求的资源不在缓存中,这时再去数据库中找,找到后返回给客户端,并将这个资源加入缓存中。

  • 命中(HIT)

    当客户发端起一个请求,如果被请求的资源在缓存中,这个资源就会被使用,我们就叫它缓存命中。

  • 未命中(MISS)

    当客户端发起一个请求,如果没有在缓存中找到,我们称这种情况为缓存未命中。这时就需要查询数据库,并且将查询结果加入缓存中。 

  • 存储成本

    当未命中时,我们会从数据库取出数据,然后加入缓存。把这个数据放入缓存所需要的时间和空间,就是存储成本。

  • 失效

    当缓存中的数据需要更新时,就意味着缓存中的这个数据失效了。

    一种是数据库中的数据发生了变化,那么如果这个数据在缓存,相应的缓存数据也要同步更新。例如原来 id=1 的编程语言叫 Java,结果管理员修改成了 PHP,那么缓存里面的 id=1 的值就要同步成最新的值。

    另一种情况是该缓存过了失效时间。因为缓存会占用内存,太多的缓存是不合理的,我们可以通过设置失效时间的方式让缓存定时过期失效。

  • 失效策略(缓存算法)

    如果缓存满了,而当前请求又没有命中缓存,那么就会按照某一种策略,把缓存中的某个旧资源剔除,而把新的资源加入缓存。这些决定应该剔除哪个旧资源的策略统称为失效策略。

  • 替代策略

    当缓存没有命中时,并且缓存容量已经满了,就需要在缓存中踢出一个老的条目,加入一条新的条目,而到底应该踢出什么条目,就由替代策略决定。

  • 最优替代策略

    最优的替代策略就是想把缓存中最没用的条目给踢出去,但是未来是不能够被预知的,所以这种策略是不可能实现的。但是有很多策略,都是朝着这个目前去努力。

缓存算法

  • 原则上,失效策略需要考虑到以下这几点

    • 成本

      如果缓存对象有不同的存储成本,应该把那些难以获得的对象保存下来;

    • 容量

      如果缓存对象有不同的大小,应该把那些大的缓存对象清除,让更多的小缓存对象进来了;

    • 时间

      一些缓存设定有过期时间,应该在到时间之后将它们失效。
      应该根据缓存对象的性质选择合适的失效策略,常见的失效策略有这么几种:

      关于常见的缓存算法见博客:缓存那些事–常用的缓存失效策略

缓存中存在的问题

在缓存中存在缓存击穿、缓存雪崩、缓存并发等问题

缓存击穿

  • 问题描述

    缓存穿透是指查询一个一定不存在的数据,此时缓存是不被把命中的,那么就需要查数据库来获取这个值并写入缓存后返回,但是由于在数据库中也没有这个值,所以结果也不会写入缓存中。这将导致这个存在的数据每次请求都要到存储层去查询,失去了缓存的意义。

    在流量大的时候,可能数据库就崩溃了。另外要是有人利用不存在的 key 频繁请求数据库,这就是系统的漏洞。

  • 解决方法:常见的有两种:过滤器和设定指定值。

    (1)过滤器

    最常见的是采用布隆过滤器,将所有可能存在的数据哈希到一个足够大的 bitmap 中,一个一定不存在的数据会被这个 bitmap 拦截掉,从而避免了对底层存储系统的查询压力。

    (2)设定指定值

    这种方法比较巧妙,如果一个查询返回的数据为空(可能由于数据不存在,也可能是系统故障),我们仍然把这个空结果进行缓存,缓存的值设定为一个指定值,同时设置它的过期时间很短,最长不超过五分钟。(因为缓存会占用内存,长时间缓存一个不存在的值比较耗资源。)在这五分钟内,这个值可能由于写入操作从而不再是一个不存在的值,这是就要更新缓存,用真实值替代指定值。

    比如,设定不存在的值缓存为 &&,也就是 “key” ===> “&&”。当返回这个 && 值的时候,就可以认为这是不存在的 key,然后决定是继续等待访问,还是放弃掉这次操作。如果继续等待访问,那么经过一个时间轮询点后,再次请求这个 key,如果取到的值不再是 &&,则可以认为这时候 key 有值了,从而避免了透传到数据库,从而把大量的类似请求挡在了缓存之中。

缓存雪崩

  • 问题描述

    缓存雪崩指的是在某一个时刻,大量缓存同时失效,请求全部转到了数据库,导致数据库压力过大。

    引起这个问题的主要原因还是高并发。平时我们设定一个缓存的过期时间时,可能有一些会设置1分钟后或5分钟后。当并发很高时,会出在某一个时间同时生成了很多的缓存,并且过期时间都一样,这个时候就可能引发一当过期时间到后,这些缓存同时失效,请求全部转发到 DB ,DB 可能会压力过重。

    当发生大量的缓存穿透,例如对某个失效的缓存的高并发访问也会造成缓存雪崩。

  • 解决方法

    缓存失效时的雪崩效应对底层系统的冲击非常可怕。遗憾的是,这个问题目前并没有很完美的解决方案。

    一种常用的方法是,用加锁或者队列的方式保证缓存的单线程(进程)写,从而避免失效时大量的并发请求落到底层存储系统上。

    另一种方法是合理设计的缓存过期时间,将数据失效时间均匀地分布在时间轴上,一定程度上能够避免缓存同时失效带来的雪崩效应。例如可以在原有的失效时间基础上增加一个随机值,比如1-5分钟随机,这样每一个缓存的过期时间的重复率就会降低,就很难引发集体失效的事件。

缓存并发

  • 问题描述

    有时候如果网站并发访问高,一个缓存如果失效,可能出现多个进程同时查询 DB,同时设置缓存的情况,如果并发确实很大,这也可能造成 DB 压力过大,还有缓存频繁更新的问题。

  • 解决方法

    常用的解决方法是对缓存查询加锁,如果 KEY 不存在,就加锁,然后查 DB 后写入缓存,然后解锁;其他进程如果发现有锁就等待,然后等解锁后返回数据或者进入 DB 查询。

    这种解决方式会造成部分请求等待。

缓存算法

缓存算法是指令的一个明细表,用于决定缓存系统中哪些数据应该被删去。

缓存需要被清理时(比如空间占用已经接近临界值了),需要使用某种淘汰算法来决定清理掉哪些数据。常用的淘汰算法有下面几种:

  • FIFO:First In First Out,先进先出。判断被存储的时间,离目前最远的数据优先被淘汰。
  • LRU:Least Recently Used,最近最少使用。判断最近被使用的时间,目前最远的数据优先被淘汰。
  • LFU:Least Frequently Used,最不经常使用。在一段时间内,数据被使用次数最少的,优先被淘汰。
  • ARC自适应缓存替换算法(ARC):

    在IBM Almaden研究中心开发,这个缓存算法同时跟踪记录LFU和LRU,以及驱逐缓存条目,来获得可用缓存的最佳使用。

  • MRU:Most Recently Used,最近最常使用算法,和 LRU 正好相反。它会移除最近最多被使用的对象。

LRU类算法对比
由于不同的访问模型导致命中率变化较大,此处对比仅基于理论定性分析,不做定量分析

对比点 对比
命中率 LRU-2 > MQ(2) > 2Q > LRU
复杂度 LRU-2 > MQ(2) > 2Q > LRU
代价 LRU-2 > MQ(2) > 2Q > LRU

LRU

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

  • 实现,最常见的实现是使用一个链表保存缓存数据,详细算法实现如下:

    • 新数据插入到链表头部;
    • 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
    • 当链表满的时候,将链表尾部的数据丢弃。
  • 命中率:当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。

  • 复杂度:实现简单。

  • 代价:命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。

MySQL的InnoDB引擎设置有索引及数据缓存池,其中用到的LRU算法来维持缓存的命中率

LRU-K

  • 原理

    LRU-K中的K代表最近使用的次数,因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题,其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

  • 实现

    相比LRU,LRU-K需要多维护一个队列,用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-K会淘汰第K次访问时间距当前时间最大的数据。详细实现如下:

    • 数据第一次被访问,加入到访问历史列表;
    • 如果数据在访问历史列表里后没有达到K次访问,则按照一定规则(FIFO,LRU)淘汰;
    • 当访问历史队列中的数据访问次数达到K次后,将数据索引从历史队列删除,将数据移到缓存队列中,并缓存此数据,缓存队列重新按照时间排序;
    • 缓存数据队列中被再次访问后,重新排序;
    • 需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第K次访问离现在最久”的数据。

LRU-K具有LRU的优点,同时能够避免LRU的缺点,实际应用中LRU-2是综合各种因素后最优的选择,LRU-3或者更大的K值命中率会高,但适应性差,需要大量的数据访问才能将历史访问记录清除掉。

  • 命中率:LRU-K降低了“缓存污染”带来的问题,命中率比LRU要高。

  • 复杂度:LRU-K队列是一个优先级队列,算法复杂度和代价比较高。

  • 代价:由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象,因此内存消耗会比LRU要多;当数据量很大的时候,内存消耗会比较可观。

LRU-K需要基于时间进行排序(可以需要淘汰时再排序,也可以即时排序),CPU消耗比LRU要高。

参考:

  1. 缓存那些事–什么是缓存,为什么要用缓存
  2. 缓存那些事–缓存中常见的问题
  3. 缓存那些事–分布式缓存
  4. 缓存、缓存算法和缓存框架简介
  5. 缓存淘汰算法–LRU算法
  6. 缓存那些事–常用的缓存失效策略