Redis布隆过滤器应用

Redis 的五种数据结构各有特色，用对了才能发挥它的优势。很多人只用到了 String 和 Hash，却不知道 List、Set、ZSet 在特定场景下更合适。本文从应用场景出发，讲什么时候用什么类型。

一、布隆过滤器原理

#

1.1 基本结构

布隆过滤器由两部分组成：
1. 一个长度为m的bit数组（初始全为0）
2. k个独立的哈希函数

初始状态：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┘

#

1.2 添加元素

添加"Alice"：
1. 用k个哈希函数计算：h1("Alice")=2, h2("Alice")=5
2. 将bit数组对应位置设为1

┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┘
        ↑           ↑
      h1(Alice)  h2(Alice)

添加"Bob"：
h1("Bob")=3, h2("Bob")=5

┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 1 │ 1 │ 0 │ 1 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┘
            ↑       ↑
          h1(Bob) h2(Bob)

#

1.3 查询元素

查询"Alice"：
h1("Alice")=2, h2("Alice")=5
检查bit[2]和bit[5]都是1 → "可能在集合中"

查询"Charlie"：
h1("Charlie")=1, h2("Charlie")=6
检查bit[1]=0 → "一定不在集合中"

查询"David"：
h1("David")=2, h2("David")=3
检查bit[2]=1, bit[3]=1 → "可能在集合中"（实际不在，误判！）

#

1.4 特点

特性	说明
空间效率	极高效，存储1亿个元素仅需约100MB
查询时间	O(k)，k是哈希函数数量，常数时间
添加时间	O(k)，常数时间
误判率	存在（可能判断为存在，实际不存在）
漏判率	不存在（判断为不存在，一定不存在）
删除	不支持（或需要特殊实现）

二、RedisBloom模块

#

2.1 安装

# 方式1：编译安装RedisBloom
git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make

# 在redis.conf中加载模块
loadmodule /path/to/redisbloom.so

# 方式2：使用Docker
docker run -p 6379:6379 redislabs/rebloom:latest

# 方式3：Redis Stack（包含RedisBloom）
docker run -d --name redis-stack -p 6379:6379 redis/redis-stack:latest

#

2.2 基本命令

# 创建布隆过滤器
BF.RESERVE user_filter 0.01 1000000
# BF.RESERVE <key> <error_rate> <capacity>

# 添加元素
BF.ADD user_filter user:1001
BF.ADD user_filter user:1002

# 批量添加
BF.MADD user_filter user:1003 user:1004 user:1005

# 查询元素
BF.EXISTS user_filter user:1001    # 返回1（可能存在）
BF.EXISTS user_filter user:9999    # 返回0（一定不存在）

# 批量查询
BF.MEXISTS user_filter user:1001 user:1002 user:9999

# 查看信息
BF.INFO user_filter
# 输出：
# 1) Capacity
# 2) (integer) 1000000
# 3) Size
# 4) (integer) 2396279
# 5) Number of filters
# 6) (integer) 1
# 7) Number of items inserted
# 8) (integer) 2
# 9) Expansion rate
# 10) (integer) 2

#

2.3 自动扩容

# 使用BF.ADD（不预先RESERVE）会自动创建
BF.ADD auto_filter user:1001
# 使用默认参数：error_rate=0.1%, capacity=100

# 当容量不足时，BF会自动扩容
BF.ADD auto_filter user:101
# 自动扩容，误判率会略有增加

三、Java中使用RedisBloom

#

3.1 Redisson实现

@Configuration
public class BloomFilterConfig {
    
    @Bean
    public RBloomFilter<String> userBloomFilter(RedissonClient redisson) {
        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("userFilter");
        
        // 初始化：预期100万元素，误判率1%
        bloomFilter.tryInit(1000000L, 0.01);
        
        return bloomFilter;
    }
}

@Service
public class UserService {
    
    @Autowired
    private RBloomFilter<String> userBloomFilter;
    @Autowired
    private StringRedisTemplate redis;
    @Autowired
    private UserMapper userMapper;
    
    // 初始化布隆过滤器
    @PostConstruct
    public void init() {
        List<Long> userIds = userMapper.findAllIds();
        for (Long id : userIds) {
            userBloomFilter.add("user:" + id);
        }
    }
    
    public User getUser(Long id) {
        String key = "user:" + id;
        
        // 1. 布隆过滤器判断
        if (!userBloomFilter.contains(key)) {
            return null;  // 一定不存在
        }
        
        // 2. 查缓存
        String json = redis.opsForValue().get(key);
        if (json != null) {
            return JSON.parseObject(json, User.class);
        }
        
        // 3. 查数据库
        User user = userMapper.findById(id);
        if (user != null) {
            redis.opsForValue().set(key, JSON.toJSONString(user), 3600, TimeUnit.SECONDS);
        }
        
        return user;
    }
}

#

3.2 Guava + Redis实现

@Component
public class GuavaBloomFilter {
    
    private BloomFilter<String> bloomFilter;
    
    @PostConstruct
    public void init() {
        // 创建布隆过滤器（本地内存）
        bloomFilter = BloomFilter.create(
            Funnels.stringFunnel(StandardCharsets.UTF_8),
            1000000,   // 预期元素数
            0.01       // 误判率
        );
        
        // 加载数据
        loadData();
    }
    
    public boolean mightContain(String element) {
        return bloomFilter.mightContain(element);
    }
    
    public void put(String element) {
        bloomFilter.put(element);
    }
}

四、应用场景

#

4.1 缓存穿透防护

@Service
public class CachePenetrationProtection {
    
    @Autowired
    private RBloomFilter<String> bloomFilter;
    @Autowired
    private StringRedisTemplate redis;
    @Autowired
    private ProductMapper productMapper;
    
    public Product getProduct(Long id) {
        String key = "product:" + id;
        
        // 布隆过滤器先判断
        if (!bloomFilter.contains(key)) {
            return null;  // 一定不存在，直接返回
        }
        
        // 查缓存
        String json = redis.opsForValue().get(key);
        if (json != null) {
            return JSON.parseObject(json, Product.class);
        }
        
        // 查数据库（只有布隆过滤器判断可能存在时才查）
        Product product = productMapper.findById(id);
        if (product != null) {
            redis.opsForValue().set(key, JSON.toJSONString(product), 3600, TimeUnit.SECONDS);
        }
        
        return product;
    }
}

#

4.2 URL去重（爬虫）

@Service
public class CrawlerService {
    
    @Autowired
    private RBloomFilter<String> urlBloomFilter;
    
    public boolean shouldCrawl(String url) {
        // 如果URL可能在集合中，跳过
        if (urlBloomFilter.contains(url)) {
            return false;  // 已爬过（可能误判，会漏掉少量未爬的）
        }
        
        // 新URL，添加到布隆过滤器
        urlBloomFilter.add(url);
        return true;
    }
}

#

4.3 用户ID去重

@Service
public class UserIdDeduplication {
    
    @Autowired
    private RBloomFilter<String> userIdFilter;
    
    // 检查用户是否已注册
    public boolean isUserRegistered(String userId) {
        return userIdFilter.contains(userId);
    }
    
    // 用户注册时添加
    public void registerUser(String userId) {
        userIdFilter.add(userId);
    }
}

#

4.4 推荐系统（已推荐过滤）

@Service
public class RecommendationService {
    
    @Autowired
    private RBloomFilter<String> recommendationFilter;
    
    public List<Article> recommendArticles(Long userId) {
        List<Article> candidates = articleMapper.findCandidates();
        List<Article> result = new ArrayList<>();
        
        for (Article article : candidates) {
            String key = userId + ":" + article.getId();
            
            // 如果可能已推荐过，跳过
            if (recommendationFilter.contains(key)) {
                continue;
            }
            
            result.add(article);
            recommendationFilter.add(key);
            
            if (result.size() >= 10) break;
        }
        
        return result;
    }
}

五、参数调优

#

5.1 误判率与空间的关系

公式：
bit数组大小 m = -n * ln(p) / (ln(2)^2)
哈希函数数 k = m * ln(2) / n

其中：
n = 预期元素数量
p = 误判率

示例：
n = 100万, p = 1%
m ≈ 9585058 bits ≈ 1.14MB
k ≈ 7

n = 100万, p = 0.1%
m ≈ 14377078 bits ≈ 1.72MB
k ≈ 10

#

5.2 参数选择建议

场景	预期元素数	可接受误判率	推荐大小
缓存穿透防护	1000万	1%	11.4MB
URL去重	1亿	0.1%	172MB
用户ID	1000万	0.01%	22.9MB
日志去重	10亿	1%	1.14GB

#

5.3 动态扩容

# RedisBloom支持自动扩容
BF.RESERVE myfilter 0.01 1000000 EXPANSION 2
# EXPANSION: 扩容倍数，默认2

# 当容量达到100万时，自动创建子过滤器
# 子过滤器容量 = 100万 * 2 = 200万
# 误判率会略有增加

六、布隆过滤器的局限

#

6.1 不支持删除

问题：
删除"Alice"时，不能简单将bit[2]和bit[5]设为0
因为"Bob"也可能使用了bit[5]

解决方案：
1. Counting Bloom Filter（每个bit改为计数器）
2. Cuckoo Filter（支持删除的变体）

#

6.2 误判不可控

一旦创建，误判率固定（除非扩容）
不能根据查询结果调整

缓解方案：
1. 使用白名单记录误判的元素
2. 定期重建布隆过滤器

七、Counting Bloom Filter

#

7.1 原理

将bit数组改为计数器数组：

添加"Alice"：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┘

添加"Bob"：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 1 │ 1 │ 0 │ 2 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┘
                ↑       ↑
              h1(Bob) h2(Bob)（h2位置已有Alice，计数+1）

删除"Alice"：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┘
        ↑               ↑
      减1             减1（但不小于0）

#

7.2 Redis实现

# RedisBloom的CF（Cuckoo Filter）支持删除
CF.ADD mycf item1
CF.EXISTS mycf item1    # 返回1
CF.DEL mycf item1       # 删除
CF.EXISTS mycf item1    # 返回0

八、总结

特性	布隆过滤器	HashSet
空间效率	极高	低
查询时间	O(1)	O(1)
误判	有	无
删除	不支持	支持
适用场景	大数据量，允许误判	小数据量，精确判断

布隆过滤器的核心价值：

1. 空间效率：用极少的空间存储大量元素的存在信息
2. 时间效率：O(1)的查询时间
3. 零漏判：判断为不存在则一定不存在

使用建议：

1. 适合”可能存在”的场景，不适用于”一定存在”
2. 根据预期数据量和可接受误判率选择参数
3. 定期重建以保持误判率
4. 不能替代精确查询，只能用于前置过滤

核心要点

1. String：简单的键值对，适合缓存、计数器

2. Hash：存储对象属性，适合用户信息、配置

3. List：有序列表，适合消息队列、最新列表

4. Set：无序去重，适合共同好友、抽奖

5. ZSet：有序集合，适合排行榜、积分系统

总结

选择合适的数据结构是使用 Redis 的关键。在实际项目中，根据业务需求选择合适的类型，可以提升性能和开发效率。