布隆过滤器介绍和业务使用说明

时间：2024-11-08 07:57:09

目录

一、快速了解布隆过滤器

（一）布隆过滤器

（二）写入过程说明

（三）查询过程说明

二、简单实现一个布隆过滤

三、Guava实现布隆过滤及源码分析

四、经典解决案例

基本编程能力考查

扩展能力深入

1.布隆过滤器有误判率吗？为啥会误判，举例说明？

2.如何处理布隆过滤器的误判率？在实际应用中有哪些补救措施？

3.如何在插入超过预期数量的元素时处理布隆过滤器的误判率增加问题？

4.布隆过滤器可以合并吗？如何实现？误判率会增加吗？

的Guava库提供了高效的布隆过滤器实现，如果使用其现成的内容，上面代码该如何实现？

的BloomFilter是如何控制误判率和内存使用的？

的BloomFilter是否支持扩展，即动态增加元素后仍保持较低的误判率？

的BloomFilter是线程安全的吗？如果不是，如何确保线程安全？给出实现？

方法1：显式锁---使用显式锁可以确保在对BloomFilter的每次访问（读或写）时，都只有一个线程能够执行操作。

方法2：使用并发集合---在这种方法中，我们将多个布隆过滤器分片存储在一个并发集合（如ConcurrentHashMap）中，通过将元素散列到不同的布隆过滤器分片来减少争用。

方法3：使用ReadWriteLock---使用ReadWriteLock可以在读操作不需要互斥的情况下提高并发性，只有在写操作时才进行锁定。

干货分享，感谢您的阅读！

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

一、快速了解布隆过滤器

缓存穿透是每次查询都要经过缓存，查询未命中回溯到数据库中，如果我们用一种存储结构存储所有数据，在查询缓存之前提前过滤要查询的数据是否一定不存在，如果存在就不用再去查缓存了，也就避免了缓存穿透的问题，当然这对过滤器的存储结构要求就比较高了。

（一）布隆过滤器

如果不考虑内存容量问题，hashmap是最简单的一种过滤器，把所有数据存在map中，通过get(key)是否存在进行过滤，当然我们这里用hashmap是不现实的，因为不满足内存容量要求，而布隆过滤器就是这样一种用比较少的内存存储大量数据映射，能满足提前过滤要查询的数据在系统中是否一定不存在的要求。

布隆过滤器，借助bitset的存储特性和一组Hash算法构成，是一种空间效率极高的概率型算法和数据结构，主要用来判断一个元素是否在集合中存在。初始时bit数组每一位为0，每个输入值通过一组hash算法，得到一组bit数组的下标，并把该bit位标识为1。如果一个要验证的值通过这组hash函数得到的下标有不为1的情况，那么可以肯定这个值肯定不存在。

（二）写入过程说明

写入过程(如有3个hash函数)：

  1. 初始时bit数组每一位都初始标记为0。

  2. "user_10"这个值经过3个hash函数计算后，得到的bit数组下标分别为[3,6,12]，并把对应的bit数组标识为1。

  3. 同理值为"user_20"经过hash计算得出的下标为[6,10,15]，分别标识为1。注意在标记数值位6时已经被标记为1，则保持为1。

（三）查询过程说明

查询一个原始值在布隆过滤器中是否存在的过程如下：

  1. 待查询的值"user_30" 经过同样的hash计算后得出的bit下标为[3,6,13]，可以看出13位为0，则"user_30"一定不存在。

  2. 待查询的值"user_20" 经过同样的hash计算后得出的bit下标为[6,10,10]，可以看出都匹配为1，得出在布隆过滤器中这个值一定存在的结论？

  3. 其实不一定，因为有hash冲突的存在，多个值hash的bit位重复的情况都标识为1，假如不存在的值"user_404"值hash得出下标为[3,6,10]，因为hash冲突得出都为1，其实这个值并不存在，因此，“布隆过滤器能确定一个值一定不存在，但是不能确定一个值一定存在”。但我们缓存穿透要利用的就是前一句"布隆过滤器能确定一个值一定不存在"，因此不存在计算误差。

二、简单实现一个布隆过滤

基本思路：

  • 初始化一个大小为 size 的 int 数组作为位数组。
  • 写入数据时，使用 numHashFunctions 个哈希函数进行哈希运算，并将对应位置置为 1。
  • 查询数据时，同样使用 numHashFunctions 个哈希函数进行哈希运算，如果对应位置有一个值为 0，则认为数据不存在。

注意：提高数组长度以及 hash 计算次数可以降低误报率，但相应的 CPU、内存的消耗就会提高；这就需要根据业务需要自行权衡。

package ;

import ;
import ;

/**
 * @program: zyfboot-javabasic
 * @description: 布隆过滤器的基本思路和使用方法
 * 基本思路：
 *
 * 初始化一个大小为 size 的 int 数组作为位数组。
 * 写入数据时，使用 numHashFunctions 个哈希函数进行哈希运算，并将对应位置置为 1。
 * 查询数据时，同样使用 numHashFunctions 个哈希函数进行哈希运算，如果对应位置有一个值为 0，则认为数据不存在。
 * @author: zhangyanfeng
 * @create: 2017-03-23 22:33
 **/
public class ZYFBloomFilter {
    /**
     * 位数组的大小
     */
    private final int size;

    /**
     * 用于存储布隆过滤器的位数组
     */
    private final BitSet bitSet;

    /**
     * 哈希函数的数量
     */
    private final int numHashFunctions;

    /**
     * 构造方法，创建一个指定大小和哈希函数数量的布隆过滤器
     *
     * @param size 位数组的大小
     * @param numHashFunctions 哈希函数的数量
     */
    public ZYFBloomFilter(int size, int numHashFunctions) {
        if (size <= 0 || numHashFunctions <= 0) {
            throw new IllegalArgumentException("位数组大小和哈希函数数量必须为正数。");
        }
         = size;
         = numHashFunctions;
         = new BitSet(size);
    }

    /**
     * 添加一个键到布隆过滤器中
     *
     * @param key 要添加的键
     */
    public void add(String key) {
        if (key == null) {
            throw new IllegalArgumentException("键不能为null。");
        }
        byte[] bytes = (StandardCharsets.UTF_8);
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = computeHash(bytes, i);
            ((hash % size), true);
        }
    }

    /**
     * 检查一个键是否可能存在于布隆过滤器中
     *
     * @param key 要检查的键
     * @return 如果键可能存在于布隆过滤器中，则返回true；如果键肯定不存在，则返回false
     */
    public boolean contains(String key) {
        if (key == null) {
            throw new IllegalArgumentException("键不能为null。");
        }
        byte[] bytes = (StandardCharsets.UTF_8);
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = computeHash(bytes, i);
            if (!((hash % size))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 计算给定数据和种子的哈希值
     *
     * @param data 要哈希的数据
     * @param seed 哈希函数的种子
     * @return 计算出的哈希值
     */
    private int computeHash(byte[] data, int seed) {
        int hash = 0;
        for (byte b : data) {
            hash = 31 * hash + b;
        }
        return hash ^ seed;
    }

    public static void main(String[] args) {
        // 初始化布隆过滤器，位数组大小为1000，使用3个哈希函数
        ZYFBloomFilter bloomFilter = new ZYFBloomFilter(1000, 3);

        // 添加数据到布隆过滤器
        ("hello");

        // 检查数据是否可能存在
        (("hello"));  // true
        (("world"));  // false
    }
}

三、Guava实现布隆过滤及源码分析

为使性能效果和内存利用率做到最好，建议使用Guava BloomFilter实现。源码分析如下：

static <T> BloomFilter<T> create(
    Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
    checkNotNull(funnel);
    checkArgument(expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
    checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
    checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
    checkNotNull(strategy);
 
    if (expectedInsertions == 0) {
      expectedInsertions = 1;
    }
 
    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);
    }
  }

从代码可以看出，需要4个参数，分别是

  • funnel 用来对参数做转化,方便生成hash值
  • expectedInsertions 预期插入的数据量大小，也就是上文公式中的n
  • fpp 误判率，也就是上文公式中的误判率p
  • strategy 生成hash值的策略，guava中也提供了默认策略，一般不需要你自己重新实现

从上面代码可知，BloomFilter创建过程中先检查参数的合法性

  • 使用n和p来计算bitmap的大小m（optimalNumOfBits(expectedInsertions, fpp)）
  • 通过n和m计算hash函数的个数k（optimalNumOfHashFunctions(expectedInsertions, numBits)）

这俩方法的具体实现如下：

static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return (1, (int) ((double) m / n * (2)));
  }
  static long optimalNumOfBits(long n, double p) {
    if (p == 0) {
      p = Double.MIN_VALUE;
    }
    return (long) (-n * (p) / ((2) * (2)));
  }

除此之外，BloomFilter除了提供创建和几个核心的功能外，还支持写入Stream或从Stream中重新生成BloomFilter，方便数据的共享和传输。

最关键的两个函数如下：put函数和mightContain函数

MURMUR128_MITZ_64() {
    @Override
    public <T> boolean put(
        T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
      long bitSize = ();
      byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
      long hash1 = lowerEight(bytes);
      long hash2 = upperEight(bytes);
 
      boolean bitsChanged = false;
      long combinedHash = hash1;
      for (int i = 0; i < numHashFunctions; i++) {
        // Make the combined hash positive and indexable
        bitsChanged |= ((combinedHash & Long.MAX_VALUE) % bitSize);
        combinedHash += hash2;
      }
      return bitsChanged;
    }
 
    @Override
    public <T> boolean mightContain(
        T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
      long bitSize = ();
      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
        if (!((combinedHash & Long.MAX_VALUE) % bitSize)) {
          return false;
        }
        combinedHash += hash2;
      }
      return true;
    }

抽象来看，put是写，mightContain是读，两个方法的代码有一点相似，都是先利用murmur3 hash对输入的funnel计算得到128位的字节数组，然后高低分别取8个字节（64位）创建2个long型整数hash1，hash2作为哈希值。循环体内采用了2个函数模拟其他函数的思想，即上文提到的gi(x) = h1(x) + ih2(x) ，这相当于每次累加hash2，然后通过基于bitSize取模的方式在bit数组中索引。

在put方法中，先是将索引位置上的二进制置为1，然后用bitsChanged记录插入结果，如果返回true表明没有重复插入成功，而mightContain方法则是将索引位置上的数值取出，并判断是否为0，只要其中出现一个0，那么立即判断为不存在。

再说一下底层bit数组的实现，主要代码如下：

static final class BitArray {
    final long[] data;
    long bitCount;
 
    BitArray(long bits) {
      this(new long[((bits, 64, ))]);
    }
 
    // Used by serialization
    BitArray(long[] data) {
      checkArgument( > 0, "data length is zero!");
       = data;
      long bitCount = 0;
      for (long value : data) {
        bitCount += (value);
      }
       = bitCount;
    }
 
    /** Returns true if the bit changed value. */
    boolean set(long index) {
      if (!get(index)) {
        data[(int) (index >>> 6)] |= (1L << index);
        bitCount++;
        return true;
      }
      return false;
    }
 
    boolean get(long index) {
      return (data[(int) (index >>> 6)] & (1L << index)) != 0;
    }
 
    /** Number of bits */
    long bitSize() {
      return (long)  * ;
    }
...
}

Guava没有使用，而是封装了一个long型的数组，另外还有一个long型整数，用来统计数组中已经占用（置为1）的数量，在第一个构造函数中，它把传入的long型整数按长度64分段（例如129分为3段），段数作为数组的长度，你可以想象成由若干个64位数组拼接成一个超长的数组，它的长度就是64乘以段数，即bitSize，在第二个构造函数中利用方法来统计对应二进制编码中的1个数，这个方法在JDK1.5中就有了，其算法设计得非常精妙，有精力的同学可以自行研究。

另外两个重要的方法是set和get，在get方法中，参考put和mightContain方法，传入的参数index是经过bitSize取模的，因此一定能落在这个超长数组的范围之内，为了获取index对应索引位置上的值，首先将其无符号右移6位，并且强制转换成int型，这相当于除以64向下取整的操作，也就是换算成段数，得到该段上的数值之后，又将1左移index位，最后进行按位与的操作，如果结果等于0，那么返回false，从而在mightContain中判断为不存在。在set方法中，首先调用了get方法判断是否已经存在，如果不存在，则用同样的逻辑取出data数组中对应索引位置的数值，然后按位或并赋值回去。

到这里，对Guava中布隆过滤器的实现就基本讨论完了，简单总结一下：

  • BloomFilter类的作用在于接收输入，利用公式完成对参数的估算，最后初始化Strategy接口的实例；
  • BloomFilterStrategies是一个枚举类，具有两个实现了Strategy接口的成员，分别为MURMUR128_MITZ_32和MURMUR128_MITZ_64，另外封装了long型的数组作为布隆过滤器底层的bit数组，其中在get和set方法中完成核心的位运算。

四、经典解决案例

 一个网站有 20 亿 url 存在一个黑名单中，这个黑名单要怎么存？若此时随便输入一个 url，你如何快速判断该 url 是否在这个黑名单中？并且需在给定内存空间（比如：500M）内快速判断出。

基本编程能力考查

要在有限的内存空间内存储和快速判断一个URL是否在一个20亿条URL的黑名单中，可以使用布隆过滤器（Bloom Filter）。布隆过滤器是一种空间效率很高的概率型数据结构，可以用于判断一个元素是否属于一个集合。它能够以较小的内存开销和快速查询来满足这种需求。

对应代码实现如下：

package ;

import ;
import ;
import ;

/**
 * @program: zyfboot-javabasic
 * @description: 布隆过滤器
 * @author: zhangyanfeng
 * @create: 2021-08-10 22:44
 **/
public class BloomFilter {
    private BitSet bitSet;
    private int bitSize;
    private int[] hashSeeds;
    private int hashFunctionCount;

    public BloomFilter(int expectedInsertions, double falsePositiveProbability) {
        // 计算位数组大小和哈希函数数量
         = (int) (-expectedInsertions * (falsePositiveProbability) / ((2) * (2)));
         = (int) (bitSize / expectedInsertions * (2));
         = new BitSet(bitSize);
         = new int[hashFunctionCount];

        Random random = new Random();
        for (int i = 0; i < hashFunctionCount; i++) {
            hashSeeds[i] = ();
        }
    }

    public void add(String url) {
        byte[] bytes = (StandardCharsets.UTF_8);
        for (int seed : hashSeeds) {
            int hash = hash(bytes, seed);
            ((hash % bitSize));
        }
    }

    public boolean contains(String url) {
        byte[] bytes = (StandardCharsets.UTF_8);
        for (int seed : hashSeeds) {
            int hash = hash(bytes, seed);
            if (!((hash % bitSize))) {
                return false;
            }
        }
        return true;
    }

    private int hash(byte[] bytes, int seed) {
        int result = 0;
        for (byte b : bytes) {
            result = result * seed + b;
        }
        return result;
    }

    public static void main(String[] args) {
        int expectedInsertions = 2000000000; // 20亿
        double falsePositiveProbability = 0.01; // 1% 的误判率
        BloomFilter bloomFilter = new BloomFilter(expectedInsertions, falsePositiveProbability);

        // 插入URL
        ("");

        // 查询URL
        (("")); // true
        (("")); // false
    }
}

扩展能力深入

1.布隆过滤器有误判率吗？为啥会误判，举例说明？

布隆过滤器是一种用于快速判断一个元素是否存在于集合中的数据结构，它使用一系列哈希函数和位数组来实现。布隆过滤器在判断元素存在性时非常高效，但也有可能发生误判，即判断一个元素存在于集合中，但实际上并不存在。

误判主要由以下几个因素引起：

  • 哈希碰撞： 布隆过滤器使用多个哈希函数来将元素映射到位数组中的位置。如果两个不同的元素映射到了相同的位置，就会产生哈希碰撞。这样，即使一个元素在位数组中被标记为存在，也可能是因为另一个元素的哈希函数产生了相同的位置。
  • 位数组大小： 布隆过滤器的位数组大小决定了其容纳元素的能力。如果位数组大小有限，当插入大量元素时，不可避免地会出现冲突，导致误判。

举个例子来说明：

假设我们有一个位数组大小为 8，并使用两个哈希函数来映射元素到位数组上的位置。现在，我们向布隆过滤器插入两个元素：A 和 B。元素 A 经过两个哈希函数后映射到位数组的第 2 和第 5 个位置，元素 B 映射到位数组的第 3 和第 6 个位置。

如果现在我们想判断元素 C 是否存在于集合中，它经过哈希函数后映射到位数组的第 2 和第 6 个位置，与元素 A 和元素 B 的映射位置重合。这将导致布隆过滤器错误地判断元素 C 存在于集合中，尽管实际上并没有插入过元素 C。

因此，布隆过滤器在设计和使用时需要权衡容错性和误判率。可以通过增加位数组大小、使用更多的哈希函数等方式来降低误判率，但同时也会增加内存占用和计算成本。

2.如何处理布隆过滤器的误判率？在实际应用中有哪些补救措施？

误判率无法完全消除，但可以通过一些方式减轻其影响，比如：

  • 二次检查: 在关键业务场景中，使用布隆过滤器作为第一层筛选，再通过其他准确但较慢的方法进行二次验证。
  • 动态调整: 根据实际使用情况动态调整布隆过滤器的参数（如位数组大小和哈希函数数量）或重建过滤器。
  • 分层过滤器: 使用多个不同参数的布隆过滤器分层过滤，降低每层的误判率。
3.如何在插入超过预期数量的元素时处理布隆过滤器的误判率增加问题？

可以使用可扩展布隆过滤器（Scalable Bloom Filter），它通过创建多个布隆过滤器并在每个过滤器达到容量限制时添加新的过滤器来动态扩展。每个新的过滤器都有不同的误判率，这样可以在保证误判率上限的同时扩展容量。

4.布隆过滤器可以合并吗？如何实现？误判率会增加吗？

可以合并两个相同大小、使用相同哈希函数的布隆过滤器。合并操作是对两个布隆过滤器的位数组进行按位或操作。例如：

BitSet mergedBitSet = (BitSet) ();
(bitSet2);

合并后的布隆过滤器包含两个原始过滤器中的所有元素，但误判率也会增加。

的Guava库提供了高效的布隆过滤器实现，如果使用其现成的内容，上面代码该如何实现？

优点: 易用且经过优化，直接上代码：

import ;
import ;

/**
 * @program: zyfboot-javabasic
 * @description: 布隆过滤器
 * @author: zhangyanfeng
 * @create: 2021-08-10 22:49
 **/
public class BloomFilterExample {
    public static void main(String[] args) {
        BloomFilter<CharSequence> bloomFilter = (
                (Charsets.UTF_8), 2000000000, 0.01);
        
        // 添加URL到布隆过滤器
        ("");
        
        // 查询URL是否在布隆过滤器中
        (("")); // true
        (("")); // false
    }
}
的BloomFilter是如何控制误判率和内存使用的？

通过两个参数来控制：预计插入的元素数量和期望的误判率。布隆过滤器会根据这两个参数来计算所需的位数组大小和哈希函数数量。位数组越大，误判率越低；哈希函数越多，误判率越低，但插入和查询时间也会增加。

的BloomFilter是否支持扩展，即动态增加元素后仍保持较低的误判率？

Guava的BloomFilter不支持动态扩展。一旦初始化了位数组大小和哈希函数数量，它们是固定的。如果实际插入的元素数量超过预期，会导致误判率上升。解决方案之一是使用可扩展布隆过滤器（Scalable Bloom Filter），但这需要自己实现，Guava没有直接提供这种功能。

的BloomFilter是线程安全的吗？如果不是，如何确保线程安全？给出实现？

Guava的BloomFilter本身不是线程安全的。为了在多线程环境中安全地使用Guava的BloomFilter，我们可以采用多种策略来确保线程安全：

  • 显式锁: 简单直接，但可能会导致较高的锁竞争。
  • 并发集合: 通过分片减少竞争，但增加了复杂度和内存开销。
  • 读写锁: 提高读操作的并发性，但复杂度相对较高。

现在可以选择任意方式进行代码实现。

方法1：显式锁---使用显式锁可以确保在对BloomFilter的每次访问（读或写）时，都只有一个线程能够执行操作。
import ;
import ;

import ;
import ;
import ;

public class ThreadSafeBloomFilter<T> {
    private final BloomFilter<T> bloomFilter;
    private final Lock lock;

    public ThreadSafeBloomFilter(int expectedInsertions, double falsePositiveProbability) {
         = ((("UTF-8")), expectedInsertions, falsePositiveProbability);
         = new ReentrantLock();
    }

    public void put(T element) {
        ();
        try {
            (element);
        } finally {
            ();
        }
    }

    public boolean mightContain(T element) {
        ();
        try {
            return (element);
        } finally {
            ();
        }
    }
}
方法2：使用并发集合---在这种方法中，我们将多个布隆过滤器分片存储在一个并发集合（如ConcurrentHashMap）中，通过将元素散列到不同的布隆过滤器分片来减少争用。
import ;
import ;

import ;
import ;

public class ConcurrentBloomFilter<T> {
    private final ConcurrentHashMap<Integer, BloomFilter<T>> bloomFilters;
    private final int numberOfFilters;

    public ConcurrentBloomFilter(int numberOfFilters, int expectedInsertions, double falsePositiveProbability) {
         = new ConcurrentHashMap<>();
         = numberOfFilters;
        for (int i = 0; i < numberOfFilters; i++) {
            (i, ((("UTF-8")), expectedInsertions, falsePositiveProbability));
        }
    }

    private int getFilterIndex(T element) {
        return () % numberOfFilters;
    }

    public void put(T element) {
        int index = getFilterIndex(element);
        (index).put(element);
    }

    public boolean mightContain(T element) {
        int index = getFilterIndex(element);
        return (index).mightContain(element);
    }
}
方法3：使用ReadWriteLock---使用ReadWriteLock可以在读操作不需要互斥的情况下提高并发性，只有在写操作时才进行锁定。
import ;
import ;

import ;
import ;
import ;

public class ReadWriteLockBloomFilter<T> {
    private final BloomFilter<T> bloomFilter;
    private final ReadWriteLock readWriteLock;

    public ReadWriteLockBloomFilter(int expectedInsertions, double falsePositiveProbability) {
         = ((("UTF-8")), expectedInsertions, falsePositiveProbability);
         = new ReentrantReadWriteLock();
    }

    public void put(T element) {
        ().lock();
        try {
            (element);
        } finally {
            ().unlock();
        }
    }

    public boolean mightContain(T element) {
        ().lock();
        try {
            return (element);
        } finally {
            ().unlock();
        }
    }
}

相关文章