布隆过滤器及缓存相关问题

本文主要是介绍布隆过滤器及缓存相关问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

（一）布隆过滤器

布隆过滤器（英语，Bloom Filter）是1970年由布隆提出的。它实际是一个很长的二进制数组+多个随机Hash算法映射函数，主要用于判断一个元素是否在集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，HashTable）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会线性增长，最终达到瓶颈。同时检索越来越慢，上述三种结构的检索时间复杂度分别为O(n), O(logn)，O(1).这个时候，布隆过滤器应运而生。

布隆过滤器的特点：

1 高效地插入与查询，占用空间少，返回的结果是不确定性的。

2 一个元素如果判断为存在的时候不一定存在，但是如果判断为不存在时则一定不存在。

3 布隆过滤器可以添加元素，但是不能删除元素。因为删除元素会导致误判率增加。

4 误判只会发生在过滤器没有添加过的元素，对于添加过的元素不会发生误判。

布隆过滤器主要解决缓存穿透的问题：

缓存穿透：一般情况下，先查询redis是否有该条数据，缓存中没有时再查询数据库。当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透。

带来的问题：当有大量请求查询数据不存在时，就会给数据库带来压力，甚至会拖垮数据库。

可以使用布隆过滤器解决缓存穿透的问题：把已经存在的数据的key存在布隆过滤器中，相当于redis前面挡着一个布隆过滤器。

当有新的请求时，先到布隆过滤器中查询是否存在。如果布隆过滤器中不存在该条数据则直接返回。如果布隆过滤器中存在（可能存在），才去查询redis，如果redis没有查询到则穿透到数据库。因此对于不存在的直接过滤，对于可能存在的，只有极小一部分会因为误判穿透到数据库。如果要穿透，要求非常严格，即这个key经过多个Hash后都有冲突。

布隆过滤器的原理：

Java中传统hash 容易出现hash冲突。

布隆过滤器实质是一个大型为数组和几个不同的无偏(分布均匀)的hash函数。

添加key值时，使用多个hash函数对key进行hash运算得到一个整数索引值，对为数组长度进行取模运算得到一个位置。

每个hash函数会的带一个不同的位置，将这几个位置置1就完成了add操作。

查询key时，只要其中一位是0就表示这个key不存在，但如果都是1，则不一定存在对应的Key.

 当有变量被加入集合时，通过N个映射函数将这个变量映射成位图中的N个点。把他们位置置为1（假定有两个变量都通过3个映射函数）

在查询某个变量的时候我们只要看看这些点是不是都是1，即可大概率知道集合中有没有这个变量了。

同时，我们布隆过滤器可以添加元素，但是不能删除元素。因为删除元素会导致误判率增加。比如图中，我们将obj1删除，则位置1 3 12都会变为0，但是Obj2共有位置3，这个时候查询obj2时发现位置3的值为0，就会判定不存在obj2，就会造成误判。

（二）缓存问题

2.1 缓存雪崩：

发生场景：1 redis主机挂了，Redis全盘崩溃。 2 比如缓存中有大量数据同时过期。3 内存达到阙值，内存淘汰机制删除了一些数据。

解决办法：

 redis缓存集群实现高可用 主从+ 哨兵。 redis cluster 

emcache 本地缓存 + Hystrix 或者阿里sentinel限流 + 降级

开启redis持久化机制aof/rdb, 尽快恢复缓存集群。

2.2 缓存穿透：

请求去查询一条记录，先redis然后mysql发现都查询不到该条记录，但是请求每次都会到数据库查询，导致后台数据库压力暴增，这种现象我们称为缓存穿透，如此redis几乎成为了摆设。

数据库没有，redis也没有。直接绕过了redis.

危害：第一次来查询后，如果我们有回写机制，第二次来查的时候就有了，偶尔出现穿透现象无关紧要。如果没有回写，下次继续穿透。

解决方案：

方案1 ：一旦发生缓存穿透，我么就可以针对查询的数据，在redis中缓存一个空值或是和业务层协商确定的缺省值。紧接着，应用发送的后续请求再进行查询时，就可以直接从redis中读取空值或者缺省值，返回给业务应用了。避免了把大量请求发送给数据库处理，保持了数据库的正常运行。这种方法可以杜绝相同key的反复请求。针对于大量不同的key，还是存在缓存穿透的问题。

方案2：google guava解决缓存穿透 

 以上场景为布隆过滤器做白名单使用：白名单里有的才让通过，没有直接返回，但是存在误判由于误判率很小，mysql可以接受。使用时需注: 所有key需要往redis和布隆过滤器里面放入。

布隆过滤器做黑名单使用：

2.3 缓存击穿：

大量的请求同时请求一个key时，此时这个key正好失效了，就会导致大量的请求都打到数据库。简单来说就是热点key突然失效了，暴打mysql.   可能布隆过滤器存在，但是此时redis的key突然失效.

数据库有，redis之前有，但是突然没有。

危害：会造成某一时刻，数据库的访问点突然暴增。

解决方法：

互斥更新，随机退避，差异化失效时间。

1 新建 

开辟两块内存，主A从B，先更新B，在更新A，严格按照这个顺序

2 查询

先查询主缓存A，如果A没有（消失或者失效）再查询从缓存B。

从B先删除，然后从数据库加载，时间设置20天。

主A后删除，然后从数据加载，时间设置15天。 

如果主A到期，但是从B还存在。

对于频繁访问的key，干脆就不设置过期时间

互斥独占锁防止击穿 （多个线程同时去查询这条数据，在第一个查询的请求上使用一个互斥锁来锁住它，其它线程只有等到第一个线程查询到数据，然后缓存。后面的线程进来后发现已经有缓存 了，就直接走缓存）

public User findUserById(Integer id)
{
    User user = null;
    String key = "user:"+id;

    //1 先从redis里面查询，如果有直接返回结果，如果没有再去查询mysql
    user = (User) redisTemplate.opsForValue().get(key);
    if(user != null){
        return user;
    }

    if(user == null)
    {
        //2 对于高QPS的优化，进来就先加锁，保证一个请求操作，让外面的redis等待一下，避免击穿mysql
        synchronized (UserService.class){
        //这里让之前在外面等待的线程随后进来后可以直接走缓存，前提是前面有线程回写。
            user = (User) redisTemplate.opsForValue().get(key);
            //3 二次查redis还是null，可以去查mysql了(mysql默认有数据),
            if (user == null) {
                //4 查询mysql拿数据
                user = userMapper.selectByPrimaryKey(id);//mysql有数据默认
               //5 mysql里面有数据的，需要回写redis，完成数据一致性的同步工作
                redisTemplate.opsForValue().setIfAbsent(key,user,7L,TimeUnit.DAYS);
                return user;
                }
            }
        }
    }
    
}

这篇关于布隆过滤器及缓存相关问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！