跳至主要內容

布隆过滤器技术解读

GGBOND2025/12/3大约 5 分钟

布隆过滤器技术解读

1. 什么是布隆过滤器？

布隆过滤器是一种非常省空间的工具，用来快速判断「一个东西是不是存在于一个大集合里」。在淘票票项目中，它被用来防止恶意请求攻击数据库、避免重复处理数据、快速识别恶意用户等，让系统跑得更快更稳。

简单来说，布隆过滤器就像一个特殊的记事本，可以快速告诉你：

  • 「这个东西肯定不在集合里」
  • 或者「这个东西可能在集合里」

2. 布隆过滤器是怎么工作的？

2.1 基本原理

想象一下，布隆过滤器就像是一个巨大的棋盘，棋盘上的每个格子只有两种状态：空（0）或被标记（1）。

它的工作过程可以这样理解：

  1. 初始化：所有格子都是空的（0）
  2. 添加元素：当我们要记录一个元素时，用几个不同的「标记规则」（哈希函数）在棋盘上做几个标记（把对应位置设为1）
  3. 查询元素：当我们想知道某个元素是否存在时，同样用这几个「标记规则」检查棋盘
    • 如果有任何一个标记位置是空的，说明这个元素肯定没记录过
    • 如果所有标记位置都被标记过，说明这个元素可能被记录过（有可能是不同元素恰好产生了相同的标记）

2.2 优点和缺点

优点：

  • 空间效率高：相比存储完整元素，布隆过滤器所需空间很小
  • 查询效率高：时间复杂度为O(k)，k为哈希函数数量
  • 插入效率高：时间复杂度为O(k)
  • 隐私保护：不存储原始数据，只存储哈希结果

缺点：

  • 可能会误判：偶尔会把不存在的元素说成「可能存在」（但永远不会把存在的说成不存在）
  • 不能删除：无法简单地移除已记录的元素
  • 不知道具体数量：只知道元素可能存在，不知道有多少个

3. 布隆过滤器在淘票票中的应用

3.1 防止数据库被恶意请求攻击

当有人故意查询不存在的电影ID时，请求会直接打到数据库，导致数据库压力过大。布隆过滤器可以快速判断「这个ID可能存在吗？」，把大量明显不存在的请求直接拦截掉，保护数据库。

3.2 避免重复处理数据

在处理用户行为日志、电影推荐等场景时，布隆过滤器可以快速判断「这条数据之前处理过吗？」，避免重复计算，提高效率。

3.3 快速识别恶意用户

把已知的「刷单用户」「恶意评论用户」的ID存入布隆过滤器，系统可以在用户发起请求时快速检查，提前拦截恶意行为。

3.4 加速权限验证

对于需要频繁检查用户权限的场景，可以先用布隆过滤器快速排除那些明显没有权限的用户，减轻权限系统的压力。

4. 布隆过滤器的实现方式

4.1 使用Redis实现布隆过滤器

Redis提供了布隆过滤器的扩展模块，使用起来很方便：

@Service
public class RedisBloomFilterService {
    
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;
    
    /**
     * 添加元素到布隆过滤器
     */
    public <T> void add(String key, T value, int expectedInsertions, double fpp) {
        // 确保布隆过滤器已初始化
        ensureBloomFilter(key, expectedInsertions, fpp);
        
        // 添加元素到布隆过滤器
        redisTemplate.execute((RedisCallback<Boolean>) connection -> {
            byte[] keyBytes = redisTemplate.getKeySerializer().serialize(key);
            byte[] valueBytes = redisTemplate.getValueSerializer().serialize(value);
            return connection.execute("BF.ADD", keyBytes, valueBytes);
        });
    }
    
    /**
     * 判断元素是否可能在布隆过滤器中
     */
    public <T> boolean mightContain(String key, T value) {
        return redisTemplate.execute((RedisCallback<Boolean>) connection -> {
            byte[] keyBytes = redisTemplate.getKeySerializer().serialize(key);
            byte[] valueBytes = redisTemplate.getValueSerializer().serialize(value);
            return connection.execute("BF.EXISTS", keyBytes, valueBytes);
        });
    }
    
    /**
     * 初始化布隆过滤器
     */
    private void ensureBloomFilter(String key, int expectedInsertions, double fpp) {
        redisTemplate.execute((RedisCallback<Boolean>) connection -> {
            byte[] keyBytes = redisTemplate.getKeySerializer().serialize(key);
            
            // 检查布隆过滤器是否存在
            Boolean exists = connection.execute("EXISTS", keyBytes);
            if (!exists) {
                // 创建布隆过滤器
                return connection.execute("BF.RESERVE", 
                        keyBytes, 
                        String.valueOf(fpp).getBytes(), 
                        String.valueOf(expectedInsertions).getBytes());
            }
            return true;
        });
    }
}

4.2 缓存穿透防护实例

下面是一个简单的例子，展示如何用布隆过滤器防止缓存穿透：

@Service
public class BloomFilterCacheService {
    
    @Autowired
    private RedisBloomFilterService bloomFilterService;
    
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;
    
    @Autowired
    private MovieRepository movieRepository;
    
    // 布隆过滤器的键名
    private static final String MOVIE_ID_BLOOM_FILTER = "movie:id:bloom_filter";
    // 预计存储的电影数量
    private static final int EXPECTED_MOVIES = 100000;
    // 允许的误判率
    private static final double FPP = 0.001; // 0.1%的误判率
    
    /**
     * 初始化时加载所有电影ID到布隆过滤器
     */
    @PostConstruct
    public void initMovieIdBloomFilter() {
        // 从数据库加载所有电影ID并添加到布隆过滤器
        List<String> movieIds = movieRepository.findAllMovieIds();
        if (!movieIds.isEmpty()) {
            // 批量添加所有电影ID
            bloomFilterService.addAll(MOVIE_ID_BLOOM_FILTER, movieIds, EXPECTED_MOVIES, FPP);
        }
    }
    
    /**
     * 查询电影信息，使用布隆过滤器防止缓存穿透
     */
    public Movie getMovieById(String movieId) {
        // 第一步：检查布隆过滤器
        boolean mightExist = bloomFilterService.mightContain(MOVIE_ID_BLOOM_FILTER, movieId);
        if (!mightExist) {
            // 布隆过滤器说「肯定不存在」，直接返回
            System.out.println("这个电影ID肯定不存在，无需查询数据库");
            return null;
        }
        
        // 布隆过滤器说「可能存在」，继续查询缓存
        String cacheKey = "movie:" + movieId;
        Movie movie = (Movie) redisTemplate.opsForValue().get(cacheKey);
        
        if (movie == null) {
            // 缓存中没有，查询数据库
            movie = movieRepository.findById(movieId).orElse(null);
            
            if (movie != null) {
                // 找到了，更新缓存
                redisTemplate.opsForValue().set(cacheKey, movie, 1, TimeUnit.HOURS);
            }
        }
        
        return movie;
    }
}

5. 如何调整布隆过滤器的参数？

使用布隆过滤器时，主要需要设置两个参数：

5.1 误判率（FPP）

误判率就是布隆过滤器把不存在的元素说成「可能存在」的概率。

  • 要求非常精确：设置为0.001%（0.00001），但需要更多存储空间
  • 一般场景：推荐设置为0.1%（0.001），空间和准确性比较平衡
  • 允许一定误差：设置为1%（0.01），节省空间

5.2 预期元素数量

告诉布隆过滤器你预计要存多少个元素：

  • 尽量准确估计，避免存太多元素导致误判率上升
  • 如果实际存的元素远超预期，考虑重建布隆过滤器
  • 可以定期更新布隆过滤器，保持较低的误判率
Copyright © 2025 GGBOND