布隆（Bloom）过滤器

本文还是对《区块链：原理、设计与应用》的一个基础技术的总结和摘录。

散列的本质，是把任意内容，映射成固定长度的内容域里的某一个内容。

布隆过滤器的本质，是在常数时间内回答，“一个元素是否在一个集合内”的问题。

直观的方法及其缺陷

假设我们总可以把任意内容映射到某一个数组的 item 上，那么只要看看那个数组的 item 是否为空，就可以确认某一个内容是否存在。然而现实之中，一个数组总是会产生冲突，操作性能会因为局部冲突而产生退化。

多重散列的布隆过滤器

布隆过滤器的原理很简单，就是插入元素时，在一个容量为 m 的bit数组上， 用 k 要确认某个内容是否存在，可以使用布隆过滤器（Bloom Filter），它是一种高效的空间节省型数据结构，用于快速判断一个元素是否属于某个集合。以下是关键点总结：

布隆过滤器工作原理

graph TD
    A[布隆过滤器 Bloom Filter] --> B[位数组 Bit Array]
    A --> C[k个哈希函数]
    
    B --> D["初始状态: [0,0,0,0,0,0,0,0,0,0]"]
    
    E[添加元素 Add Element] --> F["元素: 'apple'"]
    F --> G[Hash1: apple → 2]
    F --> H[Hash2: apple → 5] 
    F --> I[Hash3: apple → 8]
    
    G --> J["设置 bit[2] = 1"]
    H --> K["设置 bit[5] = 1"]
    I --> L["设置 bit[8] = 1"]
    
    J --> M["结果: [0,0,1,0,0,1,0,0,1,0]"]
    K --> M
    L --> M
    
    N[查询元素 Query Element] --> O["查询: 'banana'"]
    O --> P[Hash1: banana → 1]
    O --> Q[Hash2: banana → 5]
    O --> R[Hash3: banana → 7]
    
    P --> S["检查 bit[1] = 0 ❌"]
    Q --> T["检查 bit[5] = 1 ✅"]
    R --> U["检查 bit[7] = 0 ❌"]
    
    S --> V[有任何位为0]
    T --> V
    U --> V
    V --> W["肯定不存在 Definitely NOT in set"]
    
    X[查询元素 Query Element] --> Y["查询: 'apple'"]
    Y --> Z[Hash1: apple → 2]
    Y --> AA[Hash2: apple → 5]
    Y --> BB[Hash3: apple → 8]
    
    Z --> CC["检查 bit[2] = 1 ✅"]
    AA --> DD["检查 bit[5] = 1 ✅"]
    BB --> EE["检查 bit[8] = 1 ✅"]
    
    CC --> FF[所有位都为1]
    DD --> FF
    EE --> FF
    FF --> GG["可能存在 Possibly in set<br/>（可能误判）"]
    
    style A fill:#e1f5fe
    style W fill:#ffebee
    style GG fill:#fff3e0
    style M fill:#e8f5e8

• 插入元素：使用 k 个不同的哈希函数将元素映射到位数组（bit array）中的 k 个位置，并将这些位置标记为1。
• 查询元素：同样使用 k 个哈希函数查找对应的 k 个位置，如果所有位都是1，则认为该元素可能存在；如果至少有一个位是0，则该元素一定不存在。

graph LR
    subgraph "布隆过滤器结构"
        A[位数组 Bit Array<br/>固定大小m位] 
        B[哈希函数1<br/>h1x]
        C[哈希函数2<br/>h2x]
        D[哈希函数k<br/>hkx]
        
        A -.-> E["[0,0,0,0,0,0,0,0,0,0]<br/>初始全为0"]
    end
    
    style A fill:#e3f2fd
    style B fill:#f3e5f5
    style C fill:#f3e5f5
    style D fill:#f3e5f5

sequenceDiagram
    participant E as 元素 Element
    participant H1 as Hash函数1
    participant H2 as Hash函数2  
    participant H3 as Hash函数3
    participant BA as 位数组
    
    E->>H1: "apple"
    H1->>BA: 设置 bit[2] = 1
    
    E->>H2: "apple"  
    H2->>BA: 设置 bit[5] = 1
    
    E->>H3: "apple"
    H3->>BA: 设置 bit[8] = 1
    
    Note over BA: [0,0,1,0,0,1,0,0,1,0]

graph TD
    A[查询元素] --> B{计算所有哈希值}
    B --> C{检查对应位置}
    
    C --> D{所有位都为1?}
    D -->|是| E["可能存在<br/>🟡 False Positive 可能"]
    D -->|否| F["肯定不存在<br/>🔴 绝对准确"]
    
    E --> G["需要进一步验证<br/>（查询原始数据）"]
    F --> H["可以确信不存在"]
    
    style E fill:#fff3e0
    style F fill:#ffebee
    style G fill:#e8f5e8
    style H fill:#e8f5e8

特点

mindmap
  root((布隆过滤器))
    优点
      空间效率高
      查询速度快 O(k)
      插入速度快 O(k)
      无假阴性
    缺点  
      有假阳性
      无法删除元素
      无法确定元素个数
    应用场景
      缓存穿透防护
      爬虫URL去重
      分布式系统
      数据库查询优化
    参数设计
      位数组大小 m
      哈希函数个数 k  
      预期元素个数 n
      误判率 p

• 无假阴性：如果布隆过滤器说元素不存在，那它一定不在集合中。
• 可能有假阳性：如果布隆过滤器说元素存在，它可能实际上并不存在（误报）。
• 不支持删除（标准版本）：因为多个元素可能共享某些位，删除一个元素可能会误影响其他元素。但可以扩展为计数布隆过滤器（Counter Bloom Filter）支持删除。

优化参数

graph LR
    subgraph "布隆过滤器设计公式"
        A["误判率 p ≈ (1-e^(-kn/m))^k"]
        B["最优哈希函数个数 k = (m/n)×ln(2)"]
        C["所需位数组大小 m = -n×ln(p)/(ln(2))²"]
    end
    
    D[输入参数] --> E[预期元素个数 n]
    D --> F[可接受误判率 p]
    
    E --> B
    F --> C
    C --> B
    B --> A
    
    style A fill:#ffcdd2
    style B fill:#c8e6c9  
    style C fill:#bbdefb

• 最佳哈希函数数量：$$k = (\ln 2) \cdot \frac{m}{n}$$，其中：
  • m 是位数组大小（bit数）
  • n 是预期插入的元素数量
• 错误率越低，所需位数越多。

应用示例：找出多个大文件中的共同URL

• 当内存受限时（如4GB），布隆过滤器可以有效减少内存使用。
• 可先将一个文件的URL插入布隆过滤器，再逐个检查另一个文件的URL是否在其中。
• 若需处理多个文件，可使用多轮布隆过滤器或结合外部排序方法。

一个布隆过滤器相关的面试题

问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。

小结

布隆过滤器适用于需要快速判断元素是否存在、容忍一定误报率、但不能接受假阴性情况的场景，如缓存系统、数据库查询优化、网络应用等。 k 个 bit，而查找元素时，再用 k 个散列函数来寻找 k 个 bit，若这 k 个 bit 都被标记过了，则这个内容存在。

普通的布隆过滤器是不应该支持删除的，因为删除一个 bit 可能顺便删除掉其他内容的 bit。但如果把 bit 换成一个计数器，那么就可以考虑删除了。这也就会产生 counter bloom filter。

当hash函数个数k=(ln2)*(m/n)时错误率最小。

实际上，不管是散列算法，还是布隆过滤器，基本思想是一致的，都是基于内容的编址。Hash 函数存在冲突，布隆过滤器同样存在冲突。这就造成了两种方法都存在着假阳性误报问题（false positive），但绝不会存在假阴性漏报的问题（false negative）。布隆过滤器的误报率比单纯的散列算法低得多。

所以依据布隆过滤器设计方案的原则是：

1. 把所有可能需要查存的数据一次性加载进过滤器里。
2. 针对每个请求进行测试，如果测试不存在，则拒绝请求。
3. 如果存在，需要走入实地查询流程。
4. 合理选择参数（位数组大小、哈希函数个数、预期元素个数、误判率）。
   • 最佳哈希函数数量：( k = \frac{m}{n} \times \ln(2) )
   • 位数组大小：( m = -\frac{n \times \ln§}{(\ln(2))^2} )
   • 误判率：( p \approx \left(1 - e^{-\frac{k \times n}{m}}\right)^k )
5. 考虑误判率对业务的影响。对于一些对准确性要求不高的场景，可以接受较高的误判率以节省空间；而对于对准确性要求较高的场景，则需要降低误判率。
6. 避免过度使用布隆过滤器。当数据量较小且内存足够时，使用HashSet可以避免误判问题。因此，在选择使用布隆过滤器时，需要权衡其优缺点。
7. 考虑扩展性和维护性。在分布式系统中，布隆过滤器的状态可能需要在多个节点之间共享。此时，需要考虑如何高效地同步和更新布隆过滤器的状态。此外，布隆过滤器的维护也很重要，例如在数据更新时，需要及时更新布隆过滤器的状态，以保证其准确性。

实战

存穿透防护

场景描述

graph TD
    A[用户请求] --> B{布隆过滤器检查}
    B -->|不存在| C[直接返回空结果]
    B -->|可能存在| D[查询缓存]
    D -->|缓存命中| E[返回结果]
    D -->|缓存未命中| F[查询数据库]
    F --> G[更新缓存]
    G --> H[返回结果]
    
    style C fill:#ffcdd2
    style E fill:#c8e6c9
    style H fill:#c8e6c9

具体实现方案

@Service
public class ProductCacheService {
    
    // 布隆过滤器：存储所有存在的商品ID
    private BloomFilter<String> productBloomFilter;
    
    // Redis缓存
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;
    
    @PostConstruct
    public void initBloomFilter() {
        // 预期100万商品，误判率0.01%
        productBloomFilter = BloomFilter.create(
            Funnels.stringFunnel(Charset.defaultCharset()),
            1_000_000,
            0.0001
        );
        
        // 初始化：将所有存在的商品ID加入布隆过滤器
        List<String> existingProductIds = productRepository.getAllProductIds();
        existingProductIds.forEach(productBloomFilter::put);
    }
    
    public Product getProduct(String productId) {
        // 1. 布隆过滤器预检查
        if (!productBloomFilter.mightContain(productId)) {
            // 肯定不存在，直接返回
            return null;
        }
        
        // 2. 查询缓存
        Product cached = (Product) redisTemplate.opsForValue()
            .get("product:" + productId);
        if (cached != null) {
            return cached;
        }
        
        // 3. 查询数据库
        Product product = productRepository.findById(productId);
        if (product != null) {
            // 4. 更新缓存
            redisTemplate.opsForValue()
                .set("product:" + productId, product, Duration.ofHours(1));
        }
        
        return product;
    }
    
    // 新增商品时更新布隆过滤器
    public void addProduct(Product product) {
        productRepository.save(product);
        productBloomFilter.put(product.getId());
    }
}

性能提升

• ❌ 攻击前：恶意查询不存在的商品ID → 每次都查数据库
• ✅ 防护后：99.99%的恶意请求被布隆过滤器拦截

爬虫URL去重

场景描述

graph TD
    A[发现新URL] --> B{布隆过滤器检查}
    B -->|已访问| C[跳过该URL]
    B -->|未访问| D[加入爬取队列]
    D --> E[执行爬取]
    E --> F[将URL添加到布隆过滤器]
    F --> G[解析页面获取新URL]
    G --> A
    
    style C fill:#ffcdd2
    style D fill:#c8e6c9

具体实现方案

@Component
public class WebCrawler {
    
    // 布隆过滤器：记录已访问的URL
    private BloomFilter<String> visitedUrls;
    
    // 待爬取队列
    private Queue<String> crawlQueue = new LinkedBlockingQueue<>();
    
    @PostConstruct
    public void initCrawler() {
        // 预期爬取1000万URL，误判率0.1%
        visitedUrls = BloomFilter.create(
            Funnels.stringFunnel(Charset.defaultCharset()),
            10_000_000,
            0.001
        );
    }
    
    public void addUrlToCrawl(String url) {
        // 标准化URL
        String normalizedUrl = normalizeUrl(url);
        
        // 检查是否已访问
        if (visitedUrls.mightContain(normalizedUrl)) {
            log.debug("URL可能已访问，跳过: {}", normalizedUrl);
            return;
        }
        
        // 添加到爬取队列
        crawlQueue.offer(normalizedUrl);
        log.info("新URL加入队列: {}", normalizedUrl);
    }
    
    @Async
    public void crawl() {
        while (!crawlQueue.isEmpty()) {
            String url = crawlQueue.poll();
            
            try {
                // 执行爬取
                Document doc = Jsoup.connect(url).get();
                
                // 标记为已访问
                visitedUrls.put(url);
                
                // 提取新的链接
                Elements links = doc.select("a[href]");
                for (Element link : links) {
                    String newUrl = link.absUrl("href");
                    addUrlToCrawl(newUrl);
                }
                
                // 处理页面内容
                processPageContent(doc);
                
            } catch (Exception e) {
                log.error("爬取失败: {}", url, e);
            }
        }
    }
    
    private String normalizeUrl(String url) {
        // 移除fragment、统一协议等
        return url.toLowerCase()
                  .replaceAll("#.*$", "")
                  .replaceAll("/$", "");
    }
}

内存效率对比

graph LR
    subgraph "传统方法 HashSet"
        A[1000万URL] --> B[每个URL平均100字节]
        B --> C[需要约1GB内存]
    end
    
    subgraph "布隆过滤器"
        D[1000万URL] --> E[误判率0.1%]
        E --> F[仅需约14MB内存]
    end
    
    C --> G[内存使用减少98.6%]
    F --> G
    
    style G fill:#c8e6c9

分布式系统去重

场景描述

graph TD
    subgraph "微服务A"
        A1[接收消息] --> A2[布隆过滤器检查]
        A2 -->|重复| A3[丢弃消息]
        A2 -->|新消息| A4[处理并转发]
    end
    
    subgraph "微服务B"  
        B1[接收消息] --> B2[布隆过滤器检查]
        B2 -->|重复| B3[丢弃消息]
        B2 -->|新消息| B4[处理并转发]
    end
    
    subgraph "共享状态"
        C[Redis集群存储<br/>布隆过滤器状态]
    end
    
    A2 -.-> C
    B2 -.-> C
    
    style A3 fill:#ffcdd2
    style B3 fill:#ffcdd2
    style A4 fill:#c8e6c9
    style B4 fill:#c8e6c9

具体实现方案

@Service
public class DistributedDeduplicationService {
    
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;
    
    private static final String BLOOM_FILTER_KEY = "dedup:bloom_filter";
    private static final int EXPECTED_ELEMENTS = 10_000_000;
    private static final double FALSE_POSITIVE_RATE = 0.001;
    
    // Redis位图实现布隆过滤器
    public boolean addAndCheck(String messageId) {
        // 使用多个哈希函数
        int[] hashes = getHashValues(messageId);
        
        boolean isNew = false;
        for (int hash : hashes) {
            // 检查位是否已设置
            Boolean bitValue = redisTemplate.opsForValue()
                .getBit(BLOOM_FILTER_KEY, hash);
            
            if (!bitValue) {
                isNew = true;
                // 设置位
                redisTemplate.opsForValue()
                    .setBit(BLOOM_FILTER_KEY, hash, true);
            }
        }
        
        // 设置过期时间（滑动窗口去重）
        redisTemplate.expire(BLOOM_FILTER_KEY, Duration.ofHours(24));
        
        return isNew;
    }
    
    private int[] getHashValues(String input) {
        // 使用MurmurHash等高质量哈希函数
        int hash1 = Hashing.murmur3_32().hashString(input, StandardCharsets.UTF_8).asInt();
        int hash2 = Hashing.crc32().hashString(input, StandardCharsets.UTF_8).asInt();
        
        // 生成k个哈希值
        int[] hashes = new int[3];
        for (int i = 0; i < 3; i++) {
            hashes[i] = Math.abs((hash1 + i * hash2) % getBitArraySize());
        }
        return hashes;
    }
    
    private int getBitArraySize() {
        // 计算最优位数组大小
        return (int) (-EXPECTED_ELEMENTS * Math.log(FALSE_POSITIVE_RATE) / (Math.log(2) * Math.log(2)));
    }
}

@Component
public class MessageProcessor {
    
    @Autowired
    private DistributedDeduplicationService dedupService;
    
    @EventListener
    public void handleMessage(MessageEvent event) {
        String messageId = event.getMessageId();
        
        // 分布式去重检查
        if (!dedupService.addAndCheck(messageId)) {
            log.warn("重复消息，已丢弃: {}", messageId);
            return;
        }
        
        // 处理新消息
        processNewMessage(event);
    }
}

数据库查询优化

场景描述

graph TD
    A[查询请求] --> B{布隆过滤器<br/>分区检查}
    B -->|分区1可能包含| C1[查询分区1]
    B -->|分区2不包含| C2[跳过分区2]
    B -->|分区3可能包含| C3[查询分区3]
    
    C1 --> D[合并结果]
    C3 --> D
    D --> E[返回最终结果]
    
    style C2 fill:#ffcdd2
    style C1 fill:#c8e6c9
    style C3 fill:#c8e6c9

具体实现方案

@Repository
public class PartitionedUserRepository {
    
    // 每个分区对应一个布隆过滤器
    private Map<String, BloomFilter<String>> partitionBloomFilters = new HashMap<>();
    
    @PostConstruct
    public void initPartitionFilters() {
        List<String> partitions = Arrays.asList("user_2023", "user_2024", "user_2025");
        
        for (String partition : partitions) {
            BloomFilter<String> filter = BloomFilter.create(
                Funnels.stringFunnel(Charset.defaultCharset()),
                1_000_000,  // 每个分区预期100万用户
                0.01        // 1%误判率
            );
            
            // 初始化：加载分区中所有用户ID
            List<String> userIds = getUserIdsFromPartition(partition);
            userIds.forEach(filter::put);
            
            partitionBloomFilters.put(partition, filter);
        }
    }
    
    public User findUserById(String userId) {
        List<String> candidatePartitions = new ArrayList<>();
        
        // 检查哪些分区可能包含该用户
        for (Map.Entry<String, BloomFilter<String>> entry : partitionBloomFilters.entrySet()) {
            if (entry.getValue().mightContain(userId)) {
                candidatePartitions.add(entry.getKey());
            }
        }
        
        // 只查询候选分区
        for (String partition : candidatePartitions) {
            User user = queryUserFromPartition(partition, userId);
            if (user != null) {
                return user;
            }
        }
        
        return null;
    }
    
    @Transactional
    public void saveUser(User user) {
        String partition = determinePartition(user);
        saveUserToPartition(partition, user);
        
        // 更新对应分区的布隆过滤器
        partitionBloomFilters.get(partition).put(user.getId());
    }
}

各场景性能对比

graph TD
    subgraph "性能提升数据"
        A["缓存穿透防护<br/>🚀 恶意请求拦截率: 99.99%<br/>💾 内存开销: < 1MB"]
        B["URL去重<br/>🚀 内存节省: 98.6%<br/>⚡ 查询速度: O1"]
        C["分布式去重<br/>🚀 网络请求减少: 95%<br/>🔄 横向扩展性: 优秀"]
        D["数据库优化<br/>🚀 查询分区减少: 70%<br/>📈 查询性能提升: 3-5倍"]
    end
    
    style A fill:#e8f5e8
    style B fill:#e3f2fd
    style C fill:#fff3e0
    style D fill:#f3e5f5

这些实现方案展示了布隆过滤器在不同场景下的强大威力：

1. 极低的内存开销
2. 超快的查询速度
3. 优秀的扩展性
4. 显著的性能提升