一、起源:布尔状态的空间浪费与近似判断的内存约束

1. 一个布尔状态的存储代价

判断“某个标识是否出现过”只需要一个二值状态,但在多数语言与实现中,这个状态并不会真的只占一位。

承载方式 单个状态的占用 说明
基本类型数组(boolean[]) 1 字节 语言中不存在按位寻址的元素类型,最小的可独立寻址单元是字节
整型数组(int[]、long[],一个元素一个状态) 4 或 8 字节 用整数表示状态时的直接写法
对象引用数组 4 至 8 字节的引用,加上被引用对象的实例头 引用与对象头都属于固定开销,与状态本身无关
散列集合(HashSet) 每个元素数十字节 元素对象、桶节点、桶数组与装载因子预留的槽位累加,单元素开销的对照见 Java 集合框架实现原理 中“内存占用估算”一节

一个布尔状态在最小的按字节方案下也要占 8 位,按对象方案则要占数十字节。当状态数量不大时这些开销无关紧要;当状态数量进入十亿量级,按字节需要 1GB,按对象方案需要数十 GB,内存成为唯一不可忽略的约束。位图(Bitmap)针对的正是这 8 倍的固定浪费:把 8 个布尔状态压进同一个字节,用位运算取出其中之一。

2. 两类需求:是否存在与有多少种

位图与布隆过滤器服务的需求可以归为两类,两者的内存约束不同:

  • 判断“是否存在”。给定一个标识,回答它是否属于某个集合。精确回答需要保存标识本身(或至少保存能唯一还原标识的信息),空间与元素数量成正比。当元素本身较大(URL、长字符串、UUID)或数量极大时,保存全部元素的内存超出可用范围。
  • 判断“有多少种”。只需要不同的元素个数,不需要枚举具体值,甚至不需要判断单个元素是否出现过。这类需求进一步放宽了要求,可以用固定内存近似回答。

散列表对这两类需求都能精确回答:集合保存元素本身,计数用去重后的元素数,代价是空间随元素数量增长。这正是 散列表 中“用空间换时间”的另一面——它换来了精确与 O(1),但没有把空间压到下限。

3. 允许误差换取空间的思路

位图的做法是放弃“一个位置对应一个元素”,改为“一个比特对应一个取值”,把空间降到理论下限。但它要求取值可以映射为一段连续的下标,且下标上界可控,这个前提在标识为长字符串或 64 位散列值时并不成立。

当元素本身无法映射为紧凑下标、而又必须容纳任意形态的元素时,只剩一种选择:不保存元素,只保存元素的散列结果,并容忍由此产生的误判。这类结构被称为概率型数据结构(probabilistic data structure):

确定性结构:保存元素,判断结果绝对正确,空间与元素数量成正比
概率型结构:保存元素的散列指纹,判断结果在单侧允许出错,空间与元素数量弱相关或无关

由此形成本文的三条主线:位图是把布尔状态压到一位的紧凑结构,但仍需精确的取值映射;布隆过滤器在位图之上加入散列,把“取值映射”的限制换成“可控的假阳性”;基数估算结构(HyperLogLog)则进一步放弃单元素判断,只保留下基数信息,用固定内存回答“有多少种”。

二、原理

1. 位图

1.1 用比特表示状态

位图把一段连续整数区间上的每个取值对应到一个二进制位,位的取值表示该值对应的状态:

value = 5  →  第 5 位为 1 表示“存在”,为 0 表示“不存在”
bitmap[5] = 1

一个位图由两个参数确定:容量(能表示的取值个数,即位数组长度 m)与底层数组的元素类型。底层数组通常选机器字(32 位或 64 位整数),原因是按字访问与按位访问的代价相同,而一次字操作可以覆盖 32 或 64 个状态。

容量 m = 1000 位
用 long(64 位)存储:需要 ceil(1000 / 64) = 16 个字,占用 128 字节

1.2 位运算

位图上的全部操作都是位运算的组合,与或非异或负责状态的整体操作,移位与掩码负责定位到具体的位。

运算 符号(C 系列语言) 在位图中的用途
按位与 & 取交集;测试某一位(与掩码相与后判断是否为 0)
按位或 \| 取并集;置位(与掩码相或)
按位异或 ^ 取对称差;翻转某一位(与掩码异或)
按位取反 ~ 清零某一位(与掩码取反后相与)
左移 << 由位下标生成掩码
右移 >>、>>> 由位下标计算字下标;>>> 为无符号右移,避免符号位参与

定位一个位的三个基本动作:

设位下标为 b,字宽为 W(32 或 64)
字下标  wordIndex = b / W          等价于 b >> log2(W)
字内偏移 bitIndex  = b % W          等价于 b & (W - 1)
掩码    mask      = 1 << bitIndex

置位    words[wordIndex] |=  mask
清零    words[wordIndex] &= ~mask
翻转    words[wordIndex] ^=  mask
测试    (words[wordIndex] & mask) != 0

低位取模技巧。b % W 与 b / W 需要除法,代价高于位运算;当 W 为 2 的幂时两者可分别替换为 b & (W - 1) 与 b >> log2(W)。这与散列表容量取 2 的幂时用 hash & (m - 1) 替代取模是同一条性质的两次应用,推导见 散列表 第 1.4 节。

字内偏移要求 bitIndex ∈ [0, W),这一点在按位移动时是正确性前提而非优化:多数语言的移位指令只使用移位量的低位(对 64 位类型取模 64,对 32 位类型取模 32),因此 1L << 64 的结果等同于 1L << 0,即 1L。若位下标未经归一化就直接参与移位,超出范围的移位会静默地绕回,把状态写到错误的位上,而不是报错。实现部分的位操作代码给出了归一化写法(见三、1.2 节)。

符号相关的两个陷阱:

  • 小整型提升。Java 中 byte、short 参与运算时先提升为 int,若最高位为 1 则发生符号扩展,byte b = 0x80; b & 0x01 得到的结果与预期一致,但 (int) b 会得到 -128。从字节数组中取位之前应先与 0xFF 相与。
  • 有符号右移。Java 的 >> 会复制符号位,用于无符号位图(如以 32 位整数为字的位图)时应使用 >>>;C 语言中右移负数由实现定义,应使用无符号类型。

1.3 容量与索引映射

位图的第 i 位对应的整数是 i(或 i + offset),因此位图只接受可以映射为连续非负整数的取值。映射方式决定了它的适用范围:

原始取值 映射方式 限制
非负整数且上界已知 直接作为下标,或减去最小值后作为下标 内存随取值上界而非元素个数增长
有符号整数,范围跨零 减去最小值后作为下标 需要保存 offset,用于反解与遍历
自增主键、用户 ID 直接使用,或哈希到固定区间 区间必须有上界,否则单点写入会把位图撑到极端下标
任意字符串、UUID、URL 散列到固定区间 只可用于存在性判断与去重,不能用于排序与枚举
有字典序或时间语义的标识 编码为整数(如日期转序号) 编码规则需保证不冲突

容量与索引的关系是位图内存的直接来源:

内存 = ceil(容量 / 8) 字节
容量 10^6  → 125 KB
容量 10^8  → 12.5 MB
容量 10^9  → 125 MB

这三个数量级解释了位图的两个边界:取值上界在千万以内时,位图的空间优势压倒其他方案;上界进入百亿量级时,位图本身也会成为内存问题,需要先压缩取值域或改用散列加过滤器。

1.4 与数组、集合的空间对比

以“保存 10⁶ 个互不相同的整数并回答存在性”为例,各方案的空间量级:

方案 每元素空间 10⁶ 元素 10⁹ 元素 能力
位图(取值域即元素数) 1 位 125 KB 125 MB 存在性、去重、排序、枚举(按位遍历)
boolean 数组 1 字节 1 MB 1 GB 同上,但空间为位图的 8 倍
long 数组(一个元素一个状态) 8 字节 8 MB 8 GB 同上
HashSet<Integer> 数十字节 数十 MB 不适用 元素为任意整数,无上界要求
布隆过滤器(p = 0.01) 约 1.2 字节(9.6 位) 约 1.2 MB 约 1.2 GB 存在性,允许假阳性,不可枚举与删除
HyperLogLog 固定 12 KB 12 KB 12 KB 仅基数估算,误差约 0.81%

位图与 boolean 数组的差距是固定不变的 8 倍;位图与散列集合的差距随元素对象的开销变化,从数倍到数十倍不等。作为 ADT 层面,位图实现的仍是“集合”的成员判断语义,只是把取值域限制成一段连续整数,其与集合、映射的抽象关系见 抽象数据类型(ADT)。

2. 位图的应用

2.1 整数去重与排序

位图的第 i 位为 1 表示整数 i 出现过,因此写入过程天然完成去重:重复写入同一个下标不会改变位图状态。而按下标从 0 到容量遍历一遍,读出的下标序列必然是升序,这构成了位图排序:

for i in [0, capacity):
    if bitmap[i] == 1:
        output i

这一步的性质需要用复杂度衡量:遍历成本与容量成正比,而不是与元素个数成正比。元素稠密(取值域接近元素个数)时它比通用排序更快;元素稀疏(10⁶ 个元素分散在 10⁹ 的取值域上)时,遍历 10⁹ 位只为输出 10⁶ 个值的开销不可接受。

三条限制需要在选型时明确:

  1. 只能处理非负整数,其他类型需要先编码为满足映射要求的整数。
  2. 只能去重,不能计数。同一个值出现多次只留下一个位的状态;需要计数时改为多位表示(每个取值占若干位充当计数器,或用多级位图分别表示出现次数)。
  3. 不适用于取值范围远大于元素个数的场景,此时应先压缩取值域或改用散列方案。

2.2 存在性判断

位图的存在性判断是定位一次位并测试,与元素个数无关。当判断频繁而写入较少时,可以把位图常驻内存并周期性与持久层同步。多个位图之间的集合运算(并、交、差)可以按字并行完成:

并集:result[i] = a[i] | b[i]
交集:result[i] = a[i] & b[i]
差集:result[i] = a[i] & ~b[i]

这一点是位图在统计场景中的关键收益:按天分键存储的位图,用一次按位或即可合并出周活与月活集合,用按位与即可求出连续活跃的用户集合。字与字之间彼此独立,合并操作可以按分片并行执行,也可以下推到存储层完成(Redis 的 BITOP 即为按位运算命令)。

2.3 权限与标签位

位掩码(bitmask)是位图思想在单变量上的应用:把一组互不重叠的布尔属性放进同一个整数,每个属性占据固定的位。

READ    = 1 << 0   = 0001
WRITE   = 1 << 1   = 0010
DELETE  = 1 << 2   = 0100
ADMIN   = 1 << 3   = 1000

角色权限 = READ | WRITE          = 0011      合并权限
判定是否可写 = (角色权限 & WRITE) != 0
摘除某项权限 = 角色权限 & ~WRITE

这种方式把权限组合压缩成一个整数,比较、传递与存储都只需要一个数值,适合权限项数量固定且能用少量枚举描述的场景。它的边界同样明确:

  • 单变量能容纳的位数有限(32 位或 64 位),权限项超过位宽后需要扩展为整数数组或真正的位图,此时判定方式从一次位运算变成定位到某个字再做位运算。
  • 位与位之间必须互不重叠且语义独立。若把“查看他人订单”与“查看本人订单”编码进不同的位,则天然携带互斥约束的场景无法用单个掩码表达,需要额外的组合校验。
  • 超出位宽或权限项频繁增加时,位掩码的可读性迅速下降。此时改用“权限标识 + 集合”的表达方式更易维护,代价是空间与判定成本上升。

位掩码在数据库中的对应物是位图索引:在低基数列上按位存储“该行是否取某个取值”,多个条件的与或运算可以直接在位图上完成。它的适用边界与限制(更新时需要调整整张位图、锁粒度受限、不适合高并发写入)见 MySQL 索引与执行计划 第 2.1.1 节。

2.4 布隆过滤器与基数估算的底层

位图是两类概率型结构的存储底座:

  • 布隆过滤器用一个位数组加多个散列函数记录元素的散列指纹,位数组本身就是一个位图。
  • HyperLogLog用固定数量的寄存器保存散列值的分桶统计量,寄存器宽度为 6 位,整个结构可以看作固定长度的位图。
  • Redis 中这一层关系更为直接:bitmap 与 HyperLogLog 都以 string 类型的值作为载体,前者是原始位串,后者是编码后的寄存器数组。九种结构的语义、命令与底层编码见 Redis 核心与数据结构 第 2.2 节。

2.5 稀疏位图与 Roaring Bitmap

位图的空间与取值上界成正比,当取值稀疏而且分布跨度极大(例如数十亿个取值上只有百万个元素,且集中在若干区段)时,绝大部分字是 0,按完整位数组分配是纯粹浪费。稀疏位图的思路是按块选择存储方式,而不是一律用位数组。

Roaring Bitmap 是这一思路的代表:把 32 位整数按高 16 位分成块(chunk),每块内部是一个容器,容器按其内容选择表示:

容器类型 适用条件 表示方式 每块空间量级
数组容器 块内元素数不超过 4096 有序的 16 位整数数组 元素数 × 2 字节
位图容器 块内元素数超过 4096 固定 65536 位的位图 8 KB
连续区间容器 块内元素构成少量长连续区间 若干(起点、长度)对 区间数 × 4 字节

分块带来三个收益:稀疏区段只付出与元素数成正比的空间,稠密区段退化为位图的高效按字运算;块是独立的操作单位,集合运算可以按块并行,也可以只对存在交集的块求交;单个块的空间有限,避免了超大位图的分配与复制成本。4096 这个阈值来自两种容器的空间平衡点:4096 × 2 字节等于 8 KB,即超过 4096 个元素后位图容器更省。

代价是结构复杂度与常数开销上升:每次定位需要先确定块、再在容器内定位,容器类型还会随元素增删发生转换。因此 Roaring Bitmap 适用于“取值域大、分布呈现块状聚集、需要频繁做集合运算”的场景;取值均匀稠密时,普通位图更简单也更快。

3. 布隆过滤器

3.1 位数组与多个散列函数

布隆过滤器(Bloom Filter)由两部分组成:一个长度为 m 的位数组(初始全为 0),以及 k 个相互独立的散列函数,每个散列函数把元素映射到 [0, m) 内的一个位置。

m 位数组:  0 0 0 0 0 0 0 0   (初始状态)
k 个散列:  h₁(x), h₂(x), ..., hₖ(x)  →  各自给出一个位下标

与位图不同,布隆过滤器不要求元素是整数:元素先经散列函数转为位下标,因此可以接受任意二进制内容。散列函数的确定性要求与散列表一致——同一个元素在任何时刻必须得到同一组下标,否则插入与查询无法对应。

3.2 插入与查询

插入 x:
    for i in [1, k]:
        pos = hᵢ(x)
        bitarray[pos] = 1

查询 x:
    for i in [1, k]:
        pos = hᵢ(x)
        if bitarray[pos] == 0:
            return 不存在        // 任一位为 0 即可断定不存在
    return 可能存在              // k 位全为 1

两个过程都只需要 k 次散列计算与 k 次位访问,复杂度与已插入元素数无关。查询的两个返回值的确定性程度不同,这是整个结构最需要记住的一点:

  • 返回“不存在”是确定的。若元素确实插入过,它的 k 个位必然在插入时被置为 1,而位数组只被置位、不被清零(普通实现不支持删除),因此不可能出现“插入过却查到 0”的情况。
  • 返回“可能存在”是不确定的。这 k 个位可能是被其他元素的散列位置共同置为 1 的,此时过滤器把不存在的元素判为存在,称为假阳性(false positive)。

3.3 假阳性与假阴性的不对称

布隆过滤器在无删除操作时不会出现假阴性,只会出现假阳性。这个不对称性来源于操作的单向性:

结论 依据 例外
无假阴性 插入只置位、不清零,元素自己的 k 个位永久为 1 引入删除操作(清除某位)后不再成立,见 5.1 节
有假阳性 位由多个元素共享,其他元素的置位可能恰好覆盖目标的 k 个位 无

理解这一点的工程价值在于:判定结果的可用方向是单向的。“不存在”可以直接作为否定结论使用(例如直接拒绝查询请求),而“可能存在”必须用其他手段确认(查缓存、查数据库,或查一份精确的子集)。反过来使用(“过滤器判定存在即认为存在”)在逻辑上是不成立的,误判会直接变成业务错误。

3.4 误判率与位数组长度、散列个数的关系

误判率的推导只需要考虑“位数组被随机置位后,某一位仍为 0 的概率”。

单个散列函数把元素映射到某一位,该位保持为 0 的概率是 1 - 1/m。插入 n 个元素、每个元素 k 次散列,共执行 kn 次独立置位,该位仍为 0 的概率是:

(1 - 1/m)^(kn)  ≈  e^(-kn/m)        // 利用 (1 - 1/m)^m ≈ 1/e,m 较大时误差可忽略

因此某一位为 1 的概率(填充度)为 f = 1 - e^(-kn/m)。查询一个不存在的元素时,需要它的 k 个位置全部为 1,若近似认为各位相互独立,误判率为:

p = f^k = (1 - e^(-kn/m))^k

这个式子里的 k 出现在两个方向相反的位置,这是理解参数取舍的关键:

  • k 越大,查询需要的位越多,偶然全部命中越难(外层的 k 次幂使 p 下降);
  • k 越大,置位次数也越多,填充度 f 上升,单次命中的概率变大(内层的指数使 p 上升)。

只要 m/n 与 k 同比例(k = (m/n) × ln2),误判率就能被压到该 m/n 下的最小值,此时 p ≈ 0.6185^(m/n),即每增加 1 位/元素的预算,误判率乘以约 0.62。反过来,固定 k 而元素数增长时,填充度上升使误判率迅速恶化(见 4.3 节)。

3.5 最优散列个数

把 p 视为 k 的函数并对 k 求极小值,得到最优散列个数:

令 f = 1 - e^(-kn/m),p = f^k
求导后得到:  k_opt = (m / n) × ln2 ≈ 0.693 × (m / n)
此时:        f = 1/2,p = (1/2)^k ≈ 0.6185^(m/n)

三个可直接使用的结论:

  1. 最优状态下位数组恰好填充一半。填充度过低说明 k 偏小或容量过剩,填充度过高说明 k 偏大或容量不足。
  2. 最优 k 只与每元素位预算 m/n 有关,与元素总数无关。每元素 10 位对应 k ≈ 6.9(取 7),每元素 16 位对应 k ≈ 11。
  3. p 随 m/n 指数下降,而不是随 k 下降。试图只靠增加散列函数个数降低误判率,在超过最优值后会让结果变差——位被过早填满,后续元素几乎没有可用的 0 位。

4. 参数与容量

4.1 按元素数量与目标误判率计算参数

工程中通常给定预期元素数量 n 与可接受误判率 p,反解位数组长度与散列个数:

m = -n × ln p / (ln 2)²        位数组长度(位)
k = (m / n) × ln 2 = -ln p / ln 2   散列函数个数(取整)

例:n = 1,000,000,p = 0.01
    m = -10⁶ × (-4.605) / 0.4805 ≈ 9.58 × 10⁶ 位 ≈ 1.2 MB
    k = 4.605 / 0.693 ≈ 6.6  →  取 7

取整时需要处理两个细节:m 向上取整到机器字长的整数倍(便于按字访问,也避免最后一位落在数组之外),k 向上取整并保证至少为 1;取整后的实际误判率会略微偏离目标值,可代入 3.4 节的公式复核。

不同误判率目标下的参数与内存(按每元素位预算给出):

每元素位预算 m/n 最优散列个数 k 理论误判率 p 每元素内存 10⁶ 元素内存
6 4 0.056 0.75 字节 0.75 MB
8 6 0.021 1.0 字节 1.0 MB
10 7 0.0082 1.25 字节 1.25 MB
12 8 0.0031 1.5 字节 1.5 MB
16 11 0.00046 2.0 字节 2.0 MB
20 14 0.000067 2.5 字节 2.5 MB

这张表给出的量级关系值得记下:误判率每降低一个数量级,每元素的位预算大约增加 5 位(对应 p 乘以 0.6185^5 ≈ 0.09)。

4.2 内存占用估算

布隆过滤器的内存就是位数组:

内存(字节) = m / 8 = -n × ln p / (8 × (ln 2)²) ≈ 1.44 × n × log₂(1/p) / 8

两个与实现有关的修正项:

  • 取整与字对齐:m 向上取整到 64 的倍数,以及对象头与字段(k、m、计数、散列种子)的开销,在小容量时占比明显。
  • 散列函数的常数开销:位数组之外,若实现为每个散列函数保存状态(种子表、散列对象),这部分开销与元素数无关,但在容器化部署与分片数量很大时需要计入。

与精确结构的对比可以给出一个直观比例:10⁶ 个整数放入 HashSet<Integer> 时,计入元素对象、桶节点与桶数组,空间在数十 MB 量级(单元素开销的对照见 Java 集合框架实现原理 中“内存占用估算”一节);误判率 1% 的布隆过滤器只需要约 1.2 MB。这个差距正是它被放在高并发查询前置位置的原因。

4.3 填充度与误判率

误判率随元素数上升而恶化,速度比直觉更快。以 k = 7、按 n 个元素设计的过滤器为例,实际元素数增长后的误判率:

实际元素数 / 设计容量 m/n 实际值 填充度 f 误判率 p 相对设计值
1.0 10 0.503 0.008 1 倍
1.5 6.7 0.649 0.049 约 6 倍
2.0 5.0 0.753 0.14 约 17 倍
3.0 3.3 0.878 0.40 约 49 倍

结论有两条:容量估算偏低会以远快于线性的速度推高误判率,因此 n 的取值应按业务增长预留余量,并在运行期持续观测实际元素数与填充度;填充度是可观测的中间量,由位数组中 1 的个数除以 m 得到,把它与理论值对比可以判断误判率异常是容量问题还是散列质量问题(见三、5 节的排查表)。

5. 变体

5.1 计数布隆过滤器

标准布隆过滤器无法删除元素,原因是位被多个元素共享,把某一位清零会破坏其他元素的记录,产生假阴性。计数布隆过滤器(Counting Bloom Filter)把每个位替换为一个计数器:

插入:计数器 +1
查询:全部计数器 > 0 判为可能存在
删除:计数器 -1      // 归零后位等效为 0

代价是空间按计数器位宽成倍增加(每元素 4 位的计数器会把内存放大到约 4 倍),并引入计数器溢出问题:位宽有限(常见 3 至 4 位),插入量极大时计数器可能饱和,饱和后删除会导致该位被错误清零。工程上的处理是给计数器设上限(饱和后不再增加,也不再允许删除该位置),或按元素总量估算所需位宽。

计数布隆过滤器适用的场景是“元素集合持续增删且不能重建”:删除量相对于总量较小、且允许在饱和时退化为标准过滤器(失去删除能力)。若删除是主要操作,Cuckoo Filter 的定位更合适(见 5.4 节)。

5.2 分区布隆过滤器

标准实现中,k 个散列函数在整个位数组上独立取值,因此最坏情况下多个散列可能落在同一位置,使实际生效的位少于 k 个,实际误判率高于理论值。分区布隆过滤器(Partitioned Bloom Filter)把位数组均分为 k 个区,第 i 个散列函数只在第 i 个区内取值:

区间大小 = m / k
第 i 个位置 = i × (m / k) + (hᵢ(x) mod (m / k))

这样每个区被恰好置位一次,各区的填充过程相互独立,实际误判率更接近理论值;同时第 i 次访问固定在区 i 内,便于并行、向量化与硬件流水。代价是每个区的填充互相独立,容量较小时尾部区段可能先被填满。

5.3 可扩展布隆过滤器

元素数量无法预估时,可扩展布隆过滤器(Scalable Bloom Filter)用一组过滤器分段承接:

插入:写入当前(最后一个)过滤器;当前过滤器达到设计容量后,新建一个容量更大、
      目标误判率更低的过滤器并追加到链尾
查询:依次查询所有过滤器,任一判定“可能存在”即返回可能存在

每新增一个过滤器,其目标误判率按一个收敛比率缩小(常见 0.5),使整条链的总误判率有上界。代价是查询需要访问多个过滤器,查询成本与过滤器个数成正比(可用布隆过滤器本身判断“某个过滤器内是否可能有该元素”来跳过部分查询),且内存只增不减,删除与回收必须整体重建。

5.4 Cuckoo Filter

Cuckoo Filter 以指纹(fingerprint)代替位标记,借用了布谷鸟散列的思路:元素经散列得到两个候选桶,指纹存放在其中一个桶的槽位中;插入时若两个候选桶都满,就把桶内某个指纹踢出到它的备用位置,链式搬迁直到找到空槽或达到上限(超过上限则扩容)。

维度 布隆过滤器 Cuckoo Filter
存储内容 位数组中的置位标记 桶槽中的指纹
删除 不支持(需计数变体) 支持
查询 k 次位访问 一次或两次桶访问(通常更快)
空间效率 高 接近,高装载率时更省
装载率上限 无硬上限,只是误判率上升 有硬上限(通常 0.95 左右),超过后插入失败并触发扩容
插入失败 不发生 可能发生,需要扩容或重试
实现复杂度 低 中,需要处理搬迁与扩容

定位判断的依据是“是否需要删除”与“是否能接受插入失败”:只做一次性登记、元素集合基本不变时,布隆过滤器更简单;元素集合有增有删、且查询延迟敏感时,Cuckoo Filter 更合适。

5.5 与精确集合的取舍

需求 推荐结构 理由
必须精确判断,且需要枚举元素 散列集合或有序集合 概率型结构不保存元素,无法枚举
需要删除单个元素且要求精确 散列集合 布隆过滤器删除会引入假阴性
元素数量大、只需判断“一定不存在” 布隆过滤器 空间与元素数量弱相关,且“不存在”的结论确定
元素可映射为连续整数、取值上界可控 位图 精确,空间为位级,可按位遍历与集合运算
取值分布块状聚集、需要频繁集合运算 Roaring Bitmap 稀疏区段省空间,运算按块并行
只需去重后的数量 HyperLogLog 等基数估算结构 固定内存,误差可控
元素数量很小(万级以内) 散列集合或有序数组 概率型结构的固定开销与实现复杂度不划算

选择的关键在于能否为误差设定语义:误判带来的后果必须能被业务承接——要么二次校验可以纠正(查到缓存或数据库后得到确定结果),要么误判的代价低于节省的内存与延迟成本。做不到这一点的场景,应当使用精确结构。

6. HyperLogLog

6.1 散列、分桶与调和平均

HyperLogLog 解决的是“有多少种”而不回答“是否存在”。它的输入是一批可能大量重复的元素,输出是不同元素数量的估计值,整个结构的大小与基数无关。

基本思路建立在散列值的随机性上:

1. 把元素散列为 64 位(或 32 位)值
2. 取前 p 位作为桶号,共 m = 2^p 个桶
3. 在剩余的位中,从高位开始数连续的 0 的个数(再加 1),记为 ρ
4. 每个桶只保存该桶内观察到的最大 ρ 值

估计量的直觉来自概率:一个随机位串前面出现 r 个连续 0 的概率是 2^-(r+1) 量级,因此在一个桶里观察到最大 ρ 为 R,意味着该桶收到的不同元素数量大约在 2^R 量级。取单个桶的估计值方差极大,因此用调和平均把 m 个桶的估计合并,抑制极端值的影响:

E ≈ α_m × m² / Σ(2^(-M_j))        // M_j 为第 j 个桶的最大 ρ,α_m 为与 m 有关的修正常数

m 越大,桶数越多、单桶偏差被平均得越充分,估计越准,内存也越大;这就是 HyperLogLog 唯一的取舍旋钮。

6.2 相对误差与内存的取舍

相对标准误差由桶数决定:

相对误差 ≈ 1.04 / √m

Redis 的实现:p = 14,m = 2¹⁴ = 16384 个桶,每个寄存器 6 位
内存 = 16384 × 6 / 8 = 12288 字节 ≈ 12 KB
相对误差 ≈ 1.04 / 128 ≈ 0.81%

三点性质与位图、布隆过滤器不同:

  1. 误差与基数无关。无论统计的是 1 万个还是 1 亿个不同元素,相对误差都在同一个量级;这是它相对“按位分配空间”的位图最本质的区别。反过来,基数很小(远小于桶数)时相对误差会明显变大,因为桶的利用率过低,实现通常在小基数时切换为稀疏表示并在估计值上做线性计数修正。
  2. 内存固定且极小。单个键 12 KB 与基数无关,因此可以按天、按维度大量分键而不担心内存膨胀。
  3. 只估计数量,不提供单元素判断。查询“某个元素是否出现过”需要改为“插入前后的基数是否变化”,这需要保存历史值,成本高于直接判断。

6.3 合并能力

HyperLogLog 的合并是桶级取最大值:

合并 A 与 B:result[j] = max(A[j], B[j])      // 逐个桶比较

由于每个桶只保存“观察到的最大 ρ”,合并两个统计结果等价于把两批元素合在一起重新统计。这带来两个直接可用的能力:

  • 跨时间合并:按天统计的基数可以直接合并为周、月的去重计数,不需要保存任何明细。
  • 跨分片合并:各个分片或实例独立统计,再集中合并,合并过程只需要传输 12 KB 的结构而不是元素集合。

位图在满足同口径时也能合并(按位或),但前提是两边使用同一套下标映射且取值域一致;集合的并集则需要传输全部元素。三者的合并代价差别很大,这也是统计类场景优先选择 HyperLogLog 的原因之一。

6.4 与位图去重的差别

两者都能回答“有多少个不同元素”,但适用范围不重叠:

维度 位图 HyperLogLog
结果精度 精确 相对误差约 0.81%(Redis 默认参数)
内存 与取值范围上界成正比(按位) 固定约 12 KB,与基数无关
对标识的要求 必须可映射为连续整数下标 无要求,任意可散列的内容
单元素判断 可判断某个取值是否存在 不支持
枚举元素 可按位遍历出全部取值 不支持
集合运算 与、或、差可按字并行 仅支持并集(取最大值)
典型用途 精确签到、活跃标记、权限位 大规模 UV、独立 IP 数、去重计数

选择依据可以归结为两个问题:标识能否映射为连续整数且上界可控(否则位图不成立),以及是否需要判断单个元素(需要则只能选位图或精确集合)。UV 统计中三者的对照与选择条件见 Redis 缓存实践与常见问题 第 2.4 节。

7. 局限

概率型结构的能力边界需要在选型时一次说清,这些限制不会因为实现成熟而消失。

限制 具体表现 影响与应对
不能枚举元素 无法列出过滤器中的元素,位图只能按位遍历取值 需要枚举时保留一份精确集合或明细数据
删除困难 布隆过滤器清零某位会使共享该位的其他元素产生假阴性 改用计数布隆过滤器、Cuckoo Filter,或周期性整体重建
误判方向单一但后果不对称 只有“不存在”的结论可以直接使用 业务必须能容忍假阳性,或用二次校验兜底
不支持范围与排序 散列破坏了取值之间的顺序关系 需要范围查询时改用有序结构,见 散列表 第 6.1 节
容量与误判率强耦合 元素数超出设计容量后误判率快速上升 预留容量余量、持续观测填充度、按业务增长重建
与数据变更的同步存在窗口 数据删除后过滤器仍认为存在;重建期间新增数据可能未登记 用双写、影子过滤器与原子切换控制窗口,见三、2.5 节的重建策略
不保证跨进程一致 各实例各自加载时,新写入未必及时可见 统一登记入口,或用变更事件驱动同步

其中“误判对业务的影响”最需要在设计阶段定性:以“过滤不存在”的方式使用,误判只带来多一次无效查询;以“过滤存在”的方式使用(例如黑名单只允许名单内放行),误判会直接造成业务错误。前者可以用缓存与数据库兜底,后者必须保证滤除结论的精确性,通常不适合直接使用概率型结构。

三、实现

1. 位图实现要点

1.1 结构定义与扩容

public final class BitVector {

    private static final int ADDRESS_BITS = 6;                 // long 为 64 位,2^6 = 64
    private static final int BITS_PER_WORD = 1 << ADDRESS_BITS;

    private long[] words;
    private long capacity;                                     // 位容量

    public BitVector(long capacity) {
        this.capacity = capacity;
        this.words = new long[wordIndex(capacity - 1) + 1];
    }

    private static int wordIndex(long bitIndex) {
        return (int) (bitIndex >>> ADDRESS_BITS);               // 等价于 bitIndex / 64
    }

    private static long bitMask(long bitIndex) {
        return 1L << (bitIndex & (BITS_PER_WORD - 1));          // 等价于 bitIndex % 64
    }

    private void ensureCapacity(long bitIndex) {
        if (bitIndex < capacity) {
            return;
        }
        long newCapacity = Math.max(bitIndex + 1, capacity * 2);
        long[] newWords = new long[wordIndex(newCapacity - 1) + 1];
        System.arraycopy(words, 0, newWords, 0, words.length);
        this.words = newWords;
        this.capacity = newCapacity;
    }
}

三个设计选择需要明确:

  • 容量与字数组长度分开维护。字数组长度按 64 位向上取整,容量是逻辑上的位数上限,两者不一定相等;按容量判断边界、按字数组长度访问,才不会在最后几个位越界。
  • 扩容按倍数增长。与动态数组相同,逐位扩容会退化为 O(n²),按 2 倍扩容后置位的摊还成本为 O(1),这一结论与 数组与链表 中动态数组的摊还分析一致;若容量可预估,应在构造时一次分配到位,避免扩容时的复制与内存峰值。
  • 允许按需扩容还是预先固定。允许扩容便于使用,但每次扩容都要复制整个字数组;预先固定则必须在入口处校验下标范围,超界应报错而不是静默扩容(静默扩容会把“错误的下标”变成“巨大的位图”)。

1.2 位操作的写法与易错点

public void set(long bitIndex) {
    ensureCapacity(bitIndex);
    words[wordIndex(bitIndex)] |= bitMask(bitIndex);
}

public void clear(long bitIndex) {
    if (bitIndex >= capacity) {
        return;
    }
    words[wordIndex(bitIndex)] &= ~bitMask(bitIndex);
}

public void flip(long bitIndex) {
    ensureCapacity(bitIndex);
    words[wordIndex(bitIndex)] ^= bitMask(bitIndex);
}

public boolean get(long bitIndex) {
    return bitIndex < capacity
            && (words[wordIndex(bitIndex)] & bitMask(bitIndex)) != 0;
}

public long cardinality() {                                  // 置位个数
    long count = 0;
    for (long word : words) {
        count += Long.bitCount(word);                        // 由硬件指令完成,按字统计
    }
    return count;
}

易错点集中在移位与边界两处:

易错点 表现 正确做法
移位量未归一化 bitIndex 为 64 时 1L << 64 等于 1L,状态写到第 0 位 移位前先 & 63(32 位字则 & 31)
用 32 位常量生成掩码 1 << 31 为负值,与 long 相或时发生符号扩展 需要 64 位掩码时写 1L << n
字下标用除法且容量非 2 的幂 每次定位一次除法,热点路径上开销明显 字宽固定为 2 的幂,用 >>> 与 &
有符号右移 字下标计算中出现负数导致越界 索引为 long 时用 >>>,并保证索引非负
字节数组取位前未掩码 byte 提升为 int 时符号扩展,取到的高位全为 1 先与 0xFF 相与再参与位运算
越界写入静默生效 下标超出容量时未校验,写坏相邻数据 置位前 ensureCapacity 或入口处校验
字节序假设 位图序列化后跨平台读取顺序不一致 固定字节序(如大端)并在格式头部记录字宽与字节序

Python 中的等价写法需要注意取反的位数问题(Python 的整数为任意精度补码语义,~x 返回负数,需要与掩码相与限制位宽):

class BitMap:
    """按字节实现的位图,容量为 8 的整数倍。"""

    def __init__(self, capacity):
        self._words = bytearray((capacity + 7) // 8)

    def add(self, index):
        self._words[index >> 3] |= 1 << (index & 7)

    def remove(self, index):
        self._words[index >> 3] &= (~(1 << (index & 7))) & 0xFF   # 取反后必须掩码到 8 位

    def contains(self, index):
        return (self._words[index >> 3] >> (index & 7)) & 1 == 1

1.3 并发下的原子位操作

标准库通常不提供并发位图,位操作需要自己保证原子性。围绕 AtomicLongArray 的 CAS 循环是通用写法:

public void set(int bitIndex) {
    int wordIndex = bitIndex >>> 6;
    long mask = 1L << (bitIndex & 63);
    long oldValue;
    long newValue;
    do {
        oldValue = words.get(wordIndex);
        if ((oldValue & mask) != 0) {
            return;                                          // 已置位,无需写入
        }
        newValue = oldValue | mask;
    } while (!words.compareAndSet(wordIndex, oldValue, newValue));
}

除 CAS 循环外,还有两条路径:

  • 分段加锁。按字区间分段,各段独立加锁,成本是锁管理与伪共享(相邻段落在同一缓存行时相互影响)。适合写多且需要同时统计其他指标的场合。
  • 写者串行。把位图写入集中到一个线程或一个串行队列,读侧无锁。位图只被单点写入时(例如由日志消费线程统一登记),这是最简单且无竞争开销的方案。

三种方式的选择依据是写并发度与位图规模:写并发低、位图大时 CAS 循环的失败重试成本可控;写并发高时把写入串行化往往比让多个线程争抢 CAS 更划算。

布尔状态之间的语义原子性是另一个问题:一次业务操作需要同时置位多个位(例如同时记录“当日活跃”与“周活跃”),若要求两者同时可见,则单个位操作原子是不够的,需要把这两个位放在同一个字内,用一次 CAS 完成。

1.4 持久化与内存映射

位图的序列化形式是一段连续字节,持久化有三个要点:

  • 格式头部包含元信息。容量、字宽、字节序、版本号、偏移量(若下标做了平移)必须写入头部,否则读取方无法正确解释位序,也无法判断文件是否已被截断。
  • 状态一致性。单个位图可以整体覆盖写入(先写临时文件再原子重命名);多个位图需要同时生效时,应在写入全部新文件后用一次原子操作切换引用,避免读到只更新了一半的组合。
  • 增量与全量。位图适合周期性全量落盘,配合写前日志记录增量置位,可避免每次置位都触发磁盘写入。

大位图(数百 MB 以上)适合使用内存映射文件,让操作系统按页调度,避免一次性读入:

try (FileChannel channel = FileChannel.open(path, READ, WRITE, CREATE)) {
    long bytes = ((capacity + 63) >>> 6) * 8L;                // 按字对齐的字节数
    MappedByteBuffer buffer = channel.map(FileChannel.MapMode.READ_WRITE, 0, bytes);
    long wordIndex = bitIndex >>> 6;
    buffer.putLong(wordIndex * 8L, buffer.getLong(wordIndex * 8L) | (1L << (bitIndex & 63)));
    // buffer.force();   // 需要立即落盘时调用,否则由操作系统在回写时机决定
}

内存映射的代价与边界:

  • 文件必须在映射前预分配到足够大小,映射之后的写入不会自动扩展文件,超出映射范围的写入会抛异常。这与稀疏文件的行为不同:若先写入高位下标再截断分配,中间未写入的页不会被实际占用。
  • 页的读取与回写由操作系统调度,写入的持久化时机不由进程控制,进程崩溃时最近写入的页可能丢失;需要强持久化时显式调用 force(),其代价与页缓存回写的机制说明见 页缓存与 IO 性能。
  • 内存映射的文件在进程退出后由操作系统统一回写,但异常终止(如被强制杀死)时未回写的页仍会丢失,因此关键状态需要配合日志或可重建的数据源。

2. 布隆过滤器实现要点

2.1 散列函数的选择与派生

布隆过滤器需要 k 个相互独立的散列函数,直接实现 k 个不同的散列算法(每个都遍历一遍输入)代价过高。工程上普遍使用双散列派生:只做一次 64 位散列,把结果拆成两半,再用线性组合派生出 k 个位置。

h(x)        = 一次 64 位散列,拆分为 h₁(高 32 位)与 h₂(低 32 位)
第 i 个位置 = (h₁ + i × h₂) mod m        i = 0, 1, ..., k-1

写法的三个要求:

  • h₂ 与 m 必须互质。m 取 2 的幂时 h₂ 必须为奇数(h₂ | 1),否则位置序列只覆盖一部分下标,有效位减少、误判率上升。这是双散列实现中最容易忽略的一点。
  • 散列函数质量决定实际误判率。需要雪崩性好、低位分布均匀的 64 位散列(如 MurmurHash3、xxHash、FNV-1a);直接用字符串的 hashCode() 单独使用不合格——它的低位规律明显,而位数组下标恰恰大量依赖低位(容量取 2 的幂时下标等于散列值的低位)。散列函数的均匀性要求与 散列表 第 1.1 节相同,区别在于这里不涉及键的比较,冲突表现为误判而不是链长。
  • 可选的加盐。若过滤器暴露给不可信请求,攻击者可以构造大量散列到相同位置集合的元素,把局部填满。为每次构建的过滤器引入随机盐(并持久化盐值)可让攻击者无法离线构造,这与散列表采用带随机种子的散列是同一类防护。

2.2 初始化

public final class BloomFilter {

    private static final long SEED = 0x9E3779B97F4A7C15L;        // 构建时随机生成并持久化

    private final long[] bits;
    private final int bitSize;                                   // m,取 2 的幂
    private final int hashCount;                                 // k
    private long inserted;                                       // 已插入元素数

    public BloomFilter(long expectedInsertions, double falsePositiveRate) {
        long idealBits = (long) Math.ceil(
                -expectedInsertions * Math.log(falsePositiveRate)
                        / (Math.log(2) * Math.log(2)));
        this.bitSize = (int) ceilingPowerOfTwo(Math.max(idealBits, 64));   // m 取 2 的幂
        this.hashCount = Math.max(1, (int) Math.round(Math.log(2) * bitSize / expectedInsertions));
        this.bits = new long[bitSize >>> 6];
    }

    private static long ceilingPowerOfTwo(long value) {
        long highest = Long.highestOneBit(value);                          // 不超过 value 的最大 2 的幂
        return highest == value ? value : highest << 1;
    }
}

初始化阶段需要固定下来的量,后续不可修改(序列化时必须一并保存):位数组长度 m、散列个数 k、散列算法标识与种子、设计容量与目标误判率。m 取 2 的幂是为了让取模退化为位与,这与散列表容量取 2 的幂的理由相同;取 2 的幂带来的额外好处是 bitSize >>> 6 与 & (bitSize - 1) 都变成纯位运算,定位成本稳定。

2.3 插入、查询与统计

public void add(byte[] key) {
    long hash = murmur3_64(key, SEED);                           // 一次散列
    long h1 = hash >>> 32;
    long h2 = (hash & 0xFFFFFFFFL) | 1L;                         // 保证为奇数
    for (int i = 0; i < hashCount; i++) {
        long position = (h1 + i * h2) & (bitSize - 1);           // bitSize 为 2 的幂
        bits[(int) (position >>> 6)] |= 1L << (position & 63);
    }
    inserted++;
}

public boolean mightContain(byte[] key) {
    long hash = murmur3_64(key, SEED);
    long h1 = hash >>> 32;
    long h2 = (hash & 0xFFFFFFFFL) | 1L;
    for (int i = 0; i < hashCount; i++) {
        long position = (h1 + i * h2) & (bitSize - 1);
        if ((bits[(int) (position >>> 6)] & (1L << (position & 63))) == 0) {
            return false;                                        // 任一位为 0 即可否定
        }
    }
    return true;
}

三个可观测的统计量应当暴露出来,它们是排查误判率异常的主要依据:

public long bitCount() {                                         // 已置位个数
    long count = 0;
    for (long word : bits) {
        count += Long.bitCount(word);
    }
    return count;
}

public double fillRatio() {                                      // 填充度
    return (double) bitCount() / bitSize;
}

public double estimatedFalsePositiveRate() {                     // 按当前元素数估算
    double fill = fillRatio();
    double rate = 1.0;
    for (int i = 0; i < hashCount; i++) {
        rate *= fill;                                            // f^k
    }
    return rate;
}

bitCount() 与 fillRatio() 的开销与位数组大小成正比(按字统计,每秒可处理数亿位),不适合放在请求路径上,应由监控任务周期采集。填充度与理论值 1 - e^(-k·n/m) 的偏差是判断散列质量的直接证据:偏差过大说明散列分布不均或双散列的 h₂ 未与 m 互质。

2.4 序列化与持久化

布隆过滤器的序列化比位图多一层要求:散列参数必须与位数组一同保存,否则重新加载后计算出的位置与写入时不一致,查询会把已插入的元素判为不存在(假阴性)。

字段 作用 缺失后果
版本号与格式标识 兼容后续格式变更 无法判断文件能否被当前版本读取
位数组长度 m 位置取模的基数 位置计算错误,全部查询失效
散列个数 k 每次查询需要检查的位数 检查的位错位,误判率异常或出现假阴性
散列算法标识与种子 复现位置序列 无法复现位置,过滤器不可用
已插入元素数 估算当前误判率 无法判断是否需要重建
设计容量与目标误判率 判断容量是否耗尽 无法判断是否需要扩容

位数组本身按字序列化并固定字节序。持久化位置的选择取决于重建成本:能从数据源重新构建的过滤器(例如从数据库全量扫描商品 ID),可以不做持久化,进程启动时重建;重建成本高或数据源不可全量扫描的过滤器,则必须持久化并保证加载后校验(抽样验证若干已知存在的元素是否被判定为存在)。

2.5 重建策略

过滤器不支持删除,元素被删除后对应的位仍然为 1,误判率随删除量的累积而上升。因此需要周期性重建,重建的触发条件是可量化的:

触发条件 判断依据 说明
元素数达到设计容量 已插入元素数与设计容量之比;或填充度超过 0.5 并持续上升 填充度过高意味着误判率已明显偏离目标
删除量累积 数据源中已删除的元素数与历史登记元素数之比 需要额外的计数或统计来源
时间周期 按固定的重建周期 实现简单,用于删除量难以统计的场景
数据源变更事件 全量重建事件(数据迁移、批量导入) 与业务动作绑定,避免额外定时任务

重建过程的核心矛盾是重建期间新数据的登记:新过滤器只包含重建开始时已存在的数据,若此期间有新增元素只写入旧过滤器,切换到新过滤器后这些元素会被判为不存在,产生假阴性——对于“过滤不存在”的用法,假阴性意味着本应被服务的请求被拒绝。

常用的做法是影子过滤器 + 双写 + 原子切换:

准备阶段:    构建影子过滤器(包含全量存量数据)
双写阶段:    新增元素同时写入当前过滤器与影子过滤器
切换阶段:    影子过滤器填充完成后,用一次原子引用替换把读路径指向影子过滤器
收尾阶段:    延迟保留旧过滤器一段时间(或保留只读副本),作为切换瞬间的兜底

对应的代码结构:

private volatile BloomFilter current;                            // 读路径使用
private final AtomicReference<BloomFilter> shadow = new AtomicReference<>();

public void add(byte[] key) {
    current.add(key);                                            // 始终写入当前过滤器
    BloomFilter building = shadow.get();
    if (building != null) {
        building.add(key);                                       // 重建期间双写
    }
}

public void finishRebuild() {
    BloomFilter building = shadow.getAndSet(null);
    if (building != null) {
        current = building;                                      // 原子切换
    }
}

重建期间还有四点需要在设计中明确:

  • 每个实例各自重建时的一致性。多实例部署时,各实例的重建进度不同,同一时刻不同实例对同一元素的判断可能不一致。若业务不允许这种不一致,应把过滤器做成共享结构(集中式存储或集中构建后分发),代价是增加一次网络访问或分发链路。
  • 重建的资源开销。构建过滤器需要遍历全量数据,内存占用为旧、新两份位数组之和,切换后旧数组仍需等待不再被引用才能回收。内存规划应按“新旧两份同时存在”估算,而不是按单份容量估算。
  • 切换时刻的监控。切换前后应观察拒绝率(被判为不存在的请求比例)与抽样误判率的变化:拒绝率明显下降通常说明新过滤器的容量相对宽松,但也可能是登记不完整,需要与数据源中的记录数对照;拒绝率异常升高则指向重建数据不完整或双写未覆盖。
  • 回退路径。保留旧过滤器实例与切换开关,出现问题时可以切回并重新走一次双写,避免直接进入无过滤器状态(此时全部请求都会穿透到缓存与数据源)。

3. 复杂度与实测

3.1 复杂度

结构 插入 查询 空间 说明
位图 O(1) O(1) 容量 / 8 字节 定位为一次除法(或位移)加一次位运算;容量取 2 的幂时全部为位运算
位图(统计置位数) — O(容量 / 字宽) — 遍历全部字并按字统计,硬件指令下常数很小
布隆过滤器 O(k) O(k) 约 1.44 × n × log₂(1/p) / 8 字节 k 次散列与 k 次随机位访问;散列计算是主要成本
HyperLogLog O(1) O(m) 或按需 固定(Redis 为 12 KB) 插入按桶更新最大值;估算需遍历全部寄存器
散列集合 平均 O(1) 平均 O(1) 与元素数量成正比 需要保存元素,且需处理冲突与扩容

需要强调两点:

  1. 布隆过滤器的 O(k) 中藏着随机内存访问。k 个位置在位数组中均匀分布,每次访问都可能落在不同的缓存行,因此实际耗时对位数组大小敏感——位数组超出 CPU 缓存后,单次查询的耗时主要由缓存不命中次数决定,而不是由 k 的算术成本决定。这也是分区布隆过滤器(见 2.5.2 节)在延迟敏感场景中更受青睐的原因。
  2. 空间复杂度的“与元素数量成正比”与“与取值上界成正比”是两种不同的增长方式。位图的内存由取值上界决定,布隆过滤器由元素数量与误判率决定,基数估算结构则与两者都无关。选型时先确认增长的是哪一个量,再比较常数。

空间复杂度的定义与“用空间换时间”的一般取舍,见 复杂度分析 第 2.5 节。

3.2 内存占用与误判率的测量

误判率的测量需要注意测试集的构造:用已插入的元素测试得到的是命中率而不是误判率,必须用一批未插入过的元素作为测试集,并且该测试集的分布要与真实查询一致(若查询集中在某个前缀或某个数值区间,测试集也应体现这一点)。

def measure_false_positive_rate(bloom, absent_keys):
    """absent_keys 为确定未插入过的元素集合。"""
    false_positive = sum(1 for key in absent_keys if bloom.might_contain(key))
    n = len(absent_keys)
    rate = false_positive / n
    # 95% 置信区间半径约为 1.96 * sqrt(p(1-p)/n),样本量不足时结论不可用
    half_width = 1.96 * (rate * (1 - rate) / n) ** 0.5
    return rate, (rate - half_width, rate + half_width)

测量的三个判读要点:

  • 样本量决定结论的分辨率。目标误判率为 1% 时,用 1000 个样本测出的比例区间宽度约为 ±0.6%,只能判断“量级是否一致”;要区分 0.1% 与 1%,样本量需要提升到 10⁵ 以上。
  • 把样本按取值区间分桶统计。整体比例正常但某些区间的误判率明显偏高,说明散列在位数组上分布不均,是散列质量或双散列派生方式的问题,而不是容量估算的问题。
  • 同时记录填充度。填充度与理论值吻合而误判率偏高,指向散列函数的相关性(多个散列函数给出的位置不独立);填充度本身偏高,指向容量估算偏低或元素被重复插入。

内存占用的测量分三层:

1. 位数组本身:m / 8 字节(可由参数直接算出)
2. 结构开销:对象头、字段、散列函数的状态、序列化缓冲区
3. 实际驻留:内存映射方式下按操作系统实际加载的页计算,未访问的页不占物理内存

在容器化环境下,内存映射的大位图会给内存统计带来歧义:进程的物理内存占用随页的加载增长,而与堆大小的指标无关。这类结构的内存规划应基于文件的映射范围与访问模式,而不是堆的统计值。Redis 中观测单个键的内存与编码的方式(MEMORY USAGE、OBJECT ENCODING)见 Redis 运维与监控。

3.3 与哈希集合的对比

对比的维度不止内存,还包括查询耗时与误差带来的后续成本:

维度 布隆过滤器 位图 HashSet
10⁶ 元素内存 约 1.2 MB(p = 0.01) 125 KB(取值域 10⁶) 数十 MB
单次查询 k 次散列 + k 次随机位访问 一次定位与位测试 一次散列 + 一次定位 + 比较
缓存局部性 差(k 个位置分散) 好(顺序访问,字内位相邻) 差(节点与元素对象在堆上离散)
误差 有假阳性 无 无
后续动作 判定“可能存在”后必须二次校验 判定即结论 判定即结论

微基准的设计必须覆盖三类变量,否则结论会被实现细节掩盖:

@State(Scope.Benchmark)
public class MembershipBenchmark {

    @Param({"100000", "1000000", "10000000"})
    public int size;

    @Param({"0.01", "0.001"})
    public double falsePositiveRate;

    private BloomFilter bloom;
    private BitVector bitmap;
    private HashSet<Long> set;
    private byte[][] presentKeys;
    private byte[][] absentKeys;

    @Setup(Level.Trial)
    public void setup() {
        bloom = new BloomFilter(size, falsePositiveRate);
        bitmap = new BitVector(size);
        set = new HashSet<>(size * 4 / 3 + 1);                    // 预分配容量,消除扩容干扰
        presentKeys = new byte[size][];
        absentKeys = new byte[size][];
        for (int i = 0; i < size; i++) {
            presentKeys[i] = keyOf(i);
            absentKeys[i] = keyOf(i + size);                      // 确定未插入过
            bloom.add(presentKeys[i]);
            bitmap.set(i);
            set.add((long) i);
        }
        assert bloom.mightContain(presentKeys[0]);                // 先验证正确性,再测性能
    }

    @Benchmark
    public boolean bloomQueryPresent(Blackhole bh, ThreadLocalRandom random) {
        boolean result = bloom.mightContain(presentKeys[random.nextInt(size)]);
        bh.consume(result);
        return result;
    }

    @Benchmark
    public boolean bitmapQueryPresent(Blackhole bh, ThreadLocalRandom random) {
        boolean result = bitmap.get(random.nextInt(size));
        bh.consume(result);
        return result;
    }

    @Benchmark
    public boolean setQueryPresent(Blackhole bh, ThreadLocalRandom random) {
        boolean result = set.contains((long) random.nextInt(size));
        bh.consume(result);
        return result;
    }
}

结果判读需要区分三种成本:散列计算成本(布隆过滤器做 k 次位置派生,字符串还要先做一次完整散列)、内存访问成本(随机访问次数与位数组是否超出缓存)、后续校验成本(布隆过滤器的假阳性会带来额外的缓存或数据库查询)。第三项不体现在过滤器的微基准中,却常常是端到端收益的主要决定因素:误判率从 1% 降到 0.1% 时,过滤器本身的耗时变化很小,但被放行到下游的无效查询减少了一个数量级。微基准的使用方式、预热与测量模式的选择以及结果判读的通用方法见 JMH 微基准测试。

4. 工程应用

4.1 缓存穿透防护

缓存穿透指请求的键在缓存与数据源中都不存在,缓存无法拦截这类请求,每次都会落到数据源。布隆过滤器的作用是在访问缓存之前判断“一定不存在”,直接返回并终止请求:

请求 → 参数校验 → 限流 → 布隆过滤器 → 缓存(含空值缓存) → 数据源
                          |
                       判定不存在:直接返回

落地时的五个约束:

  1. 只把“不存在”作为结论。判定“可能存在”时必须继续查缓存与数据源,不能凭过滤器放行结果。这里判断失误的代价只是多一次无效查询,方向是安全的。
  2. 与数据写入同步。数据创建时必须登记到过滤器,删除时无法从过滤器中摘除,因此删除路径只能依赖重建或计数型变体。登记入口必须覆盖全部写入路径(业务写入、批量导入、其他服务),遗漏会表现为新数据被过滤器拦截。
  3. 容量按业务增长预留。元素数超出设计容量后误判率上升,穿透防护退化为“多一层开销但拦不住请求”。
  4. 重建期间的空窗需要承接。重建期间的空窗(尤其是集中式构建的过滤器重新加载)由限流、空值缓存与入口参数校验承接,避免空窗内请求全部穿透。
  5. 与空值缓存配合。布隆过滤器挡住的是“一定不存在”的键,而空值缓存挡住的是“曾经查过但不存在”的键,两者覆盖的集合并不重合:新建的数据不在过滤器中会被拦截,因此空值缓存的过期时间也要与数据创建的时间窗口匹配。

穿透的成因、四种应对手段的对照与组合次序,以及空值缓存过期时间的取值依据,见 缓存基础与一致性 第 2.5 节;Redis 中位图自实现、布隆模块与进程内过滤器三种途径的约束见 Redis 缓存实践与常见问题 第 3.4 节。

4.2 爬虫与判重

爬虫需要对已抓取的 URL 判重,URL 数量可达亿级且形态任意,位图不适用(无法映射为紧凑整数),布隆过滤器是常见选择:

  • URL 必须先规范化。去掉默认端口、统一大小写(域名部分)、去除无意义的查询参数与锚点、对参数排序,否则同一页面会因 URL 形态不同被重复抓取。规范化规则决定了判重的实际效果,是这一环节最容易出错的部分。
  • 误判方向与业务后果。布隆过滤器把新 URL 判为已抓取(假阳性)会导致漏抓,且无法从结果中反推;把已抓取判为新(假阴性)会导致重复抓取,代价可控。因此这里的容忍度通常较高(误判率可以放到 1% 甚至更高),以换取更小的内存。
  • 规模与结构的分层。亿级 URL 可以按域名或散列前缀分片到多个过滤器,降低单结构大小、便于并行;已被判为“可能存在”的 URL 再与持久化的精确集合(或存储引擎中的键)比对,避免误判带来的漏抓。
  • 去重与已抓取状态的区分。“待抓取队列中是否已有该 URL”与“是否已抓取”是两个集合,可以共用一个过滤器(代价是两者互相推高误判率),也可以拆成两个过滤器分别设置容量与误判率。

4.3 推荐与内容去重

推荐系统的去重通常要求“不对同一用户重复推荐同一内容”,去重的粒度是(用户,内容)对,规模随用户数与内容数的乘积增长:

  • 短期去重(几小时到几天)。按时间分片维护过滤器,过期即整体丢弃,天然实现了“窗口内的去重”。相比精确集合,内存优势明显且不需要清理单个元素。
  • 曝光计数与阈值。需要“曝光不超过 N 次”这类语义时,布隆过滤器无法表达计数,改用计数布隆过滤器,或对每个用户维护一个小规模的精确计数结构(单用户维度的数据量小,精确结构可行)。
  • 误判的后果。把未推荐过的内容判为已推荐,结果是内容曝光减少,属于可控的收益损失;反过来(漏判)会造成重复推荐,影响体验。两侧代价都不致命,因此这类场景适合使用误判率较高的紧凑配置。
  • 新内容与冷启动。新上架内容尚未登记时,任何过滤器都会产生假阴性,因此登记路径必须与内容上线流程绑定,或在查询路径上用内容的创建时间做兜底判断。

4.4 UV 与活跃用户统计

“有多少独立访客”只需要数量,不需要判断单个用户,属于基数估算的直接应用:

方案 精度 内存 能力边界
位图(按日分键) 精确 与用户标识最大值成正比(按位) 要求标识可映射为连续整数;可按位或合并出周活与月活
HyperLogLog 相对误差约 0.81% 固定(约 12 KB/键) 不能判断单个用户,支持合并
精确集合 精确 与基数成正比 支持判断单个用户;仅在基数可控(万级以内)时使用

三种方案的对照与选择条件见 Redis 缓存实践与常见问题 第 2.4 节;Redis 中 bitmap 与 HyperLogLog 的语义、命令与内存开销见 Redis 核心与数据结构 第 2.2.2 与 2.2.4 节。

位图方案的两个实现要点:

  • 按键与时间分片。位图存在单键体积上限(Redis 的偏移量上限为 2³² 位,约 512MB),用户标识很大时单个位图会变成大 key;按日分键既控制了单键大小,也让合并与清理变得简单(合并用按位或,清理直接删除过期键)。
  • 偏移量过大的浪费。若用户标识的最大值远大于实际活跃用户数(例如以 10⁹ 量级的内部分配 ID 作为下标,实际日活只有 10⁵),位图中间的大段 0 仍会占用内存。此时应先做标识到紧凑下标的映射,或改用 HyperLogLog。

4.5 审计与风控中的黑名单

黑名单(恶意 IP、失信标识、风险设备指纹)的规模大且要求低延迟判断,过滤器常被放在判定链路的前端:

  • 误判的方向必须与业务后果对齐。黑名单的判定结论是“命中则拒绝”,因此过滤器的假阳性会误拦截正常请求,影响直接可见。缓解手段是把过滤器作为初筛:命中后与精确黑名单(数据库或缓存中的集合)二次校验,只有精确命中才执行拦截,过滤器只承担“排除绝大多数正常请求”的作用。
  • 列表频繁变更时不适合直接使用过滤器。移除一个标识无法从过滤器中摘除,只能等重建;而黑名单的解除(申诉成功、误封纠正)要求即时生效。这类场景需要把“可即时变更的部分”放在精确集合中,过滤器只承载“长期稳定的大集合”。
  • 审计日志的判重。审计场景中常需要判断某条事件是否已经处理过(幂等),过滤器的假阳性会导致事件被错误地判定为已处理而丢弃,这类后果不可接受,应使用具有原子性与精确性的标记(带过期时间的键或去重表)。

4.6 数据库与存储引擎

位图与布隆过滤器在存储系统中的应用都属于“用极小的空间排除不可能的读取路径”:

  • 位图索引。在低基数列上为每个取值维护一个位图,多个条件的与或运算直接在位图上完成,适合分析型场景;限制是更新需要调整整张位图、锁粒度受限、不适合高并发写入,见 MySQL 索引与执行计划 第 2.1.1 节。
  • LSM 存储引擎中的 SSTable 过滤器。每个数据文件按请求的键建布隆过滤器,读取前先查过滤器,判断目标键不在该文件中即可跳过该文件的磁盘读取。这一层过滤直接减少的是磁盘 IO 次数,收益与文件数量成正比;内存表部分的结构与跳表的应用见 跳表。
  • 文件系统的空闲块管理。空闲块位图用一位表示一个块是否空闲,分配与回收即为位测试与位翻转;位图常驻内存,因此单个位图能管理的块数量受内存限制,这是文件系统划分成多个分区与块组的背景之一,相关元数据的组织见 文件系统基础。
  • 查询与去重前置过滤。数据库或计算引擎在扫描前用过滤器排除不可能命中的分区、文件或行组(元数据层的过滤),把条件下推到存储层以减少读取量。

5. 常见问题与排查

现象 可能原因 验证方式 处理
误判率明显高于设计值 实际元素数超出设计容量,填充度偏高 统计已插入元素数与位数组填充度,与理论值 1 - e^(-kn/m) 对比 按当前元素数重算参数并重建,预留增长余量
填充度与理论值一致但误判率偏高 散列函数相关性强,或双散列的 h₂ 与 m 不互质,位置序列未覆盖全部下标 检查 h₂ 是否为奇数;按取值区间分桶统计误判率,看是否局部偏高 更换散列函数或修正派生方式;改用分区布隆过滤器
误判率随时间缓慢上升 元素被删除后位仍为 1,位数组中“无效的 1”累积 对比数据源中有效元素数与过滤器登记元素数的差值 周期性重建;或改用计数布隆过滤器、Cuckoo Filter
原本存在的键被判定为不存在 重建期间新增数据未登记;或序列化时散列参数丢失导致位置计算不一致 检查重建窗口内的写入路径是否双写;抽样验证已知存在的元素 双写加原子切换;把 m、k、散列标识与种子写入序列化头部
位图占用内存远超预期 取值上界远大于实际元素数,或下标由 64 位散列值直接给出 打印容量与最大下标,比较实际元素数与取值域大小 先压缩映射(标识转紧凑下标),或改用 Roaring Bitmap / 布隆过滤器
写入位图后进程内存持续增长 下标越界触发静默扩容;或内存映射文件随访问被逐页载入 记录容量变化与文件映射范围;查看进程的物理内存与页加载情况 入口处校验下标范围;限制映射范围或分片
过滤器与数据不同步,新数据被拦截 多实例各自加载,写入未同步;或有写入路径未登记 对比数据源中的新增记录与过滤器的登记量;按写入路径逐条验证 统一登记入口;用变更事件驱动同步;集中构建后分发
过滤器重建期间请求被大量拒绝 重建数据不完整或切换发生在双写完成之前 观察切换时刻的拒绝率与误判率曲线 严格按“构建、双写、切换、收尾”四阶段执行,保留旧实例用于回退
HyperLogLog 估算误差大于预期 基数远小于桶数(稀疏阶段相对误差大);或同一逻辑实体存在多种字符串表示 用精确集合在同一批数据上对比;检查元素表示是否唯一(如 ID 是否带时间戳) 统一元素表示;基数很小时改用精确结构;按需增大桶数
过滤器内存映射的写入未落盘 页回写由操作系统调度,进程异常终止时未回写的页丢失 对比文件内容与预期状态 关键状态显式调用 force(),或改为可重建的设计
集合运算(与、或)结果不对 参与运算的位图下标映射不一致(偏移量或编码规则不同) 比对两侧的映射规则与容量 统一映射规则;把映射规则写入元数据并校验

排查的通用顺序是先区分容量问题与散列问题,再区分数据同步问题:

  1. 看填充度。填充度偏离理论值指向容量或散列分布问题。
  2. 看误判率的分布。整体偏高指向容量,局部偏高指向散列质量。
  3. 看方向。出现假阴性(本应存在的被判为不存在)一定不是误判率问题,而是数据同步、重建窗口或序列化参数问题。

前两类问题的修法都是重建,区别在于重建时是否需要调整参数;第三类问题重建无法解决,必须修同步路径。

6. 选型与检查清单

6.1 选型

需求 推荐 理由
布尔状态且取值可映射为连续整数,上界可控 位图 每状态 1 位,精确,可枚举与集合运算
同上,但取值域大且分布呈块状聚集 Roaring Bitmap 稀疏区段只付元素数成本,运算可按块并行
判断“一定不存在”,可容忍假阳性 布隆过滤器 空间与元素数量弱相关,否定结论确定
判断存在性且需要删除元素 计数布隆过滤器或 Cuckoo Filter 支持删除,代价是空间与插入失败概率
元素数量无法预估且集合持续增长 可扩展布隆过滤器 分段承接,误判率有上界,内存只增不减
只需去重后的数量 HyperLogLog 固定内存,误差可控,支持合并
需要精确判断、枚举或范围查询 散列集合或有序结构 概率型结构不保存元素,也不保证顺序
元素数量很小(万级以内) 精确结构 概率型结构的固定开销与实现复杂度不划算
误判的后果不可接受且无法二次校验 精确结构 误差必须能被业务语义承接,否则不适用

6.2 参数评审要点

检查项 评审内容
元素数量 n 取值的依据(当前量与增长预测),是否预留余量;超出后误判率的恶化幅度
目标误判率 p 由业务后果反推,而不是凭经验取值;p 变化一个数量级对应每元素约 5 位的空间差
位数组长度 m 按公式计算后向上取整到字对齐;是否为 2 的幂(决定是否可用位与替代取模)
散列个数 k 是否取在最优值附近(0.693 × m/n),取整后的实际误判率是否复核过
散列函数 是否为 64 位、低位分布是否均匀;双散列的 h₂ 是否与 m 互质;是否需要加盐
位图下标映射 标识到连续下标的映射是否唯一、是否稳定;最大值是否有上界;偏移量是否随数据一同持久化
内存预算 按峰值估算(新旧两份位数组同时存在、映射文件的范围),而不是按稳态估算
持久化格式 头部是否包含版本、m、k、散列标识与种子、字节序、已插入元素数
重建策略 触发条件可量化;四阶段流程与回退路径是否齐备;多实例之间的一致性如何处理
观测手段 填充度、误判率抽样、拒绝率、登记量与数据源中有效元素数的差值是否已接入监控

6.3 上线前检查清单

  1. 误判的后果是否已经定性,判定“不存在”与判定“存在”分别会导致什么业务结果,是否都有兜底路径。
  2. 容量是否按增长后的元素数量估算,是否有量化指标在元素数接近设计容量时触发重建。
  3. 散列函数是否可复现,种子与算法标识是否随数据一同持久化,重建与跨进程读取是否能得到一致的位置。
  4. 位图下标映射是否稳定,映射规则变化时是否会破坏已有的持久化数据。
  5. 登记路径是否覆盖全部写入,包括业务写入、批量任务、其他服务与数据修复操作。
  6. 重建流程是否经过演练,双写窗口、切换动作与回退路径是否在预发环境验证过。
  7. 观测指标是否齐备,填充度、抽样误判率、拦截量与下游实际查询量的对比是否可观测。
  8. 是否避免了把过滤器当作精确判断使用,是否存在“返回可能存在即认为存在”的判断分支。

四、总结

位图与布隆过滤器解决的是同一类约束下的不同问题:当布尔状态的数量进入内存无法按字节承载的量级时,必须把表示单位从字节压缩到位,并在此过程中决定放弃哪些能力。

原理层面的结论可以归为几条主线:

  • 位图把表示单位压到理论下限。一位表示一个状态,空间为容量除以 8,代价是要求取值可映射为连续非负整数且上界可控。它的全部操作由位运算构成,容量取 2 的幂时下标计算可以完全用位移与掩码完成;移位量必须归一化到字宽以内,这是实现正确性而非优化项。
  • 位图的价值不只在省空间。按位遍历天然得到有序结果(整数去重与排序);按字并行完成交并差,因此多个位图可以直接合并出周活、月活这类聚合集合;位掩码把一组互斥的布尔属性压进一个整数,是权限与标签的常用表达。代价是它只表达存在性这一种语义,需要计数时得为每个取值分配多个位,也不能表达范围与顺序关系。
  • 稀疏位图用分块容器替代统一位数组。Roaring Bitmap 按高 16 位分块,块内按元素密度选择有序数组、位图或连续区间表示,把“空间与取值上界成正比”改为“空间与实际元素数相关”,同时保留了按块并行做集合运算的能力。
  • 布隆过滤器用散列把位图的门槛降到任意元素。位数组加 k 个散列函数,插入置位、查询检查,不保存元素本身。它只有假阳性而没有假阴性,这个不对称的来源是位只被置位、从不被清零;由此得到的使用规则是“不存在”的结论可以直接使用,“可能存在”必须二次校验。
  • 误判率的形状由一个公式决定。填充度为 1 - e^(-kn/m),误判率为 f^k;k 同时出现在降低(外层幂)与抬高(填充度)误判率的两个位置,最优取值为 k = (m/n) × ln2,此时位数组恰好填充一半,误判率约为 0.6185^(m/n)。由此得到两条可操作结论:误判率每降低一个数量级约需每元素增加 5 位;容量估算偏低会以远快于线性的速度推高误判率,实际元素数为设计容量的 2 倍时,误判率从 0.8% 升到 14% 量级。
  • 变体针对的是标准实现的三个缺陷。计数布隆过滤器解决删除(代价是空间成倍与计数器饱和),分区布隆过滤器解决散列相关性与并行(代价是分区独立填充),可扩展布隆过滤器解决容量不可预估(代价是查询随段数增长),Cuckoo Filter 用指纹换取了删除能力与更快的查询(代价是装载率上限与插入失败)。
  • HyperLogLog 处理的是另一类需求。只回答“有多少种”,用散列分桶与调和平均把误差压到 1.04/√m,内存固定且与基数无关,支持桶级取最大值的合并。它与位图的区别是:位图要求标识可映射为连续整数并能判断单元素,HyperLogLog 无标识要求但不提供单元素判断;两者回答基数时的精度与内存取舍完全不同。

工程层面的结论同样收敛:

  • 先确认能力的边界,再比较常数。位图、布隆过滤器与基数估算结构放弃的能力依次增多(排序与枚举、删除与精确性、单元素判断),选型时先看业务是否真的不需要这些能力,再比较空间与延迟。
  • 误判必须有承接路径。可用形态只有两种:判定“不存在”直接返回,或判定“可能存在”后二次校验;任何把概率型判断当作确定结论的分支都是设计缺陷。
  • 重建不是可选项,而是这类结构的生命周期组成部分。触发条件要可量化(元素数、填充度、删除量),流程要包含构建、双写、原子切换与回退四个阶段,内存要按新旧两份同时存在来规划。
  • 观测填充度比观测误判率更及时。填充度可以在不构造测试集的前提下持续采集,是判断容量是否耗尽、散列是否均匀的直接指标;误判率抽样则需要独立测试集与足够样本量才有分辨率。
  • 排查先分方向。误判率与填充度同时偏高指向容量,填充度正常而误判率偏高指向散列质量,出现假阴性则一定是数据同步、重建窗口或序列化参数的问题——第三种与前两种的修法完全不同。

位图与布隆过滤器延续了 散列表 中“用空间换时间”的思路,但把交换的对象从“时间”换成了“精确性”:位图用取值映射的前提换掉 8 倍的字节浪费,布隆过滤器用可控的假阳性换掉保存元素的全部开销,基数估算结构用单元素判断能力换掉与基数相关的内存。三者共同的方法论是——先把需求中真正必需的能力列出来,再把其余部分作为可交换的成本。