布隆过滤器是一个精巧并且经典的数据结构。

你或许没想到： RocketMQ、 Hbase 、Cassandra 、LevelDB 、RocksDB 这些知名项目中都有布隆过滤器的身影。

关于后端程序员来讲，学习和了解布隆过滤器有很大的必要性。来吧，咱们一起品味布隆过滤器的设计之美。

1 缓存穿透

咱们先来看一个产品服务查询详情的接口：

public Product queryProductById (Long id){
   // 查询缓存
   Product product = queryFromCache(id);
   if(product != null) {
     return product ;
   }
   // 从数据库查询
   product = queryFromDataBase(id);
   if(product != null) {
       saveCache(id , product);
   }
   return product;
}

假定此产品既不存储在缓存中，也不存在数据库中，则没有办法回写缓存，当有相似这样许多的请求拜访服务时，数据库的压力就会极大。

这是一个典型的缓存穿透的场景。

为了处理这个问题呢，一般咱们能够向分布式缓存中写入一个过期时刻较短的空值占位，但这样会占用较多的存储空间，性价比不足。

问题的本质是：”怎么以极小的价值检索一个元素是否在一个调集中？”

咱们的主角布隆过滤器进场了，它就能游刃有余的平衡好时刻和空间两种维度。

2 原了解析

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器能够用于检索一个元素是否在一个调集中。它的优点是空间功率和查询时刻都远远超越一般的算法，缺点是有必定的误识别率和删去困难。

布隆过滤器的原理：当一个元素被参加调集时，经过 K 个散列函数将这个元素映射成一个位数组中的 K 个点，把它们置为 1。检索时，咱们只要看看这些点是不是都是 1 就（大约）知道调集中有没有它了：假如这些点有任何一个 0，则被检元素必定不在；假如都是 1，则被检元素很或许在。

简略来说便是预备一个长度为 m 的位数组并初始化一切元素为 0，用 k 个散列函数对元素进行 k 次散列运算跟 len (m) 取余得到 k 个方位并将 m 中对应方位设置为 1。

如上图，位数组的长度是８，散列函数个数是 3，先后保持两个元素ｘ，ｙ。这两个元素都经过三次哈希函数生成三个哈希值，并映射到位数组的不同的方位，并置为1。元素 x 映射到位数组的第０位，第４位，第７位，元素ｙ映射到数组的位数组的第１位，第４位，第６位。

保存元素 x 后，位数组的第4位被设置为1之后，在处理元素 y 时第4位会被掩盖，同样也会设置为 1。

当布隆过滤器保存的元素越多，被置为 1 的 bit 位也会越来越多，元素 x 即使没有存储过，假定哈希函数映射到位数组的三个位都被其他值设置为 1 了，关于布隆过滤器的机制来讲，元素 x 这个值也是存在的，也便是说布隆过滤器存在必定的误判率。

▍ 误判率

布隆过滤器包括如下四个特点：

• k : 哈希函数个数

• m : 位数组长度

• n : 刺进的元素个数

• p : 误判率

若位数组长度太小则会导致一切 bit 位很快都会被置为 1 ，那么检索恣意值都会回来”或许存在“ ， 起不到过滤的作用。 位数组长度越大，则误判率越小。

一起，哈希函数的个数也需求考量，哈希函数的个数越大，检索的速度会越慢，误判率也越小，反之，则误判率越高。

从张图咱们能够观察到相同位数组长度的情况下，随着哈希函数的个人的增长，误判率显著的下降。

误判率 p 的公式是

1. k 次哈希函数某一 bit 位未被置为 1 的概率为

   

2. 刺进 n 个元素后某一 bit 位仍旧为 0 的概率为

   

3. 那么刺进 n 个元素后某一 bit 方位为1的概率为

   

4. 整体误判率为

   

   ，当 m 足够大时，误判率会越小，该公式约等于

   

咱们会预估布隆过滤器的误判率 p 以及待刺进的元素个数 n 别离推导出最适宜的位数组长度 m 和 哈希函数个数 k。

▍ 布隆过滤器支撑删去吗

布隆过滤器其实并不支撑删去元素，由于多个元素或许哈希到一个布隆过滤器的同一个方位，假如直接删去该方位的元素，则会影响其他元素的判别。

▍ 时刻和空间功率

布隆过滤器的空间复杂度为 O(m) ，刺进和查询时刻复杂度都是 O(k) 。 存储空间和刺进、查询时刻都不会随元素添加而增大。 空间、时刻功率都很高。

▍哈希函数类型

Murmur3，FNV 系列和 Jenkins 等非密码学哈希函数适宜，由于 Murmur3 算法简略，能够平衡好速度和随机分布，许多开源产品经常选用它作为哈希函数。

3 Guava完结

Google Guava是 Google 开发和保护的开源 Java开发库，它包括许多根本的东西类，例如字符串处理、调集、并发东西、I/O和数学函数等等。

1、添加Maven依赖

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

2、创立布隆过滤器

BloomFilter<Integer> filter = BloomFilter.create(
  //Funnel 是一个接口，用于将恣意类型的目标转换为字节省，
  //以便用于布隆过滤器的哈希核算。
  Funnels.integerFunnel(), 
  10000, 	// 刺进数据条目数量
  0.001 	// 误判率
);

3、添加数据

@PostConstruct
public void addProduct() {
    logger.info("初始化布隆过滤器数据开端");
    //刺进4个元素
     filter.put(1L);
     filter.put(2L);
     filter.put(3L);
     filter.put(4L);
     logger.info("初始化布隆过滤器数据完毕");
}

4、判别数据是否存在

public boolean maycontain(Long id) {
    return filter.mightContain(id);
}

接下来，咱们查看 Guava 源码中布隆过滤器是怎么完结的 ？

static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BloomFilter.Strategy strategy) {
    // 省掉部分前置验证代码 
    // 位数组长度
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    // 哈希函数次数
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter<T>(
                    new LockFreeBitArray(numBits), 
                    numHashFunctions, 
                    funnel,
                    strategy
      );
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
}

//核算位数组长度
//n:刺进的数据条目数量
//p:期望误判率
@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
   if (p == 0) {
     p = Double.MIN_VALUE;
   }
   return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
// 核算哈希次数
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}

Guava 的核算位数组长度和哈希次数和原了解析这一节展示的公式保持一致。

关键来了，Bloom filter 是怎么判别元素存在的 ？

办法名就非常有 google 特征 ， ”mightContain“ 的中文表意是：”或许存在“ 。办法的回来值为 true ，元素或许存在，但若回来值为 false ，元素必定不存在。

public <T extends @Nullable Object> boolean mightContain(
    @ParametricNullness T object,
    //Funnel 是一个接口，用于将恣意类型的目标转换为字节省，
    //以便用于布隆过滤器的哈希核算。
    Funnel<? super T> funnel,  
    //用于核算哈希值的哈希函数的数量
    int numHashFunctions,
    //位数组实例，用于存储布隆过滤器的位集
    LockFreeBitArray bits) {
  long bitSize = bits.bitSize();
  //运用 MurmurHash3 哈希函数核算目标 object 的哈希值，
  //并将其转换为一个 byte 数组。
  byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
  long hash1 = lowerEight(bytes);
  long hash2 = upperEight(bytes);
  long combinedHash = hash1;
  for (int i = 0; i < numHashFunctions; i++) {
    // Make the combined hash positive and indexable
    // 核算哈希值的索引，并从位数组中查找索引处的位。
    // 假如索引处的位为 0，表明目标不在布隆过滤器中，回来 false。
    if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
      return false;
    }
    // 将 hash2 加到 combinedHash 上，用于核算下一个哈希值的索引。
    combinedHash += hash2;
  }
  return true;
}

3 Redisson完结

Redisson 是一个用 Java 编写的 Redis 客户端，它完结了分布式目标和服务，包括调集、映射、锁、行列等。Redisson的API简略易用，使得在分布式环境下运用Redis 更加容易和高效。

1、添加Maven依赖

<dependency>
   <groupId>org.redisson</groupId>
   <artifactId>redisson</artifactId>
   <version>3.16.1</version>
</dependency>

2、装备 Redisson 客户端

@Configuration
public class RedissonConfig {
 Bean
 public RedissonClient redissonClient() {
    Config config = new Config();
    config.useSingleServer().setAddress("redis://localhost:6379");
    return Redisson.create(config);
 }
}

3、初始化

RBloomFilter<Long> bloomFilter = redissonClient.
                                      getBloomFilter("myBloomFilter");
//10000表明刺进元素的个数，0.001表明误判率
bloomFilter.tryInit(10000, 0.001);
//刺进4个元素
bloomFilter.add(1L);
bloomFilter.add(2L);
bloomFilter.add(3L);
bloomFilter.add(4L);

4、判别数据是否存在

public boolean mightcontain(Long id) {
    return bloomFilter.contains(id);
}

好，咱们来从源码分析 Redisson 布隆过滤器是怎么完结的 ？

public boolean tryInit(long expectedInsertions, double falseProbability) {
    // 位数组巨细
    size = optimalNumOfBits(expectedInsertions, falseProbability);
    // 哈希函数次数
    hashIterations = optimalNumOfHashFunctions(expectedInsertions, size);
    CommandBatchService executorService = new CommandBatchService(commandExecutor);
    // 履行 Lua脚本，生成装备
    executorService.evalReadAsync(configName, codec, RedisCommands.EVAL_VOID,
            "local size = redis.call('hget', KEYS[1], 'size');" +
                    "local hashIterations = redis.call('hget', KEYS[1], 'hashIterations');" +
                    "assert(size == false and hashIterations == false, 'Bloom filter config has been changed')",
                    Arrays.<Object>asList(configName), size, hashIterations);
    executorService.writeAsync(configName, StringCodec.INSTANCE,
                                            new RedisCommand<Void>("HMSET", new VoidReplayConvertor()), configName,
            "size", size, "hashIterations", hashIterations,
            "expectedInsertions", expectedInsertions, "falseProbability", BigDecimal.valueOf(falseProbability).toPlainString());
    try {
        executorService.execute();
    } catch (RedisException e) {
    }
    return true;
}

Redisson 布隆过滤器初始化的时候，会创立一个 Hash 数据结构的 key ，存储布隆过滤器的4个中心特点。

那么 Redisson 布隆过滤器怎么保存元素呢 ？

public boolean add(T object) {
    long[] hashes = hash(object);
    while (true) {
        int hashIterations = this.hashIterations;
        long size = this.size;
        long[] indexes = hash(hashes[0], hashes[1], hashIterations, size);
        CommandBatchService executorService = new CommandBatchService(commandExecutor);
        addConfigCheck(hashIterations, size, executorService);
        //创立 bitset 目标， 然后调用setAsync办法，该办法的参数是索引。
        RBitSetAsync bs = createBitSet(executorService);
        for (int i = 0; i < indexes.length; i++) {
            bs.setAsync(indexes[i]);
        }
        try {
            List<Boolean> result = (List<Boolean>) executorService.execute().getResponses();
            for (Boolean val : result.subList(1, result.size()-1)) {
                if (!val) {
                    return true;
                }
            }
            return false;
        } catch (RedisException e) {
        }
    }
}

从源码中，咱们发现 Redisson 布隆过滤器操作的目标是 位图（bitMap） 。

在 Redis 中，位图本质上是 string 数据类型，Redis 中一个字符串类型的值最多能存储 512 MB 的内容，每个字符串由多个字节组成，每个字节又由 8 个 Bit 位组成。位图结构正是运用“位”来完结存储的，它经过将比特位设置为 0 或 1来到达数据存取的意图，它存储上限为 2^32 ，咱们能够运用getbit/setbit命令来处理这个位数组。

为了方便咱们了解，我做了一个简略的测验。

经过 Redisson API 创立 key 为 mybitset 的 位图 ，设置索引 3 ，5，6，8 位为 1 ，右侧的二进制值也完全匹配。

4 实战关键

经过 Guava 和 Redisson 创立和运用布隆过滤器比较简略，咱们下面讨论实战层面的注意事项。

1、缓存穿透场景

首要咱们需求初始化布隆过滤器，然后当用户请求时，判别过滤器中是否包括该元素，若不包括该元素，则直接回来不存在。

若包括则从缓存中查询数据，若缓存中也没有，则查询数据库并回写到缓存里，最后给前端回来。

2、元素删去场景

现实场景，元素不仅仅是只有添加，还存在删去元素的场景，比如说产品的删去。

原了解析这一节，咱们已经知晓：布隆过滤器其实并不支撑删去元素，由于多个元素或许哈希到一个布隆过滤器的同一个方位，假如直接删去该方位的元素，则会影响其他元素的判别。

咱们有两种方案：

▍计数布隆过滤器

计数过滤器（Counting Bloom Filter）是布隆过滤器的扩展，规范 Bloom Filter 位数组的每一位扩展为一个小的计数器（Counter），在刺进元素时给对应的 k （k 为哈希函数个数）个 Counter 的值别离加 1，删去元素时给对应的 k 个 Counter 的值别离减 1。

虽然计数布隆过滤器能够处理布隆过滤器无法删去元素的问题，可是又引入了另一个问题：“更多的资源占用，并且在许多时候会造成极大的空间浪费”。

▍ 守时从头构建布隆过滤器

从工程角度来看，守时从头构建布隆过滤器这个方案可行也牢靠，一起也相对简略。

1. 守时使命触发全量产品查询 ;
2. 将产品编号添加到新的布隆过滤器 ;
3. 使命完结，修改产品布隆过滤器的映射（从旧 A 修改成 新 B ）;
4. 产品服务依据布隆过滤器的映射，挑选新的布隆过滤器 B进行相关的查询操作 ；
5. 挑选适宜的时刻点，删去旧的布隆过滤器 A。

5 总结

布隆过滤器是一个很长的二进制向量和一系列随机映射函数，用于检索一个元素是否在一个调集中。

它的空间功率和查询时刻都远远超越一般的算法，可是有必定的误判率 （函数回来 true , 意味着元素或许存在，函数回来 false ，元素必定不存在）。

布隆过滤器的四个中心特点：

• k : 哈希函数个数

• m : 位数组长度

• n : 刺进的元素个数

• p : 误判率

Java 国际里 ，经过 Guava 和 Redisson 创立和运用布隆过滤器非常简略。

布隆过滤器无法删去元素，但咱们能够经过计数布隆过滤器和守时从头构建布隆过滤器两种方案完结删去元素的作用。

为什么这么多的开源项目中运用布隆过滤器 ？

由于它的设计精巧且简练，工程上完结非常容易，效能高，虽然有必定的误判率，但软件设计不便是要 trade off 吗 ？

---

参考资料：

hackernoon.com/probabilist…

假如我的文章对你有所帮助，还请帮助点赞、在看、转发一下，你的支撑会鼓励我输出更高质量的文章，非常感谢！