基于 Java + Redis 布隆过滤器实现高性能黑名单功能

发布于:2025-07-09 ⋅ 阅读:(14) ⋅ 点赞:(0)

目录

1. 为什么选择布隆过滤器?

2. 布隆过滤器原理概述

3. 布隆过滤器参数计算

4. Java + Redis 实现布隆过滤器黑名单

4.1 核心依赖

4.2 布隆过滤器工具类设计

4.3 Spring Boot 配置与使用

5. 数据的最终落库与持久化策略

5.1 核心架构

5.2 详细数据流与同步策略

5.2.1 添加黑名单项

5.2.2 移除黑名单项

5.2.3 查询黑名单项

5.3 宕机恢复与数据一致性

6. 优化与扩展

6.1 误判率与存储容量的平衡

6.2 应对假阳性(误判)

6.3 动态扩容与 RedisBloom 模块

6.4 分布式场景下的考虑

7. 总结


随着互联网业务的飞速发展,恶意请求、垃圾邮件、爬虫抓取等问题层出不穷,对系统性能和数据安全造成了严重威胁。传统的黑名单机制虽然能起到一定的防护作用,但在数据量庞大时,内存占用和查询效率会成为瓶颈。布隆过滤器(Bloom Filter) 作为一种高效的空间利用型概率型数据结构,能很好地解决这些问题。

本文将详细介绍如何使用 Java 语言结合 Redis 实现基于布隆过滤器的黑名单功能,并提供一套完善的实现方案,旨在帮助开发者构建高性能、低资源消耗且具备数据可靠性的黑名单系统。


1. 为什么选择布隆过滤器?

当黑名单数据量非常大(例如千万甚至上亿条记录)时,如果使用 HashMap、HashSet 或数据库来存储,将面临以下挑战:

  • 内存占用高: 每条记录都需要存储完整的键值或数据,消耗大量内存。

  • 查询效率瓶颈: 随着数据量的增加,查询速度可能下降,尤其是在分布式环境下。

  • 网络开销: 如果黑名单存储在远程数据库中,每次查询都需要网络往返,增加延迟。

布隆过滤器通过牺牲一定的准确性(存在误判,即“假阳性”,但不会有“假阴性”)来换取极高的空间效率和查询速度。它特别适用于判断一个元素“可能存在”或“一定不存在”的场景,这与黑名单的需求高度契合。

布隆过滤器的优势:

  • 空间效率高: 相较于存储实际元素,布隆过滤器只需要少量位(bit)即可表示大量元素。

  • 查询速度快: 每次查询都是固定次数的哈希计算,时间复杂度为 O(k),其中 k 是哈希函数的数量,与元素数量无关。

  • 插入速度快: 插入操作也同样快速,为 O(k)。

布隆过滤器的劣势:

  • 存在误判(假阳性): 少量不存在的元素可能会被判断为存在。

  • 不能直接删除元素: 一旦元素被添加到布隆过滤器中,就不能直接删除,否则会影响其他元素的判断。

  • 容量固定: 布隆过滤器创建后,其位数组的大小是固定的,如果插入元素过多,误判率会急剧上升。


2. 布隆过滤器原理概述

布隆过滤器由一个位数组(bit array)和多个哈希函数组成。

  1. 初始化: 创建一个长度为 m 的位数组,所有位都初始化为 0。

  2. 添加元素: 当添加一个元素 x 时,使用 k 个独立的哈希函数分别计算出 k 个哈希值,并将位数组中对应哈希值索引处的位设置为 1。

  3. 查询元素: 当查询一个元素 y 时,同样使用这 k 个哈希函数计算出 k 个哈希值。

    • 如果所有对应索引处的位都为 1,则布隆过滤器判断 y 可能存在

    • 如果任何一个对应索引处的位为 0,则布隆过滤器判断 y 一定不存在

下图形象地展示了布隆过滤器的工作原理:

               +-------------------+
               |                   |
  Element A -->| Hash Func 1 ----> Bit Array Index 1 |
               | Hash Func 2 ----> Bit Array Index 2 |
               | ...               |
               | Hash Func k ----> Bit Array Index k |
               |                   |
               +-------------------+
                     (Set bits to 1)

               +-------------------+
               |                   |
  Query B ---->| Hash Func 1 ----> Check Bit Array Index 1 |
               | Hash Func 2 ----> Check Bit Array Index 2 |
               | ...               |
               | Hash Func k ----> Check Bit Array Index k |
               |                   |
               +-------------------+
                  (All 1s? -> Probably Exists)
                  (Any 0s? -> Definitely Not Exists)

3. 布隆过滤器参数计算

在设计布隆过滤器时,有两个关键参数需要确定:位数组的长度 m哈希函数的数量 k。这两个参数的选取会直接影响到误判率和空间效率。我们可以根据预期要存储的元素数量 n 和可接受的误判率 p 来计算 m 和 k。

最优参数计算公式:

  • 位数组长度 m: m=−fracnlnp(ln2)2

  • 哈希函数数量 k: k=fracmnln2

其中:

  • n:预期要存储的元素数量。

  • p:可接受的误判率(例如 0.01 表示 1% 的误判率)。

  • ln2approx0.693

示例计算:

假设我们要存储 1000 万(n=107)个黑名单项,并希望误判率控制在 0.01%(p=0.0001)。

  • m=−frac107timesln0.0001(ln2)2approx−frac107times(−9.21)(0.693)2approxfrac9.21times1070.480approx1.91times108 bits (约 22.7 MB)

  • k=frac1.91times108107ln2approx19.1times0.693approx13.2 (取整数 13 或 14 个哈希函数)

可以看出,即使存储千万级别的数据,布隆过滤器所需的内存也非常小。


4. Java + Redis 实现布隆过滤器黑名单

我们将利用 Redis 的 SETBITGETBIT 命令来操作位数组,同时使用 Java 来实现哈希函数和布隆过滤器的逻辑。

4.1 核心依赖

在 Maven 项目中,我们需要引入以下依赖:

<dependencies>
    <dependency>
        <groupId>redis.clients</groupId>
        <artifactId>jedis</artifactId>
        <version>5.1.2</version> </dependency>
    <dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>33.1.0-jre</version>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-data-redis</artifactId>
        <version>3.3.1</version>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
        <version>3.3.1</version>
    </dependency>
</dependencies>

4.2 布隆过滤器工具类设计

我们将创建一个 RedisBloomFilter 工具类,封装布隆过滤器的核心逻辑。

import org.springframework.data.redis.core.StringRedisTemplate;
import com.google.common.hash.Funnels;
import com.google.common.hash.Hashing;
import java.nio.charset.StandardCharsets;

public class RedisBloomFilter {

    private StringRedisTemplate redisTemplate;
    private String bloomFilterName; // 布隆过滤器在 Redis 中的 Key
    private long numBits;           // 位数组的长度 m
    private int numHashFunctions;   // 哈希函数的数量 k

    /**
     * 构造函数
     * @param redisTemplate Spring Data Redis 的 StringRedisTemplate
     * @param bloomFilterName 布隆过滤器在 Redis 中的 Key
     * @param expectedInsertions 预期插入的元素数量 n
     * @param falsePositiveProbability 可接受的误判率 p
     */
    public RedisBloomFilter(StringRedisTemplate redisTemplate, String bloomFilterName, long expectedInsertions, double falsePositiveProbability) {
        this.redisTemplate = redisTemplate;
        this.bloomFilterName = bloomFilterName;

        // 计算最优的位数组长度 m
        this.numBits = calculateOptimalNumBits(expectedInsertions, falsePositiveProbability);
        // 计算最优的哈希函数数量 k
        this.numHashFunctions = calculateOptimalNumHashFunctions(expectedInsertions, numBits);

        System.out.println("Bloom Filter: " + bloomFilterName + " initialized with:");
        System.out.println("  Expected insertions (n): " + expectedInsertions);
        System.out.println("  False positive probability (p): " + falsePositiveProbability);
        System.out.println("  Calculated numBits (m): " + numBits);
        System.out.println("  Calculated numHashFunctions (k): " + numHashFunctions);
    }

    /**
     * 计算最优的位数组长度 m
     * m = -(n * ln p) / (ln 2)^2
     */
    private long calculateOptimalNumBits(long expectedInsertions, double falsePositiveProbability) {
        return (long) (-expectedInsertions * Math.log(falsePositiveProbability) / (Math.log(2) * Math.log(2)));
    }

    /**
     * 计算最优的哈希函数数量 k
     * k = (m / n) * ln 2
     */
    private int calculateOptimalNumHashFunctions(long expectedInsertions, long numBits) {
        return Math.max(1, (int) Math.round((double) numBits / expectedInsertions * Math.log(2)));
    }

    /**
     * 添加元素到布隆过滤器
     * @param element 要添加的元素
     */
    public void add(String element) {
        // 使用多个哈希函数计算出多个哈希值
        long[] hashValues = generateHashValues(element);
        // 将对应的位设置为 1
        for (long hashValue : hashValues) {
            redisTemplate.opsForValue().setBit(bloomFilterName, hashValue, true);
        }
    }

    /**
     * 判断元素是否存在于布隆过滤器中
     * @param element 要查询的元素
     * @return true 可能存在,false 一定不存在
     */
    public boolean mightContain(String element) {
        long[] hashValues = generateHashValues(element);
        // 检查所有对应的位是否都为 1
        for (long hashValue : hashValues) {
            Boolean bit = redisTemplate.opsForValue().getBit(bloomFilterName, hashValue);
            if (bit == null || !bit) {
                return false; // 只要有一个位为 0,则一定不存在
            }
        }
        return true; // 所有位都为 1,则可能存在
    }

    /**
     * 生成给定元素的 k 个哈希值
     * 这里使用 Guava 的 MurmurHash3 算法,该算法具有很好的均匀性和低冲突性
     * @param element 元素
     * @return 包含 k 个哈希值的数组
     */
    private long[] generateHashValues(String element) {
        long[] hashValues = new long[numHashFunctions];
        // Guava Hashing.murmur3_128 返回 128 位哈希值
        // 我们将其拆分为两个 64 位值来模拟更多的哈希函数
        long hash1 = Hashing.murmur3_128().hashObject(element, Funnels.stringFunnel(StandardCharsets.UTF_8)).asLong();
        long hash2 = Hashing.murmur3_64().hashObject(element, Funnels.stringFunnel(StandardCharsets.UTF_8)).asLong(); // 另一个哈希函数

        // 利用双哈希技术生成 k 个哈希值
        // g(i, x) = (h1(x) + i * h2(x)) mod m
        for (int i = 0; i < numHashFunctions; i++) {
            hashValues[i] = Math.abs((hash1 + i * hash2) % numBits);
        }
        return hashValues;
    }

    /**
     * 清空布隆过滤器(谨慎操作,会清除所有数据)
     */
    public void clear() {
        redisTemplate.delete(bloomFilterName);
    }
}

代码解释:

  1. 构造函数: 根据预期插入的元素数量 expectedInsertions 和可接受的误判率 falsePositiveProbability,计算出最优的 numBits(位数组长度 m)和 numHashFunctions(哈希函数数量 k)。

  2. calculateOptimalNumBitscalculateOptimalNumHashFunctions 实现布隆过滤器参数计算公式。

  3. add(String element) 调用 generateHashValues 方法生成元素的 k 个哈希值,并通过 redisTemplate.opsForValue().setBit() 将 Redis 中对应位设置为 1。

  4. mightContain(String element) 生成元素的 k 个哈希值,通过 redisTemplate.opsForValue().getBit() 检查 Redis 中对应位是否为 1。如果所有位都为 1,返回 true(可能存在);否则,返回 false(一定不存在)。

  5. generateHashValues(String element) 使用 Guava 库的 MurmurHash3 算法。通过双哈希技术(g(i,x)=(h_1(x)+itimesh_2(x))pmodm)生成 k 个独立的哈希值,确保哈希值均匀分布在位数组范围内。

  6. clear() 提供清除布隆过滤器所有数据的方法。

4.3 Spring Boot 配置与使用

如果你的项目是 Spring Boot,可以方便地配置 StringRedisTemplate 并将布隆过滤器注册为 Bean。

application.yml (或 .properties) 配置 Redis:

spring:
  redis:
    host: localhost
    port: 6379
    # password: yourpassword # 如果 Redis 有密码
    database: 0

RedisConfig.java 配置类:

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.core.StringRedisTemplate;

@Configuration
public class RedisConfig {

    @Bean
    public StringRedisTemplate stringRedisTemplate(RedisConnectionFactory redisConnectionFactory) {
        StringRedisTemplate template = new StringRedisTemplate();
        template.setConnectionFactory(redisConnectionFactory);
        return template;
    }

    /**
     * 将布隆过滤器注册为 Spring Bean
     * 假设我们预期有 1000 万个黑名单项,误判率为 0.01%
     */
    @Bean
    public RedisBloomFilter blackListBloomFilter(StringRedisTemplate redisTemplate) {
        String bloomFilterName = "blacklist:bloom"; // Redis Key
        long expectedInsertions = 10_000_000L; // 预期黑名单数量
        double falsePositiveProbability = 0.0001; // 0.01% 误判率
        return new RedisBloomFilter(redisTemplate, bloomFilterName, expectedInsertions, falsePositiveProbability);
    }
}

使用示例:黑名单服务

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import javax.annotation.PostConstruct;
import java.util.Arrays;
import java.util.List;

@Service
public class BlacklistService {

    @Autowired
    private RedisBloomFilter blackListBloomFilter;

    /**
     * 模拟初始化黑名单数据
     * 实际应用中,这些数据可能来自数据库或文件
     */
    @PostConstruct
    public void initBlacklist() {
        System.out.println("Initializing blacklist...");
        List<String> initialBlacklist = Arrays.asList(
                "192.168.1.1",
                "baduser@example.com",
                "spam_keyword",
                "malicious_ip",
                "another_bad_user"
        );

        for (String item : initialBlacklist) {
            addBlacklistItem(item);
        }
        System.out.println("Blacklist initialization complete. Added " + initialBlacklist.size() + " items.");
    }

    /**
     * 将项添加到黑名单中
     * @param item 要添加的项(如IP地址、用户名、邮箱等)
     */
    public void addBlacklistItem(String item) {
        blackListBloomFilter.add(item);
        System.out.println("Added to blacklist: " + item);
    }

    /**
     * 检查项是否在黑名单中
     * @param item 要检查的项
     * @return true 如果可能在黑名单中,false 如果一定不在黑名单中
     */
    public boolean isInBlacklist(String item) {
        boolean result = blackListBloomFilter.mightContain(item);
        System.out.println("Checking '" + item + "': " + (result ? "Possibly in blacklist" : "Definitely NOT in blacklist"));
        return result;
    }

    /**
     * 清空黑名单(谨慎使用)
     */
    public void clearBlacklist() {
        blackListBloomFilter.clear();
        System.out.println("Blacklist cleared.");
    }
}

Spring Boot Controller 示例:

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;

@RestController
@RequestMapping("/blacklist")
public class BlacklistController {

    @Autowired
    private BlacklistService blacklistService;

    @PostMapping("/add")
    public String addBlacklistItem(@RequestParam String item) {
        blacklistService.addBlacklistItem(item);
        return "Added '" + item + "' to blacklist (Bloom Filter).";
    }

    @GetMapping("/check")
    public String checkBlacklistItem(@RequestParam String item) {
        boolean isInBlacklist = blacklistService.isInBlacklist(item);
        if (isInBlacklist) {
            return "'" + item + "' is potentially in the blacklist.";
        } else {
            return "'" + item + "' is definitely NOT in the blacklist.";
        }
    }

    @PostMapping("/clear")
    public String clearBlacklist() {
        blacklistService.clearBlacklist();
        return "Blacklist cleared.";
    }
}

5. 数据的最终落库与持久化策略

布隆过滤器存储在 Redis 中,而 Redis 是基于内存的,虽然有自己的持久化机制,但在极端情况下数据仍然存在丢失的风险。此外,布隆过滤器本身是概率型数据结构,存在误判,且无法直接删除元素

因此,黑名单的原始、精确数据必须落库,通常存储在关系型数据库或 NoSQL 数据库中。数据库作为黑名单的权威数据源,提供数据的可靠性、完整性、可审计性,并用于消除布隆过滤器的误判。

5.1 核心架构

+----------------+        +-------------------+        +---------------------+
|   管理后台/    |        |                   |        |                     |
| 业务系统(添加/|------->|    应用服务       |------->|   关系型数据库/     |
| 删除黑名单)   |        | (BlacklistService)|        |   NoSQL数据库       |
+----------------+        |                   |        | (持久化黑名单数据)  |
         ^                |      查询请求     |        +----------^----------+
         |                |       (如IP)      |                   |
         |                +---------|---------+                   |
         |                          |                               |
         |                          v                               |
         |                +-------------------+                     |
         |                |                   |                     |
         +----------------|  Redis 布隆过滤器 |                     |
                          | (Bloom Filter)    |                     |
                          |                   |                     |
                          +-------------------+                     |
                                    |                               |
                                    +-------------------------------> 同步/重建
                                                                      (异步)

5.2 详细数据流与同步策略

5.2.1 添加黑名单项
  1. 持久化: 当一个新项需要加入黑名单时,首先将其写入数据库INSERT 操作)。

  2. 同步到 Redis 布隆过滤器: 数据库写入成功后,通过消息队列(如 Kafka、RabbitMQ)发送一条“黑名单添加”消息,或者直接在应用服务层调用 RedisBloomFilter.add() 方法。对于非实时性要求高的场景,可以定时从数据库查询新增的黑名单项进行批量同步。

5.2.2 移除黑名单项

布隆过滤器不支持直接删除元素。因此,删除操作需要以下策略:

  1. 持久化删除: 首先,从数据库中删除该黑名单项(DELETE 操作)。

  2. 布隆过滤器处理:

    • 不处理(推荐): 布隆过滤器中被设置为 1 的位会继续保持为 1。这意味着该项仍可能被布隆过滤器误判为存在。但由于数据库中已经删除,二次校验时会将其识别为非黑名单。这是最简单、最常用的方法。

    • 重建布隆过滤器: 如果删除操作频繁,或者误判率累积到无法接受的程度,可以考虑周期性地从数据库中加载所有当前的黑名单项,然后重建一个新的布隆过滤器(或者使用一个新的 Redis Key),并切换流量到新的过滤器。旧的过滤器可以被删除。

5.2.3 查询黑名单项
  1. 布隆过滤器初筛: 接收到查询请求时,首先查询 Redis 布隆过滤器

    • 如果布隆过滤器返回 false(一定不存在),则立即返回结果,无需进一步查询。

    • 如果布隆过滤器返回 true(可能存在),则进入下一步。

  2. 数据库二次校验(消除误判): 对于布隆过滤器判断为“可能存在”的项,回源到数据库进行精确查询

    • 如果数据库中存在该项,则确认其为黑名单项。

    • 如果数据库中不存在该项,则说明是布隆过滤器的误判(假阳性),将其视为非黑名单项。

5.3 宕机恢复与数据一致性

  • Redis 宕机:

    • 如果 Redis 配置了 RDB 快照或 AOF 日志持久化,重启后 Redis 会尝试恢复数据。

    • 即使 Redis 数据完全丢失,由于数据库中保存了完整的黑名单数据,我们可以编写一个启动脚本或定时任务,在 Redis 服务可用后,从数据库中读取所有黑名单项,重新填充(重建)Redis 中的布隆过滤器。

  • 数据库宕机:

    • 数据库通常有高可用方案(如主从复制、集群),可以保证在单点故障时服务的连续性。

    • 如果数据库完全不可用,那么布隆过滤器虽然能继续工作(提供可能存在的判断),但无法进行二次校验,也无法更新黑名单。因此,数据库的稳定性是整个系统的基石。


6. 优化与扩展

6.1 误判率与存储容量的平衡

  • 初始容量估算: 在系统设计之初,尽量准确地估算黑名单的最大容量 n,以避免后期因容量不足导致误判率急剧升高。

  • 可接受的误判率: 根据业务场景选择合适的误判率 p。对于像垃圾邮件过滤这类场景,可以接受较高的误判率;而对于安全敏感的场景,则需要将误判率降到极低。

6.2 应对假阳性(误判)

对于那些被布隆过滤器判断为“可能存在”的项,务必进行二次校验,回源到精确的黑名单存储(如数据库、Redis Set/HashMap)进行最终确认。

6.3 动态扩容与 RedisBloom 模块

布隆过滤器一旦创建,容量是固定的。如果需要动态扩容,可以考虑:

  • 分片: 创建多个布隆过滤器,根据哈希或其他规则将元素分散到不同的过滤器中。

  • 重建: 当误判率达到阈值时,创建一个更大的布隆过滤器,并将旧数据全部迁移过去。

  • RedisBloom 模块: Redis 官方提供了 RedisBloom 模块,原生支持布隆过滤器(BF.ADDBF.EXISTS)以及 Cuckoo Filter。如果您的 Redis 服务器支持安装模块,强烈推荐使用,因为它性能更优且更易于使用。

6.4 分布式场景下的考虑

  • Redis 集群: 在分布式环境中,建议使用 Redis Cluster 来存储布隆过滤器,以提高可用性和扩展性。布隆过滤器的 Key 会根据哈希槽分布到不同的节点上。


7. 总结

本文详细介绍了如何使用 Java 语言结合 Redis 布隆过滤器实现高效、可靠的黑名单功能。通过合理选择布隆过滤器的参数,我们可以在牺牲极小误判率的前提下,大幅提升黑名单查询性能并降低内存消耗。

关键点回顾:

  • 布隆过滤器优势: 高空间效率、高查询速度,适用于判断“可能存在”或“一定不存在”的场景。

  • 核心原理: 位数组 + 多个哈希函数。

  • 参数计算: 根据预期元素数量 n 和误判率 p 计算最优的位数组长度 m 和哈希函数数量 k。

  • Java 实现: 封装 RedisBloomFilter 工具类,使用 Guava 的哈希函数和 Redis 的 SETBIT / GETBIT 命令。

  • Spring Boot 集成: 方便地将布隆过滤器作为 Bean 进行管理和使用。

  • 数据持久化: 黑名单的原始数据必须落库(数据库),作为权威数据源,用于消除误判、重建布隆过滤器和进行精确管理。

  • 数据同步: 设计合理的同步机制,将数据库中的黑名单数据实时或周期性地同步到 Redis 布隆过滤器。

  • 优化与扩展: 考虑误判处理(二次校验)、动态扩容、持久化与同步、以及分布式场景下的解决方案。

通过这种“布隆过滤器 + 数据库”的双重机制,我们可以构建一个既高效又可靠的黑名单系统,有效应对大规模数据下的恶意请求挑战。

📌 点赞 + 收藏 + 关注,每天带你掌握底层原理,写出更强健的 Java 代码!


网站公告

今日签到

点亮在社区的每一天
去签到