布隆过滤器

是一种节省空间的概率数据结构，其作用是将一个大的数据集映射到一个小的数据集上面。

是一个用来检索一个元素是否在一个集合中的算法，效率高，性能好

布隆过滤器应用很广泛，比如垃圾邮件过滤，爬虫的url过滤，防止缓存击穿等等。

安装redis

wget http://download.redis.io/releases/redis-5.0.4.tar.gz
tar zxvf redis-5.0.4.tar.gz
cd redis-5.0.4
make

安装RedisBloom

wget https://github.com/RedisBloom/RedisBloom/archive/v2.0.3.tar.gz
tar zxvf v2.0.3.tar.gz
cd RedisBloom-2.0.3
make

RedisBloom安装完成后可以看到log信息，找到redisbloom.so存放目录，修改redis配置

loadmodule /home/RedisBloom-2.0.3/redisbloom.so
./redis-server ./../redis.conf &

或者不修改redis.conf的情况下加载

./redis-server ./../redis.conf --loadmodule /home/RedisBloom-2.0.3/redisbloom.so &

启动redis

./redis-server ./../redis.conf &

测试

>redis-cli
BF.ADD newFilter foo
BF.EXISTS newFilter foo

Redis提供了自定义参数的布隆过滤器，来降低误判率，只需要在add之前使用bf.reserve指令创建。

如若对应的key已经存在，bf.reserve会报错。

bf.reserve有三个参数,分别是key,error_rate（错误率）和initial_size。

error_rate越低，需要的空间越大。

initial_size表示预计放入的元素数量，当实际数量超过这个数值时，误判率会上升。

// The default error rate is 0.01 and the default initial capacity is 100.
redis-server --loadmodule /path/to/redisbloom.so INITIAL_SIZE 400 ERROR_RATE 0.004

具体语法

BF.RESERVE {key} {error_rate} {capacity}
BF.RESERVE urls 0.00001 1000

布隆过滤器有缺点

1、会有一定概率误判

2、设置后不能删除

在上面两个缺点基础上，诞生了布谷过滤器，参考

https://oss.redislabs.com/redisbloom/Quick_Start/

GIT

https://github.com/RedisBloom/RedisBloom

同样布谷过滤器也提供了RESERVE

CF.RESERVE {key} {capacity}

PHP用法

$redis->rawCommand("BF.RESERVE", "bf", "0.001", 1000)
$redis->rawCommand("BF.ADD", "bf", "RedisLabs")
$redis->rawCommand("BF.EXISTS", "bf", "RedisLabs")