什么是布隆过滤器?
它实际上是一个很长的二进制向量和一系列随机映射函数. 把一个目标元素通过多个 hash 函数的计算, 将多个随机计算出的结果映射到二进制向量的位中, 依次来间接标记一个元素是否存在于一个集合中.
布隆过滤器可以做什么?
布隆过滤器可以用于检索一个元素是否在一个集合中. 它的优点是空间效率和查询时间都比一般的算法要好的多, 缺点是有一定的误识别率和删除困难.
布隆过滤器特点
如果布隆过滤器显示一个元素不存在于集合中, 那么这个元素 100% 不存在与集合当中
如果布隆过滤器显示一个元素存在于集合中, 那么很有可能存在, 可能性取决于对布隆过滤器的定义(BF.RESERVE {key} {error_rate} {capacity})
布隆过滤器的原理图, 这个就很容易理解了.
Redis 中的布隆过滤器实现(rebloom 模块扩展)
下载并编译
- Git clone Git://GitHub.com/RedisLabsModules/rebloom
- cd rebloom
- make
配置文件中加载 rebloom
loadmodule /your_path/rebloom.so
重启 Redis 服务器即可
- ./bin/Redis-cli -h 127.0.0.1 -p 6379 -a ****** shutdown
- ./bin/Redis-server Redis.conf
rebloom 在 Redis 中的使用
bloom filter 定义
BF.RESERVE {key} {error_rate} {capacity}
使用给定的期望错误率和初始容量创建空的 Bloom 过滤器(如果不存在的话). 如果打算向 Bloom 过滤器中添加许多项, 则此命令非常有用, 否则只能使用 BF.ADD 添加项.
初始容量和错误率将决定过滤器的性能和内存使用情况. 一般来说, 错误率越小(即对误差的容忍度越低), 每个过滤器条目的空间消耗就越大.
bloom filter 基本操作
1,BF.ADD {key} {item}
单条添加元素
向 Bloom filter 添加一个元素, 如果该 key 不存在, 则创建该 key(过滤器).
如果项是新插入的, 则为 "1"; 如果项以前可能存在, 则为 "0".
2,BF.MADD {key} {item} [item...]
批量添加元素
布尔数 (整数) 的数组. 返回值为 0 或 1 的范围的数据, 这取决于是否将相应的输入元素新添加到过滤器中, 或者是否已经存在.
3,BF.EXISTS {key} {item}
判断单个元素是否存在
如果存在, 返回 1, 否则返回 0
4,BF.MEXISTS {key} {item} [item...]
判断多个元素是否存在
布尔数 (整数) 的数组. 返回值为 0 或 1 的范围的数据, 这取决于是否将相应的元是否已经存在于 key 中.
- 127.0.0.1:8001> bf.reserve bloom_filter_test 0.0000001 1000000
- OK
- 127.0.0.1:8001> bf.reserve bloom_filter_test 0.0000001 1000000
- (error) ERR item exists
- 127.0.0.1:8001>
- 127.0.0.1:8001>
- 127.0.0.1:8001> bf.add bloom_filter_test key1
- (integer) 1
- 127.0.0.1:8001> bf.add bloom_filter_test key2
- (integer) 1
- 127.0.0.1:8001>
- 127.0.0.1:8001> bf.madd bloom_filter_test key2 key3 key4 key5
- 1) (integer) 0
- 2) (integer) 1
- 3) (integer) 1
- 4) (integer) 1
- 127.0.0.1:8001> bf.exists bloom_filter_test key2
- (integer) 1
- 127.0.0.1:8001> bf.exists bloom_filter_test key3
- (integer) 1
- 127.0.0.1:8001> bf.mexists bloom_filter_test key3 key4 key5
- 1) (integer) 1
- 2) (integer) 1
- 3) (integer) 1
- 127.0.0.1:8001>
- 5,bf.insert
- bf.insert{
- key
- } [CAPACITY {
- cap
- }] [ERROR {
- ERROR
- }] [NOCREATE] ITEMS {
- item...
- }
该命令将向 bloom 过滤器添加一个或多个项, 如果它还不存在, 则默认情况下创建它. 有几个参数可用于修改此行为.
key: 过滤器的名称
capacity: 如果指定了, 应该在后面加上要创建的过滤器的所需容量. 如果过滤器已经存在, 则忽略此参数. 如果自动创建了过滤器, 并且没有此参数, 则使用默认容量(在模块级指定). 见 bf.reserve.
error: 如果指定了, 后面应该跟随着新创建的过滤器的错误率(如果它还不存在). 如果自动创建过滤器而没有指定错误, 则使用默认的模块级错误率. 见 bf.reserve.
nocreate: 如果指定, 表示如果过滤器不存在, 就不应该创建它. 如果过滤器还不存在, 则返回一个错误, 而不是自动创建它. 如果需要在创建过滤器和添加过滤器之间进行严格的分离, 可以使用这种方法. 将 NOCREATE 与容量或错误一起指定是一个错误.
item: 指示要添加到筛选器的项的开头. 必须指定此参数.
- 127.0.0.1:8001> bf.insert bloom_filter_test2 items key1 key2 key3
- 1) (integer) 1
- 2) (integer) 1
- 3) (integer) 1
- 127.0.0.1:8001> bf.insert bloom_filter_test2 items key1 key2 key3
- 1) (integer) 0
- 2) (integer) 0
- 3) (integer) 0
- 127.0.0.1:8001> bf.insert bloom_filter_test2 capacity 10000 error 0.00001 nocreate items key1 key2 key3
- 1) (integer) 0
- 2) (integer) 0
- 3) (integer) 0
- 127.0.0.1:8001>
- 127.0.0.1:8001> bf.insert bloom_filter_test2 capacity 10000 error 0.00001 nocreate items key4 key5 key6
- 1) (integer) 1
- 2) (integer) 1
- 3) (integer) 1
- 127.0.0.1:8001>
bf 持久化操作
BF.SCANDUMP {key} {iter}
对 bloom 过滤器进行增量保存. 这对于不能适应常规 save 和 restore 模型的大型 bloom filter 非常有用.
第一次调用这个命令时, iter 的值应该是 0. 这个命令将返回连续的 (iter, data) 对, 直到(0,NULL), 以表示完成
Python 伪代码演示:
- chunks = []
- iter = 0
- while True:
- iter, data = BF.SCANDUMP(key, iter)
- if iter == 0:
- break
- else:
- chunks.append([iter, data])
- # Load it back
- for chunk in chunks:
- iter, data = chunk
- BF.LOADCHUNK(key, iter, data)
bf.scandump 示例
- 127.0.0.1:8001> bf.scandump bloom_filter_test2 0
- 1) (integer) 1
- 2) "\x06\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x04\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x06\x00\x00\x00\x00\x00\x00\x00{\x14\xaeG\xe1z\x84?\x88\x16\x8a\xc5\x8c+#@\a\x00\x00\x00j\x00\x00\x00\n"
- 127.0.0.1:8001> bf.scandump bloom_filter_test2 1
- 1) (integer) 129
- 2) "\x00\x00\x00\x00\xa2\x00\x00\x00\x00\x00\x00B\x01\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00 \x00\x00\b\x00\x00\x00\x00\b\x00\x00@\x00\x01\x04\x18\x02\x00\x00\x00\x82\x00\x00\x80@\x00\b\x00\x00\x00\x00 \x00\x00@\x00\x00\x00\x00\x18\b\x00\b\x00\b\x00\x80B\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x00 (\x00\x00\x00\x00@\x00\x00\x00\x00@\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x80\x00\x00@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\b"
- 127.0.0.1:8001> bf.scandump bloom_filter_test2 129
- 1) (integer) 0
- 2) ""
- 127.0.0.1:8001>
blool filter 数据类型的属性
bf.debug
这里可以看到, 随着 bloom filter 元素的增加, 其空间容量也在不断地增加
- 127.0.0.1:8001> bf.debug bloom_filter_test
- 1) "size:5"
- 2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:5 ratio:1e-07"
- 127.0.0.1:8001>
- 127.0.0.1:8001>
- 127.0.0.1:8001> bf.debug bloom_filter_test
- 1) "size:128955"
- 2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:128955 ratio:1e-07"
- 127.0.0.1:8001>
- 127.0.0.1:8001>
- 127.0.0.1:8001> bf.debug bloom_filter_test
- 1) "size:380507"
- 2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:380507 ratio:1e-07"
- 127.0.0.1:8001>
- 127.0.0.1:8001>
- 127.0.0.1:8001> bf.debug bloom_filter_test
- 1) "size:569166"
- 2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:569166 ratio:1e-07"
- 127.0.0.1:8001>
- 127.0.0.1:8001>
- 127.0.0.1:8001> bf.debug bloom_filter_test
- 1) "size:852316"
- 2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:852316 ratio:1e-07"
- 127.0.0.1:8001>
- 127.0.0.1:8001>
- 127.0.0.1:8001> bf.debug bloom_filter_test
- 1) "size:1000005"
- 2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:1000005 ratio:1e-07"
- 127.0.0.1:8001>
关于布隆过滤器数据类型的空间分析
Redis 的 bigkeys 选项可以分析整个实例中的 big keys 信息, 但是无法分析出 MBbloom-- 类型的 key 值得大小
这里基于 Redis 的 debug object 功能, 实现对 MBbloom-- 类型的 key 的统计(没有找到怎么用 Python 执行 bf.debug 原生命令的执行方式).
- import Redis
- import sys
- import time
- import random
- def get_bf_bigkeys():
- try:
- redis_conn = Redis.StrictRedis(host='127.0.0.1', port=8001, db=0, password='******')
- except:
- print("connect redis error")
- sys.exit(1)
- dict_key = {}
- cursor = 1
- while cursor != 0:
- if cursor == 1:
- key = redis_conn.scan(cursor=0, match='*', count=5000)
- else:
- key = redis_conn.scan(cursor=cursor,match='*', count=5000)
- cursor = key[0]
- if len(key[1])> 0:
- for var in key[1]:
- if str(redis_conn.type(var), encoding = "utf-8") == 'MBbloom--':
- info = redis_conn.debug_object(var)
- dict_key[var] = float(info['serializedlength']) / 1024 / 1024 # byte ---> mb
- res = sorted(dict_key.items(), key=lambda dict_key: dict_key[1], reverse=True)
- for i in range(10 if len(res)> 10 else len(res)):
- print(res[i])
- if __name__ == "__main__":
- get_bf_bigkeys()
统计结果示例如下
- [root@tencent02 redis8001]# python3 static_big_bf_keys.py
- (b'bloom_filter_test', 4.000059127807617)
- (b'my_bf2', 0.04577445983886719)
- (b'bloom_filter_test2', 0.00014019012451171875)
- (b'my_bf1', 0.0001220703125)
- [root@tencent02 redis8001]#
来源: http://www.linuxidc.com/Linux/2019-09/160787.htm