布隆过滤器（Bloom Filter）和计数型布隆过滤器（Counting Bloom Filter）都是高效的概率性数据结构，用于判断某个元素是否在集合中。它们的设计目标是降低内存开销，通过多个哈希函数与位数组的组合，实现快速查询，但允许一定的误判率。
文章目录
1. 布隆过滤器（Bloom Filter）
1.1 原理
布隆过滤器使用多个哈希函数将元素映射到一个位数组中的多个位置。插入元素时，将这些位置标记为1；查询时，检查这些位置是否都为1。如果有任何位置为0，元素一定不存在；如果全为1，元素可能存在。
1.2 特性
- 空间效率高：布隆过滤器占用的内存较小，适合处理大规模数据。
- 允许误判：布隆过滤器存在误判情况，即可能认为某个元素存在，实际上不存在（假正例）；但不会出现假负例。
- 不可删除元素：布隆过滤器无法移除已插入的元素，因为移除一个元素可能会影响其他元素的判断。
- 查询速度快：插入和查询操作的时间复杂度都是
O(k)，其中k是哈希函数的数量。
1.3 使用场景
- 缓存穿透防护：用于过滤不存在的数据请求，避免直接查询数据库，减轻数据库压力。
- 垃圾邮件过滤：判断邮件是否在黑名单中。
- URL去重：用于爬虫系统中避免重复抓取网页。
2. 计数型布隆过滤器（Counting Bloom Filter）
2.1 原理
计数型布隆过滤器是在布隆过滤器基础上进行扩展的，通过将布隆过滤器中的位数组替换为计数器数组。每个哈希位置使用计数器来记录元素出现的次数，插入元素时计数器加1，删除元素时计数器减1。
2.2 特性
- 支持删除操作：通过计数器，计数型布隆过滤器可以支持删除元素，弥补了标准布隆过滤器的不足。
- 空间开销较大：由于使用计数器数组（而非位数组），计数型布隆过滤器的内存需求较高。
- 误判率：与布隆过滤器相同，计数型布隆过滤器也可能出现误判，即返回元素存在的假正例。
2.3 使用场景
- 动态数据管理：适用于需要不断添加和删除元素的场景，如缓存系统中删除过期数据或爬虫系统中移除已抓取的URL。
- 缓存系统：用于防止缓存穿透，并允许在缓存失效或数据更新时动态删除相应的元素。
3. 布隆过滤器与计数型布隆过滤器对比
| 特性 | 布隆过滤器 | 计数型布隆过滤器 |
|---|---|---|
| 空间占用 | 较小，使用位数组 | 较大，使用计数器数组 |
| 删除操作 | 不支持 | 支持 |
| 误判率 | 存在假正例 | 存在假正例 |
| 使用场景 | 静态集合，不常有删除需求 | 动态集合，允许添加和删除 |
| 查询时间复杂度 | O(k) |
O(k) |
在Spring中，布隆过滤器和计数型布隆过滤器可以结合Redis和缓存管理机制，帮助防止缓存穿透。具体实现步骤如下：
4. 综合案例流程
- 商品数据初始化：启动时，将所有商品ID加载到布隆过滤器或计数型布隆过滤器中，初始化过滤器。
- 查询时判断：每次用户查询商品时，首先通过过滤器判断商品是否存在：
- 布隆过滤器：若不存在，直接返回空值；若可能存在，查询缓存或数据库。
- 计数型布隆过滤器：如果需要删除商品ID，可通过Redis的计数来动态删除数据。
- 缓存穿透防护：过滤器减少无效的数据库查询，提升系统性能，并有效防止缓存穿透。
- 动态删除和添加：对于计数型布隆过滤器，当商品下架时，可以删除商品ID，保证过滤器的实时性。
通过这种方式，布隆过滤器和计数型布隆过滤器在Spring应用中结合Redis等工具，能够有效防止缓存穿透，并支持动态数据的增删处理，提升电商系统的整体性能。
4.1 布隆过滤器在Spring中的使用
4.1.1 引入依赖
如果想自己实现布隆过滤器，需编写简单的布隆过滤器类，也可以使用第三方库，如Google Guava，其中包含了布隆过滤器的实现。引入依赖：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0-jre</version>
</dependency>
4.1.2 初始化布隆过滤器
在Spring的@Configuration类中初始化布隆过滤器，加载商品ID到布隆过滤器中。假设你已经有商品ID集合。
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
@Configuration
public class BloomFilterConfig {
@Bean
public BloomFilter<Long> productBloomFilter() {
// 假设我们估计有1000万商品，期望误判率为0.01
BloomFilter<Long> bloomFilter = BloomFilter.create(Funnels.longFunnel(), 10000000, 0.01);
// 从数据库加载商品ID并初始化布隆过滤器
List<Long> productIds = loadAllProductIdsFromDatabase();
for (Long productId : productIds) {
bloomFilter.put(productId);
}
return bloomFilter;
}
// 假设这是从数据库中加载所有商品ID的函数
private List<Long> loadAllProductIdsFromDatabase() {
// 具体实现略，假设从数据库中查询所有商品ID
return new ArrayList<>();
}
}
4.1.3 使用布隆过滤器查询
在用户查询商品时，首先通过布隆过滤器判断商品ID是否可能存在：
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
@Service
public class ProductService {
@Autowired
private BloomFilter<Long> productBloomFilter;
@Autowired
private ProductRepository productRepository;
public Product getProductById(Long productId) {
// 先用布隆过滤器判断
if (!productBloomFilter.mightContain(productId)) {
// 如果布隆过滤器认为商品不存在，直接返回null，避免数据库查询
return null;
}
// 如果布隆过滤器认为商品可能存在，则查询缓存或数据库
return productRepository.findById(productId).orElse(null);
}
}
4.2 计数型布隆过滤器在Spring中的使用
对于计数型布隆过滤器，我们需要额外的库或手动实现，可以考虑将计数器存储在Redis中，实现类似于计数型布隆过滤器的功能。
4.2.1 计数器在Redis中的存储
在Redis中，每个商品ID对应多个哈希值位置，可以通过Redis的哈希结构来存储计数信息。
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.HashOperations;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Component;
@Component
public class CountingBloomFilter {
@Autowired
private RedisTemplate<String, Integer> redisTemplate;
private static final String BLOOM_FILTER_KEY = "bloom_filter";
private int[] hashSeeds = {7, 11, 13, 31, 37}; // 自定义哈希种子数组
// 插入元素
public void add(Long productId) {
HashOperations<String, String, Integer> hashOps = redisTemplate.opsForHash();
for (int seed : hashSeeds) {
int hash = hash(productId, seed);
String field = String.valueOf(hash);
hashOps.increment(BLOOM_FILTER_KEY, field, 1);
}
}
// 查询元素是否存在
public boolean mightContain(Long productId) {
HashOperations<String, String, Integer> hashOps = redisTemplate.opsForHash();
for (int seed : hashSeeds) {
int hash = hash(productId, seed);
String field = String.valueOf(hash);
Integer count = hashOps.get(BLOOM_FILTER_KEY, field);
if (count == null || count == 0) {
return false; // 如果任何一个位置为0，则元素一定不存在
}
}
return true; // 所有位置非0，元素可能存在
}
// 删除元素
public void remove(Long productId) {
HashOperations<String, String, Integer> hashOps = redisTemplate.opsForHash();
for (int seed : hashSeeds) {
int hash = hash(productId, seed);
String field = String.valueOf(hash);
hashOps.increment(BLOOM_FILTER_KEY, field, -1);
}
}
// 简单哈希函数，使用种子计算
private int hash(Long value, int seed) {
return Math.abs((int) (value ^ seed) % 100000);
}
}
4.2.2 使用计数型布隆过滤器
与标准布隆过滤器类似，计数型布隆过滤器的使用可以在商品管理中实现商品的增删操作。
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
@Service
public class ProductService {
@Autowired
private CountingBloomFilter countingBloomFilter;
@Autowired
private ProductRepository productRepository;
public Product getProductById(Long productId) {
// 使用计数型布隆过滤器进行查询
if (!countingBloomFilter.mightContain(productId)) {
return null; // 商品不存在
}
return productRepository.findById(productId).orElse(null); // 查询缓存或数据库
}
public void addProduct(Product product) {
// 添加商品并加入布隆过滤器
productRepository.save(product);
countingBloomFilter.add(product.getId());
}
public void removeProduct(Long productId) {
// 删除商品并从布隆过滤器中移除
productRepository.deleteById(productId);
countingBloomFilter.remove(productId);
}
}
总结
布隆过滤器和计数型布隆过滤器都是高效的集合查询工具，适合大规模数据场景。布隆过滤器适用于不需要删除操作的静态集合，空间利用率高，而计数型布隆过滤器通过引入计数器，支持元素的动态增删，适合需要频繁更新数据的场景。两者在防止缓存穿透、URL去重、垃圾邮件过滤等领域都有广泛应用。