布隆过滤器 - 一种先进而经典的数据结构

terry 2年前 (2023-09-27) 阅读数 97 #数据结构与算法

布隆过滤器是一种先进而经典的数据结构。

你可能没想到：布隆过滤器被用于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 原理分析

布隆滤波器（英文：Bloomer Filter）是布隆在1970年提出的。它基本上是一个长的二元向量和一系列 任意映射函数。

Yao 过滤器可用于检索集合中是否存在某个元素。优点是空间效率和查询时间都远大于一般算法。缺点是有一定的误识别和清除难度。

布隆过滤器的原理：当一个元素被添加到集合中时，该元素通过K个哈希函数被分配到一个位数组中的K个点，并将它们设置为1。检索时，我们只需要看到如果这些点都为 1 就知道（大约）它是否在集合中：如果这些 点中的任何一个有 0，那么被检查的 元素一定不存在 ；如果都是1，那么被检查的元素可能在中。

简单来说，准备一个长度为m的位数组，将所有元素初始化为0，使用k个哈希函数对元素进行k次哈希运算，对len(m)取余得到k个位置和m得到。 in对应位置设置为1。

如上图所示，位数组长度为8，哈希函数个数为3，连续保留两个元素x和y。两个元素经过三个哈希函数生成三个哈希值，分配到位数组中的不同位置并设置为1。元素x分配到位数组的第0、4、7位，元素y 被分配给位数组的第 1 位、第 4 位和第 6 位。

存储元素x后，位数组的第4位被设置为1，处理元素y时，第4位被覆盖并被设置为1。

随着布隆过滤器存储更多元素，将有越来越多的位设置为1。即使不存储元素x，假设有哈希函数，分配给位数组的三个位都被其他值设置为1。对于布隆过滤器机制来说，元素x的值也存在，这意味着布隆过滤器有一定的收视率。

▍ 误报率

布隆过滤器包含以下四个属性：

k：哈希函数数量
m：位数组长度
n：插入元素数量
p ：误报百分比

如果位数组的长度太小，很快所有位都会被设置为1，并且每个检索到的值都会返回“可能存在”，从而达不到过滤效果。位数组的长度越大，误报率越小。

同时，还必须考虑哈希函数的数量。哈希函数的数量越多，检索速度越慢，误报率越小。反之，误报率越高。

从图中我们可以看到，在相同的位数组长度下，随着哈希函数中个体数量的增加，误判率显着下降。

误报率 p 的公式为

第 k 个哈希函数的给定位未设置为 1 的概率为
插入 n 个元素后给定位仍为 0 的概率是
则插入n个元素后给定位位置为1的概率为
。错误估计的总百分比为。如果m足够大，错误估计的百分比就会更小。该公式约等于

。通过估计布隆过滤器的误判次数p和需要插入的元素数量n，我们可以分别推导出最合适的位数组长度m和哈希函数的数量k。

▍布隆滤镜支持移除吗？

布隆过滤器并不真正支持删除元素，因为多个元素可以散列到布隆过滤器的同一位置。如果立即删除该位置的元素，会影响其他元素的判断。

▍时间和空间效率

布隆过滤器的空间复杂度为O(m)，插入和检索的时间复杂度均为O(k)。存储空间、插入和查找时间不会随着元素数量的增加而增加。空间和时间效率非常高。

▍哈希函数类型

Murmur3，FNV系列和Jenkins等非加密哈希函数比较适合，因为Murmur3算法简单，可以平衡速度和随机分布。许多开源产品经常使用它作为哈希函数。

3 Guava 实现

Google Guava 是一个由 Google 开发和维护的开源 Java 开发库。它包含许多基本工具类，例如字符串处理、集合、并发工具、I/O 和数学函数等。经过？

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计算出的位数组长度和哈希数与原理分析部分所示的公式相对应。

事情是这样的：布隆过滤器如何判断元素的存在？方法名称

是 Google 特有的。 “可能含有”的中文意思是：“可能存在”。 方法的返回值为 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。？？

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;
}

Bf配置信息

Redisson在初始化布隆过滤器时，会创建Hash数据结构的一个key，用于存储布隆过滤器的四个核心属性。

那么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中，位图本质上是一种字符串数据类型。 Redis 中的字符串类型值最多可以存储 512 MB 的内容。每个字符串由多个字节组成，每个字节由 8 个复合位组成。位图结构使用“位”来实现存储。它通过将位设置为0或1来达到数据访问的目的。存储限制为2^32，我们可以使用getbit/setbit命令来处理这个位数组。

为了方便大家理解，我做了一个简单的测试。