最资讯丨Redis系列16：聊聊布隆过滤器（原理篇）
Redis系列1：深刻理解高性能Redis的本质Redis系列2：数据持久化提高可用性Redis系列3：高可用之主从架构Redis系列4：高可用之Sentinel(哨兵模式）Redis系列5：深入分析Cluster 集群模式 追求性能极致：Redis6.0的多线程模型追求性能极致：客户端缓存带来的革命Redis系列8：Bitmap实现亿万级数据计算Redis系列9：Geo 类型赋能亿级地图位置计算Redis系列10：HyperLogLog实现海量数据基数统计Redis系列11：内存淘汰策略Redis系列12：Redis 的事务机制Redis系列13：分布式锁实现Redis系列14：使用List实现消息队列Redis系列15：使用Stream实现消息队列
1 Bloom Filter 介绍布隆过滤器（Bloom Filter）是 Redis 4.0 版本提供的新功能，我们一般将它当做插件加载到 Redis 服务器中，给 Redis 提供强大的去重功能。它是一种概率性数据结构，可用于判断一个元素是否存在于一个集合中。相比较之 Set 集合的去重功能，布隆过滤器空间上能节省 90% +，不足之处是去重率大约在 99% 左右，那就是有 1% 左右的误判率，这种误差是由布隆过滤器的自身结构决定的。
优点：空间效率和查询时间都比一般的算法要好的多缺点：有一定的误识别率和删除困难2 原理分析布隆过滤器（Bloom Filter）是一个高空间利用率的概率性数据结构，由二进制向量（即位数组）和一系列随机映射函数（即哈希函数）两部分组成。通过使用exists()来判断某个元素是否存在于自身结构中。当布隆过滤器判定某个值存在时，其实这个值只是有可能存在；当它说某个值不存在时，那这个值肯定不存在，这个误判概率大约在 1% 左右。原理拆解如下：
【资料图】
当使用布隆过滤器添加 key 时，会使用不同的 hash 函数对 key 存储的元素值进行哈希计算，从而会得到多个哈希值。根据哈希值计算出一个整数索引值，将该索引值与位数组长度做取余运算，最终得到一个位数组位置，并将该位置的值变为 1。每个 hash 函数都会计算出一个不同的位置，然后把数组中与之对应的位置变为 1。这边可能出现元素碰撞的情况，比如位置3，a元素和b元素的hash计算位置一致，所以出现了碰撞。
2.2 判定元素是否存在步骤如果我们要判定一个元素是否存在，需要如下步骤：
首先对给定元素key执行哈希计算，这样可以得到元素增加时的bit位数组位置判断这些位置是否都为 1，如果其中有一个为 0，那么说明元素不存在若全部位置都为 1，则说明元素有可能存在。为啥说是可能存在呢，因为上面说过了，哈希函数出的结果会出现碰撞，所以布隆过滤器会存在误判。如上图c，他的位置被其他元素的位置完全覆盖，即使c没有存储，对应位置上也被a和b的Hash函数设置为1，这时候就可能误判为c是有存储的。有概率存在这样的 key，它们内容不同，但多次 Hash 后的 Hash 值都相同。
2.3 元素删除步骤一般不会删除元素，我们上面说了，因为可能存在碰撞情况，所以也有可能存在误删除情况。删除意味着需要将对应的 n 个 bits 位置设置为 0，其中有可能是其他元素对应的位。比如图中的b删除之后，位置3的值也被设置为0，这样a也可能会被判定为不存在。
3 使用场景介绍我们在遇到数据量大的时候，为了去重并避免大批量的重复计算，可以考虑使用 Bloom Filter 进行过滤。具体常用的经典场景如下：
解决大流量下缓存穿透的问题，参考笔者这篇《一次缓存雪崩的灾难复盘》。过滤被屏蔽、拉黑、减少推荐的信息，一般你在浏览抖音或者百度App的时候，看到不喜欢的会设置减少推荐、屏蔽此类信息等，都可以采用这种原理设计。各种名单过滤，使用布隆过滤器实现第一层的白名单或者黑名单过滤，可用于各种AB场景。4 安装集成如果是自己编译安装，可以从 github 下载，目前的latest 的 release 版本是 v2.4.5，下载地址如下：https://github.com/RedisBloom/RedisBloom/releases/tag/v2.4.5
直接按照编译的方式进行安装：
# 解压文件：tar -zxvf tar -zxvf RedisBloom-2.4.5.tar.gz# 进入目录：cd RedisBloom-2.4.5# 执行编译命令，生成redisbloom.so 文件：make# 拷贝至指定目录：cp redisbloom.so /usr/local/redis/RedisBloom-2.4.5/redisbloom.so# 需要修改 redis.conf 文件，新增 loadmodule配置，并重启 Redis。# 在redis配置文件里加入以下配置：loadmodule /usr/local/redis/RedisBloom-2.4.5/redisbloom.so# 配置完成后重启redis服务：redis-server /usr/local/redis/RedisBloom-2.4.5/redis.conf# 测试是否安装成功127.0.0.1:6379> bf.add user brand(integer) 1127.0.0.1:6379> bf.exists user brand(integer) 1大致说了布隆过滤器的原理和使用场景，下一篇我们来看看实战。
