深入详解Redis布隆过滤器

清疚 2021-09-25 11:20 277阅读 0赞

前面学习HyperLogLog数据类型来进行估算，还是非常有意义的，能解决很多精度要求不高的统计问题。 但是对于某一个值是否存在于HyperLogLog结构里面，就变现的无能为力，因为它只提供了 pfadd 和 pfcount 方法，没有提供 pfcontains 方法。

讲个使用场景，比如我们在使用新闻客户端浏览新闻时，会不停的给我们推荐新的内容，而且每次推荐都会是不同的，以去掉那些我们已经浏览过的新闻。想一想它们是咱们做到推送去重呢？

你可能会想到，服务器已经记录了用户看过的所有历史记录，当推送系统给用户进行推送新闻时则可以从每个用户历史记录里面进行筛选，过滤掉那些已经存在的记录。

但存在的问题时，当用户量很大且每个用户浏览过的新闻又很大的情况下，这种方式很难满足性能上的诉求。实际上，如果历史记录数据保存在关系数据库里，去重操作则需要频繁地对数据库执行 exists 查询，当系统并发量很高时，数据库也很难扛住压力。

可能还会想到使用缓存，但是将如此海量历史记录全都缓存起来，那得浪费很大的存储空间，同时存储空间也随着时间线性增长，短期来看能扛，但是长此以往也是很危险？不缓存的话，性能又跟不上，该怎么办呢？

redis 高级数据结构布隆过滤器闪亮登场。它是专门解决这种去重问题的。它在解决去重问题的同时还能节省90%以上内存，只是会存在一定的误判。

## 布隆过滤器简介 ##

### 哈希函数 ###

**哈希函数**：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。如下示意图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70][]

可以明显的看到，原始数据经过哈希函数的映射后称为了一个个的哈希编码，数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。

**布隆过滤器介绍**

*  巴顿.布隆于一九七零年提出
 *  一个很长的二进制向量 （位数组）
 *  一系列随机函数 (哈希)
 *  空间效率和查询效率高
 *  有一定的误判率（哈希表是精确匹配）

**布隆过滤器基本用法**

布隆过滤器有两个基本指令，bf.add 添加元素，bf.exists 查询元素是否存在，它的用法和 set 集合的 sadd 和 sismember 差不多。注意 bf.add 只能一次添加一个元素，如果想要一次添加多个，就需要用到 bf.madd 指令。同样如果需要一次查询多个元素是否存在，就需要用到 bf.mexists 指令。

127.0.0.1:6379> bf.add codehole user1 (integer) 1 127.0.0.1:6379> bf.add codehole user2 (integer) 1 127.0.0.1:6379> bf.add codehole user3 (integer) 1 127.0.0.1:6379> bf.exists codehole user1 (integer) 1 127.0.0.1:6379> bf.exists codehole user2 (integer) 1 127.0.0.1:6379> bf.exists codehole user3 (integer) 1 127.0.0.1:6379> bf.exists codehole user4 (integer) 0 127.0.0.1:6379> bf.madd codehole user4 user5 user6 1) (integer) 1 2) (integer) 1 3) (integer) 1 127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7 1) (integer) 1 2) (integer) 1 3) (integer) 1 4) (integer) 0

## 布隆过滤器原理 ##

布隆过滤器的核心实现是一个超大的位数组和几个哈希函数。假设数组的长度为m，哈希函数的个数为k

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70 1][]

以上图为例，具体的操作流程：假设集合里面有3个元素\{x, y, z\}，哈希函数的个数为3。首先将位数组进行初始化，将里面每个位都设置位0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。

**布隆过滤器添加元素**

*  将要添加的元素给k个哈希函数
 *  得到对应于位数组上的k个位置
 *  将这k个位置设为1

**布隆过滤器查询元素**

*  将要查询的元素给k个哈希函数
 *  得到对应于位数组上的k个位置
 *  如果k个位置有一个为0，则肯定不在集合中
 *  如果k个位置全部为1，则可能在集合中

## 布隆过滤器优缺点 ##

**优点**：二进制组成的数组，占用内存极少，并且插入和查询速度都足够快。

**缺点**：随着数据增加，误判率会增加；无法判断数据一定存在；另外一个重要缺点就是无法删除数据。

> 使用时 不要让实际元素数量远大于初始化数量；
> 
> 当实际元素数量超过初始化数量时，应该对布隆过滤器进行 重建，重新分配一个 size 更大的过滤器，再将所有的历史元素数据批量添加进去；

## 布隆过滤器使用场景 ##

基于上述功能，可以大致把布隆用于以下场景：

*  海量数据判是否存在：实现上述去重功能，当然如果你的服务器内存足够大的话，那么使用HashMap 也会是个不错的解决方案，理论时间复杂度可以达到O(1)。
 *  解决缓存穿透：热点数据常会放在redis中当作缓存，例如产品信息。通常一个请求过来之后会先查询缓存，而不用直接读取数据库，这是提升性能最简单直接的做法， 但是如果一直请求一个不存在的缓存，因为一定不会存在缓存中，就会有 大量请求直接打到数据库 上，造成缓存穿透，布隆也可以解决此类问题。
 *  爬虫、邮箱系统的过滤：平时不知道你有没有注意到有一些正常的邮件也会被放进垃圾邮件目录中，这就是使用布隆过滤器 误判 导致的。

## 布隆过滤器代码实现 ##

### 简单模拟实现 ###

根据上述基础理论，很容易就可以实现一个用于 简单模拟 的布隆数据结构：

public static class BloomFilter { private byte[] data; public BloomFilter(int initSize) { this.data = new byte[initSize * 2]; // 默认创建大小 * 2 的空间 } public void add(int key) { int location1 = Math.abs(hash1(key) % data.length); int location2 = Math.abs(hash2(key) % data.length); int location3 = Math.abs(hash3(key) % data.length); data[location1] = data[location2] = data[location3] = 1; } public boolean contains(int key) { int location1 = Math.abs(hash1(key) % data.length); int location2 = Math.abs(hash2(key) % data.length); int location3 = Math.abs(hash3(key) % data.length); return data[location1] * data[location2] * data[location3] == 1; } private int hash1(Integer key) { return key.hashCode(); } private int hash2(Integer key) { int hashCode = key.hashCode(); return hashCode ^ (hashCode >>> 3); } private int hash3(Integer key) { int hashCode = key.hashCode(); return hashCode ^ (hashCode >>> 16); } }

实现起来很简单，内部维护一个 byte 类型数组，另外创建三个不同的 hash 函数（借鉴 HashMap 哈希抖动方法），分别使用自身的 hash 和右移不同位数相异或的结果。并且提供基础的 add 和 contains 方法。

简单测试轮子的效果：

public static void main(String[] args) { Random random = new Random(); // 假设我们的数据有 1 百万 int size = 1_000_000; // 用一个数据结构保存一下所有实际存在的值 LinkedList<Integer> existentNumbers = new LinkedList<>(); BloomFilter bloomFilter = new BloomFilter(size); for (int i = 0; i < size; i++) { int randomKey = random.nextInt(); existentNumbers.add(randomKey); bloomFilter.add(randomKey); } // 验证已存在的数是否都存在 AtomicInteger count = new AtomicInteger(); AtomicInteger finalCount = count; existentNumbers.forEach(number -> { if (bloomFilter.contains(number)) { finalCount.incrementAndGet(); } }); System.out.printf("实际的数据量： %d, 判断存在的数据量: %d \n", size, count.get()); // 验证10个不存在的数 count = new AtomicInteger(); while (count.get() < 10) { int key = random.nextInt(); if (existentNumbers.contains(key)) { continue; } else { // 这里一定是不存在的数 System.out.println(bloomFilter.contains(key)); count.incrementAndGet(); } } }

输出结果

实际的数据量： 1000000, 判断存在的数据量: 1000000 false true false true true true false false true false

这就是前面说到的，当布隆说某个值 存在时， 这个值可能不存在，当说某个值 不存在时，肯定是不存在，并且还有一定的误判率。。

### 使用 Google 开源的 Guava 自带的布隆过滤器 ###

自己实现的目的主要是为了让自己搞懂布隆过滤器的原理，Guava 中布隆过滤器的实现算是比较权威的，所以实际项目中我们不需要手动实现一个布隆过滤器。

首先我们需要在项目中引入 Guava 的依赖：

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>28.0-jre</version> </dependency>

实际使用如下：

我们创建了一个最多存放 最多 1500 个整数的布隆过滤器，并且我们可以容忍误判的概率为百分之（0.01）

// 创建布隆过滤器对象 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 1500, 0.01); // 判断指定元素是否存在 System.out.println(filter.mightContain(1)); System.out.println(filter.mightContain(2)); // 将元素添加进布隆过滤器 filter.put(1); filter.put(2); System.out.println(filter.mightContain(1)); System.out.println(filter.mightContain(2));

在我们的示例中，当 mightContain() 方法返回 true 时，我们可以 99％ 确定该元素在过滤器中，当过滤器返回 false 时，我们可以 100％ 确定该元素不存在于过滤器中。

Guava 提供的布隆过滤器的实现还是很不错的 （想要详细了解的可以看一下它的源码实现），但是它有一个重大的缺陷就是只能单机使用 （另外，容量扩展也不容易），而现在互联网一般都是分布式的场景。为了解决这个问题，我们就需要用到 Redis 中的布隆过滤器了。

## 相关阅读 ##

*  《Redis 深度历险》 - 钱文品/ 著 - [https://book.douban.com/subject/30386804/][https_book.douban.com_subject_30386804]
 *  5 分钟搞懂布隆过滤器，亿级数据过滤算法你值得拥有！ - [https://juejin.im/post/5de1e37c5188256e8e43adfc][https_juejin.im_post_5de1e37c5188256e8e43adfc]
 *  【原创】不了解布隆过滤器？一文给你整的明明白白！ - [https://github.com/Snailclimb/JavaGuide/blob/master/docs/dataStructures-algorithms/data-structure/bloom-filter.md][https_github.com_Snailclimb_JavaGuide_blob_master_docs_dataStructures-algorithms_data-structure_bloom-filter.md]

## 最后 ##

欢迎关注个人公众号 【CodingCode】，享受第一手推送资料，不定期更新学习笔记；同时随时欢迎私信，一定知无不言、言无不尽。

![20210628104132967.jpg][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70]: /images/20210923/d207f0630004411eae5affd96390159b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70 1]: /images/20210923/bb37169b7b83467fb192fbb706687e43.png
[https_book.douban.com_subject_30386804]: https://book.douban.com/subject/30386804/
[https_juejin.im_post_5de1e37c5188256e8e43adfc]: https://juejin.im/post/5de1e37c5188256e8e43adfc
[https_github.com_Snailclimb_JavaGuide_blob_master_docs_dataStructures-algorithms_data-structure_bloom-filter.md]: https://github.com/Snailclimb/JavaGuide/blob/master/docs/dataStructures-algorithms/data-structure/bloom-filter.md
[20210628104132967.jpg]: /images/20210923/d812c57a91f74b199c15697f1589ebad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70 2]: /images/20210923/e1874f4247984c208995cf67d0d5f7a9.png