布隆过滤器(Bloom Filter)

Published: 13 Jan 2019 Category: data_struct

一、介绍

直观的说,bloom算法类似一个hash set,用来判断某个元素(key)是否在某个集合中。

和一般的hash set不同的是,这个算法无需存储key的值,对于每个key,只需要k个比特位,每个存储一个标志,用来判断key是否在集合中。

它实际上是由一个很长的二进制向量和一系列随机映射函数组成,布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率(假正例False positives,即Bloom Filter报告某一元素存在于某集合中,但是实际上该元素并不在集合中)和删除困难,但是没有识别错误的情形(即假反例False negatives,如果某个元素确实没有在该集合中,那么Bloom Filter 是不会报告该元素存在于集合中的,所以不会漏报)。

二、算法

一个Hash函数将一个元素映射成一个位阵列(Bit Array)中的一个点。但Hash面临的问题就是冲突。假设 Hash 函数是良好的,如果我们的位阵列长度为 m 个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100 个元素。显然这就不叫空间有效了(Space-efficient)。

解决方法:就是使用多个 Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们在说谎,不过直觉上判断这种事情的概率是比较低的。

bloom filter

具体步骤:

  • 1.首先需要k个hash函数,每个函数可以把key散列成为1个整数
  • 2.初始化时,需要一个长度为n比特的数组,每个比特位初始化为0
  • 3.某个key加入集合时,用k个hash函数计算出k个散列值,并把数组中对应的比特位置为1
  • 4.判断某个key是否在集合时,用k个hash函数计算出k个散列值,并查询数组中对应的比特位,如果所有的比特位都是1,认为在集合中。

优点:

  • 不需要存储key,节省空间。

缺点:

  • 1.算法判断key在集合中时,有一定的概率key其实不在集合中(False Positive)
  • 2.无法删除

典型的应用场景:某些存储系统的设计中,会存在空查询缺陷:当查询一个不存在的key时,需要访问慢设备,导致效率低下。

比如一个前端页面的缓存系统,可能这样设计:先查询某个页面在本地是否存在,如果存在就直接返回,如果不存在,就从后端获取。但是当频繁从缓存系统查询一个页面时,缓存系统将会频繁请求后端,把压力导入后端。

这是只要增加一个bloom算法的服务,后端插入一个key时,在这个服务中设置一次。需要查询后端时,先判断key在后端是否存在,这样就能避免后端的压力。

三、应用场景

3.1 黑名单

最典型的一个应用就是黑名单功能,对用户名称或者IP或者Email进行过滤,每次检查时用key进行hash后,如果不在黑名单内的,肯定可以通行,如果在的则不允许通过,误判情况增加一个排除名单来进行排除。

误判情况:将正常用户判定为黑名单用户

3.2 爬虫重复URL检测

在爬取网站URL时,要检测这条URL是否已经访问过。

误判情况:没有访问过的误判为访问过

3.3 字典纠错

检查单词拼写是否正确

误判情况:错误的单词误判为正确。

3.4 磁盘文件检测

将磁盘中或者数据库中数据key存入该结构中,检测要访问的数据是否在磁盘或数据库中,然后再发起访问,避免空查询造成磁盘或数据库压力。

误判情况:不存在该数据却误判为有该数据。

3.5 CDN(squid)代理缓存技术

先查找本地有无cache,如果没有则到其他cache服务器上去查找。为了避免无谓的查询,在每个cache服务器上保存其兄弟服务器的缓存关键字,以bloomfilter方式存储,再去其他cache服务器查找之前,先检查该结构是否有url,如果有存在url,再去对应服务器查找。

误判情况: 对应服务器不存在该URL的缓存。

REF

布隆过滤器(Bloom Filter)详解
Bloomfilter 的应用场景