概率数据结构工程实战：Bloom Filter、Count-Min Sketch 与 HyperLogLog 的误判权衡与分布式落地

在十亿级数据规模下，用一个 HashSet 去重、用一个 HashMap 统计频次、用一个精确结构数独立访客，内存账单会迅速失控。工程师们很早就在吞吐、精度与空间之间做取舍——而概率数据结构（Probabilistic Data Structures）正是这条取舍曲线上最优雅的解法：用可接受的、可量化的一小部分误差，换来对数量级更低的空间占用与常数级的时间复杂度。

本文从集合成员查询、频率估计、基数估计这三类最经典的工程问题出发，逐一拆解 Bloom Filter、Count-Min Sketch 与 HyperLogLog 的数学原理、参数推导、误判/误差边界，以及它们在 RocksDB、Redis、分布式计数等真实系统中的落地方式。站内已有大量关于精确索引与存储引擎的文章，本文聚焦"用概率换空间"这一被低估的工程武器。

一、为什么需要概率数据结构

精确数据结构的内存开销往往与数据规模线性甚至超线性增长。一个存储 10 亿个 64 位整数的 HashSet，仅键值就需要约 8 GB；若要统计每个元素的出现次数，HashMap 的条目开销会再翻数倍。当数据进入"海量"区间，这种开销在绝大多数业务里都是不可接受的。

概率数据结构的核心思想是：放弃"永远正确"，换取"几乎正确但可控"。代价是一小部分可量化的误差（误判率、估计偏差），收益则是：

• 空间：通常用 O(n·log(1/p)) 甚至 O(log log n) 比特位，而非 O(n·word) 字节；
• 时间：插入与查询均为 O(k) 或 O(d) 常数级，与集合大小无关；
• 可合并：多数结构支持跨节点逐元素合并，天然适配分布式场景。

本文将覆盖三个最经典、工程中使用频率最高的成员：

• Bloom Filter——回答"某个元素是否可能在集合中"（存在性）；
• Count-Min Sketch——回答"某个元素的出现频率大约是多少"（频率估计）；
• HyperLogLog——回答"集合中大约有多少个不重复元素"（基数估计）。

二、Bloom Filter：集合成员查询

Bloom Filter 用一个长度为 m 的位数组（bit array）和 k 个相互独立的哈希函数表达一个集合。插入元素时，用 k 个哈希函数算出 k 个位置并把对应位设为 1；查询时，若这 k 个位置全为 1，则认为"元素可能存在"，否则"一定不存在"。

2.1 误判率与参数推导

一个关键性质：Bloom Filter 不会漏报（false negative），只会误报（false positive）——即把不在集合中的元素说成"可能存在"。设位数组长度 m、预期元素数 n、哈希函数个数 k，在理想独立哈希假设下，某一位仍为 0 的概率为 (1 - 1/m)^(kn) ≈ e^(-kn/m)。于是误判率：

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

对给定 n 与 p，最优参数有闭式解：

直觉上 k 太小则位数组很快被填满（误判飙升），k 太大则每个元素触碰的位过多（同样填满更快）；0.7·m/n 是二者的平衡点。

2.2 参考实现

import math, hashlib

class BloomFilter:
    def __init__(self, n, p):
        # n: 预期元素数, p: 目标误判率
        self.m = max(1, int(-n * math.log(p) / (math.log(2) ** 2)))
        self.k = max(1, int(self.m / n * math.log(2)))
        self.bits = set()           # 用集合表达位数组, 避免位运算
        self.n, self.p = n, p

    def _hashes(self, item):
        # 双哈希派生 k 个独立位置, 规避弱独立哈希
        h1 = int.from_bytes(hashlib.md5(b"seed0" + item).digest()[:8], "big")
        h2 = int.from_bytes(hashlib.md5(b"seed1" + item).digest()[:8], "big")
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for h in self._hashes(item):
            self.bits.add(h)

    def contains(self, item):
        # 全为 1 才可能存在; 任一为 0 则一定不存在
        return all(h in self.bits for h in self._hashes(item))

bf = BloomFilter(n=1000000, p=0.01)
bf.add(b"user:10086")
print(b"user:10086" in bf)   # True
print(b"user:99999" in bf)   # 可能为 True(误判) 或 False

2.3 不可删除与工程应用

标准 Bloom Filter 无法安全删除元素——清零某一位可能影响其他元素。需要删除语义时用 Counting Bloom Filter（每位改为一个计数器，删除即减一）。典型工程落点：

• RocksDB / Cassandra 的 SSTable Block Filter：用 Bloom Filter 判断某个 key 是否"可能"在某个数据块，避免对不可能命中的块做磁盘 IO；
• 缓存穿透防护：在缓存前放一层 Bloom Filter，拦截明显不存在的 key，避免恶意/异常查询击穿到数据库；
• 爬虫 URL 去重：用极小空间记录已抓取 URL，容忍极小误判（把未抓取判成已抓取只会漏抓，可控）。

三、Count-Min Sketch：频率估计

Bloom Filter 只能回答"在不在"，不能回答"出现几次"。Count-Min Sketch（CMS）在位数组思想上叠加计数：用 d 行、每行 w 列的二维计数器表，配合 d 个哈希函数。插入时，对每个哈希函数算出列号，对应计数器加一；查询频率时取 d 行中的最小值。

3.1 误差边界与可合并性

由于哈希冲突，CMS 的估计值只会高估、不会低估。在 d = ceil(ln(1/δ)) 行、w = ceil(e/ε) 列的设置下，对任意元素的估计误差以 1-δ 的概率不超过 ε·(元素总计数)。空间开销为 O(d·w) = O((1/ε)·ln(1/δ)) 个计数器，与元素种类数无关。

CMS 的另一大优势是可合并：两个相同 (d, w) 参数的草图可逐元素取 max（或累加）合并，非常适合跨节点流量聚合。

3.2 参考实现

import hashlib

class CountMinSketch:
    def __init__(self, width, depth):
        self.w = width              # 每行计数器数
        self.d = depth              # 哈希行数
        self.table = [[0] * self.w for _ in range(self.d)]

    def _hashes(self, item):
        out = []
        for i in range(self.d):
            h = int.from_bytes(hashlib.md5(b"row%d" % i + item).digest()[:8], "big")
            out.append(h % self.w)
        return out

    def add(self, item, cnt=1):
        for i, h in enumerate(self._hashes(item)):
            self.table[i][h] += cnt

    def estimate(self, item):
        # 取各行最小值, 只可能高估
        return min(self.table[i][h] for i, h in enumerate(self._hashes(item)))

    def merge(self, other):
        # 同参数可合并, 适合跨节点聚合 Top-K
        for i in range(self.d):
            for j in range(self.w):
                self.table[i][j] += other.table[i][j]

cms = CountMinSketch(width=1024, depth=5)
for _ in range(500):
    cms.add(b"/api/login")
print(cms.estimate(b"/api/login"))   # 约 500, 可能略高

典型用途：网络流量 Top-K 热点识别、限流令牌的分布式计数、推荐系统的"热门 item"发现。它比精确 HashMap 省几个数量级内存，代价是低频项的轻微高估——而高频项（正是 Top-K 关心的）估计非常准。

四、HyperLogLog：基数估计

基数（cardinality）指集合中不重复元素的个数。用 HashSet 精确去重需要把每个元素都存下来；而很多场景（如独立访客 UV 统计）只关心"大约多少"，并不关心具体是谁。HyperLogLog（HLL）用约 1.5 KB 内存即可估计高达 10^9 级别的基数，标准误差约 2%。

4.1 原理：从前导零到调和平均

HLL 的观察很巧妙：对一个均匀随机的哈希值，若其二进制表示中前导零的个数为 r，则该值"落在大数区间"的概率约为 2^-(r+1)。于是可以用"观察到的最大前导零"来推断集合规模。为降低单次观测的方差，HLL 把哈希值分成 m = 2^b 个桶，每个桶独立记录自己的最大前导零，最后用调和平均（而非算术平均）汇总：

E ≈ α_m · m^2 / Σ(2^(-R[i])) ， α_m = (m·(m-1)/(m-1))^(1/2)·(1+δ) 类校正因子

调和平均对少数极端大值不敏感，使估计显著稳定；工业实现（如 Redis 的 HLL、Google 的 HLL++）还额外引入偏差校正与稀疏表示，把小基数区间的误差进一步压低。

4.2 参考实现

import hashlib, math

class HyperLogLog:
    def __init__(self, b=14):
        self.b = b
        self.m = 2 ** b             # 分桶数, 标准 HLL 用 2^14 = 16384
        self.mask = self.m - 1
        self.reg = [0] * self.m

    def _leading_zeros(self, w):
        # w 为去掉低 b 位后的剩余高位, 统计其前导零 + 1
        return 1 if w == 0 else w.bit_length() + 1

    def add(self, item):
        h = int.from_bytes(hashlib.sha1(item).digest()[:8], "big")
        idx = h % self.m            # 低 b 位定桶
        w = h // self.m             # 高位算前导零
        self.reg[idx] = max(self.reg[idx], self._leading_zeros(w))

    def count(self):
        alpha = 0.7213 / (1.0 + 1.079 / self.m)
        est = alpha * self.m * self.m / sum(2.0 ** (-r) for r in self.reg)
        if est < 2.5 * self.m:      # 小基数用零桶数修正
            zeros = self.reg.count(0)
            if zeros:
                est = self.m * math.log(self.m / float(zeros))
        return int(est)

hll = HyperLogLog(b=14)
for i in range(1_000_000):
    hll.add(("user:%d" % i).encode())
print(hll.count())                  # 约 1000000, 误差约 2%

真实系统中，Redis 的 PFADD / PFCOUNT 就是 HLL 工程化实现，用 12 KB 左右内存即可在毫秒级给出 UV 估计；ClickHouse 的 uniq 聚合、PostgreSQL 的近似 NDV 估计也依赖同类思想。

五、三者对比与选型

六、分布式场景落地

概率数据结构的可合并性使它们成为分布式系统的天然组件：

• 跨分片基数：每个分片维护自己的 HLL，全局 UV 只需把各分片草图"逐桶取 max"合并，无需把明细汇总到中心；
• 跨节点 Top-K：各节点维护本地 CMS，聚合时逐元素相加，再在中心取 Top-K，省去全量明细传输；
• 分片路由：用 Bloom Filter 记录"某分片可能包含哪些 key 范围"，查询时并行探查多个分片、用 OR 合并结果，减少盲目广播；
• 真实系统组合：RocksDB 用 Bloom Filter 做 block 过滤、Cassandra 用 Bloom 挡无效 SST 读取、Redis 用 HLL 做 UV、ClickHouse 用 HLL 类结构做 uniq 近似聚合——这些结构早已是存储与数据库内核的标配。

七、工程陷阱与经验

• 哈希函数要独立且低碰撞：用 Murmur3、xxHash、SHA 等；用"双哈希派生 k 个"比"k 个弱哈希"更稳，避免相关哈希把位扎堆；
• 误判率要按业务定：p 定得越小，空间越大；缓存穿透场景 p=0.01 通常够用，别盲目追求 0；
• 不可删除的代价：标准 Bloom/HLL 不支持删除，需要 TTL 或 Counting 变体；否则"已下架元素"会永久占用判断；
• 哈希偏置会污染估计：HLL 对哈希均匀性敏感，务必用 64 位以上高质量哈希，避免前导零分布失真；
• 参数一次性定死难扩容：分桶数/位数组长度一旦固定很难在线扩容，可用"可扩展 Bloom Filter"或分层结构兜底。

结语

概率数据结构不是"不精确的妥协"，而是工程上"用确定性误差换确定性成本"的主动设计。Bloom Filter、Count-Min Sketch、HyperLogLog 三者分别对应存在性、频率、基数三类根本问题，构成了海量数据下空间与精度的基石。理解它们的数学边界与误差语义，是在存储引擎、缓存、实时分析、分布式计数等场景中做对架构取舍的前提——这也是为什么它们会出现在几乎每一款现代数据库与基础设施的内核里。