[TOC] > **RedisBloom** 为 Redis 添加了四种概率数据结构：可扩展的**布隆过滤器**、**布谷鸟过滤器**、**count-min sketch**和**top-k**。 > **布隆过滤器**和**布谷鸟过滤器**用于高度确定地确定一个元素是否是集合的成员。 > 官网 https://redis.io/docs/stack/bloom ## 安装 RedisBloom 模块 ~~~sh git clone --recursive https://github.com/RedisBloom/RedisBloom.git cd RedisBloom make setup make ~~~ ## **布隆过滤器** * 由一个初值都为零的 bit 数组和多个哈希函数构成，用来快速判断某个数据是否存在 * 本质就是判断具体数据存不存在一个大的集合中 * 布隆过滤器类似 `set` 的数据结构，只是统计结构不太准确 ### 应用场景 * 垃圾邮件过滤 * 文字处理中的错误单词检测 * 网络爬虫重复URL检测 * 会员抽奖 * 判断一个元素在亿级数据中是否存在 * 缓存穿透 ### 原理 布隆过滤器(Bloom Filter) 是一种专门用来解决去重问题的高级数据结构。 实质就是一个大型**位数组和几个不同的无偏hash函数 **(无偏表示分布均匀)。**由一个初值都为零的bit数组和多个个哈希函数构成**，用来快速判断某个数据是否存在 。但是跟 HyperLogLog 一样，它也一样有那么一点点不精确，也存在一定的误判概率。 ### **添加key** 使用多个 hash 函数对 key 进行 hash 运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash 函数都会得到一个不同的位置，将这几个位置都置 1 就完成了 add 操作。 ### **查询key** 先把这个 key 通过相同的多个 hash 函数进行运算，查看对应位置不都为 1 如果这些点，**有任何一个为 0 则被查询变量一定不在，如果都是 1，则被查询变量很 可能存在** **为什么说是可能存在，而不是一定存在呢？**`那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。`  ### 误判率，为什么不能删除元素 误判是指多个输入经过 hash 之后在相同 bit 位置为1 了，这样就无法判断究竟是哪个输入所产生的，**误判的根源在于相同的 bit 位被多次映射且置 1。 ** **布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位**如果删除一位，或影响其他元素。 ### 基本命令 ~~~sh 127.0.0.1:6379> bf.reserve bf 0.1 10 # 创建一个空的布隆过滤器 错误率0.1 容量10（超出10以后性能下降)。错误率越小，需要的空间越大 OK 127.0.0.1:6379> bf.add bf a # 添加项 (integer) 1 127.0.0.1:6379> bf.add bf a (integer) 0 127.0.0.1:6379> bf.madd bf b c d e # 添加多个项 1) (integer) 1 2) (integer) 1 3) (integer) 1 4) (integer) 1 127.0.0.1:6379> bf.madd bf e f g h i j 1) (integer) 0 2) (integer) 1 3) (integer) 1 4) (integer) 1 5) (integer) 1 6) (integer) 1 127.0.0.1:6379> bf.exists bf c # 项是否存在 1：可能存在、0：一定不存在 (integer) 1 127.0.0.1:6379> bf.exists bf q (integer) 0 127.0.0.1:6379> bf.mexists bf a d h l 1) (integer) 1 2) (integer) 1 3) (integer) 1 4) (integer) 0 ~~~ 更多命令：https://redis.io/commands/?name=bf. ### 优缺点 #### **优点：** * 高效得插入和查询，占用空间少 #### **缺点：** * 不能删除元素 * 存在误判，不同的数据可能出来相同的hash值 ## 杜鹃过滤器 **解决了布隆过滤器不能删除元素的问题** ~~~sh 127.0.0.1:6379> cf.reserve cf 10 # 创建一个具有初始容量（10个项目）的空杜鹃过滤器 OK 127.0.0.1:6379> cf.add cf a (integer) 1 127.0.0.1:6379> cf.exists cf a (integer) 1 127.0.0.1:6379> cf.add cf b (integer) 1 127.0.0.1:6379> cf.add cf c (integer) 1 127.0.0.1:6379> cf.del cf a # 删除过滤器中项目 (integer) 1 ~~~ 更多命令：https://redis.io/commands/?name=cf.