亿级数据过滤和布隆过滤器

如何高效实现存在判断

在刷抖音时你有刷到过重复的推荐内容吗？这么多的推荐内容要推荐给这么多的用户，它是怎么保证每个用户在看推荐内容时，保证不会出现之前已经看过的推荐视频呢？也就是说，抖音是如何实现推送去重的呢？
你会想到服务器记录了用户看过的所有历史记录，当推荐系统推荐短视频时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。问题是当用户量很大，每个用户看过的短视频又很多的情况下，这种方式，推荐系统的去重工作在性能上跟的上么？实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行 exists 查询，当系统并发量很高时，数据库是很难抗住压力的。
你可能又想到了缓存，但是这么多用户这么多的历史记录，如果全部缓存起来，那得需要浪费多大的空间。并且这个存储空间会随着时间呈线性增长，就算你用缓存撑得住一个月，但是又能继续撑多久呢？不缓存性能又跟不上，咋办呢？

布隆过滤器是什么

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。可以把它简单理解为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那么一定不存在。

布隆过滤器的使用场景

基于上述的功能，我们大致可以把布隆过滤器用于以下的场景之中：

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

布隆过滤器原理解析

布隆过滤器的工作原理主要基于位数组和哈希函数。布隆过滤器是一种高效的多哈希函数概率型数据结构，它利用位数组和哈希函数来测试一个元素是否属于集合。以下是从不同方面去了解布隆过滤器的原理：

数据结构：布隆过滤器使用了一个大的位数组和多个哈希函数。在初始化时，所有的位都被设置为0。当添加一个元素到布隆过滤器时，该元素会被每个哈希函数处理，得到相应的哈希值，然后在位数组中的对应位置上置为1。这样，当查询一个元素时，如果所有哈希函数计算出的位置上的位都是1，那么认为该元素可能存在于集合中；如果有任意一个位置上的位是0，那么该元素肯定不在集合中。
空间计算：布隆过滤器的空间需求取决于预计要存储的元素数量和可接受的误判率。通过算法可以计算出所需的位数组大小和哈希函数的数量。较大的位数组和较多的哈希函数可以降低误判率，但会增加计算量和所需内存。
增加元素：向布隆过滤器中添加新元素时，需要用所有哈希函数对该元素进行处理，得到的结果用来定位位数组中哪些位置需要被标记为1。这个过程可能会引起位数组中某些位从0变为1的变化，这是正常的。
查询元素：查询操作涉及使用相同的哈希函数集对目标元素进行哈希处理，检查对应的位数组位置是否全为1。如果全部位都是1，则元素可能已存在；如果任意一个位置上的位是0，那么该元素肯定不存在。
删除元素难度：布隆过滤器不支持删除操作，因为一个位可能会被多个元素所共享。如果尝试删除某个位，可能会错误地影响其他元素的检测结果。

布隆过滤器的基本用法

在这里插入图片描述

布隆过滤器有两个基本指令， 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

上面使用的布隆过过滤器只是默认参数的布隆过滤器，它在我们第一次 add 的时候自动创建。Redis也提供了可以自定义参数的布隆过滤器，只需要在 add 之前使用 bf.reserve 指令显式创建就好了。如果对应的 key 已经存在， bf.reserve 会报错。

布隆过滤器代码实现

以下实现包括了三个哈希函数（hash1、hash2、hash3），以及添加元素和判断元素是否存在的方法（add、contains）。

public 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);
    }
}