返回文章列表

用 Rust 从零实现布隆过滤器:误判率不是玄学,是能算出来的

322 字·3 分钟阅读
Rust从零造轮子数据结构

缓存穿透是后台最常见的线上问题之一。有人用空值缓存,有人用布隆过滤器。

布隆过滤器的特点很反直觉:它只会误判"存在",永远不会误判"不存在"。也就是说:

  • contains(x) == false → x 一定不在集合里
  • contains(x) == true → x 可能在集合里

这个"单向确定性"就是它的全部价值。用在缓存前面,所有明确不存在的 key 根本不会打到数据库。

这篇从零实现它,重点是搞懂为什么要用 k 个哈希函数,以及误判率到底怎么算。


最朴素的版本:一个哈希不够

布隆过滤器的底层就是一个 bit 数组。

pub struct BloomFilter {
    bits: Vec<u64>,
    num_bits: usize,
    num_hashes: usize,
}

如果只用一个哈希函数,插入元素时把 hash(x) % m 位置 1:

fn insert_naive(&mut self, item: &[u8]) {
    let idx = hash(item) % self.num_bits;
    self.set_bit(idx);
}

查找就是看那个 bit 是不是 1。问题很明显:两个不同元素哈希到同一位,就会互相污染。 元素一多,bit 数组里 1 的比例迅速上升,误判率飙升。

解决办法是每个元素设 k 个位,查找时 k 个位全为 1 才认为存在。

    fn set_bit(&mut self, idx: usize) {
        self.bits[idx / 64] |= 1u64 << (idx % 64);
    }
 
    fn get_bit(&self, idx: usize) -> bool {
        (self.bits[idx / 64] >> (idx % 64)) & 1 == 1
    }

用 u64 装 bit,是性能上的基本盘——比 Vec<bool> 省 64 倍空间,位运算也比逐字节访问快。

用一个哈希生成 k 个位置

如果老老实实调用 k 个哈希函数,每个元素插入就要算 k 次哈希,开销不小。

工业实现的通用技巧是双重哈希(double hashing):用两个哈希值组合出任意多个位置。

fn hash_pair(item: &[u8]) -> (u64, u64) {
    let h1 = fnv1a(item, 0xcbf29ce484222325);
    let h2 = fnv1a(item, 0x100000001b3);
    (h1, h2)
}
 
fn index_at(h1: u64, h2: u64, i: usize, m: usize) -> usize {
    // 组合公式:h1 + i * h2
    (h1.wrapping_add((i as u64).wrapping_mul(h2)) % m as u64) as usize
}

这样只需要算两次哈希,剩下的 k 个位置用乘加就能推出来。

fn fnv1a(data: &[u8], seed: u64) -> u64 {
    let mut hash = seed;
    for &b in data {
        hash ^= b as u64;
        hash = hash.wrapping_mul(0x100000001b3);
    }
    hash
}

布隆过滤器的哈希函数不需要密码学强度,但必须分布均匀。 它只要能打散数据,不需要防碰撞攻击。

插入和查询

    pub fn insert(&mut self, item: &[u8]) {
        let (h1, h2) = hash_pair(item);
        for i in 0..self.num_hashes {
            let idx = index_at(h1, h2, i, self.num_bits);
            self.set_bit(idx);
        }
    }
 
    pub fn contains(&self, item: &[u8]) -> bool {
        let (h1, h2) = hash_pair(item);
        for i in 0..self.num_hashes {
            let idx = index_at(h1, h2, i, self.num_bits);
            if !self.get_bit(idx) {
                return false; // 只要有一位是 0,就一定不存在
            }
        }
        true // 所有位都是 1,可能存在
    }

注意 contains 里的短路:只要碰到一个 0 就立刻返回 false。 这就是"不存在的判定是确定的"的原因——位是插入时真真切切置上的,不可能凭空变 1。

误判率怎么算

这是这篇文章最想讲清楚的部分。设:

  • m:bit 数组长度
  • n:插入的元素个数
  • k:每个元素的哈希个数

插入一个元素会置 k 个位。某一个 bit 在插入一次后仍为 0 的概率是:

1 - 1/m

插入 n 个元素、每个 k 位之后,这个 bit 仍为 0 的概率:

(1 - 1/m)^(kn) ≈ e^(-kn/m)

所以它是 1 的概率是 1 - e^(-kn/m)。误判发生在"某个不存在的元素,k 个位置恰好全被置 1":

P ≈ (1 - e^(-kn/m))^k

这个公式有几个直接推论:

  1. n 越大(插入越多),误判率越高,不可逆
  2. m 越大(数组越长),误判率越低
  3. k 不是越大越好——k 太大,bit 数组很快被填满,反而更容易全 1

最优的 k 在 k = (m/n) * ln2 时取到。也就是说,每个元素分配约 m/n = 1.44 * log2(1/P) 个 bit 时最省。

工程上常按这么选:

目标误判率 每元素 bit 数 (m/n) 哈希个数 k
1% 9.6 7
0.1% 14.4 10
0.01% 19.2 13

按这些参数创建过滤器:

    pub fn with_capacity(n: usize, fp_rate: f64) -> Self {
        use std::f64::consts::LN_2;
        let m = (-(n as f64) * fp_rate.ln() / (LN_2 * LN_2)).ceil() as usize;
        let k = ((m as f64 / n as f64) * LN_2).round() as usize;
 
        Self {
            bits: vec![0; m.div_ceil(64)],
            num_bits: m,
            num_hashes: k.max(1),
        }
    }

注意 m 和 k 是从容量和误判率反推出来的,不是拍脑袋定的。这就是"误判率不是玄学"的含义——你给它一个目标,它能算出该开多大。

估算当前误判率

因为 n 是运行期变化的(比如缓存持续加载新 key),实现里通常记录已插入数量,实时估算当前误判率:

    pub fn estimated_fp_rate(&self, inserted: usize) -> f64 {
        let bits_set = self.bits.iter().map(|w| w.count_ones() as usize).sum::<usize>();
        let frac = bits_set as f64 / self.num_bits as f64;
        frac.powf(self.num_hashes as f64)
    }

这里用实际置 1 的位数来估算,比用理论公式更准,因为它把哈希分布不均也考虑进去了。

这个值很适合打成一个指标(比如 Grafana 面板),一旦逼近阈值就告警。

三个必须知道的限制

写业务的时候,布隆过滤器的坑集中在下面三点:

1. 不能删除元素。 你无法知道某一位是哪个元素置的。删掉 A,可能把 B 的位也清了,导致 B 被误判为不存在——而"不存在"本该是确定的。想支持删除要用变体的计数布隆过滤器(Counting Bloom Filter),每个位置改成计数器,空间翻好几倍。

2. 元素多了误判率会涨。 误判率对 n 是指数敏感的。超过设计容量后,最好重新建一个更大的过滤器(历史上叫"可扩展布隆过滤器")。

3. 不能枚举元素。 它只回答"在不在",不保存内容。需要枚举就用别的结构。

结论

布隆过滤器只有十几行核心逻辑,但它的价值在于用可量化的代价换掉确定性的代价:

查询确定不存在 → 立刻返回;查询可能存在 → 走正常流程。误判率由 m、n、k 三个参数算出,最优 k = (m/n)·ln2。

在 Rust 里它也很适合做成一个共享只读的结构——初始化完成后放进 Arc,读路径无锁,写路径按批重建。这种"读多写少、宁可不精确也不能漏"的场景,它几乎是最优解。