布隆过滤器

1076字约4分钟

大数据算法

2024-03-12

使用背景

布隆过滤在我们项目中的使用和提出背景: 智能抽图, 图配置连边的时候, 要寻找主键的外键, 需要进行数据相似计算.

目前, 因为内存的限制, 两边分别采样计算相似率colFullMatch(task.a.Values, task.b.Values)/sampleRate, 存在很大的不确定性.

解决的方法就是使用布隆过滤, 一边全量, 一边采样. 全量数据存储在布隆过滤器, 通过存在性判断计算采样数据的相似度.

布隆过滤

布隆过滤器是一种具有空间优势的概率数据结构, 核心就是一个超大的位数组和哈希函数, 用于回答一个元素是否存在于一个集合中这样的问题, 但是可能会出现误判——即一个元素不在集合但被认为在集合中.

布隆过滤基本原理

给定长度为 N个bits 的哈希空间.
选取 d 个哈希函数, 每个哈希函数将给定的元素映射到[0, N-1]的一个位置上, 并将该位置为 1.
将需要被判断的元素也用 2 中的 d 个哈希函数算出 d 个位置 a1,a2,...,ad
如果 a1,a1,...,ad 对应的位有一个不为 1, 则该元素一定不在集合中.
如果 a1,a1,...,ad 对应的位全为 1, 则该元素可能存在于集合中.

从上面可以看出, 一个布隆过滤器应该起码有以下参数:

哈希空间大小, 记为m. 以上示例中 m = 20 bits;
元素集合大小, 记为n. 以上示例中 n = 2;
哈希函数个数, 记为k. 以上示例中 k = 2;
因为 BF 是 Allowable Errors 的, 可能会出现一个元素原本不在集合中, 但是被错判为存在于集合中, 这个错判的概率叫 false postive, 记为ε

错误率最小, 各个参数之间的关系:

$k = \frac{m}{n} \ln2$

$m = - \frac{n \ln \epsilon}{{\left( \ln 2 \right)}^2 }$

$\frac{m}{n}=- \frac{\log_2 \epsilon}{\ln 2} \approx -1.44 \log_2 \epsilon$

如何选择哈希函数-murmur3

从概率计算和速度角度, 哈希函数需满足:

1）独立、均匀分布.

2）计算速度快.

优缺点

优点: 内存效率高、查询速度快、可并行处理;

缺点: 误判率, 主要取决于哈希函数的数量和位数组的大小, 哈希冲突;不支持删除、不能获取原始数据, 误判率.

优化: 较大的位数组可以降低误判率, 但会增加内存消耗, 因此需要权衡.

应用

数据库防止穿库. 使用BloomFilter来减少不存在的行或列的磁盘查找. 避免代价高昂的磁盘查找会大大提高数据库查询操作的性能.

业务场景中判断用户是否阅读过某视频或文章, 比如抖音或头条, 当然会导致一定的误判, 但不会让用户看到重复的内容.

m, k := bloom.EstimateParameters(uint(len(md)), 0.001)
filter := bloom.New(m, k)
for d := range md {
    if len(d) == 0 {
        continue
    }
    filter.Add([]byte(d))
}
if filter.Test([]byte(d)) {
    fmt.print("数据存在!")
}

性能比较

输入数据量0.01	bloom内存/CPU峰值	map内存/CPU峰值	内存节省
1w	0.8MB	1.18MB	32.5%
5w	1.5MB	3.3MB	54.5%
10w	1.37MB	3.66MB	62%
50w	2.24MB	23.2MB	90%
100w	2.7MB	46.1MB	94%
500w	9.3MB	191.4MB	95%
1000w	17.6MB	382.5MB	95%
5000w	61.7MB	1705.2MB	96%

内存占用bloom减少60%-90%+的内存占用

全量插入+全量查询, 耗时记录:

输入数据量0.01	bloom查询耗时	map查询耗时	耗时增加
1w	1+1=2ms	508+508=1ms	200%
5w	5.6+4.8=10.5ms	3.2+3.0=6.3ms	166%
10w	12+9.6=21.8ms	9+6=15ms	145%
50w	61.1+52.1=113.2ms	51.6+47.6=99.1ms	114%
100w	125.9+109.4=235.3ms	136.5+121.5=258ms	91%
500w	665.5+592=1.26s	723.5+711.8=1.4s	90%
1000w	1.87+1.5=3.9s	1.48+1.4=2.9s	134%
3000w	16.5s	9.8s	168%
5000w	15+13=28s	7.6+7.6=15.2s	184%

本文参考资料