Bloom Filter 全家族：Standard → Counting → Cuckoo → Ribbon

你在 LevelDB 里查一个 key，SST 文件可能有几千个。逐个打开、二分搜索？磁盘 I/O 会把你杀死。

实际的做法是：每个 SST 文件附带一个几 KB 的位数组。查询时先问它：“这个 key 可能在你这里吗？” 如果它说”不在”，那就一定不在，跳过这个文件。如果它说”可能在”，再去做真正的磁盘读取。

这个位数组就是 Bloom Filter。

1970 年，Burton Howard Bloom 在 Communications of the ACM 上发表了一页半的短文 Space/Time Trade-offs in Hash Coding with Allowable Errors。这篇论文的核心思想极其简单：如果你愿意容忍一定的误判率，就可以用远少于精确存储所需的空间来回答集合成员查询。

五十多年过去了，这个思想催生了一整个家族的数据结构：Counting Bloom Filter 解决了删除问题，Blocked Bloom Filter 解决了缓存友好性问题，Cuckoo Filter 在低误判率下实现了更好的空间效率，而 2021 年 Meta 的 Ribbon Filter 几乎逼近了信息论下界。

这篇文章从数学推导开始，走完整个家族。

一、问题定义：近似集合成员查询

精确 vs 近似

给定一个集合 \(S = \{x_1, x_2, \ldots, x_n\}\)，我们需要回答查询：“\(q \in S\)？”

精确方案（哈希表、平衡树）至少需要 \(n \cdot |x|\) 位存储，其中 \(|x|\) 是元素的位宽。对于 64 位整数和 100 万个元素，这至少是 8 MB。

近似方案放宽要求：允许 false positive（把不属于 \(S\) 的元素误判为属于），但绝不允许 false negative（属于 \(S\) 的元素绝不会漏掉）。

这个放宽带来了巨大的空间节省。

形式化

一个 Approximate Membership Query（AMQ）数据结构满足：

• 对于 \(x \in S\)：查询必须返回 true（no false negatives）
• 对于 \(x \notin S\)：查询返回 true 的概率 \(\leq \epsilon\)（false positive rate）

这里 \(\epsilon\) 是可调参数。\(\epsilon\) 越小，空间消耗越大。

信息论下界

任何满足上述条件的数据结构，每个元素至少需要多少位？

考虑 \(U\) 是全集，\(|U| = u\)。一个 AMQ 结构本质上是把全集 \(U\) 分成两部分：被判定为”在集合中”的元素集 \(A\)（\(|A| \geq n\)，因为真正的集合成员必须全部在 \(A\) 中），和被判定为”不在集合中”的元素。

false positive rate 为 \(\epsilon\) 意味着 \(|A| \leq n + \epsilon \cdot (u - n) \approx n + \epsilon u\)（当 \(u \gg n\) 时）。

但更精确的下界来自信息论：一个 AMQ 结构需要至少

\[m \geq n \log_2 \frac{1}{\epsilon}\]

位（忽略低阶项）。这就是 information-theoretic lower bound。

直觉理解：对每个元素，我们需要 \(\log_2(1/\epsilon)\) 位来”编码”它的指纹，使得误判率不超过 \(\epsilon\)。

对于 \(\epsilon = 1\%\)，下界约为 \(n \cdot 6.64\) 位/元素。这意味着理论上，用不到 1 字节/元素的空间就能实现 1% 的误判率。

二、Standard Bloom Filter：数学与直觉

结构

一个 Bloom Filter 由两部分组成：

1. 一个 \(m\) 位的位数组 \(B[0 \ldots m-1]\)，初始全为 0
2. \(k\) 个独立的哈希函数 \(h_1, h_2, \ldots, h_k\)，每个映射到 \(\{0, 1, \ldots, m-1\}\)

插入

插入元素 \(x\)：对每个 \(i \in \{1, \ldots, k\}\)，设置 \(B[h_i(x)] = 1\)。

查询

查询元素 \(q\)：对每个 \(i \in \{1, \ldots, k\}\)，检查 \(B[h_i(q)]\)。如果所有位都为 1，返回”可能在集合中”；如果任何一位为 0，返回”一定不在集合中”。

False Positive 概率推导

插入 \(n\) 个元素后，某个特定位仍为 0 的概率：

每次哈希设置一位，不命中特定位的概率为 \((1 - 1/m)\)。总共 \(kn\) 次哈希操作，所以：

\[P(\text{某位为 0}) = \left(1 - \frac{1}{m}\right)^{kn}\]

利用 \((1 - 1/m)^m \to e^{-1}\)：

\[P(\text{某位为 0}) \approx e^{-kn/m}\]

设 \(p = e^{-kn/m}\)，则某位为 1 的概率为 \(1 - p\)。

对于一个不在集合中的元素 \(q\)，它的 \(k\) 个哈希位全部为 1 的概率（即 false positive 概率）：

\[\epsilon = (1 - p)^k = \left(1 - e^{-kn/m}\right)^k\]

这就是 Bloom Filter 的 false positive rate 公式。

最优哈希数 \(k\)

我们要最小化 \(\epsilon = (1 - e^{-kn/m})^k\)。

取对数：\(\ln \epsilon = k \ln(1 - e^{-kn/m})\)。

设 \(t = kn/m\)（每位的平均”负载”），则 \(k = tm/n\)，而：

\[\ln \epsilon = \frac{tm}{n} \ln(1 - e^{-t})\]

对 \(t\) 求导并令其为零（这个推导的技巧是注意 \(\epsilon\) 在 \(p = 1/2\) 时最小，即位数组中 0 和 1 各占一半）。

结论：最优 \(k\) 满足 \(e^{-kn/m} = 1/2\)，即：

\[k^* = \frac{m}{n} \ln 2 \approx 0.693 \cdot \frac{m}{n}\]

此时 false positive rate 为：

\[\epsilon^* = \left(\frac{1}{2}\right)^k = 2^{-k} = 2^{-(m/n)\ln 2}\]

等价地：

\[\frac{m}{n} = -\frac{\ln \epsilon}{(\ln 2)^2} \approx 1.44 \log_2 \frac{1}{\epsilon}\]

与信息论下界的比较

信息论下界是 \(\log_2(1/\epsilon)\) 位/元素，而 Standard Bloom Filter 需要 \(1.44 \log_2(1/\epsilon)\) 位/元素。

Standard Bloom Filter 比理论最优多用了 44% 的空间。

这 44% 的”浪费”来自位数组中必然有约一半的位是 0（不携带信息）。

双重哈希技巧

实际实现中不需要 \(k\) 个独立哈希函数。Kirsch 和 Mitzenmacher（2006）证明了，只需要两个哈希函数 \(h_1(x)\) 和 \(h_2(x)\)，然后构造：

\[g_i(x) = h_1(x) + i \cdot h_2(x) \mod m, \quad i = 0, 1, \ldots, k-1\]

这不会增加渐近 false positive rate。

三、C 语言完整实现

下面是一个完整的、可直接编译运行的 Standard Bloom Filter 实现，包含最优 \(k\) 的自动计算。

#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * bloom_filter.c
 * Standard Bloom Filter with optimal k calculation.
 * Uses double hashing (Kirsch-Mitzenmacher technique).
 */

typedef struct {
    uint8_t *bits;
    uint64_t m;       /* number of bits */
    uint32_t k;       /* number of hash functions */
    uint64_t n_added; /* elements inserted so far */
} bloom_t;

/* FNV-1a 64-bit hash */
static uint64_t fnv1a(const void *data, size_t len) {
    const uint8_t *p = (const uint8_t *)data;
    uint64_t h = 0xcbf29ce484222325ULL;
    for (size_t i = 0; i < len; i++) {
        h ^= p[i];
        h *= 0x100000001b3ULL;
    }
    return h;
}

/* murmur-style mix for second hash */
static uint64_t hash_mix(uint64_t h) {
    h ^= h >> 33;
    h *= 0xff51afd7ed558ccdULL;
    h ^= h >> 33;
    h *= 0xc4ceb9fe1a85ec53ULL;
    h ^= h >> 33;
    return h;
}

/* Calculate optimal parameters from expected insertions and desired FPR */
static void bloom_calc_params(uint64_t expected_n, double fpr,
                              uint64_t *out_m, uint32_t *out_k) {
    /* m = -n * ln(fpr) / (ln2)^2 */
    double ln2 = 0.693147180559945;
    double m_f = -(double)expected_n * log(fpr) / (ln2 * ln2);
    *out_m = (uint64_t)ceil(m_f);
    if (*out_m < 64) *out_m = 64; /* minimum size */

    /* k = (m/n) * ln2 */
    double k_f = ((double)*out_m / (double)expected_n) * ln2;
    *out_k = (uint32_t)round(k_f);
    if (*out_k < 1) *out_k = 1;
    if (*out_k > 30) *out_k = 30; /* sanity cap */
}

bloom_t *bloom_create(uint64_t expected_n, double fpr) {
    bloom_t *bf = (bloom_t *)calloc(1, sizeof(bloom_t));
    if (!bf) return NULL;

    bloom_calc_params(expected_n, fpr, &bf->m, &bf->k);

    size_t bytes = (bf->m + 7) / 8;
    bf->bits = (uint8_t *)calloc(bytes, 1);
    if (!bf->bits) {
        free(bf);
        return NULL;
    }
    bf->n_added = 0;
    return bf;
}

void bloom_destroy(bloom_t *bf) {
    if (bf) {
        free(bf->bits);
        free(bf);
    }
}

static void bloom_get_hashes(const bloom_t *bf,
                             const void *data, size_t len,
                             uint64_t *h1_out, uint64_t *h2_out) {
    uint64_t h = fnv1a(data, len);
    *h1_out = h;
    *h2_out = hash_mix(h);
}

void bloom_add(bloom_t *bf, const void *data, size_t len) {
    uint64_t h1, h2;
    bloom_get_hashes(bf, data, len, &h1, &h2);

    for (uint32_t i = 0; i < bf->k; i++) {
        uint64_t pos = (h1 + (uint64_t)i * h2) % bf->m;
        bf->bits[pos / 8] |= (1u << (pos % 8));
    }
    bf->n_added++;
}

int bloom_test(const bloom_t *bf, const void *data, size_t len) {
    uint64_t h1, h2;
    bloom_get_hashes(bf, data, len, &h1, &h2);

    for (uint32_t i = 0; i < bf->k; i++) {
        uint64_t pos = (h1 + (uint64_t)i * h2) % bf->m;
        if (!(bf->bits[pos / 8] & (1u << (pos % 8))))
            return 0; /* definitely not in set */
    }
    return 1; /* possibly in set */
}

double bloom_current_fpr(const bloom_t *bf) {
    /* Estimate: (1 - e^{-kn/m})^k */
    double exp_val = exp(-(double)bf->k * (double)bf->n_added / (double)bf->m);
    return pow(1.0 - exp_val, (double)bf->k);
}

void bloom_stats(const bloom_t *bf) {
    printf("Bloom Filter stats:\n");
    printf("  bits (m)       : %lu\n", (unsigned long)bf->m);
    printf("  hash funcs (k) : %u\n", bf->k);
    printf("  elements added : %lu\n", (unsigned long)bf->n_added);
    printf("  bits per key   : %.2f\n",
           bf->n_added > 0 ? (double)bf->m / bf->n_added : 0.0);
    printf("  estimated FPR  : %.6f%%\n", bloom_current_fpr(bf) * 100.0);
    printf("  memory (bytes) : %lu\n", (unsigned long)((bf->m + 7) / 8));
}

/* ----- demo / test ----- */

int main(void) {
    const uint64_t N = 100000;
    const double TARGET_FPR = 0.01; /* 1% */

    bloom_t *bf = bloom_create(N, TARGET_FPR);
    if (!bf) {
        fprintf(stderr, "failed to create bloom filter\n");
        return 1;
    }

    printf("=== Bloom Filter Demo ===\n");
    printf("Target: %lu elements, %.2f%% FPR\n\n",
           (unsigned long)N, TARGET_FPR * 100);

    /* insert elements "item:0" .. "item:99999" */
    char buf[64];
    for (uint64_t i = 0; i < N; i++) {
        int len = snprintf(buf, sizeof(buf), "item:%lu", (unsigned long)i);
        bloom_add(bf, buf, (size_t)len);
    }

    bloom_stats(bf);

    /* verify: no false negatives */
    uint64_t fn_count = 0;
    for (uint64_t i = 0; i < N; i++) {
        int len = snprintf(buf, sizeof(buf), "item:%lu", (unsigned long)i);
        if (!bloom_test(bf, buf, (size_t)len))
            fn_count++;
    }
    printf("\n  false negatives : %lu (must be 0)\n", (unsigned long)fn_count);

    /* measure actual FPR with non-member queries */
    const uint64_t TEST_N = 1000000;
    uint64_t fp_count = 0;
    for (uint64_t i = 0; i < TEST_N; i++) {
        int len = snprintf(buf, sizeof(buf), "probe:%lu", (unsigned long)i);
        if (bloom_test(bf, buf, (size_t)len))
            fp_count++;
    }
    printf("  actual FPR      : %.4f%% (%lu / %lu)\n",
           (double)fp_count / TEST_N * 100.0,
           (unsigned long)fp_count, (unsigned long)TEST_N);

    bloom_destroy(bf);
    return 0;
}

编译与运行：

gcc -O2 -lm -o bloom bloom_filter.c
./bloom

典型输出：

=== Bloom Filter Demo ===
Target: 100000 elements, 1.00% FPR

Bloom Filter stats:
  bits (m)       : 958506
  hash funcs (k) : 7
  elements added : 100000
  bits per key   : 9.59
  estimated FPR  : 0.816483%
  memory (bytes) : 119814

  false negatives : 0 (must be 0)
  actual FPR      : 0.9871% (9871 / 1000000)

几个值得注意的点：

• \(m/n = 9.59\)，与理论值 \(9.58\) 吻合
• \(k = 7\)，与理论最优 \(6.64 \cdot \ln 2 \approx 6.9\) 四舍五入一致
• 实测 FPR 接近目标 1%
• 10 万个元素只占约 117 KB，而存储原始字符串至少需要几 MB

四、Counting Bloom Filter：支持删除的代价

问题

Standard Bloom Filter 不支持删除。把某一位从 1 设回 0？不行，因为多个元素可能共享同一位。删除一个元素会导致其他元素的 false negative。

解决方案

Fan 等人在 2000 年提出了 Counting Bloom Filter（CBF）：把每一位替换为一个 \(c\) 位的计数器（通常 \(c = 4\)）。

• 插入：对 \(k\) 个位置的计数器加 1
• 删除：对 \(k\) 个位置的计数器减 1
• 查询：检查 \(k\) 个位置的计数器是否全部 \(> 0\)

溢出问题

4 位计数器最大值为 15。如果某个位置被超过 15 个元素哈希到，计数器溢出。

溢出的处理策略：

1. 饱和计数：到 15 就不再增加，也不在删除时减少。这保证了 no false negatives，但该位置永远无法回到 0。
2. 更大的计数器：用 8 位甚至 16 位，但空间开销更大。

空间代价

4 位/计数器意味着 CBF 的空间是 Standard Bloom Filter 的 4 倍。对于 \(\epsilon = 1\%\)，Standard Bloom 需要约 9.6 bits/key，而 CBF 需要约 38.4 bits/key。

这个代价太高了。很多场景下，如果需要支持删除，不如直接用 Cuckoo Filter。

typedef struct {
    uint8_t *counters; /* 每个字节存两个 4-bit 计数器 */
    uint64_t m;
    uint32_t k;
} counting_bloom_t;

/* 获取第 pos 个计数器的值 */
static uint8_t cbf_get(const counting_bloom_t *cbf, uint64_t pos) {
    uint8_t byte = cbf->counters[pos / 2];
    return (pos % 2 == 0) ? (byte & 0x0F) : (byte >> 4);
}

/* 设置第 pos 个计数器的值 */
static void cbf_set(counting_bloom_t *cbf, uint64_t pos, uint8_t val) {
    uint64_t idx = pos / 2;
    if (pos % 2 == 0)
        cbf->counters[idx] = (cbf->counters[idx] & 0xF0) | (val & 0x0F);
    else
        cbf->counters[idx] = (cbf->counters[idx] & 0x0F) | ((val & 0x0F) << 4);
}

void cbf_add(counting_bloom_t *cbf, uint64_t *positions) {
    for (uint32_t i = 0; i < cbf->k; i++) {
        uint8_t v = cbf_get(cbf, positions[i]);
        if (v < 15) /* saturating increment */
            cbf_set(cbf, positions[i], v + 1);
    }
}

int cbf_remove(counting_bloom_t *cbf, uint64_t *positions) {
    /* 先检查是否所有计数器 > 0 */
    for (uint32_t i = 0; i < cbf->k; i++) {
        if (cbf_get(cbf, positions[i]) == 0)
            return -1; /* element not in filter */
    }
    for (uint32_t i = 0; i < cbf->k; i++) {
        uint8_t v = cbf_get(cbf, positions[i]);
        if (v < 15) /* don't decrement saturated counters */
            cbf_set(cbf, positions[i], v - 1);
    }
    return 0;
}

五、Blocked Bloom Filter：缓存友好

问题

Standard Bloom Filter 的查询需要访问 \(k\) 个随机位置。当 \(m\) 很大时（几百 KB 到几 MB），这些位置散布在不同的 cache line 中，导致多次 cache miss。

对于 \(k = 10\)，一次查询可能触发 10 次 L1 cache miss。在吞吐量敏感的场景下（如数据库的每次磁盘查询前的 filter check），这是不可接受的。

解决方案

Putze, Sanders, Singler（2007）提出了 Blocked Bloom Filter：

1. 把位数组分成若干 block，每个 block 的大小等于一个 cache line（通常 64 字节 = 512 位）
2. 对于元素 \(x\)，先用一个哈希函数确定它属于哪个 block
3. 然后在该 block 内部用 \(k\) 个哈希设置/检查位

查询时只需要一次内存访问（加载整个 cache line），然后所有 \(k\) 次检查都在寄存器/L1 cache 中完成。

代价

block 化会略微增加 false positive rate，因为每个 block 内的元素数量不均匀（Poisson 分布），负载较高的 block 误判率更高。

实测中，对于 \(\epsilon = 1\%\)，Blocked Bloom Filter 需要比 Standard Bloom Filter 多约 10-20% 的空间来达到同样的误判率。

但查询速度提升显著：通常是 Standard Bloom Filter 的 2-5 倍。

#define BLOCK_BYTES 64  /* one cache line */
#define BLOCK_BITS  (BLOCK_BYTES * 8) /* 512 */

typedef struct {
    uint8_t *data;
    uint64_t n_blocks;
    uint32_t k;
} blocked_bloom_t;

void bb_add(blocked_bloom_t *bb, const void *key, size_t len) {
    uint64_t h1, h2;
    /* h1 selects block, h2 seeds intra-block hashes */
    bloom_get_hashes(NULL, key, len, &h1, &h2);

    uint64_t block_idx = h1 % bb->n_blocks;
    uint8_t *block = bb->data + block_idx * BLOCK_BYTES;

    for (uint32_t i = 0; i < bb->k; i++) {
        uint32_t bit = (uint32_t)((h2 + i * 0x9e3779b97f4a7c15ULL) % BLOCK_BITS);
        block[bit / 8] |= (1u << (bit % 8));
    }
}

int bb_test(const blocked_bloom_t *bb, const void *key, size_t len) {
    uint64_t h1, h2;
    bloom_get_hashes(NULL, key, len, &h1, &h2);

    uint64_t block_idx = h1 % bb->n_blocks;
    const uint8_t *block = bb->data + block_idx * BLOCK_BYTES;

    for (uint32_t i = 0; i < bb->k; i++) {
        uint32_t bit = (uint32_t)((h2 + i * 0x9e3779b97f4a7c15ULL) % BLOCK_BITS);
        if (!(block[bit / 8] & (1u << (bit % 8))))
            return 0;
    }
    return 1;
}

RocksDB 从 2018 年起默认使用的就是一种优化的 Blocked Bloom Filter，他们的实现中每个 block 是 512 字节（8 个 cache line），在 SIMD 指令的帮助下实现了极高的吞吐。

六、Cuckoo Filter：当误判率要求更低时

Cuckoo Filter 的详细设计已经在 Cuckoo Hashing 一文中深入讨论，这里只做家族视角的比较。

核心思想

Fan, Andersen, Kaminsky, Mitzenmacher（2014）提出 Cuckoo Filter。它不存储位数组，而是存储每个元素的指纹（fingerprint），使用 Cuckoo Hashing 的桶结构来组织这些指纹。

• 每个桶可以容纳 \(b\) 个指纹（通常 \(b = 4\)）
• 指纹长度为 \(f\) 位
• 两个候选桶的位置通过 partial-key cuckoo hashing 确定

空间效率

Cuckoo Filter 的空间开销为：

\[\text{bits/key} = \frac{f}{0.955} \approx 1.05f \quad (b = 4 \text{ 时})\]

其中 fingerprint 长度 \(f\) 与目标误判率 \(\epsilon\) 的关系为：

\[f \geq \lceil \log_2(1/\epsilon) + \log_2(2b) \rceil = \lceil \log_2(1/\epsilon) + 3 \rceil \quad (b = 4)\]

对于 \(\epsilon = 1\%\)：\(f = 10\) 位，bits/key \(\approx 10.5\)。

对于 \(\epsilon = 0.001\%\)：\(f = 20\) 位，bits/key \(\approx 20.9\)。

何时选择 Cuckoo Filter

关键结论：当 \(\epsilon < 3\%\) 时，Cuckoo Filter 的空间效率优于 Standard Bloom Filter。当需要删除操作时，Cuckoo Filter 远优于 Counting Bloom Filter。

七、Ribbon Filter：逼近理论极限

背景

2021 年，Meta（当时的 Facebook）的 Peter Dillinger 和 Stefan Walzer 发表了 Ribbon Filter。它的目标很直接：在保持实用查询速度的同时，尽可能逼近信息论下界。

名字的含义

Ribbon 是 “Rapid Incremental Boolean Banding ON-the-fly” 的缩写。这个名字描述了它的构建过程。

核心思想

Ribbon Filter 的核心是一个基于带状矩阵（banded matrix）的线性代数方法。

对于集合 \(S\) 中的每个元素 \(x\)，构建一个 \(r\) 位宽的”带”（ribbon），本质上是一个在系数矩阵中连续 \(r\) 个位置上非零的行。然后通过高斯消元求解线性系统，得到一个解向量，该向量作为 filter 的存储。

查询时，对查询元素计算同样的”带”，与解向量做点积，检查结果是否匹配预期的哈希值。

更形式化地：

1. 对每个 \(x \in S\)，计算一个起始位置 \(\text{start}(x)\) 和一个 \(r\) 位的系数向量 \(\text{coeff}(x)\)
2. 同时计算一个 \(s\) 位的目标值 \(\text{result}(x)\)（元素的指纹）
3. 构建方程组：对于所有 \(x \in S\)，要求解向量 \(Z\) 满足 \(\text{coeff}(x) \cdot Z[\text{start}(x) \ldots \text{start}(x)+r-1] = \text{result}(x)\)
4. 由于系数矩阵是带状的（每行只有连续 \(r\) 个位置非零），可以用 \(O(n \cdot r)\) 的时间求解

空间效率

Ribbon Filter 每个元素需要的空间约为：

\[\text{bits/key} \approx (1 + \delta) \cdot \log_2(1/\epsilon)\]

其中 \(\delta\) 是一个很小的开销因子，通常在 1-5%。

这意味着 Ribbon Filter 几乎达到了信息论下界。

对于 \(\epsilon = 1\%\)：约 6.7-7.0 bits/key（信息论下界 6.64，Standard Bloom 需要 9.6）。

构建时间

Ribbon Filter 的主要缺点是构建时间比 Bloom Filter 慢。

构建需要高斯消元，时间复杂度为 \(O(n \cdot r)\)，其中 \(r\) 通常是 64 或 128。虽然渐近上是线性的，但常数较大。

在 RocksDB 的实际测试中，Ribbon Filter 的构建速度约为 Bloom Filter 的 1/3 到 1/2。

查询速度

查询速度与 Bloom Filter 相当，通常稍慢但在同一量级。每次查询需要：

1. 计算哈希得到 start 和 coeff
2. 从解向量中读取连续 \(r\) 位
3. 做一次点积（位与 + popcount）

这通常是 2-3 次 cache line 访问。

在 RocksDB 中的应用

从 RocksDB 7.0 开始，Ribbon Filter 成为一个可选的 filter policy。在 Meta 的生产环境中，当 SST 文件较大时（元素较多），Ribbon Filter 的空间节省显著——在同样的内存预算下，可以使用更低的误判率。

// RocksDB 中使用 Ribbon Filter
#include "rocksdb/filter_policy.h"
#include "rocksdb/table.h"

rocksdb::BlockBasedTableOptions table_options;
// 10 bits per key, using Ribbon Filter
table_options.filter_policy.reset(
    rocksdb::NewRibbonFilterPolicy(10.0));
// 对于小的 SST 文件自动回退到 Bloom Filter
// (Ribbon 的构建开销在小集合上不划算)

八、XOR Filter：更简单的接近最优方案

动机

Ribbon Filter 的构建过程涉及带状矩阵的高斯消元，实现相对复杂。有没有更简单的方法也能接近信息论下界？

XOR Filter

Dietzfelbinger 和 Walzer（2019，同一个 Walzer）提出了 XOR Filter，思想更加直观。

核心：对每个元素 \(x\)，计算三个哈希位置 \(h_0(x), h_1(x), h_2(x)\)，要求解向量 \(B\) 满足：

\[B[h_0(x)] \oplus B[h_1(x)] \oplus B[h_2(x)] = \text{fingerprint}(x)\]

其中 \(\oplus\) 是 XOR 运算，\(B\) 的每个槽位存储 \(s\) 位（\(s = \lceil \log_2(1/\epsilon) \rceil\)）。

查询时，对查询元素 \(q\) 计算三个位置，检查：

\[B[h_0(q)] \oplus B[h_1(q)] \oplus B[h_2(q)] \stackrel{?}{=} \text{fingerprint}(q)\]

如果相等，返回”可能在集合中”；否则”一定不在”。

构建过程

构建 XOR Filter 需要一个”剥离”（peeling）过程：

1. 构建一个超图（hypergraph），每个元素对应一条连接三个顶点的超边
2. 反复找到度为 1 的顶点（只有一条超边经过），移除对应的超边
3. 如果所有超边都能被移除，就按移除的逆序回填 \(B\) 的值
4. 如果卡住（没有度为 1 的顶点），需要用新的哈希函数重试

当表的大小为 \(m \approx 1.23n\) 时，剥离成功的概率很高。

空间效率

\[\text{bits/key} \approx 1.23 \cdot \lceil \log_2(1/\epsilon) \rceil\]

对于 \(\epsilon = 1\%\)：\(1.23 \times 7 = 8.61\) bits/key。比 Standard Bloom 的 9.6 好，但不如 Ribbon。

XOR+ 和 Binary Fuse Filter

XOR Filter 的改进版本：

• XOR+ 使用 3 段大小不等的表（而非 3 段等大），空间降至约 \(1.08 \cdot s\) bits/key
• Binary Fuse Filter（2022）进一步优化剥离过程，空间接近 \(1.01 \cdot s\) bits/key，构建也更快

/* XOR Filter 的查询极其简单 */
typedef struct {
    uint8_t *B;          /* fingerprint array */
    uint64_t block_len;  /* each of 3 blocks has this length */
    uint64_t seed;
} xor8_t; /* 8-bit fingerprints, epsilon ~ 1/256 ~ 0.39% */

int xor8_contain(const xor8_t *filter, uint64_t key) {
    uint64_t hash = xor8_mix(key, filter->seed);
    uint8_t fp = (uint8_t)(hash >> 56); /* top 8 bits as fingerprint */

    uint64_t h0 = hash % filter->block_len;
    uint64_t h1 = (hash >> 16) % filter->block_len + filter->block_len;
    uint64_t h2 = (hash >> 32) % filter->block_len + 2 * filter->block_len;

    return fp == (filter->B[h0] ^ filter->B[h1] ^ filter->B[h2]);
}

XOR Filter 查询只需要三次数组访问和两次 XOR，代码极其简洁。

九、空间效率全家族比较

下图比较了各种 filter 在不同误判率下的空间开销（bits per key）：

数值对比表

几个关键观察：

1. Counting Bloom Filter 的空间开销是灾难性的——4 倍于 Standard Bloom。如果需要删除，Cuckoo Filter 几乎在所有场景下都更好。

2. Standard Bloom Filter 比理论最优多 44% 空间，这个差距在 bits per key 绝对值不大时（如 \(\epsilon = 1\%\) 时差 3 bits/key）看起来可以接受，但在大规模部署中意味着大量内存浪费。

3. Cuckoo Filter 在 \(\epsilon < 3\%\) 时优于 Standard Bloom，同时还支持删除。

4. Ribbon 和 Binary Fuse Filter 几乎达到了理论极限，但它们是静态的——构建后不能增量添加元素。

5. 动态 vs 静态是一个根本性的 trade-off：如果集合在构建后不再变化（如 SST 文件的 filter），用 Ribbon/XOR；如果需要动态插入，用 Bloom 或 Cuckoo。

十、真实世界应用

LevelDB / RocksDB：SST 文件过滤

LSM-Tree 数据库的核心问题是读放大：一次 point query 可能需要查看多个 level 的多个 SST 文件。每个 SST 文件内部是有序的，可以二分搜索，但打开文件和读取 index block 本身就需要磁盘 I/O。

Bloom Filter 附加在每个 SST 文件的 metadata 中：

SST File Layout:
  [Data Block 1]
  [Data Block 2]
  ...
  [Data Block N]
  [Meta Block: Bloom Filter]  <-- filter 在这里
  [Meta Index Block]
  [Index Block]
  [Footer]

查询流程：

1. 从 MemTable 开始查找
2. 如果未命中，从 Level 0 开始逐 level 查找
3. 对于每个候选 SST 文件，先查 Bloom Filter
4. 如果 filter 说”不在”，跳过该文件（节省一次磁盘读取）
5. 如果 filter 说”可能在”，做实际的 index + data block 查找

在典型的 LSM-Tree 配置中（10 倍 size ratio，7 个 level），一次不存在的 key 查询在没有 filter 的情况下需要查看约 70 个 SST 文件。有了 1% FPR 的 Bloom Filter，期望只需要做约 0.7 次无效的磁盘读取。

RocksDB 的默认配置使用 10 bits/key 的 Bloom Filter，实际 FPR 约为 0.84%。

Google Chrome：Safe Browsing

Chrome 需要在用户访问每个 URL 时检查它是否在恶意网站列表中。这个列表有几十万条记录，不可能每次都查询远程服务器（延迟太高，隐私问题）。

Chrome 在本地维护一个 Bloom Filter，包含已知恶意 URL 的前缀。大部分查询（正常网站）会被 filter 快速拒绝。只有当 filter 返回”可能匹配”时，才会向 Google 的 Safe Browsing 服务发起网络请求确认。

这个设计同时解决了性能问题（99%+ 的查询在本地完成）和隐私问题（Google 只知道你访问了可能有问题的 URL）。

Apache Cassandra：分区过滤

Cassandra 在每个 SSTable 上维护 Bloom Filter，用于快速判断一个 partition key 是否可能存在于该 SSTable 中。

Cassandra 默认使用 10 bits/key（bloom_filter_fp_chance = 0.01，即 1% FPR），但允许每个表单独配置：

CREATE TABLE users (
    id uuid PRIMARY KEY,
    name text
) WITH bloom_filter_fp_chance = 0.001;  -- 0.1%, 更多内存换更少磁盘 I/O

对于频繁做 existence check 的表（如 counter 表），降低 FPR 可以显著减少磁盘读取。

网络路由与流量检测

在软件定义网络（SDN）和网络功能虚拟化（NFV）中，Bloom Filter 用于：

1. 重复数据包检测：路由器维护近期包的 Bloom Filter，快速判断一个包是否是重复的
2. 组播路由：在源路由头中嵌入 Bloom Filter，编码转发路径上的链路集合
3. 流量分类：用多个 Bloom Filter 实现快速的 ACL 匹配

在这些场景中，Bloom Filter 的常数时间查询和极小的空间占用使其成为在网络设备的 SRAM/TCAM 中实现高速匹配的理想选择。

十一、工程实践中的陷阱

下表总结了在生产环境中使用 Bloom Filter 家族时的常见问题和应对策略。

关于线程安全的补充

Standard Bloom Filter 的查询操作是天然线程安全的（纯只读）。但插入操作涉及对位数组的写入，在多线程环境下需要注意：

/* 方案一：原子操作（推荐，无锁） */
#include <stdatomic.h>

void bloom_add_atomic(bloom_t *bf, const void *data, size_t len) {
    uint64_t h1, h2;
    bloom_get_hashes(bf, data, len, &h1, &h2);

    for (uint32_t i = 0; i < bf->k; i++) {
        uint64_t pos = (h1 + (uint64_t)i * h2) % bf->m;
        uint64_t byte_idx = pos / 8;
        uint8_t bit_mask = 1u << (pos % 8);
        /* relaxed ordering is fine: setting a bit is idempotent */
        atomic_fetch_or_explicit(
            (_Atomic uint8_t *)&bf->bits[byte_idx],
            bit_mask, memory_order_relaxed);
    }
    atomic_fetch_add_explicit(&bf->n_added, 1, memory_order_relaxed);
}

这里使用 memory_order_relaxed 是安全的，因为把一个位从 0 设为 1 是幂等操作——即使两个线程同时设置同一位，结果也是正确的。

十二、选型决策与个人观点

选型流程

选择哪种 filter，我通常按以下逻辑判断：

1. 集合是静态的还是动态的？
   • 静态（构建后不变）：优先考虑 Ribbon 或 Binary Fuse Filter
   • 动态（需要增量插入）：继续下一步
2. 需要支持删除吗？
   • 需要：Cuckoo Filter
   • 不需要：继续下一步
3. 误判率要求多高？
   • \(\epsilon < 3\%\)：Cuckoo Filter（空间更优）
   • \(\epsilon \geq 3\%\)：Standard Bloom Filter 或 Blocked Bloom Filter
4. 吞吐量敏感吗？
   • 是：Blocked Bloom Filter
   • 否：Standard Bloom Filter

我的个人看法

Standard Bloom Filter 被过度使用了。 很多系统默认选择 Bloom Filter，因为它”经典”、实现简单、库到处都有。但在 2026 年，对于大多数场景，有更好的选择。

在数据库领域，SST 文件的 filter 天然是静态的——文件一旦写入就不再修改。这正是 Ribbon Filter 的最佳场景。Meta 在 RocksDB 中的切换已经证明了这一点：在同样的内存预算下，Ribbon Filter 比 Bloom Filter 节省约 30% 的空间，或者在同样的空间下误判率降低一个数量级。

Counting Bloom Filter 几乎没有存在的理由了。 4 倍的空间开销实在太高。如果你需要支持删除，Cuckoo Filter 在空间、查询速度、删除正确性上全面碾压 CBF。我能想到的唯一例外是你需要知道一个元素被插入了多少次（频率估计），这时计数器的语义才有意义。

XOR Filter 家族被低估了。 XOR8（8 位指纹，\(\epsilon \approx 0.39\%\)）的查询代码只有三行，性能极好。对于嵌入式系统或需要极致简洁实现的场景，XOR Filter 是一个被忽视的好选择。Go 的标准库和 Rust 的 xorf crate 都有成熟的实现。

不要在设计初期纠结 filter 选型。 从 Standard Bloom Filter 开始，加上监控（实际 FPR、内存占用、查询延迟）。等你有了真实数据后，再决定是否需要切换到更高级的变体。过早优化是万恶之源——但收集数据不是优化，是工程纪律。

哈希函数的选择比 filter 类型更重要。 我见过太多次因为哈希函数质量差导致实际 FPR 是理论值的 10 倍。用 MurmurHash3、XXHash3 或者 wyhash。不要用 CRC32，不要用简单的多项式哈希，不要自己发明哈希函数。

最后，一个经常被忽视的问题：false positive rate 是对均匀随机查询的期望值。如果你的查询分布与插入分布有相关性（这在实际系统中很常见），实际 FPR 可能远高于理论值。永远在真实 workload 上测量，不要只相信公式。

进一步阅读

• Bloom, B. H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM.
• Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (2000). Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. IEEE/ACM Transactions on Networking.（Counting Bloom Filter 的原始论文）
• Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014). Cuckoo Filter: Practically Better Than Bloom. CoNEXT.
• Putze, F., Sanders, P., & Singler, J. (2007). Cache-, Hash- and Space-Efficient Bloom Filters. JEA.
• Dillinger, P. C., & Walzer, S. (2021). Ribbon Filter: Practically Smaller Than Bloom and Xor. VLDB.
• Dietzfelbinger, M., & Walzer, S. (2019). Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row. ESA.（XOR Filter 的理论基础）
• Graf, T. M., & Lemire, D. (2022). Binary Fuse Filters: Fast and Smaller Than Xor Filters. ACM JEA.

上一篇: 一致性哈希：不要相信教科书版本 下一篇: 密码学哈希 vs 非密码学哈希：设计哲学的分野

相关阅读: - Cuckoo Hashing - HyperLogLog