外观
26 - 海量数据如何近似判断存在:Bloom Filter 原理与误判边界
前置阅读:04 - Hash 表原理与工程应用。
缓存穿透中的完整故障形态与治理见分布式 18 - 缓存穿透、击穿与雪崩。
摘要
请求携带一个订单编号,怎样在查数据库之前排除不存在的编号?保存完整编号集合可以精确判断,但面对几十亿个 Key(待判断的键,例如订单编号)时,存储成本可能过高。
Bloom Filter(布隆过滤器)只保存一组位,不保存完整的 Key。它能判断“没有加入过”或“可能加入过”:后者仍需查询精确存储确认。本文先解释这个基本模型,再说明误判率、参数计算,以及它在缓存穿透治理中的更新边界。
1. 核心结构
位数组(Bit Array)是一组初始值为 0 的二进制位,每位只能取 0 或 1。哈希函数(Hash Function)把 Key 映射到数组中的位置;同一个 Key 按相同规则计算,会得到相同的位置。
插入时,用 k 个哈希函数计算 k 个位置,把这些位设为 1。查询时,按相同规则计算位置并检查:
- 任一位为 0:一定没有加入过这个过滤器;
- 全部为 1:可能存在。
图表将在阅读到此处时加载…
为什么两种结果不对称?如果一个 Key 加入过,它对应的位就都应为 1;发现一个 0,便可以排除它。但位数组不记录每个 1 属于哪个 Key,不同 Key 可以共享位置。因此,即使查询的 Key 没有加入过,它对应的位也可能已被其他 Key 全部设为 1。
这种把未加入的 Key 判断为“可能存在”的结果叫假阳性(False Positive)。相反,把已加入的 Key 判断为不存在叫假阴性(False Negative)。标准 Bloom Filter 在正确实现、查询与插入规则一致且没有删除位的前提下,不应产生假阴性。这里的“没有加入过”只有在过滤器完整覆盖业务数据时,才能用于判断“数据库里不存在”。
2. 简化实现
下面是 Java 教学片段,没有运行入口。BitSet 用于保存位状态;add 设置位置,mightContain 检查位置,index 将哈希值映射到 0 至 size - 1。调用方需提供正整数 size 和非 null 的字符串。
java
class SimpleBloomFilter {
private final java.util.BitSet bits;
private final int size;
SimpleBloomFilter(int size) {
this.size = size;
this.bits = new java.util.BitSet(size);
}
void add(String value) {
for (int seed : new int[] { 17, 31, 47 }) {
bits.set(index(value, seed));
}
}
boolean mightContain(String value) {
for (int seed : new int[] { 17, 31, 47 }) {
if (!bits.get(index(value, seed))) return false;
}
return true;
}
private int index(String value, int seed) {
int hash = value.hashCode() * seed;
return Math.floorMod(hash, size);
}
}三个 seed(种子值)参与计算,生成三组位置;它们都基于同一个 hashCode(),不能据此认为三组结果相互独立。这是说明插入与查询流程的最小实现,不适合直接生产使用:哈希独立性、并发、序列化、容量和误判率都未充分处理。
3. 参数关系
这里的误判率是假阳性率:在确认没有加入过的查询样本中,被返回“可能存在”的比例。它由位数组大小 m、预计元素数 n 和哈希数量 k 共同决定。
容量固定时,持续加入数据会让越来越多的位变为 1,未加入的 Key 更容易碰到一组全为 1 的位置,误判率随之上升。增加 k 会让查询检查更多位置,却也让每次插入设置更多位,因此不能靠无限增加哈希数量来降低误判率。
生产选型必须先给出预计元素量和可接受误判率,再计算参数,并监控实际填充率,即数组中已设为 1 的位所占比例。
理论公式通常假设哈希分布接近均匀且各位置选择近似独立。后面的示例使用双重散列:用两个哈希值组合生成一组位置,而不是分别计算多套完整哈希。若哈希质量差,或双重散列周期与位数组大小不匹配,使生成的位置序列过早重复,实测误判率可能偏离理论值。因此参数计算只是起点,必须用接近生产 Key 分布、且确认未加入的样本测量。
4. 缓存穿透中的位置
缓存穿透是指请求查询不存在的数据,缓存又无法拦截这些请求,导致它们继续访问数据库。过滤器可以放在查询链路前面,先排除确定不存在的 Key;前提是业务数据已完整加入过滤器,且更新过程不会遗漏。
text
请求 -> Bloom Filter
一定不存在 -> 快速拒绝
可能存在 -> 查缓存/数据库做精确确认假阳性请求仍会进入缓存或数据库查询,所以过滤器不能消除所有无效查询。“可能存在”也不能直接返回业务成功,必须由精确存储确认。
5. 完整可运行示例:可配置 Bloom Filter
下面是完整 Java 示例,入口类为 BloomFilterDemo,仅依赖 JDK 标准库。构造参数分别是预计元素数与目标假阳性率;示例按 expected > 0、0 < falsePositiveRate < 1 的正常有限数值使用。
java
import java.nio.charset.StandardCharsets;
import java.util.BitSet;
/**
* 可运行示例:海量数据如何近似判断存在:Bloom Filter 原理与误判边界。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class BloomFilterDemo {
static class BloomFilter {
final BitSet bits;
final int bitSize, hashCount;
BloomFilter(long expected, double falsePositiveRate) {
if (
expected <= 0 || falsePositiveRate <= 0 || falsePositiveRate >= 1
) throw new IllegalArgumentException();
// 理论最优位数:m = -n ln(p) / (ln 2)^2。
double m =
(-expected * Math.log(falsePositiveRate)) / (Math.log(2) * Math.log(2));
// BitSet 与数组下标使用 int;超出范围时应分片或改用生产级实现。
if (m > Integer.MAX_VALUE) throw new IllegalArgumentException(
"bit array is too large for this demo"
);
bitSize = Math.max(1, (int) Math.ceil(m));
// 理论最优 Hash 数:k = (m/n) ln 2,取最接近的正整数。
hashCount = Math.max(
1,
(int) Math.round(((double) bitSize / expected) * Math.log(2))
);
bits = new BitSet(bitSize);
}
void add(String value) {
if (value == null) throw new IllegalArgumentException("null key");
long[] h = hashes(value);
// 双重散列生成多个位置,避免重复计算多套完整 Hash。
for (int i = 0; i < hashCount; i++) {
// 第 i 个位置由 h1 + i*h2 得到;不同 i 形成一组位置序列。
bits.set(index(h[0] + i * h[1]));
}
}
boolean mightContain(String value) {
if (value == null) throw new IllegalArgumentException("null key");
long[] h = hashes(value);
for (int i = 0; i < hashCount; i++) {
// 任意一个目标位为 0,就能证明该 Key 从未按同一规则加入。
if (!bits.get(index(h[0] + i * h[1]))) return false;
}
// 所有位均为 1 仍可能来自其他 Key 的叠加,因此只能返回“可能存在”。
return true;
}
int index(long hash) {
return (int) Math.floorMod(hash, bitSize);
}
long[] hashes(String value) {
// 明确 UTF-8,保证同一字符串在不同默认字符集环境中得到相同字节。
byte[] b = value.getBytes(StandardCharsets.UTF_8);
long h1 = 0xcbf29ce484222325L;
long h2 = 0x9e3779b97f4a7c15L;
for (byte x : b) {
// 第一组状态采用 FNV-1a 风格混合每个无符号字节。
h1 = (h1 ^ (x & 255)) * 0x100000001b3L;
// 第二组状态继续混合 h1,得到双重散列需要的第二个步长。
h2 ^= h1 + (h2 << 6) + (h2 >>> 2);
}
// 把 h2 最低位置 1,避免步长为 0,并减少只访问偶数槽位的情况。
return new long[] { h1, h2 | 1 };
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
BloomFilter f = new BloomFilter(10_000, 0.01);
f.add("order-100");
System.out.println(f.mightContain("order-100"));
System.out.println(f.mightContain("order-999"));
}
}阅读时先看构造器如何计算位数与哈希数量,再对照 add 和 mightContain 使用的同一组位置。hashes 提供两个哈希状态,index 把组合结果映射为数组下标。这个自定义混合方法用于教学,不代表已经验证哈希质量;生产应使用经过验证的库,并验证并发和持久化。
main 只加入 order-100。在单线程、状态不变的条件下,第一行预期为 true;第二行查询未加入的 order-999,仍需看具体位置是否发生碰撞,不能仅凭“没有加入”保证输出 false。这两次查询也不能测量目标误判率。
5.1 参数手算与误判直觉
预计放入 n=10,000 个元素,目标误判率 p=1%。沿用前述均匀、近似独立的哈希假设,公式中的 ln 表示自然对数:
- 位数约为
m = -n ln(p)/(ln2²) ≈ 95,851 bit,约 11.7 KiB; - Hash 数约为
k = (m/n)ln2 ≈ 6.64,取 7; - 当查询一个从未加入的 Key 时,它对应的 7 个位置恰好都已被其他元素置 1,才会发生假阳性。
其中 11.7 KiB 只表示位数组的理论数据量,不包含 Java 对象等额外开销。如果实际写入 50,000 个元素却仍使用这组参数,位数组会快速趋近全 1,原先的 1% 目标不再成立。目标误判率依赖容量与哈希假设,不能作为长期不变的服务质量保证(SLA)。这些数字是参数推算,不是性能或误判率实测记录。
5.2 正确性边界
第 1 节的无假阴性结论针对同一过滤器、同一编码和哈希规则,以及正确完成的插入。业务查询还依赖数据同步:数据库已有某个 Key,但当前过滤器没有它,仍可能拒绝有效请求。这属于业务假阴性,常见原因包括实例间数据不同步、过滤器重建遗漏、哈希或编码规则变更,以及数据库先提交而过滤器更新失败。
5.3 复杂度与测试
- 将哈希计算视为固定成本时,单次添加和查询时间都是
O(k),位数组空间是O(m)bit。完整示例还要遍历字符串的 UTF-8 字节,分析长 Key 的成本时也应计入这部分工作。 - 示例
BitSet不是并发更新协议;多线程或多进程共享时应采用库提供的并发/分布式实现。 - 容量增长可采用 Scalable Bloom Filter(可扩展布隆过滤器),或分代过滤器,即按批次维护多个过滤器;也可离线重建更大的过滤器后原子切换,让查询整体转向新版本。
- 建议测试:已加入元素绝不返回 false、未加入样本的实测误判率、容量超限、空串、中文、并发更新、重启后的序列化兼容性。
6. 更新顺序与可用性策略
Bloom Filter 放在数据库之前时,更新顺序会直接影响业务结果:
- 数据先写数据库、过滤器稍后更新:短窗口内可能把新数据误判为不存在;
- 先写过滤器、数据库写入失败:只会增加假阳性,但会产生无效回源;
- 重建期间直接替换:可能因漏数或版本不一致产生业务假阴性;
- 多实例独立维护:相同 Key 在不同实例上的判断可能不同。
常见做法是构建完整新版本、校验元素量和抽样结果后原子切换,并保留回滚窗口。构建期间新增的数据也要纳入更新协议,否则切换操作即使是原子的,新版本仍可能漏数。是否允许短暂业务假阴性必须由业务明确;当过滤器尚未加载完整或更新失败时,还需明确是否绕过过滤器,交由精确存储查询,以及下游能否承受增加的查询量。
7. 删除为什么困难
一个位可能由多个 Key 共同设置,直接清零会破坏其他 Key 的插入记录,使它们产生假阴性。标准过滤器保留已删除业务数据的位,则只是继续把某些请求放到精确存储确认。
Counting Bloom Filter(计数布隆过滤器)把每个位替换为计数器,插入时增加对应计数,删除时减少计数,从而支持删除。它占用更多空间,并需处理计数溢出与并发;删除操作也必须与实际插入记录匹配,不能仅凭“可能存在”就扣减计数。
8. 排障证据
- 当前设计容量、累计插入量、位数组填充率和 Hash 数;
- 对已知存在 Key 的抽样查询,检查是否出现工程假阴性;
- 对确认不存在 Key 的抽样查询,估算实际假阳性率;
- 各实例过滤器版本、Hash/编码协议和加载完成时间;
- 过滤器拦截量、缓存查询量、数据库回源量及其时间关系。
误判率突然升高时,应先检查容量超限和 Key 分布变化;出现假阴性时,应优先检查数据同步、重建、版本和并发更新,而不是修改理论公式。
9. 容易踩的坑
上线前可用下面五个问题检查设计:
- “可能存在”之后,是否仍由精确存储确认?
- 实际元素数超出设计容量时,如何扩容或重建?
- 数据库新增成功而过滤器更新失败时,如何避免拒绝有效请求?
- 删除业务数据时,是否误用了标准 Bloom Filter 的清位操作?
- 多实例是否使用一致的过滤器版本、编码与更新机制?
10. 总结
Bloom Filter 用可计算的假阳性换取高空间效率,适合“先排除一定不存在”的场景。
- 查询为
false可以排除已加入当前过滤器的 Key;要据此拒绝业务请求,还必须保证过滤器完整覆盖业务数据。true仍需精确存储验证。 - 容量、元素量和 Hash 数共同决定误判率。
- 更新一致性、扩容和重建比位数组实现本身更重要。
缓存应用继续阅读缓存穿透、击穿与雪崩。流量保护主线见限流算法实战。