Leveldb作为轻量级的持久化KV存储引擎，为了降低读取数据时的磁盘IO开销，在SSTable的读取流程中引入了BloomFilter机制。BloomFilter可以在不读取完整数据块的情况下，快速判断某个key是否可能存在于当前SSTable中，避免无效的磁盘读取操作。
Leveldb BloomFilter模块的整体设计
Leveldb的BloomFilter实现位于util/bloom.cc和util/bloom.h文件中，核心类是BloomFilterPolicy，该类继承自FilterPolicy接口。整个模块的设计目标是用最少的内存实现尽可能高的过滤准确率，同时保证计算效率。
Leveldb的BloomFilter采用位图作为底层存储结构，每个SSTable的元数据部分会存储对应BloomFilter的位图数据。当读取SSTable时，会先加载BloomFilter位图，对目标key进行多次哈希计算后比对位图，只有所有哈希位都为1时才认为key可能存在，否则直接判定key不存在。
核心实现细节
位图存储结构
BloomFilter的位图被存储在一个字节数组中，每个字节的8个bit对应8个位置。Leveldb中BloomFilter的位数由用户配置的每key占用的bit数（bits_per_key）和当前SSTable中key的数量共同决定，计算公式如下：
总位数 = key数量 * bits_per_key
为了避免位数过少导致误判率过高，Leveldb会保证总位数至少为64位。位图的长度（字节数）则是总位数除以8向上取整。
哈希函数选择
Leveldb没有直接使用多个独立的哈希函数，而是采用了一个优化方案：先对key计算一个基础的哈希值，然后通过线性变换生成多个不同的哈希值，减少哈希计算的开销。基础哈希函数使用的是Leveldb内置的Hash函数，该函数是基于Murmur哈希的简化实现，计算速度快且分布均匀。
生成第i个哈希值的公式为：
hash_i = base_hash + i * (base_hash >> 17) + i * i
这个公式可以保证生成的多个哈希值分布相对独立，同时计算成本很低。
创建BloomFilter的实现
创建BloomFilter时，需要先把所有key的对应哈希位设置为1。下面是Leveldb中创建BloomFilter的核心代码：
#include <vector>
#include <string>
#include "util/hash.h"
// 假设bits_per_key是用户配置的每key占用bit数，k是key列表
std::string CreateBloomFilter(const std::vector<std::string>& keys, int bits_per_key) {
// 计算需要的哈希函数个数，公式为k = bits_per_key * ln2，Leveldb中近似为 bits_per_key * 0.69，取整后最少为1
int k = static_cast<int>(bits_per_key * 0.69);
if (k < 1) k = 1;
if (k > 30) k = 30; // 限制最多30个哈希函数
// 计算总位数和字节长度
int bits = keys.size() * bits_per_key;
if (bits < 64) bits = 64; // 最少64位
int bytes = (bits + 7) / 8;
bits = bytes * 8;
std::string filter(bytes, 0); // 初始化全0的位图
// 遍历所有key，设置对应的哈希位
for (const auto& key : keys) {
// 计算基础哈希值
uint32_t h = leveldb::Hash(key.data(), key.size(), 0xbc9f1d34);
// 生成k个哈希值，对应设置位图的bit
for (int i = 0; i < k; i++) {
uint32_t bit_pos = (h + i * (h >> 17) + i * i) % bits;
filter[bit_pos / 8] |= (1 << (bit_pos % 8));
}
}
// 在filter末尾追加哈希函数个数，方便后续读取时解析
filter.push_back(static_cast<char>(k));
return filter;
}
判断key是否存在的实现
判断key是否存在时，需要先解析BloomFilter末尾存储的哈希函数个数k，然后对key进行同样k次哈希计算，检查所有对应位是否都为1。下面是判断逻辑的核心代码：
#include <string>
#include "util/hash.h"
bool KeyMayMatch(const std::string& key, const std::string& filter) {
int len = filter.size();
if (len < 2) return false; // 最少1字节位图+1字节k值
int k = static_cast<int>(filter[len - 1]); // 取出哈希函数个数
if (k > 30 || k < 1) return true; // 无效的k值默认认为可能存在
int bits = (len - 1) * 8; // 位图的总位数，减去末尾存储k的1字节
uint32_t h = leveldb::Hash(key.data(), key.size(), 0xbc9f1d34);
for (int i = 0; i < k; i++) {
uint32_t bit_pos = (h + i * (h >> 17) + i * i) % bits;
if ((filter[bit_pos / 8] & (1 << (bit_pos % 8))) == 0) {
return false; // 存在任意一位为0，直接判定不存在
}
}
return true; // 所有位都为1，认为可能存在
}
参数配置与误判率
Leveldb的BloomFilter误判率和bits_per_key参数直接相关，bits_per_key越大，误判率越低，但是占用的内存也会越多。根据BloomFilter的理论公式，当哈希函数个数k = bits_per_key * ln2时，误判率最低，Leveldb的参数计算也遵循这个规律。
下面是不同bits_per_key对应的近似误判率：
| bits_per_key | 近似误判率 |
|---|---|
| 5 | 约20% |
| 10 | 约5% |
| 15 | 约1% |
| 20 | 约0.3% |
用户在使用Leveldb时，可以通过Options::filter_policy参数配置BloomFilter，例如设置每key占用10个bit：
#include "leveldb/options.h" #include "util/bloom.h" leveldb::Options options; options.filter_policy = leveldb::NewBloomFilterPolicy(10); // 每key10bit // 打开数据库时使用该options即可
实现注意事项
- BloomFilter只能判断key不存在的情况一定准确，判断存在的情况可能存在误判，不能用于精确匹配。
- Leveldb的BloomFilter是针对每个SSTable单独创建的，SSTable合并时对应的BloomFilter也会被重新生成。
- 哈希函数的个数被限制在1到30之间，避免过多的哈希计算带来性能开销。
- 位图的总位数最少为64位，即使key数量很少也会保证基础的大小，避免误判率过高。
整体来看，Leveldb的BloomFilter实现非常轻量，在保证过滤效果的同时尽可能降低了计算和存储开销，是KV存储中优化读取性能的经典设计。理解这部分源码也有助于我们在其他场景中合理设计和使用BloomFilter数据结构。
LeveldbBloomFilter源码分析哈希函数修改时间：2026-06-18 12:55:02