# BloomFilter

**Repository Path**: long-xu/bloom-filter

## Basic Information

- **Project Name**: BloomFilter
- **Description**: 这是一个布隆过滤器的源码。里面包含布隆过滤器的实现源码和三个使用示例。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-11-07
- **Last Updated**: 2023-11-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 布隆过滤器 (Bloom Filter)
## 3.1、背景
无论是使用散列表还是平衡二叉树（红黑树、B树、B+树等）的数据结构，都存储了key-value值。而有些场景，内存是有限的，仅需要了解key是否存在，不想知道具体内容（value）。这时就需要布隆过滤器。

布隆过滤器是一种概率型数据结构，它的特点是高效的插入和查询，能确定某个字符串一定存在或者可能存在。
布隆过滤器不存储具体数据，所以占用空间小，查询结果存在误差，但误差可控，同时不支持删除操作。

布隆过滤器的使用场景：
（1）一个巨大的数据文件，需要知道是否存在某个key，如果把整个文件读取进行查找，这个效率就比较低。那么可以添加一个布隆过滤器，插入数据时对key做标识，查询key是否存在时直接查询key是否在布隆过滤器，从而判断key是不是存在文件中。布隆过滤器仅仅只能判断key是否存在，不能获得value值。
（2）一个数据库查询，想要查询数据库中是否存在key，可以添加一个布隆过滤器，查询key时直接查询布隆过滤器，不需要IO操作，大大提升查询效率。
## 3.2、布隆过滤器的构成
布隆过滤器的原理本质上和散列表是一样的。但布隆过滤器为了节约内存，不是使用的数组，而是使用的位图（bitmap）。位图的特点是它的槽位只有两种状态：0或者1。

（1）**位图**。bit的数组，实现方式有多种。

```cpp
// 例如
vector<char> bitmap;// 一个字节，8个bit位
uint64_t bitmap;
```
（2）**n个hash函数**。

映射关系计算公式：m % $2^n$ = m &($2^n-1$)

举例：
使用`byte buf[8]`构建64 bit 的位图，那么n=i*8+j；假设hash(key)=173，先对总长度$8\times8$ = 64取余：n=173%64=173&63=45；然后对宽度8进行取余：j=n%8=45%8=5；最后再对宽度8进行整除：i=n/8=45/8=5。因此得到坐标（5，5）位置将其置 1。

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

布隆过滤器是不支持删除操作的，原因在于：
- 在位图中每个槽位只有两种状态（0或者1），一个槽位被置为1，但不确定它被设置了多少次；也不知道被多少个key hash映射而来；以及具体被哪个hash函数映射而来。
- 只要有一个槽位为0，则key一定不存在；如果key映射的所有槽位都为1，不能说明一定存在，只能说明可能存在（假阳率）。


如上图，位图长度未知，有两个key，三个hash函数。这个怎么进行操作的呢？
- 存储：首先将`str1`分别依次对三个hash函数进行hash，然后就可以在位图中锁定三个存储位置并相应的置为1。`str2`也同样的经过三个hash函数得到三个存储位置并相应的置为1。
- 搜索：将key通过三个hash函数进行hash，找到在位图上具体的位置，只要发现其中有一个位置的值为0，则这个key肯定不存在；因为如果key存在，那么所有位置都应该是1。注意，即使所有都为1，不能说明该key一定存在，因为有假阳率。

布隆过滤器可以判断一个key一定不存在，不能判断一个key一定存在。布隆过滤器中的位图大小远远大于要存储的数据。

布隆过滤器的假阳率是可控的，可以通过配置来控制假阳率。

## 3.4、应用场景
前面介绍了布隆过滤器的原理，除了原理还需要掌握如何利用布隆过滤器解决实际问题。布隆过滤器通常用于判断某个 key 一定不存在的场景，同时允许判断存在时有误差的情况。
常见处理场景：
- 缓存穿透的解决。
- 热 key 限流。

缓存场景：为了减轻数据库（mysql）的访问压力，在server 端与数据库（mysql）之间加入缓存用来存储热点数据。
缓存穿透：server端请求数据时，缓存和数据库都不包含该数据，最终请求压力全部涌向数据库。


数据请求步骤，如图中 2 所示：
1. 先访问redis，如果存在则直接返回，如果不存在则走2访问数据库；
2. 访问数据库，如果不存在直接返回，如果存在则将MySQL存在的key写回redis。

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

解决方案，如图中 3 所示：
- 在redis设置<key，null>键值对，依次避免访问数据库；缺点是<key，null>过多会占用过多内存，可以给key设置过期expire key 600ms，停止攻击后最终由redis自动清除无用的key。
- 在服务端（server）存储一个布隆过滤器，将MySQL存在的key放入布隆过滤器中，布隆过滤器可以过滤一定不存在的数据。


## 3.5、应用分析
在实际应用中，该选择多少个 hash 函数？要分配多少空间的位图？预期存储多少元素？如何控制误差？
通常有四个参数可以控制布隆过滤器。
- n ： 预期布隆过滤器中元素的个数，如上图 只有str1和str2 两元素 那么 n=2。
- p ： 假阳率，在0-1之间。
- m： 位图所占空间。
- k ： hash函数的个数。

可以使用如下公式计算：
`n = ceil(m / (-k / log(1 - exp(log§ / 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=\lceil m\div(-k\div\log(1-e^{(\log(p)\div k))}) \rceil
$$
$$
p=(1-e^{-k\div(m\div n)})^k
$$
$$
m=\lceil (n\times\log(p)) \div \log(1\div 2^{\log2} ) \rceil
$$
$$
round((m\div n)*\log2)
$$
假设：
n = 6000
p = 0.000000001 
m = 258797 (31.59KiB)
k = 30
得到如下关系图：
![bloomfitter](https://img-blog.csdnimg.cn/4f67e3871dea484fb6d491eaab1f2560.png)
（1）假阳率p会随着插入元素的增多而逐渐变高。
（2）假阳率p会随着位图所占空间的增大而减小。
（3）假阳率p会随着hash函数个数增多，呈现快速减小后缓慢增长的趋势。hash函数个数在31时假阳率最低。这里可以验证一个结论：在hash函数中，在31处出现冲突的概率最低。

**在实际使用布隆过滤器时，首先需要确定 n 和 p，通过上面的运算得出 m 和 k**；推荐一个[布隆过滤器计算器](https://hur.st/bloomfilter)可以选出合适的值。

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

```c
#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 是位图的⼤⼩
}
```
所谓不同的hash函数主要是seed不一样创造出来的。在实际应用中会有一个seed表，用于不断的计算偏移值。每次生成hash函数的时候会把seed值修改，通过不同的数值运算来得到hash函数。在使用过程中会先填充一个随机种子，然后进行偏移计算，最终得到所需的hash函数。

## 3.6、布隆过滤器的实际使用
为了避免篇幅过长，代码已经上传到gitee，感兴趣可以点击了解。里面包含布隆过滤器的实现源码和三个使用示例。

布隆过滤器的接口分为两个部分：
1. 计算所需的四个参数：n、p、m、k；主要是根据n、和p计算出m和k。利用一个类封装好，包含计算m、k的值。
2. 布隆过滤器。会准备一个位图，实现插入元素的接口，定义hash函数的最大个数，确定布隆过滤器的长度，预期插入元素的个数，已经插入元素的个数，seed随机值，具体的假阳率等等。

使用过程：先插入，然后contain。
## 3.7、小结
布隆过滤器的特征：
- 能确定一个key一定不存在，可控假阳率确定存在。
- 不能删除。可以通过准备两个布隆过滤器来解决删除时也降低假阳率，添加放在第一个布隆过滤器，删除放在第二个布隆过滤器。判断key是否存在时先判断key是否在第二个布隆过滤器（目的是检查之前是否删除过该key），如果之前删除过该key，就可以将该key加入第一个布隆过滤器。