【布隆过滤器】一

解决缓存穿透的办法之一，就是布隆过滤器

缓存穿透：指缓存和数据库中都没有的数据，而用户不断发起请求，如发起id为“-1”的数据或id为其他不存在的数据。这时的用户很可能是攻击者，攻击会导致数据库压力过大。

布隆过滤器（Bloom Filter）

布隆过滤器（Bloom Filter）是1970年，由一个叫布隆的小伙子提出的。

它实际上是一个很长的二进制向量和一系列随机映射函数，二进制存储的数据不是0就是1，默认是0。

主要用于判断某个数据是否在一个集合中，0代表不存在，1代表存在。

布隆过滤器用途

• 解决Redis缓存穿透（此篇重点讲解）

• 在爬虫时，对爬虫网址进行过滤，已经存在布隆中的网址，不在爬取。

• 垃圾邮件过滤，对每一个发送邮件的地址进行判断是否在布隆的黑名单中，如果在就判断为垃圾邮件。

• ......

布隆过滤器原理

存入过程

当一个数据加入这个集合时，经历如下洗礼（这里有缺点，下面会讲）：

• 通过K个哈希函数计算该数据，返回K个计算出的hash值
• 这些K个hash值映射到对应的K个二进制的数组下标
• 将K个下标对应的二进制数据改成1。

例如，第一个哈希函数返回x，第二个第三个哈希函数返回y与z，那么：X、Y、Z对应的二进制改成1。如图所示：

查询过程

布隆过滤器主要作用就是查询一个数据，在不在这个二进制的集合中，查询过程如下：

• 通过K个哈希函数计算该数据，对应计算出的K个hash值

• 通过hash值找到对应的二进制的数组下标

• 判断：如果有个下标对应的二进制数据是0，那么该数据不存在。如果都是1，该数据存在集合中。（这里有缺点，下面会讲）

  可以通过乘法判断是否有二进制数据为0的。

删除过程

一般不能删除布隆过滤器里的数据，这是一个缺点之一，我们下面会分析。

布隆过滤器的优缺点

优点

• 由于存储的是二进制数据，所以占用的空间很小
• 它的插入和查询速度是非常快的，时间复杂度是O（K），可以联想一下HashMap的过程
• 保密性很好，因为本身不存储任何原始数据，只有二进制数据

缺点

添加数据是通过计算数据的hash值，那么很有可能存在这种情况：两个不同的数据计算得到相同的hash值。hash冲突。

例如图中的“你好”和“hello”，假如最终算出hash值相同，那么他们会将同一个下标的二进制数据改为1。这个时候，你就不知道下标为2的二进制，到底是代表“你好”还是“hello”。

• 存在误判：假如上面的图没有存"hello"，只存了"你好"，那么用"hello"来查询的时候，会判断"hello"存在集合中。因为“你好”和“hello”的hash值是相同的，通过相同的hash值，找到的二进制数据也是一样的，都是1。
• 删除困难：因为“你好”和“hello”的hash值相同，对应的数组下标也是一样的。这时候如果想去删除“你好”，将下标为2里的二进制数据，由1改成了0。结果我们连“hello”都一起删了呀。（0代表有这个数据，1代表没有这个数据）

实现布隆过滤器

有很多种实现方式，其中一种就是Guava提供的实现方式。

一、引入Guava pom配置

  com.google.guava
  guava
  29.0-jre

二、代码实现

注意：布隆过滤器存在误判率，可以手动设置，误判率越小，占用内存和hash计算耗时越大

package cn.lxiaol.www.bloomfilter;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterCase {

    /**
     * 预计要存入多少数据
     */
    private static final int size = 1000000;

    /**
     * 期望的误判率
     */
    private static double fpp = 0.01;

    /**
     * 布隆过滤器
     */
    private static BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);


    private static final int total = 1000000;

    public static void main(String[] args) {

        // 插入100万条样本数据
        for (int i = 0; i < total; i++) {
            bloomFilter.put(i);
        }


        //用另外10万测试误判率
        int count = 0;
        for (int i = total; i < total+100000; i++) {
            if(bloomFilter.mightContain(i)){
                count++;
                System.out.println(i+"误判了");
            }
        }

        System.out.println("总误判数:"+count);
        System.out.println("fpp：" + 1.0 * count / 100000);

    }
}

10万数据里有947个误判，约等于我们代码里设置的误判率：fpp = 0.01。

深入分析代码

    @VisibleForTesting
    static  BloomFilter create(Funnel<? super T> funnel, long expectedInsertions, 
                                     double fpp, BloomFilter.Strategy strategy) {
        Preconditions.checkNotNull(funnel);
        Preconditions.checkArgument(expectedInsertions >= 0L, "Expected insertions (%s) must be >= 0", expectedInsertions);
        Preconditions.checkArgument(fpp > 0.0D, "False positive probability (%s) must be > 0.0", fpp);
        Preconditions.checkArgument(fpp < 1.0D, "False positive probability (%s) must be < 1.0", fpp);
        Preconditions.checkNotNull(strategy);
        if (expectedInsertions == 0L) {
            expectedInsertions = 1L;
        }

        long numBits = optimalNumOfBits(expectedInsertions, fpp);
        int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);

        try {
            return new BloomFilter(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
        } catch (IllegalArgumentException var10) {
            throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", var10);
        }
    }

这里有四个参数：

• funnel：数据类型(一般是调用Funnels工具类中的)
• expectedInsertions：期望插入的值的个数
• fpp：误判率(默认值为0.03)
• strategy：哈希算法

我们重点讲一下fpp参数

fpp误判率

情景一：fpp = 0.01

• 误判个数：947

• 占内存大小：9585058位数

  

情景二：fpp = 0.03（默认参数）

• 误判个数：3033

• 占内存大小：7298440位数

  

  

情景总结

• 误判率可以通过fpp参数进行调节
• fpp越小，需要的内存空间就越大：0.01需要900多万位数，0.03需要700多万位数。
• fpp越小，集合添加数据时，就需要更多的hash函数运算更多的hash值，去存储到对应的数组下标里。（忘了去看上面的布隆过滤存入数据的过程）

上面的numBits，表示存一百万个int类型数字，需要的位数为7298440，700多万位。理论上存一百万个数，一个int是4字节32位，需要481000000=3200万位。如果使用HashMap去存，按HashMap50%的存储效率，需要6400万位。可以看出BloomFilter的存储空间很小，只有HashMap的1/10左右

上面的numHashFunctions表示需要几个hash函数运算，去映射不同的下标存这些数字是否存在（0 or 1）。

解决Redis缓存雪崩

上面使用Guava实现的布隆过滤器是把数据放在了本地内存中。分布式的场景中就不合适了，无法共享内存。

我们还可以用Redis来实现布隆过滤器，这里使用Redis封装好的客户端工具Redisson。

其底层是使用数据结构bitMap，大家就把它理解成上面说的二进制结构。

代码实现

pom配置：

  org.redisson
  redisson-spring-boot-starter
  3.13.4

java代码：

package cn.lxiaol.www.bloomfilter;

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

public class RedissonBloomFilter {

    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:2020");
        config.useSingleServer().setPassword("yiguan789");

        // 构造redis
        RedissonClient redissonClient = Redisson.create(config);

        // 获取布隆过滤器，并给该过滤器起一个名字，叫做 nickNameList
        RBloomFilter