本文主要是介绍吃透Redis系列(四):布隆(bloom)过滤器详细介绍,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Redis系列文章:
吃透Redis系列(一):Linux下Redis安装
吃透Redis系列(二):Redis六大数据类型详细用法
吃透Redis系列(三):Redis管道,发布/订阅,事物,过期时间 详细介绍
吃透Redis系列(四):布隆(bloom)过滤器详细介绍
吃透Redis系列(五):RDB和AOF持久化详细介绍
吃透Redis系列(六):主从复制详细介绍
吃透Redis系列(七):哨兵机制详细介绍
吃透Redis系列(八):集群详细介绍
吃透Redis系列(九):Redis代理twemproxy和predixy详细介绍
吃透Redis系列(十):Redis内存模型详细介绍
吃透Redis系列(十一):Jedis和Lettuce客户端详细介绍
文章目录
- 布隆过滤器应用场景
- 布隆过滤器简介
- 1,添加数据
- 2,判断数据是否存在?
- 3,布隆过滤器优缺点
- Redis实现布隆过滤器
- Redis安装布隆过滤器模块
- 1,访问github地址,下载模块源码
- 2,执行make编译动态库
- 3,启动redis加载该动态库
- Redis使用布隆过滤器
- 1,常用命令
- 2,布隆过滤器准确率
- 3,在项目中使用
本篇博客我们主要介绍如何用Redis实现布隆过滤器,但是在介绍布隆过滤器之前,我们首先介绍一下,为啥要使用布隆过滤器。
布隆过滤器应用场景
- 解决缓存穿透的问题
一般情况下,先查询缓存是否有该条数据,缓存中没有时,再查询数据库。当数据库也不存在该条数据时,每次查询都要访问数据库,这就是缓存穿透。缓存穿透带来的问题是,当有大量请求查询数据库不存在的数据时,就会给数据库带来压力,甚至会拖垮数据库。
可以使用布隆过滤器解决缓存穿透的问题,把已存在数据的key
存在布隆过滤器中。当有新的请求时,先到布隆过滤器中查询是否存在,如果不存在该条数据直接返回;如果存在该条数据再查询缓存查询数据库。
- 黑名单校验
发现存在黑名单中的,就执行特定操作。比如:识别垃圾邮件,只要是邮箱在黑名单中的邮件,就识别为垃圾邮件。假设黑名单的数量是数以亿计的,存放起来就是非常耗费存储空间的,布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中,再收到邮件时,判断邮件地址是否在布隆过滤器中即可。
**场景一:**原本有10亿个号码,现在又来了10万个号码,要快速准确判断这10万个号码是否在10亿个号码库中?
解决办法一:将10亿个号码存入数据库中,进行数据库查询,准确性有了,但是速度会比较慢。
解决办法二:将10亿号码放入内存中,比如Redis缓存中,这里我们算一下占用内存大小:10亿*8字节=8GB,通过内存查询,准确性和速度都有了,但是大约8gb的内存空间,挺浪费内存空间的。
**场景二:**购物网站搜索商品,客户在商品搜索栏输入商品,首先要判断此商品在我数据库中存不存在,如果存在才会去执行数据库查询操作!
那么对于类似这种,大数据量集合,如何准确快速的判断某个数据是否在大数据量集合中,并且不占用内存,布隆过滤器应运而生了。
布隆过滤器简介
带着上面的几个疑问,我们来看看到底什么是布隆过滤器。
布隆过滤器:一种数据结构,是由一串很长的二进制向量组成,可以将其看成一个二进制数组。既然是二进制,那么里面存放的不是0,就是1,但是初始默认值都是0。
如下所示:
1,添加数据
介绍概念的时候,我们说可以将布隆过滤器看成一个容器,那么如何向布隆过滤器中添加一个数据呢?
如下图所示:当要向布隆过滤器中添加一个元素key时,我们通过多个hash函数,算出一个值,然后将这个值所在的方格置为1。
比如,下图hash1(key)=1,那么在第2个格子将0变为1(数组是从0开始计数的),hash2(key)=7,那么将第8个格子置位1,依次类推。
2,判断数据是否存在?
知道了如何向布隆过滤器中添加一个数据,那么新来一个数据,我们如何判断其是否存在于这个布隆过滤器中呢?
很简单,我们只需要将这个新的数据通过上面自定义的几个哈希函数,分别算出各个值,然后看其对应的地方是否都是1,如果存在一个不是1的情况,那么我们可以说,该新数据一定不存在于这个布隆过滤器中。
反过来说,如果通过哈希函数算出来的值,对应的地方都是1,那么我们能够肯定的得出:这个数据一定存在于这个布隆过滤器中吗?
答案是否定的,因为多个不同的数据通过hash函数算出来的结果是会有重复的,所以会存在某个位置是别的数据通过hash函数置为的1。
我们可以得到一个结论:布隆过滤器可以判断某个数据一定不存在,但是无法判断一定存在。
3,布隆过滤器优缺点
优点:优点很明显,二进制组成的数组,占用内存极少,并且插入和查询速度都足够快。
缺点:随着数据的增加,误判率会增加;还有无法判断数据一定存在;另外还有一个重要缺点,无法删除数据。
Redis实现布隆过滤器
在Redis中是用bitmap
来实现布隆过滤器的!
bitmap
我们知道计算机是以二进制位作为底层存储的基础单位,一个字节等于8位。
比如“big”字符串是由三个字符组成的,这三个字符对应的ASCII码分为是98、105、103,对应的二进制存储如下:
在Redis中,Bitmaps 提供了一套命令用来操作类似上面字符串中的每一个位。
设置值
setbit key offset value
127.0.0.1:6379> set k1 big
OK
127.0.0.1:6379> setbit k1 7 1
(integer) 0
127.0.0.1:6379> get k1
"cig"
127.0.0.1:6379>
我们知道"b"的二进制表示为0110 0010,我们将第7位(从0开始)设置为1,那0110 0011 表示的就是字符“c”,所以最后的字符 “big”变成了“cig”。
获取位图指定范围值为1的个数
bitcount key [start end]
如果不指定,那就是获取全部值为1的个数。
注意:start和end指定的是字节的个数,而不是位数组下标。
127.0.0.1:6379> set k1 big
OK
127.0.0.1:6379> bitcount k1
(integer) 12
127.0.0.1:6379> bitcount k1 0 0
(integer) 3
127.0.0.1:6379> bitcount k1 0 1
(integer) 7
127.0.0.1:6379>
Redis安装布隆过滤器模块
1,访问github地址,下载模块源码
https://github.com/RedisBloom/RedisBloom
直接用git clone或则下载zip
git clone https://github.com/RedisBloom/RedisBloom.git
2,执行make编译动态库
cd RedisBloom
make
执行完成之后,会生成一个redisbloom.so动态库
3,启动redis加载该动态库
# 我习惯把该库放到redis的安装目录下,这步骤看自己喜好
sudo cp redisbloom.so /opt/redis/
# 先停掉redis进程
sudo kill -9 pid
# 加载动态库
redis-server --loadmodule /opt/redis/redisbloom.so
出现下图显示加载完成:
然后就可以用redis-cli
客户端来连接测试了
Redis使用布隆过滤器
1,常用命令
bf.add 添加元素
bf.exists 查询元素是否存在
bf.madd 一次添加多个元素
bf.mexists 一次查询多个元素是否存在
127.0.0.1:6379> bf.add k1 1
(integer) 1
127.0.0.1:6379> bf.add k1 2
(integer) 1
127.0.0.1:6379> bf.exists k1 1
(integer) 1
127.0.0.1:6379> bf.exists k1 5
(integer) 0
127.0.0.1:6379>
2,布隆过滤器准确率
在 redis 中有两个值决定布隆过滤器的准确率:
error_rate:允许布隆过滤器的错误率,这个值越低过滤器的位数组的大小越大,占用空间也就越大。
initial_size:布隆过滤器可以储存的元素个数,当实际存储的元素个数超过这个值之后,过滤器的准确率会下降。
redis 中有一个命令可以来设置这两个值:
bf.reserve test 0.01 100
第一个值是过滤器的名字。
第二个值为 error_rate 的值。
第三个值为 initial_size 的值。
注意必须在add之前使用bf.reserve指令显式创建,如果对应的 key 已经存在,bf.reserve会报错。同时设置的错误率越低,需要的空间越大。如果不使用 bf.reserve,默认的error_rate是 0.01,默认的initial_size是 100。
3,在项目中使用
3.1
引入包
<dependency><groupId>com.redislabs</groupId><artifactId>jrebloom</artifactId><version>1.0.2</version>
</dependency>
JAR包里只有三个类,对连接方式 和 数据类型 的支持都不够
代码:
Client client = new Client(redisProperties.getHost(), redisProperties.getPort(), 10000, 100);
client.add("bobo", "123");
boolean bo = client.exists("bobo", "123");
System.out.println(bo);
3.2:Guava中的BloomFilter
google的guava包中提供了BloomFilter类,直接用的是服务器内存
导入包
<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>22.0</version>
</dependency>
代码:
private static int size = 1000000;
private static BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), size, 0.0001);public void test2() {String bo = "bobo";bloomFilter.put(bo);System.out.println(bloomFilter.mightContain(bo));
}
这篇关于吃透Redis系列(四):布隆(bloom)过滤器详细介绍的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!