布隆过滤器(Bloom Filter)

2022-03-30 本文已影响0人 reflex

image.png

晚上和朋友开黑，他用的布隆，操作carry全场，不过我说的这个布隆的格挡技术不亚于这个英雄。

先来讲一个香皂盒的故事。

联合利华引进了一条香皂包装生产线，结果发现这条生产线有个缺陷：常常会有盒子里没装入香皂。总不能把空盒子卖给顾客啊，他们只得请了一个学自动化的博士后设计一个方案来分拣空的香皂盒。博士后拉起了一个十几人的科研攻关小组，综合采用了机械、微电子、自动化、X射线探测等技术，花了几十万，成功解决了问题。每当生产线上有空香皂盒通过，两旁的探测器会检测到，并且驱动一只机械手把空皂盒推走。
中国南方有个乡镇企业也买了同样的生产线，老板发现这个问题后大为发火，找了个小工来说:你他妈给老子把这个搞定，不然你给老子爬出去。小工很快想出了办法：他在生产线旁边放了台风扇猛吹，空皂盒自然会被吹走。

其实做软件开发的时候我们也会遇到很多类似的情况。

解决啥问题

我们的应用通常可以抽象成三部分，由请求处理、计算逻辑和数据存取三部分。根据性能瓶颈的侧重点不同，偏向计算逻辑
的叫CPU密集型应用，数据存取逻辑的是IO密集型。所以以前我在考虑架构优化的侧重点也就在计算逻辑，和数据存取最多。
这种优化的方式往往是从CPU计算的结构算法复杂度，或者是数据存储的类型，减少磁盘操作等等的优化。这些都是偏向于技术方面的。

但是从业务角度出发，往往有些场景，用特定的手段可以取到意想不到的效果。

缓存击穿

比如查询用户的信息，有些用户可能并不存在，那我们可能把基本信息查询放在了最前边(代码的第一行)，如果不存在就直接返回，就会避免后边的数据拼接和其他的IO查询。
但是一个用户基本信息的数据库查询还是会走一次IO。

在生产环境中，往往我们会对一些热点用户信息做缓存，但是也免不了恶意用户，抓住漏洞，大量请求不存在的用户信息，这些用户不存在缓存中，全部走磁盘IO 会给数据库带来非常大的压力。也就是造成了缓存击穿

解决方案

回写空值
过滤器

过滤器

可以在最外层根据用户ID 做一层缓存，把所有用户信息都放到缓存层，请求进来先经过缓存，发现没有该用户，则直接返回，那所有用户ID的缓存需要的空间应该会不少吧。

内存计算

为了方便计算内存占用，先来回顾一下计算机存储的基础知识。

1KB=1024字节
1024K=1M
1024M=1G
一个字节(KB)占8位
char是 2个字节 16位，char 最大值 65535
int 是4 个字节 32位 int 最大值 2147483647

哈希表

如果我们的数据量是千万级以内，我们可以用哈希表，利用hashMap 的的一些优势，碰撞扩容，拉链法解决冲突，然后演变红黑二叉树等等。我们甚至可以记录出现次数等额外信息。

连续数组

但是如果我们有一亿的用户量。将用户的信息放到缓存，还要支持快速查找，该怎么处理呢？

快速查找的方案有很多，比如放到数组里排好序，每个指针指向一个ID，二分法查找，时间复杂度 log n,
用什么数据结构存储呢，我们都知道 char 的取值范围是65535，所以最少要用int （最大2147483647）， int 是32位，4个字节，一亿个ID 耗费的内存就是 4亿/1000/1000 =400M，（大约估算）

位图BitMap

有没有更好的方法呢，再来分析一下我们的业务需求，要判断某个用户ID在一亿个数的集合中是否存在，先来分析用户的ID的取值范围，如果用int定义的用户ID的话，那最大是21 4748 3647，二十亿的大小，
我们可以开辟一个 20亿（大约）个连续内存空间，每一个空间表示一个用户ID，属性只有存在和不存在,我们使用最小的内存 bit(位)(0:不存在，1:存在)存储
这样的内存大小就是 20亿/8 /1000/1000=250M,而查找效率都用下标指针取值，一次取值 n1 就可以，这种方案明显就比上边的方案要好。(真的好吗？)

怎么来实现呢。这个时候我们的问题就变成了怎么用最小的内存空间bit(位)来标记一个数字。下来我们就用到了 位图的结构。

位图：数据结构

内部维护数组 char [M] [N];

位图在内部维护了一个M×N维的数组char[M][N]，在这个数组里面每个字节占8位，因此可以存储M×N×8个数据。假如要存储的数据范围为0～15，则只需使用M=1, N=2的数据进行存储。
在我们要存储的数据为{1,3,6,10,15}时，只需将有数据的位设置为1，表示该位存在数据，将其他位设置为0 ，如图所示

image.png

具体为啥要用char ，我也不知道。存40亿位的数大概需要 40亿/8/M/=N 的大小

然后来看看怎么初始化？怎么设置值？怎么取值？

位操作

这里会涉及到一些位操作

& : 0&1=0 ，0&0=0，1&1=1
| : 0|1=1，0|0=0，1|1=1
<< : 左移，高位舍去，如果高位舍去的是零相当于乘以2的N(左移位数)次， 1<<3 就是 0000 0001 变成 0000 1000
>> : 右移，低位舍去，如果低位舍去的是零相当于除以2的N(右移位数)次， 7>>3 就是 1111 1111 变成 0001 1111

位图中设置一个值也就是要设置一个char(16位)中的一位，要用到位运算 a|1<<n a代表原来的char ,n 代表第几位

  我们想设置char 中某一位 为1,可以与该位为1其他位都是0的一个二进制进行或运算
比如: 0000 0001 中想设置第三位 为1 则 用0000 1000 | 0000 0001=0000 1001

怎么得到某一位为1 其他位都是0 的数 可以用 1<< 左移，
1=0000 0001 
1<<3=000 1000

缺点

这样实现基本的用位图过滤就实现了，那我们再深入了解一下需求，如果我们的ID不是连续的而是非常离散稀疏的呢，举个极端的例子比如我们只有少量用户，一个ID是1，一个id是999 999 999 。
这样是不是造成了非常大的空间浪费，再比如我们的ID是Long 类型 64bit 的数据，大小=2048PB=2EB，这个量级的数据已经不是硬件(内存)所能承担的了。