布隆过滤器是个啥!

用户头像
诸葛小猿
关注
发布于: 2020 年 07 月 20 日
布隆过滤器是个啥!

Redis系列目录



redis系列之——分布式锁



redis系列之——缓存穿透、缓存击穿、缓存雪崩



redis系列之——Redis为什么这么快?



redis系列之——数据持久化(RDB和AOF)



redis系列之——一致性hash算法



redis系列之——高可用(主从、哨兵、集群)



redis系列之——事物及乐观锁



redis系列之——数据类型geospatial:你隔壁有没有老王?



redis系列之——数据类型bitmaps:今天你签到了吗?



布隆过滤器是个啥!



引子



“之前坑是你留的吧?!怎么不过来填上,我在坑里还没出来呢!”



十分抱歉啊,之前坑留的有点多。就请你给我多一点点时间,再多一点点温柔,不要让我如此难受。





不用担心,我说过,挖的坑跪着我也会填上的。今天就填一个Bloom Filter的坑。这是之前一期中《redis系列之——缓存穿透、缓存击穿、缓存雪崩》留下的。



今天我们就哔哔一下布隆过滤器的那些事!



知识背景



具体的定义请自行问某度,就不哔哔了。



相关背景可以回顾一下我之前的文章《redis系列之——缓存穿透、缓存击穿、缓存雪崩》。



Bloom Filter是一个占用空间很小、效率很高的随机数据结构,它由一个bit数组和一组Hash算法构成。主要作用是:判断一个元素是否在一个集合中,具有查询效率很高,节省空间等优点;缺点是有一定的误识别率(false-positive,假阳性),可能会把不是集合内的元素判定为存在于集合内,但是概率相当小,在大部分的生产环境中是可以接受的;关于假阳性问题,请记住一句话Bloom Filter说这条数据存在,这条数据不一定存在;但是Bloom Filter说这条数据不存在,这条数据一定不存在。



原理也比较简单,听起来不像人话。S集合中有n个元素,利用k个哈希函数,将S中的每个元素映射到一个长度为m的位(bit)数组B中不同的位置上,这些位置上的二进制数均置为1,如果待检测的元素经过这k个哈希函数的映射后,发现其k个位置上的二进制数不全是1,那么这个元素一定不在集合S中,反之,该元素可能是S中的某一个元素。



简单实例



使用一个例子,将上面这一段翻译成人话:



假如,数据库中有100条订单数据,id分别从1到100,现在用户通过id查询订单数据,为了防止缓存穿透,我们需要提前做一个bloom filter(一个自定义的bit数组长度为1000,并自定义一个hash算法),将数据库中的所有id提前通过hash算法计算后,放到bit数组中;当用户的请求到达controller层中,先到这个数组中查询这个id是否存在,如果存在,在让请求往下走,访问redis或mysql;如果不存在则直接返回。



那么这个如何将这100个id通过hash算法存到bit数组中呢?





上面这个图就是将订单Id通过hash函数放入bit数据之前的情况。这里需要注意hash函数的要求,同时bit数组长度暂定为1000。然后通过下图,将每一个订单id,通过hash函数的计算,得到一个0-999之间的一个数字;比如id=1通过hash函数计算的到3,就将bit数组中索引为3的位置的值由0变成1,依次类推处理剩余的所有id,这样就得到一个id处理后的bit数组。





当用户通过id查询时订单时,同样将id通过这个hash函数生成bit数组的下标,如果这边下标对应的bit元素的值为1,则表示数据存在,可以继续查询redis或mysql;如果这个下标对应的bit元素的值为0,表示这个数据不存在,直接返回。



从上面可以看出,存储100个id使用的内存就是1000bit,比直接存储id时占用的内存空间小很多。



同时,这种判断机制也大大提高了查询效率。



存在的问题



上面的案例,假设id=110的数据经过hash函数计算的值也是3,那么当用户查询这条数据时,数据库不存在这条数据,但是bloom filter查询后显示数据存在,所有也会查询redis和mysql。这就是hash碰撞导致的假阳性,所以说Bloom Filter说这条数据存在,这条数据不一定存在;但是Bloom Filter说这条数据不存在,这条数据一定不存在。



如何解决这个问题呢?可以通过增加hash函数的个数和增加bit数组的长度来解决。



增加hash函数,如下图所示,每一个id都通过两个hash函数计算,得到两个索引位置,通过两个位置的值是不是1来确定该数据是否存在,可以降低hash碰撞概率。



同时增加bit数组长度,可以增大hash函数生成的数据的范围,也可以降低hash碰撞,减少假阳性概率。



从上面可以看出,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。





那么,对于不同的场景,在可接受的假阳性率范围内,使用几个hash函数及bit数组应该设置为多长就是可优化的点。具体的算法的优化就不是我的能力范围内的事情了,只能送大家到这里了。





最后简单介绍一下实现。目前bloom filter已经有相应实现的开源类库,如Google的Guava类库,Twitter的Algebird类库,和ScalaNLP breeze等等。也可以基于Redis自带的Bitmaps作为底层的bit数组自行设计bloom filter;同时redis 在 4.0 的版本中加入了 module 功能,布隆过滤器可以通过 module 的形式添加到 redis 中使用。



关注公众号,输入关键字"java-summary",可以获得源码。



完成,收工!!





传播知识,共享价值】,感谢小伙伴们的关注和支持,我是【诸葛小猿】,一个彷徨中奋斗的互联网民工。





发布于: 2020 年 07 月 20 日 阅读数: 40
用户头像

诸葛小猿

关注

我是诸葛小猿,一个彷徨中奋斗的互联网民工 2020.07.08 加入

公众号:foolish_man_xl

评论

发布
暂无评论
布隆过滤器是个啥!