布隆过滤器

背景

1. 在比特币网络中，如何快速避免交易的重复验证，提高效率？
2. 在大规模数据处理中，如何过滤掉不必要的数据，提高查询速度和减少网络带宽的占用？
3. 在Redis缓存中，如何避免缓存击穿问题？
4. 在解决垃圾邮件过滤、评论去重等问题时，如何高效地判断一个字符串是否已经存在于已有数据集中，从而实现快速过滤或去重？
5. 网络爬虫程序，怎么让它不去爬相同的url页面？

原理

布隆过滤器（Bloom Filter）是基于一组哈希函数和一个位数组实现的。具体来说，它可以被看作是一个长度为 m 的位数组和 k 个哈希函数的集合。

在向布隆过滤器中添加一个元素时，会将这个元素经过 k 个哈希函数的计算得到 k 个哈希值，然后将这 k 个哈希值对应的位数组位置设为 1。

在查询某个元素是否在布隆过滤器中时，同样需要将这个元素经过 k 个哈希函数的计算得到 k 个哈希值，然后检查这 k 个哈希值对应的位数组位置是否都为 1，若都为 1，则说明该元素可能存在于布隆过滤器中，否则该元素一定不存在于布隆过滤器中。

由于哈希函数的作用，不同的元素可能会得到相同的哈希值，从而导致不同元素在位数组上的位置发生冲突。这就意味着，布隆过滤器在判断某个元素是否存在于其中时，可能会出现误判，即将一个不存在于布隆过滤器中的元素判定为存在于其中。为了控制误判率，布隆过滤器需要设定合适的位数组长度 m 和哈希函数个数 k。较大的位数组长度和哈希函数个数可以降低误判率，但会占用更多的内存空间。

根据其原理得出的结论：

• 快速判断字符串的可能存在或者一定不存在。。
• 不存储具体数据，节省存储空间。
• 可以控制查询误差。
• 不支持删除操作。

网络爬虫程序url去重为什么不用散列表？

使用布隆过滤器进行网页去重，相比使用散列表判重，布隆过滤器在存储空间消耗上降低了非常多。例如，在需要判重的网页有10亿的情况下，使用散列表需要至少100GB的空间，而使用布隆过滤器只需要一个大小为10倍的位图，即大约1.2GB的存储空间。

如何避免缓存击穿问题？

• 在高并发场景下，缓存和数据库中都不存在某个被请求的数据，此时大量请求会直接击穿数据库，导致数据库压力过大，甚至宕机，整个系统也会瘫痪。
  • 解决方法一：可以在缓存中设置一个空值来过滤一定不存在的数据。但空值的Key太多的话，占用过多的内存。
  • 解决方法二：为了避免空值占用过多内存，使用布隆过滤器。

容量评估

那我们应该如何评估使用的数组是多长，hash算法使用几个？

可以通过 Bloom Filter Calculator 来评估容量。

• n：预期过滤器中的元素个数。
• p：误报概率。
• m：位图所占空间。
• k：哈希函数的数量。

只需要填写，相应的 n，p 就能评估出 m 所占空间和 k 所需哈希函数的数量。

选择一个 hash 函数，通过给 hash 传递不同的种子偏移值，采用线性探寻的方式构造多个 hash 函数；

1
2
3
4
5
6
7

#define MIX_UINT64(v) ((uint32_t)((v>>32)^(v)))
uint64_t hash1 = MurmurHash2_x64(key, len, Seed);
uint64_t hash2 = MurmurHash2_x64(key, len, MIX_UINT64(hash1));
for (i = 0; i < k; i++) // k 是hash函数的个数
{
	Pos[i] = (hash1 + i*hash2) % m; // m 是位图的⼤⼩
}