在低缓存命中率的系统中，大量查询商品信息的请求会穿透缓存到数据库，因为数据库对于并发的承受能力是比较脆弱的。一旦数据库承受不了用户大量刷新商品页面、定向搜索衣服信息，查询就会变慢，大量的请求也会阻塞在数据库查询上，造成应用服务器的拦截和线程资源被占满，最终导致整个系统崩溃。
一般来说，我们的核心缓存命中率要保持在99%以上，非核心缓存的命中率也要尽量保证90%以上，如果低于这个标准你可能就需要优化缓存的使用方式了。
那么我们该如何减少它的发生呢？接下来我们学习面对缓存穿透时，我们有哪些应对措施。
什么事缓存穿透
缓存穿透就是指从缓存中没有查到数据，而不得不从后端系统(如DB)中查询的情况。不过少量的缓存穿透不可避免，对系统也没有损害。
既然缓存的容量有限，并且大部分的访问只会请求20%的热点数据，那么理论上说，我们只需要在有限的缓存空间里存储20%的热点数据就可以有效的保护脆弱的后端系统了，也就可以放弃缓存另外80%的非热点数据了。所以这种少狼的缓存穿透时不可避免且没有损害的。
大量的穿透请求超过了后端的承受范围造成了后端系统的崩溃的缓存穿透是对系统有害的。
缓存穿透的解决方案
场景：在电商系统的用户表中，我们需要通过用户id查询用户的信息，缓存的读写策略采用cache aside策略。
那么如果要读取一个用户表中未注册的用户，会发生什么？按照这个策略，我们会先读缓存再穿透读DB。由于用户并不存在，所以缓存和数据库中都没有查询到数据。因此也就不会向缓存中回种数据。这样当再次请求这个用户数据的时候还是会再次穿透到数据库，在这种场景下缓存不能有效的阻挡请求穿透，它的作用就微乎其微了。
如何解决穿透呢？回种空值以及使用布隆过滤器。
1.回种空值
回顾上面的场景你会发现最大的问题在于DB中并不存在用户的数据，这就造成无论查询多少次，DB中永远不会存在这个用户的数据，穿透永远都会发生。
类似的场景还有：比如由于代码的bug导致查询数据库的时候抛出了异常，这样可以认为从DB查询出来的数据为空，同样不会回种缓存。
那么当我们从DB中查询到空值或者发生异常时，我们就可以向缓存中回种一个空值。但是因为控制不是准确的业务数据，并且会占用缓存的空间，所以我们会给这个空值加一个比较短的过期时间，让空值在短时间之内能够快速过期淘汰。下图是伪代码：
Object nullValue = new Object();
try {
Object valueFromDB = getFromDB(uid); //从数据库中查询数据
if (valueFromDB == null) {
cache.set(uid, nullValue, 10); //如果从数据库中查询到空值，就把空值写入缓存，设置较短的超时时间
} else {
cache.set(uid, valueFromDB, 1000);
}
} catch(Exception e) {
cache.set(uid, nullValue, 10);
}
回种空值虽然能够阻挡大量穿透的请求，但如果有大量获取未注册用户信息的请求，缓存内就会有大量的空值缓存，也就会浪费缓存的存储空间，如果缓存空间被占满了，还会剔除掉一些已经被缓存的用户信息，反而会造成缓存命中率的下降。
这个方案在使用之前应该评估一下 缓存容量是否能够支撑。如果需要大量的缓存节点来支持，那么就无法通过回种空值的方式来解决，这时可以考虑布隆过滤器。
使用布隆过滤器
1970年布隆提出了一种布隆过滤器的算法，用来判断一个元素是否在一个集合中。这种算法由一个二进制数据和一个hash算法组成，基本算法如下：
我们把集合中的每一个值按照提供的hash算法算出对应的hash值，然后将hash值对数组长度取模后，得到需要计入数组的索引值，并且将数组这个位置的值从0改为1，在判断一个元素是否存在于这个集合中时，你只需要将这个元素按照相同的算法计算出索引值，如果这个位置的值为1，就认为这个元素在集合中，否则不在集合中。
image.png
ABC等元素组成了一个集合，元素D计算出的hash值对应的数组中的值是1，所以可以认为D也在集合中，而F在数组中的值是0，所以F不在数组中。
如何利用布隆过滤器来解决缓存穿透的问题？
以存储用户信息的表为例，首先我们初始化一个很大的数组。比如说长度为20亿的数组，接下来我们选择一哥hash算法，然后我们将现有的所有用户的ID计算出Hash值并且映射到这个大数组只中，映射位置的值设为1，其他值设置为0。
新注册的用户除了需要写入到DB中之外，也需要依照同样的算法更新布隆过滤器的数组中相应位置的值。
那么当我们需要查询某一个用户的信息，先查询在这个ID在布隆过滤器中是否存在，如果不存在就直接返回空值，而不需要继续查询DB和缓存，这样就极大地减少异常查询带来的缓存穿透。
image.png
布隆过滤器性能极高，无论是写入还是读取操作，时间复杂度都是O(1)。在空间上，相对于其他数据结构它也有很大的优势，比如20亿的数组需要2000000000/8/1024/1024 = 238M的空间，而如果用数组来存储，假设每个用户id斗殴善用4个字节的空间，那么存储20亿用户需要7600M的空间，是布隆过滤器的32倍。
布隆过滤器有两个缺陷：
1.它在判断元素是否在集中时是有一定错误几率的，比如它会把不是集合中的元素判断为处在集合中；
2.不支持删除元素。
第一个缺陷主要是hash算法的问题。因为布隆过滤器是由一个二进制数组和一个hash算法组成的，hash算法存在着一定的碰撞几率。(不同的输入值经过hash运算后得到了相同的hash结果)。
本来**hash的含义是不同的输入一句不同的算法映射成独一无二的固定长度的值，。但是现实中hash短发的输入值是无限的，输出值的值空间确实固定的，比如16位的hash值的空间是65535，那么它碰撞的几率是1/65535，即如果时输入值的个数超过65535就一定会发生碰撞。
为什么不映射成更长的hash值呢？
因为更长的hash值会带来更高的存储成本和计算成本。即使使用32位的hash算法，它的值空间长度是2^32-1，约等于42亿，用来映射20亿的用户数据，碰撞几率依然有接近50%。
hash碰撞造成了两个用户id，A和B会计算出相同的hash值，那么如果A是注册用户，它的hash值对应的数组中的值是1，那么B即使不是注册用户，它在数组中的位置和A是相同的，这就产生了误判。
布隆过滤器有一个特点，就是它只会出现“false positive”的情况。就是当布隆过滤器判断元素在集合中时，这个元素可能不在集合中。但是一旦布隆过滤器判断这个元素不在集合中时，它一定不在集合中。这一点非常适合解决缓存穿透的问题：
如果布隆过滤器会将集合中的元素判定为不在集合中，那么我们就不确定该元素是不是在集合中。假设刚才的场景中，如果有大量查询未注册的用户信息的请求存在，那么这些请求到达布隆过滤器后，即使判断为不是注册用户，那么我们也不确定它是不是真的非注册用户，那么还是需要去DB和缓存中查询，这就使过滤器失去了价值。
布隆过滤器虽然存在误判的情况，但还是会减少缓存穿透的情况，只是我们需要尽量减少误判的几率，这样布隆过滤器的判断正确的几率更高，对缓存的穿透也更少。
一个解决方案是：
使用多个Hash算法为元素计算出多个hash值，只有所有的hash值对应的数组中的值都为1时，才会认为这个元素在集合中。
布隆过滤器不支持删除元素的缺陷也和hash碰撞有关。
举例：假如两个元素A和B都是集合中的元素，它们有相同的hash值，它们就会映射到数组的同一个位置。这时我们删除了A，数组中对应位置的值也从1变为0，那么在判断B的时候发现值是0，也会判断B是不是在集合中的，得到错误的结论。
如何解决这个问题？可以让数组中不再只有0和1两个值，而是存储一个计数。比如，如果A和B同时命中了一个数组的索引，那么这个位置的值就是2，如果A被删除了就把这个值从2改为1,。这个方案中的数组不再存储bit位，而是存储数值，也就会增加空间的消耗。所以要一句业务场景来选择是否能够使用布隆过滤器。比如注册用户的场景下，因为用户删除的情况基本不存在，所以还是可以使用布隆过滤器来解决缓存穿透的问题的。
布隆过滤器的使用建议：
1.选择多个Hash函数计算多个Hash值，这样可以减少误判的几率；
2.布隆过滤器会消耗一定的内存空间，所以在使用时需要评估业务场景下需要多大的内存，存储成本是否可以接受。
总的来说，回种空值和布隆过滤器是解决缓存穿透问题的两种最主要的解决方案，但是它们也有各自的适用场景，并不能解决所有问题。比如说当有一个极热点的缓存项，它一旦失效就会有大量的请求穿透到DB，这会对DB造成瞬时极大的压力，我们把这个场景叫做“狗桩效应”。
这是典型的缓存并发穿 穿透的问题，如何解决？思路是尽量的减少缓存穿透后的并发。
1.在代码中控制在某一个热点缓存项失效之后启动一个后台进程，穿透到DB，将数据加载到缓存中，在缓存未加载之前，所有访问这个缓存的请求都不再穿透而直接返回。
2.通过Memcached或者redis中设置分布式锁，只有获取到锁的请求才能穿透到DB。
分布式锁的方式也比较简单，比如说ID为1的用户是一个热点用户，当他的用户信息缓存失败后，我们需要从数据库中重新加载数据时，先向Memcached中写入一个key为“lock.1”的缓存项，然后去DB里面加载数据，当数据加载完成后再把这个key删掉。这时，如果另外一个线程也要请求这个用户的数据，它发现缓存中有key为“lock.1”的缓存，就认为目前已经有线程在加载DB中的值到缓存中了，它就可以重新去缓存中查询数据，不再穿透DB了。
总结
了解一些解决缓存穿透的方案，你可以在发现自己的缓存系统命中率下降的时从中得到一些借鉴的思路，需要明确的重点是：
1.回种空值是一种最常见的解决思路，实现起来最简单，如果评估空值缓存占据的缓存空间可以接受，那么可以有限使用这种方案；
2.布隆过滤器会引入一个新的组件，也会引入一些开发上的复杂度和运维上的成本。所以只有在存在海量查询DB中，不存在数据的请求时才会使用，在使用时也要关注布隆过滤器对内存空间的消耗；
3.对于极热点缓存数据穿透造成的狗桩效应，可以通过设置分布式锁或者后台线程定时加载的方式来解决。
除此之外，还需要了解DB是一个脆弱的资源，无论是在扩展性，性能还是在承担并发能力上，相比缓存都处于绝对的劣势，所以我们解决缓存穿透问题的核心目标在于减少对于DB的并发请求。了解了这个核心思想，也许你还会在日常工作中找到其他更好的解决缓存穿透问题的方案。
网友评论