基于Redis扩展模块的布隆过滤器使用

191次阅读

共计 6085 个字符，预计需要花费 16 分钟才能阅读完成。

什么是布隆过滤器？
它实际上是一个很长的二进制向量和一系列随机映射函数。把一个目标元素通过多个 hash 函数的计算，将多个随机计算出的结果映射到二进制向量的位中，依次来间接标记一个元素是否存在于一个集合中。
布隆过滤器可以做什么？
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器特点
如果布隆过滤器显示一个元素不存在于集合中，那么这个元素 100% 不存在与集合当中
如果布隆过滤器显示一个元素存在于集合中，那么很有可能存在，可能性取决于对布隆过滤器的定义（BF.RESERVE {key} {error_rate} {capacity}）

布隆过滤器的原理图，这个就很容易理解了。

基于 Redis 扩展模块的布隆过滤器使用

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 扩展模块的布隆过滤器使用

这里基于 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]#