目录
提到布隆过滤器,我想大家首先能想到的就是解决缓存击穿的问题。确实不错,它确实能在Redis中应用的最为广泛。其实布隆过滤器是一种算法思想,常用来用作判断某一个对象是否存在。接下来我将从使用场景、实现原理、如何使用、优劣势来介绍它。
在前言中我们提到了布隆过滤器常用来判断某一个对象是否存在,最常见的应用就是在Redis中,判断某一个key是否在Redis中存在,避免因为缓存穿透,认为恶意的攻击Redis缓存中不存在的值,直接将请求打到数据库,增加数据库的压力。
我们还有一些常用的使用场景比如:
我们在前面提供布隆过滤器的主要使用场景,在于过滤,在于判断某个对象是否存在。如果说仅仅只是判断是否存在。
其实我们可以使用HashMap去判断一个key是否存在。并且时间复杂度为O(1) , 可以说是非常的高效。在数据量小的情况下HashMap确实能帮助我们实现,但是当数据量特别大的时候,时间复杂度还是没有变化,但是空间复杂度却发生变化。HashMap需要更多的内存去存储数据的内容。
为了解决内存占用的问题。布隆过滤器使用bit位的0和1来存储对象是否存在的结果。和HashMap一样,布隆过滤器也使用hash函数来判断对象是否存在,但是Hash函数我们知道有冲突的可能性。为了解决这个问题的解决方案是。如果一个Hash函数有冲突,那么就利用多个hash函数,然后将多个hash函数的判断结果存放到bit位中。这样既解决了内存消耗的问题,也解决了hash冲突的问题。具体实现原理如下图:
在使用方式上,有分单机版和分布式版本。
在单机版本上,我们可以直接使用Google开源的Guava库布隆过滤器的实现类Bloomfilter
- // 创建布隆过滤器对象
-
- BloomFilter
filter = BloomFilter.create( -
- Funnels.stringFunnel(Charsets.UTF_8),
-
- 10000,
-
- 0.1);
-
- // 判断指定元素是否存在
-
- System.out.println(filter.mightContain("ABC"));
-
- // 将元素添加进布隆过滤器
-
- filter.put("ABC");
-
- System.out.println(filter.mightContain("ABC"));
如果需要在分布式的场景下使用布隆过滤器就需要使用Redis,布隆过滤器是redis的一个插件,如果想使用需要单独安装。RedisBloom 是 Redis 官方推荐的布隆过滤器插件,可以通过https://github.com/RedisBloom/RedisBloom来下载。
下面我们介绍一个判断元素是否存在的命令
bf.exists test user1
bf.exists 判断 user1 是否在 test 过滤器中,与之对应的有一个 bf.mexists 命令可以批量判断多个元素是否存在:
bf.mexists test user1 user2
最后我们介绍最重要的命令 bf.reserve,它的功能是创建一个布隆过滤器,
格式如下:
bf.reserve {key} {error_rate} {size} [expansin]
下面我介绍一下每个参数的含义:
针对布隆过滤器使用的优势与劣势。
首先最大的优势是在数据量特别大的场景。能占用比较小的场景下快速判断对象是否存在。虽然需要用多个hash函数,但是判断过程是CPU密集型的计算,相比HashMap的一次hash函数,但是需要在内存中比较是否对象是否相等。这是属于内存密集型计算,理论上布隆过滤器的判断更加高效。
缺点就是:布隆过滤器存在一定的误判率,一般用于判断元素不存在。
经过它计算的结果是不存在,那么元素一定不存在,如果计算的结果为存在,会存在,不能一定确认元素存在,因为,可能所有的hash函数都冲突了,别的元素提前将bit为设置为1。