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 核心原理与实战》