当前位置：首页 > news >正文

从零手写Java版本的LSM Tree （五）：布隆过滤器

news 2025/6/10 6:44:25

🔥 推荐一个高质量的Java LSM Tree开源项目！
https://github.com/brianxiadong/java-lsm-tree
java-lsm-tree 是一个从零实现的Log-Structured Merge Tree，专为高并发写入场景设计。
核心亮点：
⚡ 极致性能：写入速度超过40万ops/秒，完爆传统B+树
🏗️ 完整架构：MemTable跳表 + SSTable + WAL + 布隆过滤器 + 多级压缩
📚 深度教程：12章详细教程，从基础概念到生产优化，每行代码都有注释
🔒 并发安全：读写锁机制，支持高并发场景
💾 数据可靠：WAL写前日志确保崩溃恢复，零数据丢失
适合谁？

想深入理解LSM Tree原理的开发者
需要高写入性能存储引擎的项目
准备数据库/存储系统面试的同学
对分布式存储感兴趣的工程师
⭐ 给个Star支持开源！

第5章：布隆过滤器

什么是布隆过滤器？

布隆过滤器 (Bloom Filter) 是一种概率型数据结构，用于快速判断一个元素是否可能存在于集合中。它具有以下特性：

无假阴性: 如果布隆过滤器说元素不存在，那么元素一定不存在
有假阳性: 如果布隆过滤器说元素存在，元素可能不存在
空间高效: 相比哈希表，内存占用极小
时间高效: 查询和插入都是O(k)，k是哈希函数数量

布隆过滤器在LSM Tree中的作用

在LSM Tree中，布隆过滤器被广泛应用于SSTable文件中：

查询流程:
1. 检查MemTable (可能存在)
2. 检查Immutable MemTable (可能存在)  
3. 对每个SSTable:a. 检查布隆过滤器 (可能存在？)b. 如果可能存在，读取文件查找c. 如果不存在，直接跳过 (避免磁盘I/O)

Immutable MemTable指的是数据已满，准备写到磁盘中的MemTable

性能提升: 布隆过滤器可以减少90%以上的无效磁盘I/O操作！

核心原理

工作机制图解

步骤1: 初始状态

位置	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
位值	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

步骤2: 添加 “apple”

hash1(“apple”) = 3, hash2(“apple”) = 7, hash3(“apple”) = 12

位置	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
位值	0	0	0	1	0	0	0	1	0	0	0	0	1	0	0	0

步骤3: 添加 “banana”

hash1(“banana”) = 1, hash2(“banana”) = 9, hash3(“banana”) = 15

位置	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
位值	0	1	0	1	0	0	0	1	0	1	0	0	1	0	0	1

步骤4: 查询测试

元素	hash位置	位值检查	结果	说明
“apple”	3,7,12	1,1,1	✅ 可能存在	确实存在
“cherry”	2,6,10	0,0,0	❌ 确定不存在	位置2为0
“grape”	1,7,9	1,1,1	⚠️ 可能存在	假阳性!

核心洞察:

插入: 多个哈希函数将元素映射到不同位置，全部设为1
查询: 检查所有对应位置，任一为0则确定不存在
假阳性: 不同元素可能hash到相同位置，导致误判
无假阴性: 如果元素真实存在，对应位置必然为1

布隆过滤器实现

核心实现

package com.brianxiadong.lsmtree;import java.util.BitSet;/*** 布隆过滤器实现* 用于快速判断键是否可能存在于SSTable中*/
public class BloomFilter {private final BitSet bitSet;               // 位数组，存储布隆过滤器的位private final int size;                    // 位数组的大小private final int hashFunctions;           // 哈希函数的数量// 构造函数：根据预期元素数和假阳性概率初始化public BloomFilter(int expectedElements, double falsePositiveProbability) {// 计算最优位数组大小：m = -n * ln(p) / (ln(2))^2this.size = (int) (-expectedElements * Math.log(falsePositiveProbability)/ (Math.log(2) * Math.log(2)));// 计算最优哈希函数个数：k = (m/n) * ln(2)this.hashFunctions = (int) (size * Math.log(2) / expectedElements);this.bitSet = new BitSet(size);        // 创建位数组}/*** 向布隆过滤器添加元素*/public void add(String key) {for (int i = 0; i < hashFunctions; i++) {      // 使用k个哈希函数int hash = hash(key, i);                   // 计算第i个哈希值bitSet.set(Math.abs(hash % size));         // 设置对应位为1}}/*** 检查元素是否可能存在* 返回false表示绝对不存在* 返回true表示可能存在*/public boolean mightContain(String key) {for (int i = 0; i < hashFunctions; i++) {      // 检查k个哈希位置int hash = hash(key, i);                   // 计算第i个哈希值if (!bitSet.get(Math.abs(hash % size))) {  // 如果任一位为0return false;                          // 确定不存在}}return true;                                   // 所有位都为1，可能存在}/*** 多重哈希函数实现* 使用Double Hashing技术避免实现多个独立的哈希函数*/private int hash(String key, int i) {int hash1 = key.hashCode();                    // 第一个哈希值int hash2 = hash1 >>> 16;                      // 第二个哈希值（高16位）return hash1 + i * hash2;                      // 组合生成第i个哈希值}/*** 获取位数组序列化数据（用于持久化）*/public byte[] toByteArray() {return bitSet.toByteArray();                   // 将BitSet转换为字节数组}/*** 从字节数组恢复布隆过滤器*/public static BloomFilter fromByteArray(byte[] data, int size, int hashFunctions) {BloomFilter filter = new BloomFilter(1000, 0.01); // 临时创建参数filter.bitSet.clear();                         // 清空当前位数组BitSet restored = BitSet.valueOf(data);        // 从字节数组恢复BitSetfilter.bitSet.or(restored);                    // 合并到当前位数组return filter;}
}

代码解析：这个布隆过滤器实现采用了经典的设计模式。构造函数根据数学公式计算最优的位数组大小和哈希函数数量，确保在给定的假阳性率下达到最佳性能。双重哈希技术避免了实现多个独立哈希函数的复杂性，通过组合两个基础哈希值生成所需数量的哈希值。toByteArray和fromByteArray方法支持布隆过滤器的持久化，这在SSTable文件中存储布隆过滤器时非常有用。