缓存穿透和缓存击穿

一、背景介绍

几乎所有互联网公司都采用缓存的方案来解决瞬时流量超高，或者长期流量过高的问题。但使用缓存存在风险——缓存穿透和缓存击穿：简单的讲就是如果该数据原本就不存在，那么就会发生缓存穿透；如果缓存内容因为各种原因失效，那么就会发生缓存击穿。
具体一点来说，如果缓存中不存在需要查询的内容，一般情况下需要再深入一层进行查询，一般为不能承受压力的关系型数据库（承压能力为缓存的1%，甚至更低），如果数据库中不存在，则叫做缓存穿透；反之，如果数据库中存在这个数据，则叫做缓存击穿（如果同一时刻大量的缓存失效叫做缓存雪崩，本文暂不讨论该问题）。这种查询在流量不高的情况下，不会出现问题，如果查询数据库的流量过高，尤其是数据库中不存在的情况下，严重时会导致数据库不可用，连带影响使用数据库的其他业务，本业务也有很大的可能性受到影响。

二、缓存穿透常见的处理方式

2.1 空值缓存

既然该数据本身就不存在，最简单粗暴的方式就是直接将不存在的值定义为空（视具体业务和缓存的方式定义为null或者””）。具体方式是每次查询完数据库，我们可以将key在缓存中设置对应的值为空，短期内再次查询这个key的时候就不用查询数据库了。
通常的简单做法：
在这里插入图片描述
这里需要强调注意：为了系统的最终一致性，这些key必须设置过期时间，或者必须存在更新方式，防止这个key的数据后期真实存在，但改key始终为空，导致数据不一致的情况出现。
这种方式的缺点也十分的明显：如果key数量巨大且分散无任何规律，就会浪费大量缓存空间，并且不能抗住瞬时流量冲击（尤其是遇到恶意的攻击的时候，有可能将缓存空间打爆，影响范围更大），需要额外配置降级开关（查询数据库的开关或者限流），这时本方案就显得没想象的那么美好。针对不能抗住瞬时流量的情况，常见的处理方式是使用计数器，对不存在的key进行计数，当某个key在一定时间达到一定的量级，就查询一次数据库，按照数据库的返回值对key进行缓存。未达指定阈值数量之前，按照商定的空值返回。

故这种解决方案的建议使用场景为：key全集数据数据量级较小，并且完全可预测，可以通过提前填充的方式直接将数据缓存。

2.2 布隆过滤器（BloomFilter）

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。实际应用中，Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。

布隆过滤器的原理如下：
在这里插入图片描述
假如“京东”经过hash后占位为618，加入后，如下所示：

假如大促经过hash后占位为为678，加入后，如下所示：

假如某宝hash后占位256，则可以完全判断该key不存在，直接返回null即可。但某某多hash后占位167，则不能判断是否存在，需要进行查库操作进行判断。

这里需要强调注意的是必须使用高效的hash算法，否则这种方式会严重影响系统的性能，建议的算法包括MurmurHash、Fnv的稳定高效的算法。

使用过程中，通常把有数据的key都放到BloomFilter中，每次查询的时候都先去BloomFilter判断，如果没有就直接返回空。由于布隆过滤器不支持删除操作（具体结合上图推算删除一个就可以得知），对于删除的key，查询就会经过BloomFilter然后查询缓存再查询数据库，所以BloomFilter建议结合缓存空值用，对于删除的key，可以在缓存中缓存空。（当然有同学自行实现了可删除的布隆过滤器——Counting Bloom Filter，原理较为简单，本文不做具体分析，个人感觉将简单的问题复杂化了）。

同样它也不支持扩容操作，这就要求布隆过滤器建立初期必须进行严格的推算，确保后期不需要扩容，否则重建布隆过滤器的成本可能会超乎想象。具体的推算公式如下（具体的推算过程非本文重点，请各位自行查找）：
在这里插入图片描述
k 为哈希函数的个数，m 为布隆过滤器的长度，n 为插入元素的个数（需要处理的数据个数），p 为误报率。
布隆过滤器的使用场景受key的状态限制，如果key是动态无规律的，不建议使用该方式。作者使用布隆过滤器作为用户是否参与活动的过滤，布隆过滤器在活动期间最大值为目前的会员数量，完全可控。考虑真实情况下，缓存的存储空间及性能问题，在真实使用中，为了避免热key和大key的问题，首先对用户标识进行了Hash，首先对hash按照布隆过滤器的数量进行取余，确定使用哪个布隆过滤器，然后使用布隆过滤器。具体情况如下：
在这里插入图片描述

三、缓存击穿常见的处理方式

3.1 互斥锁（mutex key）

这是比较常见的做法，是在缓存失效的时候，不是立即去查询数据库，先抢互斥锁（比如Redis的SETNX一个mutex key），当操作返回成功时（即获取到互斥锁），再进行查询数据库的操作并回设缓存；否则，就重试整个获取缓存的方法或者直接返回空。SETNX，官方的解释是只在键 key 不存在的情况下，将键 key 的值设置为 value 。若键 key 已经存在，则 SETNX 命令不做任何动作。SETNX 是『SET if Not eXists』（如果不存在，则SET）的简写。
但这种方式显然存在问题，Redis的SETNX命令是当key不存在时设置key，但SETNX不能同时完成EXPIRE设置失效时长，不能保证SETNX和EXPIRE的原子性。这会导致SETNX成功但EXPIRE失败时，锁永远不会释放，下面提供了一种可行的代码，供大家讨论：

try {Boolean snx =redisClient.setNX(redisKey, value);if (snx && timeout>0){boolean flag = redisClient.expire(redisKey, timeout, unit);if (!flag){redisClient.del(redisKey);}return flag;}
} catch (Exception e) {LOG.error("setnx: key="+redisKey ,e);
}
return false;

Redis还是善解人意的，从 2.6.12 起，我们可以使用SET命令完成SETNX和EXPIRE的操作，并且这种操作是原子操作，可以完全替代上述的代码了。

这种简单粗暴的方式有着严格是使用场景（换句话说就是有着严重的缺陷），如果缓存大量失效（缓存雪崩），那么对于数据库是一场灾难；如果数据库查询缓慢，不仅对数据是一场灾难，对于使用该缓存的接口会造成线程阻塞，接口性能又开启了另外一场灾难！一般情况下，这种方式适用于永久缓存的key，或者key偶尔丢失的情况下，其他情况请各位读者慎重考虑或增加其他机制保护数据库和接口（如使用Hystrix限流&降级等）。

3.2 异步构建缓存

当缓存失效时，不是立刻去查询数据库，而是先创建缓存更新的异步任务，然后直接返回空值。这种做法不会阻塞当前线程，并且对于数据库的压力基本可控，但牺牲了整体数据的一致性。从实际的使用看，这种方法对于性能非常友好，唯一不足的就是构建缓存时候，所有查询返回的内容均为空值，但是对于一致性要求不高的互联网功能来说这个还是可以忍受。
在这里插入图片描述