布隆过滤器

发布日期: 2022-04-16

文章字数: 2.6k

阅读时长: 9 分

阅读次数:

简介

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

原理

通常判断某个元素是否存在用什么？

HashMap 确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率很高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。

一个 MAC 地址需要占用六个字节。
HashMap：一亿个地址大约要 573MB，即六亿字节的内存
Bloom Filter：一亿个地址，千分之一误报率，大约需要171MB

是一种数据结构，其主要功能是判断某个元素是否出现在集合中。
它通过使用多个哈希函数将元素映射到一个位数组中，并将对应位标记为1，来实现对元素的判重。
如果一个元素在位数组中对应的位置上有一位为0，那么该元素一定不存在于集合中，
如果所有对应位都为1，那么该元素可能存在于集合中。

布隆过滤器主要做用就是查询一个数据，在不在这个二进制的集合中，过程如下：

经过K个哈希函数计算该数据，对应计算出的K个hash值
经过hash值找到对应的二进制的数组下标
判断：如果存在任意一位为0，那么该元素不存在于集合中。如果所有位都为1，那么该元素可能存在于集合中，需要进一步确认。

误判率取决于哈希函数的数量和位向量的长度

举例：

假设有3个hash函数，key1 通过3个hash函数生成hash值对数组长度取模得到下标分别为1、5、7，key1 通过3个hash函数生成hash值对数组长度取模得到下标分别为2、4、7。

当我们查询key3时，假设下标为1，4，5发现三个位置都为1，那么key3一定存在么？不一定，key3可能存在。因为随着增加的值越来越多，被置为1的位置越来越多，具有一定概率的误判性。（不同值计算出来的hash值有可能相同，hash值不同，原值一定不同）

公式

m代表bit位的数量（字节数组长度）， n代表插入的元素个数，k代表hash函数个数，p代表误报率

计算hash函数数量

当m/n=10的时候我们需要的k元素数量为7，也就是7个哈希函数才能实现一个比较低的误报率。

计算需要字节数

下图是布隆过滤器误报率 p 与位数组大小 m 和集合中插入元素个数 n 的关系图，假定 Hash 函数个数选取最优数目

在线布隆计算器：https://hur.st/bloomfilter/

假定插入元素个数n=1亿，误报率为千分之一，则预计字节数组大小为171MB，hash函数个数为10

优缺点

优点

因为存储的是二进制数据，因此占用的空间很小
它的插入和查询速度是很是快的，时间复杂度是O(K)
保密性很好，由于自己不存储任何原始数据，只有二进制数据

缺点

存在一定误报率
需要预估插入数据量，超过则误报率大大提升
不能删除（Counting Bloom filter 计数过滤器提供了一种在Bloom过滤器上实现删除操作而无需重新创建过滤器的方法）

应用

Dmp数据营销项目使用布隆过滤器来判断是否推送过广告。
Pwc爬虫使用布隆过滤器来判断是否爬取过url。
Google Bigtable、Apache HBase和Apache Cassandra和PostgreSQL 使用布隆过滤器来减少对不存在的行或列的磁盘查找。避免昂贵的磁盘查找可显着提高数据库查询操作的性能。
Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。
Microsoft Bing搜索引擎对其搜索索引BitFunnel使用多级分层布隆过滤器。
Redis 缓存穿透

Bloom filter used to speed up answers in a key-value storage system. Values are stored on a disk which has slow access times. Bloom filter decisions are much faster. However some unnecessary disk accesses are made when the filter reports a positive (in order to weed out the false positives). Overall answer speed is better with the Bloom filter than without the Bloom filter. Use of a Bloom filter for this purpose, however, does increase memory usage
在很多Key-Value系统中使用了布隆过滤器来加快查询过程，Value 保存在访问时间较慢的磁盘中，布隆过滤器可以快速判断某个Key对应的Value是否存在，然而某些误报会导致磁盘访问磁盘。总体来说，使用Bloom过滤比不使用Bloom过滤的应答速度更快，但是是引入布隆过滤器会带来一定的内存消耗

MAC、CMEI、SN去重

有个业务场景，MAC、CMEI、SN导入或者生成时需要去重，源数据是保存在MySQL中，虽然有索引，但是每次导入几万数据使用查询来去重很耗时间，我们最终选择使用Redis Bitmap来解决这个问题

Redis Bitmap

Bitmap：是一种Bit数组数据结构，它的主要作用是储存0和1两个状态

内存占用

在Redis中，Bitmap通过字符串来实现，一个字符串可以存储超过2^32个元素，所以一个bloom能存储的最大上限就是2^32个，约42.9亿。

在redis底层bitmap 和string 其实是同一个结构，只是提供了不同的命令来进行操作，想要看一个redis 对象占用多少内存可以使用 MEMORY USAGE Key，返回的是字节数：

Bitmap内存分配

这里有个需要注意的问题是，如果index比较大，比如在10亿位上写1，那么redis在内存分配时其实是分配了一个完整的10亿长度的数组（10亿位是1，前面的全部补0）。

可以理解为是一个非常长的字符串，而不是下意识我们想象很简单的1个bit那么小，它瞬间分配的内存大概在128M

Bitmap读取

既然一个10亿位的bitmap需要128M内存，那么很直接的想法就是，这么大的内存，bitmap读起来会慢吗？结论当然是不会的。

因为bitmap是一个位数组，它在内存中是连续的，CPU并不需要去读取完整的128M内存，它只要获取到这个数组起始位置 + index 就可以计算出对应的位置然后进行读取，也就是说，它的时间复杂度是 O(1)

虽然读操作是O(1)的，但是很显然创建一个大的bitmap时是非常重量级的一个操作，布隆过滤的Hash函数计算基本都是32位，64位长度的Hash值

我们无法控制bitmap的增长是一个顺序过程，所以最直接的办法就是控制最大长度

分片 – Roaring Bitmap

规划MAC、CMEI、SN数据总量要有1亿+，肯定不能都放入一个Bitmap中，这样就会有个非常大的key，最简单的优化方向就是分片

MAC是48位6字节，保存为字符串就是12字节000E1FA338E5，而CMEI是15个字节，类似111037060001000

Roaring Bitmap (RBM)就是类似的算法，RBM 的主要思想并不复杂，简单来讲，有如下三条：

范围划分：将 32-bit 的范围 ([0, n)) 划分为 2^16 个桶，每一个桶有一个 Container 来存放一个数值的低16位；
存储：在存储和查询数值的时候，将一个数值 k 划分为高 16 位(k % 2^16)和低 16 位(k mod 2^16)，取高 16 位找到对应的桶，然后在低 16 位存放在相应的 Container 中；
查询判断：当查询一个数值 k 是否存在时，我们只需要判断 k mod 2^16 是否存在于对应的 Container 中即可。

821697800 对应的 16 进制数为 30FA1D08，其中高 16 位为 30FA，低16位为 1D08。

找到数值为 30FA 的容器（如果该容器不存在，则新建一个）。

这里用 Bitmap 做存储，找到了相应的容器后，看一下低 16 位的数值 1D08，它相当于是 7432，因此在 Bitmap 中找到相应的位置，将其置为 1 即可。