Redis布隆过滤器

在redis中我们可以使用布隆过滤器(BloomFilter)来解决缓存穿透的问题, 具体流程就是, 在更新缓存时, 我们会将缓存数据的key添加到布隆过滤器中, 然后在查询缓存之前, 我们先判断key在布隆过滤器中是否存在, 存在才去查询缓存, 不存在则直接返回空.

布隆过滤器(BloomFilter) 是一种插入和查询性能非常高的数据结构, 功能有点类似于HashMap, 但相对于HashMap来说, 它的性能更高, 占用的空间更少.

布隆过滤器的原理

布隆过滤器由一个长度为n的bit数组和k个哈希函数组成. bit数组的每个元素都只占用1bit, 值只能是0或1.

一个元素添加到布隆过滤器的过程如下:

如何保证哈希值不超过数组长度, 有两种办法:

a. tab[hash%n] = 1
b. tab[hash&(n-1)] = 1(n为偶数)

判断一个元素在布隆过滤器中是否存在的过程如下:

从上文可以知道布隆过滤器的性能与n和k的值有关, n值越大, 布隆过滤器的错误率就越低, k值越大, 保证准确率的元素个数就越少(比如保证100个元素的准确率很高, 超过100个后准确率就明显下降).

布隆过滤器安装

布隆过滤器是作为redis的一个插件安装的.

(1) github地址

https://github.com/RedisBloom/RedisBloom

(2) 下载包

wget https://github.com/RedisBloom/RedisBloom/archive/v2.0.2.tar.gz

(3) 解压包

tar -zxvf v2.0.2.tar.gz -C /usr/local/apps/bloomfilter/

(4) 进入解压后的包中, 进行编译

cd /usr/local/apps/bloomfilter/RedisBloom-2.0.2
make

(5) 编译后会生成一个redisbloom.so文件, 配置到redis.conf中

loadmodule /usr/local/apps/bloomfilter/RedisBloom-2.0.2/redisbloom.so

(6) 启动redis

redis-server /usr/local/redis.conf

(7) 进入redis客户端

redis-cli

(8) 测试bloomfilter

newFilter为过滤器的名称, foo为key.

(9) 布隆过滤器配置

bf.reserve 过滤器名称 error_rate initial_size

原文链接：csdn.net/litianxiang_kaola/article/details/104401924