linuxsir首页 LinuxSir.Org | Linux、BSD、Solaris、Unix | 开源传万世,因有我参与欢迎您!
网站首页 | 设为首页 | 加入收藏
您所在的位置:主页 > Linux数据库 >

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

时间:2019-11-20  来源:未知  作者:admin666

什么是布隆过滤器?
它实际上是一个很长的二进制向量和一系列随机映射函数。把一个目标元素通过多个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
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])

        
友情链接
  • Mozilla发布Firefox 67.0.4,修复沙箱逃逸漏洞
  • 蚂蚁金服正式成为CNCF云原生计算基金会黄金会员
  • Firefox 68将采用Microsoft BITS安装更新
  • OpenSSH增加对存储在RAM中的私钥的保护
  • 谷歌想实现自己的curl,为什么?
  • Raspberry Pi 4发布:更快的CPU、更大的内存
  • Firefox的UA将移除CPU架构信息
  • Ubuntu放弃支持32位应用程序实属乌龙,Steam会否重回Ubuntu怀抱
  • Qt 5.13稳定版发布:引入glTF 2.0、改进Wayland以及支持Lottie动
  • 红帽企业Linux 7现已内置Redis 5最新版
  • Slack进入微软内部禁用服务清单,GitHub也在其列?
  • 安全的全新编程语言V发布首个可用版本
  • Windows Terminal已上架,快尝鲜
  • 阿里巴巴微服务开源生态报告No.1
  • 面世两年,Google地球将支持所有基于Chromium的浏览器
  • 推进企业容器化持续创新,Rancher ECIC千人盛典完美收官
  • CentOS 8.0最新构建状态公布,或于数周后发布
  • Debian移植RISC
  • 微软拆分操作系统的计划初现雏形
  • Oracle发布基于VS Code的开发者工具,轻松使用Oracle数据库
  • Ubuntu 19.10停止支持32位的x86架构
  • 微软为Windows Terminal推出全新logo
  • 联想ThinkPad P系列笔记本预装Ubuntu系统
  • 微软发布适用于Win7/8的Microsoft Edge预览版
  • 启智平台发布联邦学习开源数据协作项目OpenI纵横
  • 经过六个多月的延迟,微软终于推出Hyper
  • ZFS On Linux 0.8.1 发布,Python可移植性工作
  • DragonFly BSD 5.6.0 发布,HAMMER2状态良好
  • Linux Kernel 5.2
  • CentOS 8.0 看起来还需要几周的时间
  • 百度网盘Linux版正式发布
  • PCIe 6.0宣布:带宽翻倍 狂飙至256GB/s
  • PHP 7.4 Alpha 发布,FFI扩展,预加载Opcache以获得更好的性能
  • Canonical将在未来的Ubuntu版本中放弃对32位架构的支持
  • Scala 2.13 发布,改进的编译器性能
  • 微软的GitHub收购了Pull Panda,并且使所有订阅完全免费
  • Windows Subsystem for Linux 2 (WSL 2)现在适用于Windows 10用
  • Debian 10 “Buster”的RISC
  • MariaDB宣布发布MariaDB Enterprise Server 10.4
  • DXVK 1.2.2 发布,带来微小的CPU开销优化
  • DragonFlyBSD 5.6 RC1 发布,VM优化,默认为HAMMER2
  • PrimeNG 8.0.0 发布,支持Angular 8,FocusTrap等
  • GIMP 2.10.12 发布,一些有用的改进
  • 清华大学Anaconda 镜像服务即将恢复
  • Debian GNU/Linux 10 “Buster” 操作系统将于2019年7月6日发布
  • 时时彩论坛
  • 五星体育斯诺克
  • 北单比分直播
  • 河北11选5走势图
  • 福建体彩36选7开奖结果
  • 九龙图库下载