缓存穿透解决方案-布隆过滤器

@[toc]

1. 什么是布隆过滤器

布隆过滤器（Bloom Filter）是一个叫做Bloom 于1970年提出的。我们可以把它看做由二进制向量（或者说位数组）和一系列随机映射函数（哈希函数）两部分组成的数据结构。相比于我们平时用的 List 、Map 、Set 等数据结构，它占用看见更少并且效率更高。但是缺点是其返回的结果是概率性的，而不是非常准确的。理论情况下添加到集合中的元素越多，误报的可能性就越大，并且，存放在布隆过滤器的数据不易删除。

在这里插入图片描述

位数组中的每个元素都只占用 1 bit , 并且每个元素只能是0 或 1 。这样申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000 / 10214 kb ≈ 122kb 的空间

2. 布隆过滤器使用场景

1. 防止缓存穿透：用户查询一个数据导致缓存于数据库都未命中, 这就相当于缓存穿透， 布隆过滤器（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等
2. 去重：爬虫我们爬取的url千万，如何判断这个 url 我们是否爬过
3. 邮箱过滤：判断是否为垃圾邮件

3. 布隆过滤器原理介绍

添加元素

当一个元素加入布隆过滤器中的时候：

1. 使用布隆过滤器的哈希函数再次进行相同的 hash 计算，算出一个值
2. 得到值之后判断位数组中每个元素是否都为1，如果值都为1，那么说明这个值在布隆过滤器中，如果存在一个值不为1，说明该元素不在布隆过滤器中

在这里插入图片描述

如图所示，当字符串要加入布隆过滤器中时，计算 hash(key) 值，然后将其对应的位数组的下表设置为1 （当数组初始化时，所有位置均为0）

获取元素

布隆过滤器中如果判断某个字符串是否在布隆过滤器中时，只需要对该 hash 值重新计算，得到值之后判断位数中的每个元素是否都为1，如果为1，说明这个值在布隆过滤器中，如果值不为1，该元素不在布隆过滤器中

在这里插入图片描述

不同的字符串可能哈希出来的位置相同，这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。

4. Java手写布隆过滤器

1. 实现初始化的数组保存数据
2. 计算 hash 值
3. 添加到布隆过滤器数组
4. 判断元素是否存在

public class BloomFileter {

    /**
     * 初始化大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;

    /**
     * 位数组。数组中到元素只能是 0 和 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);


    /**
     * 计算hash值
     * @param key
     * @return
     */
    static final int hash(Object key) {
        int h;
        return (key == null) 0 : Math.abs((h = key.hashCode()) ^ (h >>> 16));
    }


    public BloomFileter(){
    }

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
            bits.set(hash(value), true);
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        return bits.get(hash(value));
    }



}

测试

public static void main(String[] args) {
        String value1 = "https://javaguide.cn/";
        String value2 = "https://github.com/Snailclimb";
        BloomFileter filter = new BloomFileter();
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));
        filter.add(value1);
        filter.add(value2);
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));
    }

false
false
true
true

5. 利用Google开源的Guava中自带的布隆过滤器

Guava 中布隆过滤器的实现算是比较权威的

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.0-jre</version>
</dependency>

public class GuavaBloomFilter {
    public static void main(String[] args) {
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);
       // 判断指定元素是否存在
       System.out.println(filter.mightContain(1));
       System.out.println(filter.mightContain(2));
       // 将元素添加进布隆过滤器
       filter.put(1);
       filter.put(2);
       System.out.println(filter.mightContain(1));
       System.out.println(filter.mightContain(2));
    }
}

6. Redis中的布隆过滤器

我们知道计算机是以二进制作为底层存储到基础单位，一个字节等于8位在 Redis 中，Bitmaps 提供了一套命令操作类似上面字符串的每一位

setbit :

在这里插入图片描述

getbit :

在这里插入图片描述

bitcount

在这里插入图片描述

Redisson:

public class RedissonBloomFilter {

    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://192.168.14.104:6379");
        config.useSingleServer().setPassword("123");
        //构造Redisson
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
        //初始化布隆过滤器：预计元素为100000000L,误差率为3%
        bloomFilter.tryInit(100000000L,0.03);
        //将号码10086插入到布隆过滤器中
        bloomFilter.add("10086");

        //判断下面号码是否在布隆过滤器中
        System.out.println(bloomFilter.contains("123456"));//false
        System.out.println(bloomFilter.contains("10086"));//true
    }
}

个人博客地址：http://blog.yanxiaolong.cn ｜ <font color = "orange"> 『纵有疾风起，人生不言弃』 </font>