Redis 7 实现布隆过滤器

核心概念

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于快速判断一个元素是否可能存在于集合中。它具有以下特点：

• 无误判存在：如果返回”不存在”，则元素一定不存在
• 可能误判存在：如果返回”存在”，元素可能不存在（假阳性）
• 空间效率高：相比传统Set结构，内存占用极小

Redis 7 实现原理

1. 底层数据结构

Redis 7 通过 RedisBloom 模块原生支持布隆过滤器，底层基于位图（BitMap）实现：

// 布隆过滤器核心参数
public class BloomFilterConfig {
    private long expectedElements;    // 预期元素数量
    private double falsePositiveRate; // 误判率
    private int hashFunctions;        // 哈希函数个数
    private long bitArraySize;        // 位数组大小
}

2. 关键算法

位数组大小计算：

m = -(n * ln(p)) / (ln(2)^2)

哈希函数个数：

k = (m/n) * ln(2)

其中：n为预期元素数量，p为误判率，m为位数组大小，k为哈希函数个数。

Redis 7 布隆过滤器操作

1. 基本命令

# 创建布隆过滤器
BF.RESERVE myfilter 0.01 1000000

# 添加元素
BF.ADD myfilter "user:123"
BF.MADD myfilter "user:123" "user:456" "user:789"

# 检查元素
BF.EXISTS myfilter "user:123"
BF.MEXISTS myfilter "user:123" "user:999"

# 获取过滤器信息
BF.INFO myfilter

2. Java 客户端实现

@Component
public class RedisBloomFilter {
  
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;
  
    /**
     * 创建布隆过滤器
     */
    public void createFilter(String filterName, double errorRate, long capacity) {
        redisTemplate.execute((RedisCallback<Object>) connection -> {
            connection.execute("BF.RESERVE", 
                filterName.getBytes(), 
                String.valueOf(errorRate).getBytes(),
                String.valueOf(capacity).getBytes());
            return null;
        });
    }
  
    /**
     * 添加元素到布隆过滤器
     */
    public void add(String filterName, String... elements) {
        redisTemplate.execute((RedisCallback<Object>) connection -> {
            byte[][] args = new byte[elements.length + 1][];
            args[0] = filterName.getBytes();
            for (int i = 0; i < elements.length; i++) {
                args[i + 1] = elements[i].getBytes();
            }
            connection.execute("BF.MADD", args);
            return null;
        });
    }
  
    /**
     * 检查元素是否可能存在
     */
    public boolean mightContain(String filterName, String element) {
        return (Boolean) redisTemplate.execute((RedisCallback<Boolean>) connection -> {
            Object result = connection.execute("BF.EXISTS", 
                filterName.getBytes(), 
                element.getBytes());
            return result != null && (Long) result == 1L;
        });
    }
}

分布式场景考量

1. 缓存穿透防护

@Service
public class UserService {
  
    @Autowired
    private RedisBloomFilter bloomFilter;
  
    @Autowired
    private UserRepository userRepository;
  
    private static final String USER_FILTER = "user:bloom:filter";
  
    @PostConstruct
    public void initBloomFilter() {
        // 初始化布隆过滤器，预期100万用户，1%误判率
        bloomFilter.createFilter(USER_FILTER, 0.01, 1000000);
      
        // 将现有用户ID加载到布隆过滤器
        List<Long> existingUserIds = userRepository.findAllUserIds();
        String[] userIds = existingUserIds.stream()
            .map(String::valueOf)
            .toArray(String[]::new);
        bloomFilter.add(USER_FILTER, userIds);
    }
  
    public User getUserById(Long userId) {
        String userIdStr = String.valueOf(userId);
      
        // 先检查布隆过滤器
        if (!bloomFilter.mightContain(USER_FILTER, userIdStr)) {
            // 确定不存在，直接返回null，避免缓存穿透
            return null;
        }
      
        // 可能存在，继续查询缓存和数据库
        return userRepository.findById(userId).orElse(null);
    }
  
    public void createUser(User user) {
        userRepository.save(user);
        // 新用户创建后，添加到布隆过滤器
        bloomFilter.add(USER_FILTER, String.valueOf(user.getId()));
    }
}

2. 性能优化策略

@Configuration
public class BloomFilterConfig {
  
    /**
     * 批量操作优化
     */
    @Bean
    public BloomFilterBatchProcessor batchProcessor() {
        return new BloomFilterBatchProcessor();
    }
  
    public static class BloomFilterBatchProcessor {
        private final List<String> pendingElements = new ArrayList<>();
        private final ScheduledExecutorService scheduler = 
            Executors.newScheduledThreadPool(1);
      
        @PostConstruct
        public void init() {
            // 每100ms批量提交一次
            scheduler.scheduleAtFixedRate(this::flushBatch, 100, 100, 
                TimeUnit.MILLISECONDS);
        }
      
        public synchronized void addElement(String element) {
            pendingElements.add(element);
            if (pendingElements.size() >= 1000) {
                flushBatch();
            }
        }
      
        private synchronized void flushBatch() {
            if (!pendingElements.isEmpty()) {
                // 批量添加到布隆过滤器
                String[] elements = pendingElements.toArray(new String[0]);
                // bloomFilter.add(FILTER_NAME, elements);
                pendingElements.clear();
            }
        }
    }
}

最佳实践总结

1. 参数选择原则

• 误判率：通常选择0.01-0.001之间，平衡内存和准确性
• 容量预估：预留20-30%的冗余空间
• 哈希函数：Redis自动计算最优值，无需手动设置

2. 使用场景

• 缓存穿透防护：防止大量无效请求打到数据库
• 去重判断：大数据量下的快速去重
• 推荐系统：快速过滤已推荐内容

3. 注意事项

• 布隆过滤器不支持删除操作
• 需要定期重建以保持准确性
• 误判率会随着元素增加而上升
• 适合读多写少的场景

Redis 7 的原生布隆过滤器支持为分布式系统提供了高效的缓存穿透防护方案，通过合理的参数配置和批量操作优化，能够在保证性能的同时有效控制内存使用。