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"，可以获得源码。



完成，收工！！





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