URL去重策略（布隆过滤器）

#软件开发 #数据结构 2023-08-30

在网络爬虫爬取数据时需要解决海量数据的存在性问题，也即判断给定数据是否存在。比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，上亿）、防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）、邮箱的垃圾邮件过滤（判断一个邮件地址是否在垃圾邮件列表中）、黑名单功能（判断一个IP地址或手机号码是否在黑名单中）等等。

有问题的去重策略

策略	问题
在数据库中创建字段的 UNIQUE 属性	在多次数据库的 UNIQUE 报错之后，程序可能会直接崩溃
在数据库中创建一个唯一的索引，在插入数据之前检查待插入的数据是否存在	如果在每一次插入数据之前都去检查待插入的数据是否存在，需要频繁地对数据库进行 exists 查询，当系统并发量很高时，数据库是很难扛住压力的，而且也势必会影响程序的效率
使用 Redis 缓存	将海量的历史记录全部缓存起来，对存储空间的负担非常大
使用 Set 或 Map 保存数据，确保唯一	容易 OOM，从待访问队列中解析出来的URL要远比它本身要多得多，程序占用的内存太大了

布隆过滤器

优缺点

Bloom Filter 是由 Bloom 在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。

优点：占用空间小，插入和查询的效率高，即以正确率换空间和时间。
缺点：
- 有一定的误判率，且添加到集合中的元素越多，误报的可能性就越大：
  - 当布隆过滤器说某个值存在时，这个值可能不存在
  - 当布隆过滤器说某个值不存在时，这个值一定不存在
- 存放在布隆过滤器的数据不容易删除

原理

布隆过滤器实际就是一系列的 Hash 函数 + BitSet 实现的。

初始化

创建一个 m 位的 BitSet，先将所有位都初始化为 0，然后选择 k 个不同的哈希函数。第 i 个哈希函数作用于字符串 str 的结果记为 \(H_i(str)\)，且 \(H_i(str)\) 的范围是 \([0, m-1]\)。

加入字符串

对于字符串 str，分别计算 \(H_1(str), H_2(str), ..., H_k(str)\)，然后将 BitSet 的第 \(H_1(str), H_2(str), ..., H_k(str)\) 位设为 1。

检查字符串

对于字符串 str，分别计算 \(H_1(str), H_2(str), ..., H_k(str)\)，然后检查 BitSet 的第 \(H_1(str), H_2(str), ..., H_k(str)\) 位是否为 1：

若存在其中任何一位不为 1，则可以判定 str 一定没有被记录过；
若全部位为 1，则可以“认为”该 str 已被记录过。

实际上，即便是全部位都为 1，也不能完全确定该字符串被记录过，因为可能存在哈希碰撞。这种将字符串划分错误的情况，称为 false positive。

删除字符串

一般来说，字符串加入了布隆过滤器之后就被不能删除了，因为删除会影响到其他字符串。实在需要删除字符串的可以使用 Counting bloomfilter(CBF)，这是一种基本 Bloom Filter 的变体，CBF 将基本 Bloom Filter 每一个 Bit 改为一个计数器，这样就可以实现删除字符串的功能了。

哈希碰撞问题

布隆过滤器误判的原因是出现了哈希碰撞，但实际上该概率非常小。假设上述使用的哈希函数中，\(H_i\) 的碰撞概率为 \(p_i\)，则误判概率为 \(\prod_{i=1}^kp_i\)。

参数选择

Hash 函数

好的哈希函数要能近似等概率的将字符串映射到各个 bit。选择 k 个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入 k 个不同的参数。
BitSet 大小

哈希函数个数 k、位数组大小 m、加入的字符串数量 n 的关系可以参考 Bloom Filters - the math。该文献证明了对于给定的m、n，当 \(k = ln(2) \cdot m/n\) 时出错的概率是最小的。同时该文献还给出了特定的 k，m，n 的出错概率。例如：取 k=10，设 m = 20n 时，false positive 发生的概率是 0.0000889 ，这个概率基本能满足网络爬虫的需求了。

布隆过滤器的应用

网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
邮箱系统的从数十亿的垃圾邮件过滤一些垃圾邮件和黑名单查询
集合重复元素的判别
Google Chrome 使用布隆过滤器识别恶意 URL；
查询加速（比如基于key-value的存储系统）
新闻推荐系统，使用布隆过滤器避免推荐给用户已经读过的文章；
redis缓存穿透问题的解决

所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。

所以先将需要查询的数据存入布隆过滤器，如果布隆过滤器不存在则直接返回；如果布隆过滤器存在则再从redis查询（此时只会有少数误差数据）；如果redis中还不存在则查询数据库（此时的访问很小了），并在查询数据库可以通过并发加锁处理，保证只有一个线程可以查询该数据并写入缓存，从而避免了缓存穿透的问题。

Java 实现

import java.util.BitSet;

public class MyBloomFilter {
    /**
     * 位数组的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};
    /**
     * 位数组。数组中的元素只能是 0 或者 1
     */
    private final BitSet bits = new BitSet(DEFAULT_SIZE);
    /**
     * 存放包含 hash 函数的类的数组
     */
    private final SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
     */
    public MyBloomFilter() {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 静态内部类。用于 hash 操作
     */
    public static class SimpleHash {
        private final int cap;
        private final int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 计算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }
}