一种可扩容布隆过滤器设计

问题

猜想

上一篇文章，我们说到了怎么去实现简单的布隆过滤器，同时也提到了以下几个点：

布隆过滤器由于哈希冲突可能会存在误判；
BitSet长度以及哈希函数的数目和冲突有关；
BitSet长度以及哈希函数的数目由预计放入的元素数目和预期误判率计算得出。

从中，我们可以猜测：当实际放入过滤器中的元素多于预期时，布隆过滤器的效果会受到负面影响。

验证

我们采用实际的误判率（误拒率，某一原本不在集合中的元素却被检测为在该集合中的概率）作为评价指标。预计放入的元素均为[0,n)的整数，每一组测试均使用[20000,23000)共3000个不在集合内的元素。

预计放入元素数目	预计误判率	实际放入元素数目	实际误判率
5000	0.01	4000	0.0003
5000	0.01	6000	0.0083
5000	0.01	8000	0.0427
5000	0.01	10000	0.1393
5000	0.01	20000	0.7573

预计放入元素数目	预计误判率	实际放入元素数目	实际误判率
5000	0.001	4000	0.0000
5000	0.001	6000	0.0007
5000	0.001	8000	0.0090
5000	0.001	10000	0.0357
5000	0.001	20000	0.5483

可以看到，超量加入元素的确对过滤器效果有较大影响。

方案

在现实中，遇到这种超过预期的情况，最好的方法依然是重建过滤器。但是重建有一定的成本，不一定方便立刻重建。因此，可以设计扩容功能，短时间牺牲一些性能来保证准确率。在条件合适的时候再重建。

目前，对于扩容，一种比较不错的方法是并联多个过滤器，也就是使用多个BitSet。写入时，只在最新的过滤器写入；判断时，遍历各个过滤器，只要有一个判定存在则返回存在。

最后一个问题便是什么时候扩容。我认为，除了超过预计容量时需要扩容之外，应该设定一个扩容因子，当最新的布隆过滤器内1的比例超过该因子时，也要扩容。

实现

变量

static final int DEFAULT_INITIAL_CAPACITY = 1000;
static final double DEFAULT_INITIAL_MISJUDGMENT_RATE = 0.01f;
static final double DEFAULT_GROW_FACTOR = 0.5f;

// 布隆过滤器列表
List<BloomFilter> bloomFilters;
// 最新的布隆过滤器
BloomFilter curBloomFilter;
// 预计容量
int capacity;
// 预计误判率
double misjudgmentRate;
//当前容量
int size = 0;
// 布隆过滤器数目
int numBloomFilter = 0;
// 扩容因子(最新的布隆过滤器中1的比例)
double growFactor = DEFAULT_GROW_FACTOR;

构造函数

/**
 * 使用默认的元素个数(1000)、默认误判率(0.01)、默认扩容因子(0.5)构建一个布隆过滤器
 *
 * @author: loststar
 * @time: 2022/2/5 21:56
 */
public ScalableBloomFilter() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_INITIAL_MISJUDGMENT_RATE, DEFAULT_GROW_FACTOR);
}

/**
 * 使用指定的元素个数、默认误判率(0.01)、默认扩容因子(0.5)构建一个布隆过滤器
 *
 * @param capacity 元素个数
 * @author: loststar
 * @time: 2022/2/5 21:58
 */
public ScalableBloomFilter(int capacity) {
    this(capacity, DEFAULT_INITIAL_MISJUDGMENT_RATE, DEFAULT_GROW_FACTOR);
}

/**
 * 使用指定的元素个数、指定的误判率、默认扩容因子(0.5)构建一个布隆过滤器
 *
 * @param capacity        元素个数
 * @param misjudgmentRate 误判率
 * @author: loststar
 * @time: 2022/2/5 21:58
 */
public ScalableBloomFilter(int capacity, double misjudgmentRate) {
    this(capacity, misjudgmentRate, DEFAULT_GROW_FACTOR);
}

/**
 * 使用指定的元素个数、指定的误判率、指定的扩容因子构建一个布隆过滤器
 *
 * @param capacity        元素个数
 * @param misjudgmentRate 误判率
 * @param growFactor      扩容因子
 */
public ScalableBloomFilter(int capacity, double misjudgmentRate, double growFactor) {
    this.capacity = capacity;
    this.misjudgmentRate = misjudgmentRate;
    bloomFilters = new ArrayList<>();
    grow();
}

添加（关键）

在这个函数内，我们先判断当前容量是否已经超过多个布隆过滤器的总容量，以及最新的布隆过滤器内1的占比是否超过扩容因子。如果需要扩容，则调用grow方法进行扩容，如果不需要则正常在最新的过滤器添加。

/**
 * 向布隆过滤器添加一个元素，同时判断是否需要扩容
 *
 * @param value 要添加的元素
 * @return: void
 * @author: loststar
 * @time: 2022/2/5 22:00
 */
public void add(T value) {
    if (size / numBloomFilter > capacity || curBloomFilter.calculateTrueBitProportion() > growFactor) {
        grow();
    }
    size++;
    curBloomFilter.add(value);
}

扩容

/**
 * 扩容函数
 *
 * @author: loststar
 * @time: 2022/2/5 22:01
 */
private void grow() {
    curBloomFilter = new BloomFilter<T>(capacity, misjudgmentRate);
    bloomFilters.add(curBloomFilter);
    numBloomFilter++;
}

判断

判断每一个内是否存在

/**
 * 判断元素是否在布隆过滤器内
 *
 * @param value 被判断的元素
 * @return: boolean
 * @author: loststar
 * @time: 2022/2/5 22:00
 */
public boolean contains(T value) {
    for (BloomFilter bloomFilter : bloomFilters) {
        if (bloomFilter.contains(value)) {
            return true;
        }
    }
    return false;
}