/hjm4702192/article/details/80518952

/wang0112233/article/details/79558612

从缓存中加载数据的逻辑，如下图所示

缓存击穿：

查询一个数据库中不存在的数据，比如商品详情，查询一个不存在的ID，每次都会访问DB，如果有人恶意破坏，很可能直接对DB造成过大地压力。

由于缓存不命中，每次都要查询持久层。从而失去缓存的意义。如果在大流量下数据库可能挂掉。这就是缓存击穿。

场景如下图所示:

解决方案

1、缓存层缓存空值。

当通过某一个key去查询数据的时候，如果对应在数据库中的数据都不存在，我们将此key对应的value设置为一个默认的值，比如“NULL”，并设置一个缓存的失效时间，这时在缓存失效之前，所有通过此key的访问都被缓存挡住了。后面如果此key对应的数据在DB中存在时，缓存失效之后，通过此key再去访问数据，就能拿到新的value了。

–缓存太多空值，占用更多空间。（优化：给个空值过期时间）

–存储层更新代码了，缓存层还是空值。（优化：后台设置时主动删除空值，并缓存把值进去）

2、使用互斥锁

该方法是比较普遍的做法，即，在根据key获得的value值为空时，先锁上，再从数据库加载，加载完毕，释放锁。若其他线程发现获取锁失败，则睡眠50ms后重试。

集群环境的redis的代码如下所示:

Stringget(Stringkey){Stringvalue=redis.get(key);if(value==null){if(redis.setnx(key_mutex,"1")){// 3 min timeout to avoid mutex holder crashredis.expire(key_mutex,3*60)value=db.get(key);redis.set(key,value);redis.delete(key_mutex);}else{//其他线程休息50毫秒后重试Thread.sleep(50);get(key);}

public String getWithLock(String key, Jedis jedis, String lockKey, String uniqueId, long expireTime) {// 通过key获取valueString value = redisService.get(key);if (StringUtil.isEmpty(value)) {// 分布式锁，详细可以参考/fanrenxiang/article/details/79803037//封装的tryDistributedLock包括setnx和expire两个功能，在低版本的redis中不支持try {boolean locked = redisService.tryDistributedLock(jedis, lockKey, uniqueId, expireTime);if (locked) {value = userService.getById(key);redisService.set(key, value);redisService.del(lockKey);return value;} else {// 其它线程进来了没获取到锁便等待50ms后重试Thread.sleep(50);getWithLock(key, jedis, lockKey, uniqueId, expireTime);}} catch (Exception e) {log.error("getWithLock exception=" + e);return value;} finally {redisService.releaseDistributedLock(jedis, lockKey, uniqueId);}}return value;}

这样做思路比较清晰，也从一定程度上减轻数据库压力，但是锁机制使得逻辑的复杂度增加，吞吐量也降低了，有点治标不治本。

优点

思路简单

保证一致性

缺点

代码复杂度增大

存在死锁的风险

方案3、布隆过滤器

将数据库中所有的查询条件，放到布隆过滤器中。当一个查询请求来临的时候，先经过布隆过滤器进行检查，如果请求存在这个条件中，那么继续执行，如果不在，直接丢弃。

bloomfilter就类似于一个hash set，用于快速判某个元素是否存在于集合中，其典型的应用场景就是快速判断一个key是否存在于某容器，不存在就直接返回。布隆过滤器的关键就在于hash算法和容器大小

比如数据库中有10000个条件，那么布隆过滤器的容量size设置的要稍微比10000大一些，比如12000.

对于误判率的设置，根据实际项目，以及硬件设施来具体决定。但是一定不能设置为0，并且误判率设置的越小，哈希函数跟数组长度都会更多跟更长，那么对硬件，内存中间的要求就会相应的高。

private staticBloomFilter<Integer>bloomFilter=BloomFilter.create(Funnels.integerFunnel(),size,0.0001);

有了size跟误判率，那么布隆过滤器就会产生相应的哈希函数跟数组。

原文：/yinjing8435/article/details/70537046

如何判断一个元素是否存在一个集合中？

数组链表树、平衡二叉树、TrieMap (红黑树)哈希表

这几种数据结构配合常见的排序、二分搜索可以快速高效的处理绝大部分判断元素是否存在集合中的需求。但是当集合里面的元素数量足够大，如果有500万条记录甚至1亿条记录呢？这个时候常规的数据结构的问题就凸显出来了。数组、链表、树等数据结构会存储元素的内容，一旦数据量过大，消耗的内存也会呈现线性增长，最终达到瓶颈。

哈希表不是效率很高吗？查询效率可以达到O(1)。但是哈希表需要消耗的内存依然很高。使用哈希表存储一亿 个垃圾 email 地址的消耗？哈希表的做法：首先，哈希函数将一个email地址映射成8字节信息指纹；考虑到哈希表存储效率通常小于50%（哈希冲突）；因此消耗的内存：8 * 2 * 1亿 字节 = 1.6G 内存，普通计算机是无法提供如此大的内存。

这个时候，布隆过滤器（Bloom Filter）就应运而生

布隆过滤器原理

布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k

以上图为例，具体的操作流程：假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。

首先将位数组进行初始化，将里面每个位都设置位0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。

public class BloomFilterTest {private static final int capacity = 1000000;private static final int key = 999998;private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), capacity);static {for (int i = 0; i < capacity; i++) {bloomFilter.put(i);}}public static void main(String[] args) {/*返回计算机最精确的时间，单位微妙*/long start = System.nanoTime();if (bloomFilter.mightContain(key)) {System.out.println("成功过滤到" + key);}long end = System.nanoTime();System.out.println("布隆过滤器消耗时间:" + (end - start));int sum = 0;for (int i = capacity + 20000; i < capacity + 30000; i++) {if (bloomFilter.mightContain(i)) {sum = sum + 1;}}System.out.println("错判率为:" + sum);}成功过滤到999998布隆过滤器消耗时间:215518错判率为:318100w个数据中只消耗了约0.2毫秒就匹配到了key，速度足够快。然后模拟了1w个不存在于布隆过滤器中的key，匹配错误率为318/10000，也就是说，出错率大概为3%

布隆过滤器的巨大用处就是，能够迅速判断一个元素是否在一个集合中。因此他有如下三个使用场景:

网页爬虫对URL的去重，避免爬取相同的URL地址

反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）

缓存击穿，将已存在的缓存放到布隆过滤器中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

缓存雪崩

缓存在同一时间内大量键过期（失效），接着来的一大波请求瞬间都落在了数据库中导致连接异常。

如果缓存集中在一段时间内失效，发生大量的缓存穿透，所有的查询都落在数据库上，造成了缓存雪崩。

缓存层宕掉后，流量会像奔逃的野牛一样，打向后端存储

解决方案：

在缓存失效后，通过加锁或者队列来控制读数据库写缓存的线程数量。比如对某个key只允许一个线程查询数据和写缓存，其他线程等待。不同的key，设置不同的过期时间，让缓存失效的时间点尽量均匀，设置缓存超时时间的时候加上一个随机的时间长度，比如这个缓存key的超时时间是固定的5分钟加上随机的2分钟做二级缓存，或者双缓存策略。A1为原始缓存，A2为拷贝缓存，A1失效时，可以访问A2，A1缓存失效时间设置为短期，A2设置为长期。

热点key

(1) 这个key是一个热点key（例如一个重要的新闻，一个热门的八卦新闻等等），所以这种key访问量可能非常大。

(2) 缓存的构建是需要一定时间的。（可能是一个复杂计算，例如复杂的sql、多次IO、多个依赖(各种接口)等等）

于是就会出现一个致命问题：在缓存失效的瞬间，有大量线程来构建缓存，造成后端负载加大，甚至可能会让系统崩溃。

解决方法：

1. 使用互斥锁(mutex key):这种解决方案思路比较简单，就是只让一个线程构建缓存，其他线程等待构建缓存的线程执行完，重新从缓存获取数据就可以了

2. "提前"使用互斥锁(mutex key)：在value内部设置1个超时值(timeout1), timeout1比实际的memcache timeout(timeout2)小。当从cache读取到timeout1发现它已经过期时候，马上延长timeout1并重新设置到cache。然后再从数据库加载数据并设置到cache中。

3. "永远不过期"：

这里的“永远不过期”包含两层意思：

(1) 从redis上看，确实没有设置过期时间，这就保证了，不会出现热点key过期问题，也就是“物理”不过期。

(2) 从功能上看，如果不过期，那不就成静态的了吗？所以我们把过期时间存在key对应的value里，如果发现要过期了，通过一个后台的异步线程进行缓存的构建，也就是“逻辑”过期

4. 资源保护：可以做资源的隔离保护主线程池，如果把这个应用到缓存的构建也未尝不可。

四种方案对比：

作为一个并发量较大的互联网应用，我们的目标有3个:

1. 加快用户访问速度，提高用户体验。

2. 降低后端负载，保证系统平稳。

3. 保证数据“尽可能”及时更新(要不要完全一致，取决于业务，而不是技术。)

所以第二节中提到的四种方法，可以做如下比较，还是那就话：没有最好，只有最合适。

总结

1. 热点key + 过期时间 + 复杂的构建缓存过程 => mutex key问题

2.构建缓存一个线程做就可以了。

3. 四种解决方案：没有最佳只有最合适。