布隆过滤器

布隆过滤器

1.什么是布隆过滤器

布隆过滤起是1970年由布隆提出来的,它实际上是一个很长的二进制数组+一系列随机hash算法映射函数,主要用于判断一个元素是否在集合中.

总结:由一个初值都为零的bit数组和多个哈希函数构成,用来快速判断某个数据是否存在

2.特点

• 高效地插入和查询,占用空间少,返回的结果是不确定性的.
• 一个元素如果判断结果为存在的时候元素不一定存在,但是判断结果为不存在的时候则一定不存在.
• 布隆过滤器可以添加元素,但是不能删除元素,因为删掉元素会导致误判率增加.
• 误判率只会发生在过滤器没有添加过的元素,对于添加过的元素不会发生误判率

3.作用

• 解决缓存穿透
• 黑名单校验

4.简单原理

4.1数据结构

布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。
一个大型位数组（二进制数组）：

4.2使用布隆过滤器插入元素

为0的时候不存在,有一定的误判率

5.使用Guava提供的布隆过滤器(解决缓存穿透)

<!--guava Google 开源的 Guava 中自带的布隆过滤器-->
        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>23.0</version>
        </dependency>
1
2
3
4
5
6

public class GuavaBloomfilterDemo {
    
    public static final int _1W = 10000;
    //布隆过滤器里预计要插入多少数据
    public static int size = 100 * _1W;
    //误判率,它越小误判的个数也就越少(思考，是不是可以设置的无限小，没有误判岂不更好)
    //误判率小了 会影响一定的性能,选择符合自己的嘴适合
    public static double fpp = 0.01;

    /**
     * helloworld入门
     */
    public void bloomFilter() {
        // 创建布隆过滤器对象
        BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), 100);
        // 判断指定元素是否存在
        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));

    }

    /**
     * 误判率演示
     */
    public void bloomFilter2() {
        // 构建布隆过滤器
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);

        //1 先往布隆过滤器里面插入100万的样本数据
        for (int i = 0; i < size; i++) {
            bloomFilter.put(i);
        }
        List<Integer> listSample = new ArrayList<>(size);
        //2 这100万的样本数据，是否都在布隆过滤器里面存在？
        for (int i = 0; i < size; i++) {
            if (bloomFilter.mightContain(i)) {
                listSample.add(i);
                continue;
            }
        }
        System.out.println("存在的数量：" + listSample.size());

        //3 故意取10万个不在过滤器里的值，看看有多少个会被认为在过滤器里,误判率演示
        List<Integer> list = new ArrayList<>(10 * _1W);

        for (int i = size + 1; i < size + 100000; i++) {
            if (bloomFilter.mightContain(i)) {
                System.out.println(i + "\t" + "被误判了.");
                list.add(i);
            }
        }
        System.out.println("误判的数量：" + list.size());
    }

    public static void main(String[] args) {
        new GuavaBloomfilterDemo().bloomFilter2();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

6.RedissonBloom提供的布隆过滤器(解决缓存穿透)

• 布隆过滤器有,redis有
• 布隆过滤器有,redis无
• 布隆过滤器无,redis无

public class RedissonBloomFilterDemo {
    public static final int _1W = 10000;

    //布隆过滤器里预计要插入多少数据
    public static int size = 100 * _1W;
    //误判率,它越小误判的个数也就越少
    public static double fpp = 0.03;

    static RedissonClient redissonClient = null;//jedis
    static RBloomFilter rBloomFilter = null;//redis版内置的布隆过滤器

    @Resource
    RedisTemplate redisTemplate;


    static {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://192.168.111.147:6379").setDatabase(0);
        //构造redisson
        redissonClient = Redisson.create(config);
        //通过redisson构造rBloomFilter
        rBloomFilter = redissonClient.getBloomFilter("phoneListBloomFilter", new StringCodec());

        rBloomFilter.tryInit(size, fpp);

        // 1测试  布隆过滤器有+redis有
        //rBloomFilter.add("10086");
        //redissonClient.getBucket("10086",new StringCodec()).set("chinamobile10086");

        // 2测试  布隆过滤器有+redis无
        //rBloomFilter.add("10087");

        //3 测试 ，布隆过滤器无+redis无
    }

    private static String getPhoneListById(String IDNumber) {
        String result = null;

        if (IDNumber == null) {
            return null;
        }
        //1 先去布隆过滤器里面查询
        if (rBloomFilter.contains(IDNumber)) {
            //2 布隆过滤器里有，再去redis里面查询
            RBucket<String> rBucket = redissonClient.getBucket(IDNumber, new StringCodec());
            result = rBucket.get();
            if (result != null) {
                return "i come from redis: " + result;
            } else {
                result = getPhoneListByMySQL(IDNumber);
                if (result == null) {
                    return null;
                }
                // 重新将数据更新回redis
                redissonClient.getBucket(IDNumber, new StringCodec()).set(result);
            }
            return "i come from mysql: " + result;
        }
        return result;
    }

    private static String getPhoneListByMySQL(String IDNumber) {
        return "chinamobile" + IDNumber;
    }


    public static void main(String[] args) {
        //String phoneListById = getPhoneListById("10086");
        //String phoneListById = getPhoneListById("10087"); //请测试执行2次
        String phoneListById = getPhoneListById("10088");
        System.out.println("------查询出来的结果： " + phoneListById);

        //暂停几秒钟线程
        try {
            TimeUnit.SECONDS.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        redissonClient.shutdown();
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83