之前一篇文章提到了布隆过滤器，不过没有实际在REDIS中使用，这篇文章就示例在Redis使用布隆过滤器。Redis的默认版本中并没有布隆过滤器的功能，需要另外下载安装bloomfilter插件，且需要使用RedisV4.0以上版本。bloomfilter插件的官网下载地址：https://redislabs.com/blog/rebloom-bloom-filter-datatype-redis/ GIThub上有项目地址：https://github.com/RedisBloom/RedisBloom/releases 目前的最新版本是V2.2.4。本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
1.先下载redisbloom插件解压，cmake生成rebloom.so文件本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.4.tar.gz tar -zxvf v1.1.1.tar.gz cd redisbloom-2.2.4/ make本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
2.打开配置redis.conf，在loadmodule处加上rebloom.so文件的路径,重新启动redis
loadmodule /目录/rebloom.so本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
redisbloom的命令不多，也很好掌握。
1.添加元素：[bf.add key options]， 也可以添加多个元素：[bf.add key ...options]
bf.add users user3
bf.madd users user4 user5 user6 user本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
2.判断元素是否存在：[bf.exists key options]，也可以判断多个元素是否存在：[bf.add key ...options]
bf.exists users user1
bf.mexists users user4 user5 user6 user7 user8本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
bf.reserve命令有三个参数，分别是：
key：键
error_rate：期望错误率，期望错误率越低，需要的空间就越大。
capacity：初始容量，当实际元素的数量超过这个初始化容量时，误判率上升。
如果不使用bf.reserve命令创建，而是使用Redis自动创建的布隆过滤器，默认的error_rate是 0.01，capacity是 100。本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
布隆过滤器的error_rate越小，需要的存储空间就越大，对于不需要过于精确的场景，error_rate设置稍大一点也可以。布隆过滤器的capacity设置的过大，会浪费存储空间，设置的过小，就会影响准确率，所以在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。总之，error_rate和 capacity都需要设置一个合适的数值。本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
布隆过滤器的精度问题主要来自于有限的BIT数组大小和hash算法碰撞。hash算法存在碰撞的可能，Bloom Filter 不同的数据更有可能hash为一个下标数据，故为了提高精确度就可以使用如下两个方法：
1.需要使用多个(也要有限)hash 算法标记一个数据，太少hash碰撞概率增加；太多会很快占满bit位。
2.增大BIT数组的大小
这两者的变化以及数据的误差率如下图所示：本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
图中的数据意义：(K：hash函数个数; n：元素个数; m: Bit数组大小;P: 误报率) ，从图中可以看到：1千万数据， 5个hash函数，10亿bit数组，误报率远低于: 0.0001% 。而10亿bit数组的大小也即为 1000000000/1024/1024=950.37M。不到1G。本文地址:http://www.04007.cn/article/985.html,未经许可,不得转载.
本文地址:http://www.04007.cn/article/985.html 未经许可,不得转载. 手机访问本页请扫描右下方二维码.
|
|
手机扫码直接打开本页面 |
