布隆过滤器在亿级流量下的应用

一 什么场景需要使用布隆过滤器

我们来看一个实际的例子，下边是京东某商品的页面：

其地址为,其中，857这个数字就是其商品的sku，可以理解为唯一标志:

https://item.jd.com/857.html

用户请求这个界面的时候，我们的请求过程应该是：

用户 - 应用 - redis - 数据库

商品的种类非常多，所以我们缓存服务器里边就会存在大量如下的key：

假设现在有恶意请求，不管是批量攻击还是爬虫，如果他频繁的去请求一些不存在的数据，例如redis不存在的1001号商品，那么会导致什么情况呢？

1. 缓存不存在，会直接到数据库查询，此行为便被我们称为缓存穿透
   缓存穿透攻击是指恶意用户在短时内大量查询不存在的数据，导致大量请求被送达数据库进行查询，当请求数量超过数据库负载上限时，使系统响应出现高延迟甚至瘫痪的攻击行为。

二 如何预防缓存穿透？什么是布隆过滤器?

巴顿.布隆于一九七零年提出的，其主旨是采用一个很长的二进制数组，通过一系列的Hash函数来确定该数据是否存在。

布隆过滤器：

布隆过滤器其本质就是一个n位的二进制数组。

接下来我们来讲解一下布隆过滤器的原理，请看下图：

上图是编号为1的数据的初始化过程，我们将编号1进行三次（次数不固定）hash所得到的数据，填充进初始化的二进制数组：

1. 对数据hash
2. 结果在数组上表示，之前是0的位置变为1
3. 之前是1的维持不变
   直到我们将1000个编号全部计算并存入二进制数组，此时我们的数据初始化就完成了。
   数据存储完毕之后就是其读取的过程，我们来看编号858是怎么读取的：

我们将858进行三次hash，发现其计算值在二进制上均为1，则证明该数据在redis是存在的。

但是当我们请求一个不存在的数据，比如8888：

如图，8888通过三次hash，发现有一次结果其所在位为0，那么可以证明这个key一定不存在。

那么请思考，布隆过滤器就一定能判断某个key不存在吗？我们来看如下的情况：

我们可以看到，8889三次hash后，其所在位均为1，所以其实布隆过滤器也是会存在误判的，我们只需要记住口诀：真不一定真，假一定真！

但是是小概率事件，那么怎么能提升其精度呢:

1. 增加二进制数组的位数
2. 增加hash的次数

三 java如何使用布隆过滤器

添加依赖：

redisson的配置：

其项目中的使用流程：

基于以上的描述，整个布隆过滤器的设计基本已经完善，但是最后我们来考虑一下最后的问题：

1. 假如某个商品被删除了怎么？

什么是计数布隆？

通俗易懂的说就是在原本的每一位下边，新增其计数信息，归属于哪个数据