布隆过滤器(Bloom Filter):如何在海量数据中轻松找到你要的答案?

2024-10-09 21:36:40 浏览数 (2)

一、背景

无论是红黑树、平衡二叉树、散列表,结点都是存储的key-value对。而有些场景,内存是有限的,仅需要了解key是否存在,不想知道具体内容(value)。

这时就需要布隆过滤器。布隆过滤器是一种概率型数据结构,它的特点是高效的插入和查询,能确定某个字符串一定存在或者可能存在。

布隆过滤器不存储具体数据,所以占用空间小,查询结果存在误差,但误差可控,同时不支持删除操作。

(1)一个巨大的数据文件,需要知道是否存在某个key,如果把整个文件读取进行查找,这个效率就比较低。那么可以添加一个布隆过滤器,插入数据时对key做标识,查询key是否存在时直接查询布隆过滤器。

(2)一个数据库查询,想要查询数据库中是否存在key,可以添加一个布隆过滤器,查询key时直接查询布隆过滤器,不需要IO操作,大大提升查询效率。

二、布隆过滤器的构成

布隆过滤器的原理本质上和散列表是一样的。但布隆过滤器为了节约内存,不是使用的数组,而是使用的位图。

(1)位图。

bit的数组,实现方式有多种。

代码语言:javascript复制
// 例如
vector<char> bitmap;
uint64_t bitmap;

(2)n个hash函数。

举例: 使用byte buf[8]构建64bit的位图,那么n=i*8 j;假设hash(key)=173,n=173d=173&63=45,j=n%8=45%8=5,i=n/8=45/8=5。因此将(5,5)位置置 1。

bit

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

1

6

7

8

三、原理

当一个元素加入位图时,通过k个hash函数将元素映射到位图的k个点,并把它们置1;当检索时,再通过k个hash函数运算检查位图的k个点是否都为1;如果有不为1的点,那么认为该key不存在;如果全部为1,则可能存在。

布隆过滤器是不支持删除操作的,原因在于:在位图中每个槽位只有两种状态(0或者1),一个槽位被置为1,但不确定它被设置了多少次;也不知道被多少个key hash映射而来;以及具体被哪个hash函数映射而来。

值得注意的是,只要有一个槽位为0,则key一定不存在;如果key映射的所有槽位都为1,不能说明一定存在,只能说明可能存在(假阳率)。

图片图片

四、应用场景

布隆过滤器通常用于判断某个key一定不存在的情况。同时允许判断存在时有误差的情况。

常见处理场景:

(1)缓存穿透的解决。

(2)热key限流。

缓存场景:为了减轻数据库(MySQL)的访问压力,在数据库(MySQL)和服务端(server)直接加入缓存用来存储热点数据。

缓存穿透:服务端(server)请求数据时,缓存和数据库都不包含数据,最终请求压力全部涌向数据库。

数据请求步骤:

先访问redis,如果存在则直接返回,如果不存在则走2访问数据库;

访问数据库,如果不存在直接返回,如果存在则将MySQL存在的key写回redis。

发生原因:黑客利用漏洞伪造数据攻击或内部业务bug造成大量重复请求不存在的数据。

解决方案:

(1)在redis设置<key,null>键值对,依次避免访问数据库;缺点是<key,null>过多会占用过多内存,可以给key设置过期expire key 600ms,停止攻击后最终由redis自动清除无用的key。

(2)在服务端(server)存储一个布隆过滤器,将MySQL存在的key放入布隆过滤器中,布隆过滤器可以过滤一定不存在的数据。

五、应用分析

在实际应用中,该选择多少个 hash 函数?要分配多少空间的位图?预期存储多少元素?如何控制误差?

可以使用如下公式计算:

n = ceil(m / (-k / log(1 - exp(log(p) / k))))

p = pow(1 - exp(-k / (m / n)), k)

m = ceil((n * log(p)) / log(1 / pow(2, log(2))));

k = round((m / n) * log(2));

其中

n -- 预期布隆过滤器中元素的个数,如上图 只有str1和str2 两元素 那么 n=2

p -- 假阳率,在0-1之间 0.000000

m -- 位图所占空间

k -- hash函数的个数

数学公式:

图片图片

5.1、变量关系

假设:

n = 6000

p = 0.000000001

m = 258797 (31.59KiB)

k = 30

得到如下关系图:

图片图片

(1)假阳率p会随着插入元素的增多而逐渐变高。

(2)假阳率p会随着位图所占空间的增大而减小。

(3)假阳率p会随着hash函数个数增多,呈现快速减小后缓慢增长的趋势。hash函数个数在31时假阳率最低。

5.2、确定n和p

在实际使用布隆过滤器时,首先需要确定 n 和 p,通过上面的运算得出 m 和 k;推荐一个布隆过滤器计算器可以选出合适的值。

5.3、选择hash函数

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

代码语言:javascript复制
#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 是位图的⼤⼩
}

六、总结

  1. 布隆过滤器由位图和n个hash函数构成。布隆过滤器的操作是一个key经过多个hash函数,然后对位图大小进行取余等到多个槽位并对应置为1。判断时只要有一个槽位为0就一定不存在该key。
  2. 布隆过滤器能确定一个key一定不存在,不能判断key一定存在,但可控假阳率确定存在。
  3. 布隆过滤器不支持删除操作,可以通过两个布隆过滤器解决(依然存在假阳率,但会低一些),添加放在第一个布隆过滤器,删除放在第二个布隆过滤器。即要判断key是否存在,首先检查第二个布隆过滤器是否删除过,如果删除过就往第一个布隆过滤器插入。
  4. 布隆过滤器根据n和p算出m和k,hash函数个数是利用开放寻址法来计算的。

0 人点赞