布隆过滤器

布隆过滤器相信大家没用过的话，也已经听过了。

布隆过滤器主要是为了解决海量数据的存在性问题。对于海量数据中判定某个数据是否存在且容忍轻微误差这一场景（比如缓存穿透、海量数据去重）来说，非常适合。

文章内容概览：

1. 什么是布隆过滤器？
2. 布隆过滤器的原理介绍。
3. 布隆过滤器使用场景。
4. 通过 Java 编程手动实现布隆过滤器。
5. 利用 Google 开源的 Guava 中自带的布隆过滤器。
6. Redis 中的布隆过滤器。

什么是布隆过滤器？

布隆过滤器详解

1. 什么是布隆过滤器？

布隆过滤器（Bloom Filter）是一种概率性数据结构，用于判断一个元素是否在集合中。它由 位数组（Bit Array） 和 多个哈希函数 组成，具有以下特点：

1. 高效：空间占用少，查询速度快。
2. 概率性：
   • 可以明确判断一个元素不在集合中。
   • 如果判断元素在集合中，可能会存在误报（即实际不在集合中，但被认为存在）。
3. 不可删除：一旦元素被添加到布隆过滤器中，通常不能删除。

---

2. 布隆过滤器的工作原理

1. 初始化：创建一个长度为 ( m ) 的位数组（全为 0），同时定义 ( k ) 个独立的哈希函数。
2. 添加元素：
   • 使用 ( k ) 个哈希函数计算元素的 ( k ) 个哈希值，分别对 ( m ) 取模得到位数组的 ( k ) 个位置。
   • 将这些位置对应的位数组元素置为 1。
3. 查询元素：
   • 对查询的元素使用相同的 ( k ) 个哈希函数计算哈希值并对 ( m ) 取模，得到 ( k ) 个位置。
   • 检查这些位置的值：
     • 如果其中某个位为 0，则元素一定不在集合中。
     • 如果所有位都为 1，则元素可能在集合中（存在误报）。

---

3. 示例

假设位数组长度为 10，使用 3 个哈希函数：

添加元素

添加元素 A：

1. 哈希函数计算得位置为 [1, 4, 7]。
2. 设置位数组的第 1、4、7 位为 1。

添加元素 B：

1. 哈希函数计算得位置为 [2, 4, 8]。
2. 设置位数组的第 2、4、8 位为 1。

位数组状态：

[0, 1, 1, 0, 1, 0, 0, 1, 1, 0]

查询元素

查询元素 A：

1. 哈希函数计算得位置为 [1, 4, 7]。
2. 检查这些位置均为 1，因此 A 可能在集合中。

查询元素 C：

1. 哈希函数计算得位置为 [3, 5, 6]。
2. 检查第 3 位为 0，因此 C 一定不在集合中。

---

4. 优缺点

优点

1. 节省空间：位数组占用的内存远小于传统的数据结构（如 HashSet）。
2. 查询高效：哈希操作和位操作的时间复杂度为 ( O(k) )，其中 ( k ) 是哈希函数的数量。
3. 无需存储实际数据：仅依赖哈希值判断，避免了存储实际数据的开销。

缺点

1. 存在误报率：布隆过滤器不能保证查询结果的准确性。
2. 不支持删除：元素一旦添加后，由于位数组的共享特性，无法直接删除特定元素。
3. 误报率随元素数量增加而提高：随着添加的元素增多，位数组中 1 的比例增加，误报率也会升高。

---

5. 应用场景

1. 缓存穿透：

   • 在高并发场景下，布隆过滤器可用于判断请求的 key 是否存在，避免请求直接穿透缓存打到数据库。
   • 例如：Redis 缓存中存储布隆过滤器，过滤掉不存在的数据。

2. 垃圾邮件过滤：

   • 布隆过滤器判断邮件地址是否在垃圾邮件列表中。

3. 爬虫去重：

   • 用于记录已经抓取过的 URL，避免重复爬取。

4. 推荐系统：

   • 判断用户是否已经看过某个内容，避免重复推荐。

5. 区块链：

   • 用于快速判断某笔交易是否存在于区块中。

---

6. 误报率计算

布隆过滤器的误报率与以下因素有关：

1. 位数组长度 ( m )。
2. 哈希函数个数 ( k )。
3. 插入的元素数量 ( n )。

误报率的公式为：
[
P = \left( 1 - e^{-kn/m} \right)^k
]
通过调整 ( m )、( k )、( n ) 的值，可以优化误报率。

---

7. 示例代码

以下是 Java 中布隆过滤器的简单实现：

import java.util.BitSet;
import java.util.Random;

public class BloomFilter {
    private final int size; // 位数组大小
    private final BitSet bitSet;
    private final int[] hashSeeds; // 哈希函数种子

    public BloomFilter(int size, int hashCount) {
        this.size = size;
        this.bitSet = new BitSet(size);
        this.hashSeeds = new int[hashCount];
        Random random = new Random();
        for (int i = 0; i < hashCount; i++) {
            hashSeeds[i] = random.nextInt(size);
        }
    }

    // 添加元素
    public void add(String value) {
        for (int seed : hashSeeds) {
            int hash = hash(value, seed);
            bitSet.set(hash);
        }
    }

    // 查询元素
    public boolean contains(String value) {
        for (int seed : hashSeeds) {
            int hash = hash(value, seed);
            if (!bitSet.get(hash)) {
                return false;
            }
        }
        return true;
    }

    // 哈希函数
    private int hash(String value, int seed) {
        return (value.hashCode() ^ seed) % size;
    }
}

---

布隆过滤器是处理大规模数据时的高效工具，其优势在于空间和时间的显著节约，但需权衡误报率和数据量之间的关系。

布隆过滤器的原理介绍

布隆过滤器的原理详解

1. 添加元素到布隆过滤器

布隆过滤器在添加元素时的步骤如下：

1. 哈希计算：
   • 对要添加的元素使用 ( k ) 个哈希函数计算哈希值。
   • 每个哈希函数将元素映射到一个位数组的下标位置。
2. 置位操作：
   • 根据每个哈希值，将位数组中对应下标的值置为 1。
3. 更新完成：
   • 元素存入布隆过滤器。

示例：

• 假设位数组长度为 10（初始为全 0），有 3 个哈希函数。
• 添加元素 "A"，哈希函数计算的结果为 [1, 4, 7]。
• 将位数组中索引 1、4 和 7 置为 1：

  初始状态： [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  添加 "A" 后： [0, 1, 0, 0, 1, 0, 0, 1, 0, 0]

---

2. 判断元素是否存在

布隆过滤器在查询元素是否存在时的步骤如下：

1. 哈希计算：
   • 对查询的元素再次使用相同的 ( k ) 个哈希函数计算哈希值。
   • 得到该元素映射到的位数组下标。
2. 验证位数组：
   • 检查这些下标位置对应的值是否全部为 1。
     • 如果全为 1，则该元素可能存在。
     • 如果有任意一位为 0，则该元素一定不存在。

示例：

• 查询元素 "A"：
  • 哈希计算得 [1, 4, 7]。
  • 位数组对应位置 [1, 4, 7] 的值均为 1，说明 "A" 可能存在。
• 查询元素 "B"：
  • 假设哈希计算得 [2, 3, 5]。
  • 位数组中索引 3 的值为 0，说明 "B" 一定不存在。

---

3. 布隆过滤器的误判

3.1 误判原因

不同的元素通过哈希函数可能映射到相同的位置，导致这些位置在位数组中被置为 1，产生误判。

3.2 减少误判的方法

1. 增加位数组的大小 ( m )：
   • 位数组越大，哈希冲突的概率越低。
2. 优化哈希函数数量 ( k )：
   • 增加哈希函数的数量可以减少冲突，但过多的哈希函数会增加计算开销。
   • 理想的 ( k ) 值为：
     [
     k = \frac{m}{n} \ln 2
     ]
     其中 ( m ) 是位数组的大小，( n ) 是元素的数量。
3. 减少存储的元素数量 ( n )：
   • 元素数量越多，位数组中 1 的比例越高，误判率越大。

---

4. 特点总结

1. 快速判断不存在：
   • 如果位数组中某个位为 0，则该元素一定不在集合中。
2. 可能误判存在：
   • 如果位数组中所有相关位为 1，则元素可能在集合中，存在一定误报率。
3. 只支持添加操作：
   • 布隆过滤器不支持直接删除元素，因为多个元素可能共享同一位。

---

5. 布隆过滤器的优势与局限

优势

1. 高效：时间复杂度为 ( O(k) )，只需 ( k ) 次哈希计算。
2. 节省空间：位数组占用的内存远小于传统数据结构。

局限

1. 误报：无法百分百确定元素是否存在。
2. 不可删除：无法直接删除元素。
3. 精度与空间的权衡：位数组大小与误报率成反比。

---

6. 应用场景

1. 缓存穿透保护：
   • 判断请求的 key 是否存在，减少数据库查询压力。
2. 防止重复爬取：
   • 记录已经爬取过的 URL，避免重复访问。
3. 垃圾邮件过滤：
   • 判断邮件地址是否在垃圾邮件列表中。
4. 推荐系统：
   • 过滤掉用户已经看过的内容，避免重复推荐。

布隆过滤器是解决大规模数据集合快速判断问题的高效工具，在现代计算系统中有着广泛的应用。

布隆过滤器使用场景

布隆过滤器的使用场景

1. 判断给定数据是否存在

布隆过滤器的核心功能是判断某个数据是否存在于集合中，在以下场景中有广泛应用：

1. 缓存穿透防护：

   • 在高并发场景下，请求的 key 如果在缓存中未命中，可能直接穿透到数据库。
   • 使用布隆过滤器提前判断 key 是否存在，有效过滤掉不存在的数据请求，减轻数据库压力。

2. 垃圾邮件过滤：

   • 判断邮件地址是否存在于垃圾邮件黑名单中，快速拒绝不必要的处理。

3. 黑名单校验：

   • 判断用户的 IP 地址、手机号、账号等是否在黑名单中。
   • 布隆过滤器能够以极低的存储成本快速完成海量黑名单的过滤。

4. URL 校验：

   • 在爬虫系统中判断一个 URL 是否已经被访问过，防止重复抓取。

5. 交易反欺诈：

   • 判断用户的支付账号或 IP 地址是否存在风险记录库中，快速响应并阻断潜在欺诈行为。

---

2. 数据去重

布隆过滤器能够高效地解决去重问题，特别适用于海量数据的场景：

1. 爬虫 URL 去重：

   • 爬虫在访问网页时需避免对已爬取的 URL 重复抓取。
   • 布隆过滤器能够快速记录和判断 URL 是否已存在，提升爬取效率。

2. 订单号去重：

   • 电商系统中需要对海量订单号进行去重。
   • 使用布隆过滤器判断订单号是否已存在，避免重复生成或处理。

3. 用户行为日志去重：

   • 分布式系统中记录用户行为日志时，需要去重重复事件。
   • 布隆过滤器能够在高效存储的基础上实现快速判断。

4. 社交网络数据去重：

   • 在推荐系统中，对用户已经浏览过或点赞过的内容进行去重，避免重复推荐。

---

3. 大规模数据集合的存在性判断

布隆过滤器特别适用于处理大规模数据集合的快速存在性判断问题：

1. DNS 缓存：

   • 判断域名解析结果是否已经存在，快速返回结果或进行新解析。

2. 安全系统：

   • 网络防火墙中快速判断请求是否来自恶意 IP。

3. 搜索引擎去重：

   • 搜索引擎需要避免在索引中重复收录同一网页，布隆过滤器可以在低成本下完成重复判断。

---

总结

布隆过滤器以其高效性和低内存占用的特点，解决了海量数据的存在性判断和去重问题，广泛应用于各类高并发和大数据场景。它的核心在于以极低的空间成本和查询时间完成对数据的快速过滤，为现代计算系统提供了重要的支持。

编码实战

通过 Java 编程手动实现布隆过滤器

我们上面已经说了布隆过滤器的原理，知道了布隆过滤器的原理之后就可以自己手动实现一个了。

如果你想要手动实现一个的话，你需要：

1. 一个合适大小的位数组保存数据
2. 几个不同的哈希函数
3. 添加元素到位数组（布隆过滤器）的方法实现
4. 判断给定元素是否存在于位数组（布隆过滤器）的方法实现。

下面给出一个我觉得写的还算不错的代码（参考网上已有代码改进得到，对于所有类型对象皆适用）：

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 BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函数的类的数组
     */
    private 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 int cap;
        private 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((cap - 1) & seed * ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

测试：

String value1 = "https://javaguide.cn/";
String value2 = "https://github.com/Snailclimb";
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));

Output:

false
false
true
true

测试：

Integer value1 = 13423;
Integer value2 = 22131;
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));

Output:

false
false
true
true

利用 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 中的布隆过滤器

介绍

Redis v4.0 之后有了 Module（模块/插件） 功能，Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍：https://redis.io/modules

另外，官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module，地址：https://github.com/RedisBloom/RedisBloom
其他还有：

• redis-lua-scaling-bloom-filter（lua 脚本实现）：https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
• pyreBloom（Python 中的快速 Redis 布隆过滤器）：https://github.com/seomoz/pyreBloom
• ……

RedisBloom 提供了多种语言的客户端支持，包括：Python、Java、JavaScript 和 PHP。

使用 Docker 安装

如果我们需要体验 Redis 中的布隆过滤器非常简单，通过 Docker 就可以了！我们直接在 Google 搜索 docker redis bloomfilter 然后在排除广告的第一条搜素结果就找到了我们想要的答案（这是我平常解决问题的一种方式，分享一下），具体地址：https://hub.docker.com/r/redislabs/rebloom/ （介绍的很详细 ）。

具体操作如下：

➜  ~ docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
➜  ~ docker exec -it redis-redisbloom bash
root@21396d02c252:/data# redis-cli
127.0.0.1:6379>

注意：当前 rebloom 镜像已经被废弃，官方推荐使用redis-stack

常用命令一览

注意：key : 布隆过滤器的名称，item : 添加的元素。

1. BF.ADD：将元素添加到布隆过滤器中，如果该过滤器尚不存在，则创建该过滤器。格式：BF.ADD {key} {item}。
2. BF.MADD : 将一个或多个元素添加到“布隆过滤器”中，并创建一个尚不存在的过滤器。该命令的操作方式BF.ADD与之相同，只不过它允许多个输入并返回多个值。格式：BF.MADD {key} {item} [item ...] 。
3. BF.EXISTS : 确定元素是否在布隆过滤器中存在。格式：BF.EXISTS {key} {item}。
4. BF.MEXISTS：确定一个或者多个元素是否在布隆过滤器中存在格式：BF.MEXISTS {key} {item} [item ...]。

另外， BF.RESERVE 命令需要单独介绍一下：

这个命令的格式如下：

BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] 。

下面简单介绍一下每个参数的具体含义：

1. key：布隆过滤器的名称
2. error_rate : 期望的误报率。该值必须介于 0 到 1 之间。例如，对于期望的误报率 0.1％（1000 中为 1），error_rate 应该设置为 0.001。该数字越接近零，则每个项目的内存消耗越大，并且每个操作的 CPU 使用率越高。
3. capacity: 过滤器的容量。当实际存储的元素个数超过这个值之后，性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长，性能将线性下降。

可选参数：

• expansion：如果创建了一个新的子过滤器，则其大小将是当前过滤器的大小乘以expansion。默认扩展值为 2。这意味着每个后续子过滤器将是前一个子过滤器的两倍。

实际使用

127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0