LevelDB 完全指南 / 第 10 章 · Bloom Filter

第 10 章 · Bloom Filter

10.1 为什么需要 Bloom Filter

在 LevelDB 中，一次读取可能需要检查多个 SSTable 文件。如果某个 SSTable 中不包含目标 Key，仍然需要读取磁盘上的 Index Block 才能确定——这是一次无谓的磁盘 I/O。

没有 Bloom Filter 的读取：

  Get("user:9999")
    → 查 SST-1: 读取 Index Block → 未找到  ← 白读了一次磁盘
    → 查 SST-2: 读取 Index Block → 未找到  ← 又白读了一次
    → 查 SST-3: 读取 Index Block → 找到！
    
  如果数据库有 100 个 SSTable，可能需要读 100 次 Index Block

Bloom Filter 可以快速判断某个 Key 是否可能存在于 SSTable 中，从而跳过确定不存在的文件：

有 Bloom Filter 的读取：

  Get("user:9999")
    → 查 SST-1 的 Bloom Filter → 确定不存在 → 跳过！
    → 查 SST-2 的 Bloom Filter → 确定不存在 → 跳过！
    → 查 SST-3 的 Bloom Filter → 可能存在 → 读取 Index Block → 找到！
    
  大幅减少磁盘 I/O

10.2 Bloom Filter 原理

基本结构

Bloom Filter 是一个位数组加上多个哈希函数：

位数组 (m bits)：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

哈希函数：h1, h2, h3, ..., hk

插入操作

插入 "apple"：
  h1("apple") = 1
  h2("apple") = 4
  h3("apple") = 7
  
  设置位数组的第 1、4、7 位为 1

插入 "banana"：
  h1("banana") = 3
  h2("banana") = 4
  h3("banana") = 11
  
  设置位数组的第 3、4、11 位为 1

当前位数组：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 0 │ 1 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
      A   B   AB      A       B               A

查询操作

查询 "apple"：
  h1("apple") = 1  → 位数组[1] = 1 ✓
  h2("apple") = 4  → 位数组[4] = 1 ✓
  h3("apple") = 7  → 位数组[7] = 1 ✓
  所有位都为 1 → 可能存在 ✓

查询 "cherry"：
  h1("cherry") = 1  → 位数组[1] = 1 ✓
  h2("cherry") = 4  → 位数组[4] = 1 ✓
  h3("cherry") = 8  → 位数组[8] = 0 ✗
  有位为 0 → 确定不存在 ✓

查询 "grape"（假设未插入）：
  h1("grape") = 3  → 位数组[3] = 1 ✓  (碰巧为 1)
  h2("grape") = 4  → 位数组[4] = 1 ✓  (碰巧为 1)
  h3("grape") = 11 → 位数组[11] = 1 ✓  (碰巧为 1)
  所有位都为 1 → 可能存在（但是误判！）

10.3 误判率（False Positive Rate）

误判率公式

误判率 ≈ (1 - e^(-kn/m))^k

其中：
  m = 位数组大小（bits）
  n = 插入的元素数量
  k = 哈希函数数量
  e = 自然常数 ≈ 2.718

最佳哈希函数数量：
  k = (m/n) × ln(2) ≈ 0.693 × (m/n)

误判率速查表

💡 提示：LevelDB 默认每个 Key 使用 10 bits，误判率约为 2.2%。对于大多数场景已经足够。

10.4 LevelDB 中配置 Bloom Filter

C++ 配置

#include "leveldb/filter_policy.h"
#include "leveldb/db.h"

leveldb::Options options;

// 创建 Bloom Filter（每个 Key 10 bits）
options.filter_policy = leveldb::NewBloomFilterPolicy(10);

leveldb::DB* db;
leveldb::DB::Open(options, "/tmp/bloom_db", &db);

// 之后的所有读取都会自动使用 Bloom Filter
std::string value;
db->Get(leveldb::ReadOptions(), "some_key", &value);

// 清理
delete db;
delete options.filter_policy;  // filter_policy 需要手动释放

Go 配置

import "github.com/syndtr/goleveldb/leveldb/filter"

db, err := leveldb.OpenFile("/tmp/bloom_db", &opt.Options{
    Filter: filter.NewBloomFilter(10),  // 每个 Key 10 bits
})

Python 配置

db = plyvel.DB('/tmp/bloom_db', create_if_missing=True,
               bloom_filter_bits=10)  # 每个 Key 10 bits

10.5 误判率与性能的权衡

位数选择指南

内存计算

假设：
  Key 数量 = 10,000,000 (1000 万)
  每个 Key 10 bits

Bloom Filter 内存：
  10,000,000 × 10 bits = 100,000,000 bits = 12.5 MB

  分布在所有 SSTable 文件中

10.6 性能影响分析

读取性能提升

测试环境：
  数据库大小: 10GB
  Key 数量: 1000 万
  随机读取 1000 个 Key

结果：
  无 Bloom Filter:  平均 3.2ms / 读取，I/O 次数: ~2500
  有 Bloom Filter:  平均 0.8ms / 读取，I/O 次数: ~400

  性能提升: 4x

Bloom Filter 的局限性

10.7 业务场景

场景一：用户状态查询（高命中率需求）

// 场景：大部分查询的用户是存在的
// Bloom Filter 主要帮助快速跳过不包含该用户的 SSTable

leveldb::Options options;
options.filter_policy = leveldb::NewBloomFilterPolicy(14);  // 0.3% 误判率

// 读取时，对于不存在的用户，Bloom Filter 能快速排除
// 对于存在的用户，Bloom Filter 无法帮助（仍需读取数据）

场景二：黑名单检查（大部分查询不在列表中）

// 场景：大部分 IP 不在黑名单中
// Bloom Filter 的价值最大

leveldb::Options options;
options.filter_policy = leveldb::NewBloomFilterPolicy(10);

bool IsBlacklisted(leveldb::DB* db, const std::string& ip) {
    std::string value;
    leveldb::Status s = db->Get(leveldb::ReadOptions(),
                                "blacklist:" + ip, &value);
    // 如果 s.IsNotFound()，Bloom Filter 可以帮助快速判断
    // 减少不必要的磁盘 I/O
    return s.ok();
}

10.8 监控 Bloom Filter 效果

leveldb::Options options;
options.filter_policy = leveldb::NewBloomFilterPolicy(10);
options.statistics = leveldb::CreateDBStatistics();

// ... 使用数据库 ...

auto stats = options.statistics;
uint64_t positive = stats->getTickerCount(leveldb::BLOOM_FILTER_FULL_POSITIVE);
uint64_t true_positive = stats->getTickerCount(
    leveldb::BLOOM_FILTER_FULL_TRUE_POSITIVE);
uint64_t useful = stats->getTickerCount(leveldb::BLOOM_FILTER_USEFUL);

std::cout << "Bloom Filter 过滤掉的无效查询: " << useful << std::endl;
std::cout << "可能命中的查询: " << positive << std::endl;
std::cout << "实际命中的查询: " << true_positive << std::endl;
std::cout << "误判次数: " << (positive - true_positive) << std::endl;

10.9 注意事项

10.10 本章小结

扩展阅读

1. Bloom Filter 论文：Bloom, B.H. (1970). “Space/time trade-offs in hash coding with allowable errors”
2. LevelDB Filter 实现：util/bloom.cc
3. Cuckoo Filter：更高级的过滤器，支持删除
4. Ribbon Filter：RocksDB 的新型过滤器，空间效率更高

← 第 9 章 · Block Cache | 第 11 章 · 性能基准测试 →