布隆过滤器bloom

使用布隆过滤器来过滤掉DB中不存在的数据，有效减少缓存穿透发生的可能性。

先简述一下大致过程：

将DB中的数据进行哈希运算（一般要进行几次的运算），在计算出的位置上存值为1。有请求进来先访问redis缓存，发现该数据不存在，则再去访问布隆过滤器，经过哈希运算得到该位置上的数据。如果为1说明DB中存在该数据，则访问DB中的具体数据，否则不访问DB。从而减少DB的访问量。

下面看一下bloom工作的具体过程：

布隆过滤器由「初始值都为 0 的位图数组」和「 N 个哈希函数」两部分组成。当我们在写入数据库数据时，在布隆过滤器里做个标记，这样下次查询数据是否在数据库时，只需要查询布隆过滤器，如果查询到数据没有被标记，说明不在数据库中。

布隆过滤器会通过 3 个操作完成标记：

第一步，使用 N 个哈希函数分别对数据做哈希计算，得到 N 个哈希值；
第二步，将第一步得到的 N 个哈希值对位图数组的长度取模，得到每个哈希值在位图数组的对应位置。
第三步，将每个哈希值在位图数组的对应位置的值设置为 1；
举个例子，假设有一个位图数组长度为 8，哈希函数 3 个的布隆过滤器。

 

在数据库写入数据 x 后，把数据 x 标记在布隆过滤器时，数据 x 会被 3 个哈希函数分别计算出 3 个哈希值，然后在对这 3 个哈希值对 8 取模，假设取模的结果为 1、4、6，然后把位图数组的第 1、4、6 位置的值设置为 1。当应用要查询数据 x 是否数据库时，通过布隆过滤器只要查到位图数组的第 1、4、6 位置的值是否全为 1，只要有一个为 0，就认为数据 x 不在数据库中。

布隆过滤器由于是基于哈希函数实现查找的，高效查找的同时存在哈希冲突的可能性，比如数据 x 和数据 y 可能都落在第 1、4、6 位置，而事实上，可能数据库中并不存在数据 y，存在误判的情况。可以通过增加hash运算的次数来减少hash冲突，减少误判。（因为运算越多，那么想要出现所有位置上都为1的概率就会下降，自然误判也就减少。但是运算次数越多，所需数组长度也越大，运算速度也会减慢，所以要根据实际业务需求来实现）。

所以，查询布隆过滤器说数据存在，并不一定证明数据库中存在这个数据，但是查询到数据不存在，数据库中一定就不存在这个数。

原文链接：https://blog.csdn.net/qq_34827674/article/details/123463175