布隆过滤器初探与解读

2023-11-06 18:35:22

布隆过滤器初探与解读

布隆过滤器

布隆过滤器可以用来存储key是否在之前添加过的元素中出现过的一个数据结构，它在很多例如 过滤垃圾邮件，解决缓存穿透，推荐系统，屏蔽广告等问题上都有着非常大的用处。Redis已经支持了该模块了

出现的背景

当我们需要保存一个key，然后之后需要不断重复的查询，key是否真实存在。我们这个时候可以想到链表、hash字典、树、Set中。但是这些数据结构的存储如果只是从需要查询该key是否存在的场景中的话，这些数据结构还是比较局限的。主要有着两点的局限性。

  1. 需要的空间比较大一般都是O(n)的空间复杂度。
  2. 搜索的时候时间复杂度最小也是O(Logn)的时间复杂度。
    这个时候布隆过滤器就诞生了。

布隆过滤器

学过机器学习或者有了解过Ai的大概都会知道特征这个词，我们的人脸或者文字，他们都有对应的特征，如果我们需要判断重复的人脸或者文字的话，我们可以将这些人脸和文字的特征给保存起来，再次查询我们也可以通过输入的信息映射为相应的特征值，然后再由这个特征值去查询该特征是否有存在，然后根据查找到特征的来判断是否重复的概率。例如Sift和Surf或orb等这些图像匹配算法就是用不同的方法来将图片中的特征提取出来然后保存，之后查询就是去查找这个特征。不过他们的特征提取的方法相对来说比较复杂。
相对于上边这些算法，布隆过滤器的提起特征算法非常的简单，就是一个哈希函数就能搞定，我们可以通过不同的哈希函数用来计算它的不同的特征，然后将它保存在一个bit数组里面。其实这个提取特征的方法有点不靠谱，可以根据具体的场景来进行具体的调整(比如进行预处理和预提取)。

从数据结构来说其实，布隆过滤器只是bitmap的扩展，优先是读写性能高，占用空间小，缺点是存在一定的误判。设定布隆过滤器误判率为万分之一，单块bitmap为需要存储24亿个key,则最优的hash函数为14个，需要5.7G内存

大概的函数使用例子

  // BloomFilter使用例子：
  static BaseBloomFilter stBloomFilter = {0};
   // 初始化BloomFilter(最大100000元素，不超过0.00001的错误率)：
       InitBloomFilter(&stBloomFilter, 0, 100000, 0.00001);
  // 重置BloomFilter：
       ResetBloomFilter(&stBloomFilter);
  // 释放BloomFilter:
       FreeBloomFilter(&stBloomFilter);
 
   // 向BloomFilter中新增一个数值（0-正常，1-加入数值过多）：
       uint32_t dwValue;
       iRet = BloomFilter_Add(&stBloomFilter, &dwValue, sizeof(uint32_t));
  // 检查数值是否在BloomFilter内（0-存在，1-不存在）：
       iRet = BloomFilter_Check(&stBloomFilter, &dwValue, sizeof(uint32_t));

我们在初始化的时候只需要设置最大元素和错误率。

布隆过滤器和Hashmap使用的区别

布隆过滤器是数据量大的时候才会有比较好的应用场景，它和哈希函数有着密切的关系。
布隆过滤器用在过滤的算法上。它是用在允许误差的场景。
hashmap和布隆过滤器查询的效率差不多。但是主要就是插入耗时和内存占用，布隆过滤要优。

Hashmap存在的问题

Hash存在内存占用多的问题，首先他的key值都是真实存储的，然后如果表的数据超过其一半后，就要扩充。
而且如果hash冲突太多的话，就会渐渐的退化成为链表。拉链法，线性探测法

布隆过滤器的优缺点

​ 优点：

  1. 时间和空间复杂度低

  2. 在高并发的场景下使用快速

  3. 不存储元素，数据安全性高

缺点：

  1. 存在误判率

  2. 无法直接支持删除元素(因为它可能会导致其他元素的判断受到影响)

目前讨论比较多的场景和出现的问题

1、如果使用布隆过滤器来验证垃圾邮件的时候，如果误判为黑名单，需要增加他的白名单。但是它会减少某些黑名单命中的概率。
2、缓存穿透的问题 缓存穿透即当用户同时查询大量不存在的key的时候，在缓存里面无法查询的到，这个时候，大量的查询语句会堆积到数据库中，导致数据库繁忙的去查找一些不存在的数据，容易穿表。 这个时候在接入层我们可以采用一个布隆过滤器来过滤掉绝对不存在的数据，这样就可以减少查询空值的可能，还有一个比较暴力的方法就是直接缓存空值，然后设定过期时间。（雪崩是我们设置很多缓存的时候采用了相同的过期时间，导致缓存在同一时间内同时失效，请求全部转发到Db，导致Db压力过大而雪崩。设置缓存过期的时候加一个随机值不要设置为一样的）（还有一个是缓存击穿，有某个拥有高并发数据量需要求的key，这个key的过期时间到了的时候，有大量用户查询同一个key并下放到DB，导致Db负载过高，这个时候就要使用互斥锁或者设置永不过期）
3、推荐系统，推荐去重，如果推荐过的就不要再推荐了。
4、检测网络ip是否访问过我们的网站。
5、 新手机的统计，如果是新的手机就统计，手机识别码。
6、 屏蔽广告。

具体案例分析

公众号阅读数统计

阅读数是指的文章在历史上被阅读的人数我们简称为(uv)，如果同时有大量用户请求的话，计算这个人数的操作其实也是一个高并发的操作。

背景

一开始使用的是点击文章链接就会将阅读数++，这里我们称之为PV统计，但是这个统计方法存在一个问题，就是它的数量很容易被刷，这个时候我们就要改成UV来统计阅读量，即(文章-用户)。这个时候我们统计数量的时候就可以先去查询是否有(文章-用户)的数据存在，然后再做写入++。

使用

如果每天都存储阅读关系，这个数据会不断的增加，尤其像微信的微信公众号，每天有可能会有30亿的阅读关系，考虑到大部分文章的热度都是比较短的，大概一个星期左右所以，我们可以选取一个过期时间，比如7天内阅读数量只计算一次。
这个存储的key大概是，Uin_DocUid这样的。
我们可以使用两个公式来判断最优布隆过滤器的配置：

k = (m/n) In 2

m = - n ln 2/(ln 2)^2

写在最后

布隆过滤器的应用很广泛，只要是大规模的集合存在性判定，就可能派上用场，比如

  1. 网络爬虫的集合去重

  2. 存储系统中的索引结构，如leveldb, hbase

  3. 网络中的路由判定

上一篇：基于Redis的Java布隆过滤器


下一篇：Redis详解（十三）------ Redis布隆过滤器