简述
通过布隆过滤器实现大数据量的精度去重。
布隆过滤器能够了解为一个不怎么准确的 set 构造，当你应用它的 contains 办法判断某个对象是否存在时，它可能会误判。然而布隆过滤器也不是特地不准确，只有参数设置的正当，它的精确度能够管制的绝对足够准确，只会有小小的误判概率。个别用于大数据量的去重。
当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就必定不存在。打个比方，当它说不意识你时，必定就不意识；当它说见过你时，可能基本就没见过面，不过因为你的脸跟它意识的人中某脸比拟类似 (某些熟脸的系数组合)，所以误判以前见过你。
Redis 官网提供的布隆过滤器到了 Redis 4.0 提供了插件性能之后才正式退场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了弱小的布隆去重性能。
利用场景
在爬虫零碎中，咱们须要对 URL 进行去重，曾经爬过的网页就能够不必爬了。然而 URL 太多了，几千万几个亿，如果用一个汇合装下这些 URL 地址那是十分节约空间的。这时候就能够思考应用布隆过滤器。它能够大幅升高去重存储耗费，只不过也会使得爬虫零碎错过大量的页面。
布隆过滤器在 NoSQL 数据库畛域应用十分宽泛，咱们平时用到的 HBase、Cassandra 还有 LevelDB、RocksDB 外部都有布隆过滤器构造，布隆过滤器能够显著升高数据库的 IO 申请数量。当用户来查问某个 row 时，能够先通过内存中的布隆过滤器过滤掉大量不存在的 row 申请，而后再去磁盘进行查问。
邮箱零碎的垃圾邮件过滤性能也广泛用到了布隆过滤器，因为用了这个过滤器，所以平时也会遇到某些失常的邮件被放进了垃圾邮件目录中，这个就是误判所致，概率很低。
装置
docker 间接应用
> docker pull redislabs/rebloom # 拉取镜像
> docker run -p6379:6379 redislabs/rebloom # 运行容器
> redis-cli # 连贯容器中的 redis 服务插件装置
# 下载编译装置 Rebloom 插件
wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz
# 解压 tar zxvf v1.1.1.tar.gz
cd rebloom-1.1.1
make
# redis 服启动增加对应参数
rebloom_module="/usr/local/rebloom/rebloom.so"
daemon --user ${REDIS_USER-redis} "$exec $REDIS_CONFIG --loadmodule $rebloom_module --daemonize yes --pidfile $pidfile"
# 重启 redis 服务
测试命令
bf.add test testValue
命令胜利阐明开启胜利应用
布隆过滤器有二个根本指令，bf.add增加元素，bf.exists查问元素是否存在，它的用法和 set 汇合的 sadd 和 sismember 差不多。留神 bf.add 只能一次增加一个元素，如果想要一次增加多个，就须要用到 bf.madd 指令。同样如果须要一次查问多个元素是否存在，就须要用到 bf.mexists 指令。
127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.madd codehole user4 user5 user6
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7参数调优
咱们下面应用的布隆过滤器只是默认参数的布隆过滤器，它在咱们第一次 add 的时候主动创立。Redis 其实还提供了自定义参数的布隆过滤器，须要咱们在 add 之前应用 bf.reserve 指令显式创立。如果对应的 key 曾经存在，bf.reserve会报错。bf.reserve有三个参数，别离是 key,error_rate和 initial_size。错误率越低，须要的空间越大。initial_size 参数示意预计放入的元素数量，当理论数量超出这个数值时，误判率会回升。
所以须要提前设置一个较大的数值防止超出导致误判率升高。如果不应用 bf.reserve，默认的 error_rate 是 0.01，默认的 initial_size 是 100。
import redis
import random
client = redis.StrictRedis()
CHARS = ''.join([chr(ord('a') + i) for i in range(26)])
def random_string(n):
chars = []
for i in range(n):
idx = random.randint(0, len(CHARS) - 1)
chars.append(CHARS[idx])
return ''.join(chars)
users = list(set([random_string(64) for i in range(100000)]))
print 'total users', len(users)
users_train = users[:len(users)/2]
users_test = users[len(users)/2:]
falses = 0
client.delete("codehole")
# 减少了上面这一句
client.execute_command("bf.reserve", "codehole", 0.001, 50000)
for user in users_train:
client.execute_command("bf.add", "codehole", user)
print 'all trained'
for user in users_test:
ret = client.execute_command("bf.exists", "codehole", user)
if ret == 1:
falses += 1
print falses, len(users_test)输入如下：
total users 100000
all trained
6 50000咱们看到了误判率大概 0.012%，比预计的 0.1% 低很多，不过布隆的概率是有误差的，只有不比预计误判率高太多，都是失常景象。
布隆过滤器的 initial_size 预计的过大，会节约存储空间，预计的过小，就会影响准确率，用户在应用之前肯定要尽可能地准确预计好元素数量，还须要加上肯定的冗余空间以防止理论元素可能会意外高出估计值很多。
布隆过滤器的 error_rate 越小，须要的存储空间就越大，对于不须要过于准确的场合，error_rate设置稍大一点也无伤大雅。比方在新闻去重上而言，误判率高一点只会让小局部文章不能让适合的人看到，文章的整体浏览量不会因为这点误判率就带来微小的扭转。