布隆过滤器到底是个啥

1. 布隆过滤器大致介绍

  • 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
  • 简单来说，布隆过滤器就是用来检查一个元素是否在一个集合里的，接下来就来具体分析下布隆过滤器。。

2. 底层结构

  • 布隆过滤器的底层数据结构是位图，可以理解为只存储二进制数值的数组，每个位置只能存放0或1，0表示不存在，1表示存在。

底层结构

3. 在缓存穿透中的应用

什么是缓存穿透

  • 在实际的开发中，难免会遇到数据缓存在redis中，当用户访问数据的时候，都是先请求缓存，那么假如要查询的数据在缓存中和数据库中都不存在，当缓存中查询不出数据的时候，会直接查询数据库，就会造成大量的请求作用到数据库，会对数据库造成很大的压力，容易出现宕机的情况，像恶意攻击，就会出现这种情况，请求查询大量不存在的key，极容易发生宕机，这种情况就叫做缓存穿透。

缓存穿透的解决办法

  1. 缓存空数据：将从mysql中查询到的空数据缓存到redis中，当用户再来查询的时候，直接查询到redis中的空数据，这种方法比较简单，但是会消耗过大的内存空间；
  2. 第二种方案就是布隆过滤器，当请求查询的是不存在的key值，布隆过滤器会直接返回，不会作用到数据库，这一点是本文重点，接下来会具体讲解。

布隆过滤器的原理

添加数据过程

  • 会先通过k个Hash函数计算hash值；
  • 然后每个hash映射到不同的数组下标，在下标对应的位置将0改为1，表示元素存在；

查询数据过程

  • 同样先通过k个Hash函数计算hash值；
  • 然后判断每个hash值对应的二进制数字；
  • 如果所有数字都为1，则说明查询的数据存在，如果有一个为0，则说明数据不存在。

优点

  1. 存储的是二进制数值，占用空间小；
  2. 插入和删除的速度快，优点类似哈希表的结构，操作k个数值，时间复杂度为O(K)；

缺点

  • 可能存在误判：考虑这样一种情况，假如我想要添加两个数据A和B，分别计算他们对应的hash值，如果计算的hash值相同，那他们会同时将某个位置的数值置为1，这时候就不知道此位置的1代表的是什么数据了。
    • 接着上面继续分析，如果没有存数据B，此时又想去查询数据B，计算的hash值和A计算的hash值相同，就会得到数据B存在的假现象（此时只有A存在，只不过他们计算的hash相同），形成误判，看图就分析清楚了。

误判分析

  • 可能存在误删：可以和上面的a一起考虑，假设现在已经添加了数据A和B，但是我想要删除数据A，就会将A计算的hash所对应的索引位置的value置为0，此时B也会被标志删除，因为他们的hash值相同。

END