Redis布隆过滤器

Dear 丶 2023-07-06 14:47 103阅读 0赞

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

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

### 布隆过滤器的原理 ###

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

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

*  使用k个哈希函数对元素值进行hash, 得到k个哈希值.
 *  以哈希值作为下标, 将bit数组中对应的值置为1.

> 如何保证哈希值不超过数组长度, 有两种办法:  
> a. tab\[hash%n\] = 1  
> b. tab\[hash&(n-1)\] = 1(n为偶数)

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

*  使用k个哈希函数对元素值进行hash, 得到k个哈希值.
 *  以哈希值作为下标, 判断bit数组中对应的值是否为1.
 *  如果都为1, 那这个元素可能存在, 如果有一个不为1, 那这个元素一定不存在.

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdGlhbnhpYW5nX2thb2xh_size_16_color_FFFFFF_t_70]

### 布隆过滤器安装 ###

布隆过滤器是作为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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdGlhbnhpYW5nX2thb2xh_size_16_color_FFFFFF_t_70 1]

(6) 启动redis

redis-server /usr/local/redis.conf

(7) 进入redis客户端

redis-cli

(8) 测试bloomfilter

![在这里插入图片描述][2020021822013234.jpg]

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

(9) 布隆过滤器配置

bf.reserve 过滤器名称 error_rate initial_size

*  error\_rate  
    布隆过滤器的错误率, 这个值越低位数组的容量就越大.
 *  initial\_size  
    布隆过滤器可以保证准确率的元素个数, 当实际存储的元素个数超过这个值之后, 过滤器的准确率会下降

![在这里插入图片描述][20200218224721239.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdGlhbnhpYW5nX2thb2xh_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200219221121576.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdGlhbnhpYW5nX2thb2xh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdGlhbnhpYW5nX2thb2xh_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200218215740966.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdGlhbnhpYW5nX2thb2xh,size_16,color_FFFFFF,t_70
[2020021822013234.jpg]: https://img-blog.csdnimg.cn/2020021822013234.jpg
[20200218224721239.jpg]: https://img-blog.csdnimg.cn/20200218224721239.jpg