Redis 布隆过滤器
整体大纲
布隆过滤器能解决哪些问题?
举个例子 : 有 50 亿个电话号码,现在给你 10 万个电话号码,如何快速准确的判断出这些号码是否存在?
方案 A: 数据库? ----> 50 亿的电话号码,查询效率非常慢
方案 B:内存 ? —> 就按 1 个电话号码 8 个字节 , 50亿 * 8 Byte = 40 G 内存
类似的问题还有很多,比如:
- 垃圾邮件过滤
- 文字处理软件(比如word)错误单词检测
- 网络爬虫重复 URL 检测
- 判断一个元素在亿级数据中是否存在
- hbase 行过滤
- ...
这些问题归根结底就一句话:如何才能查询一个值是否存在海量数据中呢?
开启布隆过滤器
方式一:编译方式
1. 下载并安装布隆过滤器
git clone https://github.com/RedisLabsModules/redisbloom.git
cd redisbloom
make # 编译redisbloom
编译正常执行完,会在根目录生成一个 redisbloom.so
文件。
2. 启动 Redis 服务器
> ./src/redis-server redis.conf --loadmodule ./src/modules/RedisBloom-master/redisbloom.so
方式二:Docker 方式
布隆过滤器的使用
常用命令:
(1)bf.add
:添加元素
(2)bf.exists
:判断某个元素是否存在
(3)bf.madd
:添加多个元素
(4)bf.mexists
:判断多个元素是否存在
(5)bf.reserve
:设置布隆过滤器的准确率
- 可以看出此命令必须在元素刚开始执行,否则会报错,它有三个参数:
key、error_rate 和 initial_size
。其中:error_rate
:允许布隆过滤器的错误率,这个值越低过滤器占用空间也就越大,以为此值决定了位数组的大小,位数组是用来存储结果的,它的空间占用的越大(存储的信息越多),错误率就越低,它的默认值是 0.01。initial_size
:布隆过滤器存储的元素大小,实际存储的值大于此值,准确率就会降低,它的默认值是 100。
代码实战
Jedis + LUA 脚本
import redis.clients.jedis.Jedis;
import utils.JedisUtils;
import java.util.Arrays;
public class BloomExample {
private static final String _KEY = "user";
public static void main(String[] args) {
Jedis jedis = JedisUtils.getJedis();
for (int i = 1; i < 10001; i++) {
bfAdd(jedis, _KEY, "user_" + i);
boolean exists = bfExists(jedis, _KEY, "user_" + i);
if (!exists) {
System.out.println("未找到数据 i=" + i);
break;
}
}
System.out.println("执行完成");
}
/**
* 添加元素
* @param jedis Redis 客户端
* @param key key
* @param value value
* @return boolean
*/
public static boolean bfAdd(Jedis jedis, String key, String value) {
String luaStr = "return redis.call('bf.add', KEYS[1], KEYS[2])";
Object result = jedis.eval(luaStr, Arrays.asList(key, value),
Arrays.asList());
if (result.equals(1L)) {
return true;
}
return false;
}
/**
* 查询元素是否存在
* @param jedis Redis 客户端
* @param key key
* @param value value
* @return boolean
*/
public static boolean bfExists(Jedis jedis, String key, String value) {
String luaStr = "return redis.call('bf.exists', KEYS[1], KEYS[2])";
Object result = jedis.eval(luaStr, Arrays.asList(key, value),
Arrays.asList());
if (result.equals(1L)) {
return true;
}
return false;
}
}
使用 Redisson 框架
RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");
// initialize bloom filter with
// expectedInsertions = 55000000
// falseProbability = 0.03
bloomFilter.tryInit(55000000L, 0.03);
bloomFilter.add(new SomeObject("field1Value", "field2Value"));
bloomFilter.add(new SomeObject("field5Value", "field8Value"));
bloomFilter.contains(new SomeObject("field1Value", "field8Value"));
bloomFilter.count();
对于布隆过滤器来说,它说没有的值一定没有,它说有的值有可能没有。
举个例子:我们判断一个 IP
是否在黑名单中,如果黑名单中有该 IP,那它一定能判定这个 IP
在黑名单中,假如该黑名单中没有这个 IP
,那它有可能也会判定这个 IP
在黑名单中,因为哈希冲突。不过这个概率是非常小的。
原理
Redis
的底层就是一个 bitmap
。
Redis
布隆过滤器的实现,依靠的是它数据结构中的一个位数组,每次存储键值的时候,不是直接把数据存储在数据结构中,因为这样太占空间了,它是利用几个不同的无偏哈希函数,把此元素的 hash
值均匀的存储在位数组中,也就是说,每次添加时会通过几个无偏哈希函数算出它的位置,把这些位置设置成 1 就完成了添加操作。
当进行元素判断时,查询此元素的几个哈希位置上的值是否为 1,如果全部为 1,则表示此值存在,如果有一个值为 0,则表示不存在。因为此位置是通过 hash
计算得来的,所以即使这个位置是 1,并不能确定是那个元素把它标识为 1 的,因此布隆过滤器查询此值存在时,此值不一定存在,但查询此值不存在时,此值一定不存在。
并且当位数组存储值比较稀疏的时候,查询的准确率越高,而当位数组存储的值越来越多时,误差也会增大。
布隆过滤器优缺点
优点
相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 O(K)O(K)O(K),另外,散列函数相互之间没有关系,方便由硬件并行实现。
布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集,其它任何数据结构都不能。
缺点
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。
另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。
参考
《Redis 核心原理与实战》
转载自:https://juejin.cn/post/7058511684716986382