1、什么是布隆过滤器
可以把布隆过滤器理解为一个不怎么精确的set结构,当你使用它的contains方法判断某个对象是否存在时,它可能会误判。但是布隆过滤器也不是特别不精确,只要参数设置得合理,它的精确度也可以控制得相对足够精确,只会有小小的误判概率。
当布隆过滤器说某个值存在时,这个值可能不存在;当它说某个值不存在时,那就肯定不存在。打个比方,当它说不认识你时,肯定就是真的不认识;而当他说认识你时,却有可能根本没有见过你,只是因为你的脸跟它认识的某人的脸比较相似,所以误判以前认识你。
2、布隆过滤器的基本用法
redis官方提供的布隆过滤器到了redis 4.0提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到redis server中,给redis提供了强大的布隆去重功能。
布隆过滤器有两个基本指令,bf.add和bf.exists。bf.add添加元素,bf.exists查询元素是否存在,它们的用法和set集合的sadd和sismember差不多。注意bf.add只能一次添加一个元素,如果想要一次添加多个,就需要用到bf.madd指令。同样如果需要一次查询多个元素是否存在,就需要用到bf.mexists指令。
我们上面使用的布隆过滤器只是默认参数的布隆过滤器,它在我们第一次add的时候自动创建。Redis其实还提供了自定义参数的布隆过滤器,需要我们在add之前使用bf.reserve指令显示创建。如果对于的key已经存在,bf.reserve会报错。bf.reserve有三个参数,分别是key、error_rate(错误率)和initial_size。error_rate越低,需要的空间越大。initial_size表示预计放入的元素数量,当实际数量超过这个数值时,误判率会上升,所以需要提前设置一个较大的数值避免超出导致误判率升高。如果不使用bf.reserve,默认的error_rate是0.01,默认的initial_size是100。
3、布隆过滤器的原理
学会了布隆过滤器的使用,下面有必须要把它的原理解释一下,不然有些读者还会继续蒙在鼓里。
每个布隆过滤器对应到redis的数据结构里面就是一个大型的位数组和几个不一样的无偏hash函数。如下图的f、g、h就是这样的hash函数。所谓无偏就是能够把元素的hash值算得比较均匀,让元素被hash映射到位数组中的位置比较随机。
向布隆过滤器中添加key时,会使用多个hash函数对key进行hash,算得一个整数索引值,然后对位数组涨肚进行取模运算得到一个位置,每个hash函数都会算得一个不同的位置。在把位数组的这几个位置都置为1,就完成了add操作。
向布隆过滤器询问key是否存在时,跟add一样,也会把hash的几个位置都算出来,看看位数组中这几个位置是否都为1,只要有一个位为0,那么说明布隆过滤器中这个key不存在。如果这几个位置都是1,并不能说明这个key就一定存在,只是极有可能存在,因为这些位被置为1可能是因为其他的key存在所致。如果这个位数组比较稀疏,判断正确的概率就会很大,如果这个位数组比较拥挤,判断正确的概率就会降低。具体的概率计算公式比较复杂,感兴趣可以阅读相关的更深入研究的资料,不过非常烧脑,不建议读者细读。
使用时不要让实际元素数量远大于初始化数量,当实际元素数量开始超出初始化数量时,应该对布隆过滤器进行重建,重新分配一个size更大的过滤器,在将所有的历史元素批量add进去。因为error_rate不会因为数量刚一超出就急剧增加,这就给我们重建过滤器提供了较为宽松的时间。
网友评论