海量数据处理完全指南:布隆过滤器、HyperLogLog 与 Count-Min Sketch

"上亿用户里这个用户访问过吗?""今天网站独立访客大约多少?""这个 IP 最近 1 分钟来了多少次?" —— 这类海量数据问题用普通数据结构(Set / HashMap)会内存爆炸。这篇文章把概率型数据结构讲透:布隆过滤器、HyperLogLog、Count-Min Sketch、TopK,在精度换空间上做巧妙权衡。

布隆过滤器(Bloom Filter)

1970 年 Bloom 提出。功能:判断一个元素是否在集合里,但允许"假阳性"(可能误判存在),不允许"假阴性"(不存在的一定说不存在)。

原理

用一个 m 位的位数组 + k 个哈希函数:

插入:计算 k 个哈希,把对应 k 个位都置 1
查询:计算 k 个哈希,如果所有 k 个位都是 1 -> 可能在
                       否则 -> 一定不在

例:m=10, k=3,插入"apple":
hash1("apple") % 10 = 2 -> bits[2] = 1
hash2("apple") % 10 = 5 -> bits[5] = 1
hash3("apple") % 10 = 8 -> bits[8] = 1

查"apple":bits[2,5,8] 都是 1 -> 可能在
查"banana":hash 算出 [1,5,9],bits[1]=0 -> 一定不在

实现

class BloomFilter {
    constructor(size = 1000000, hashCount = 7) {
        this.size = size;
        this.hashCount = hashCount;
        this.bits = new Uint8Array(Math.ceil(size / 8));
    }

    _hash(item, seed) {
        // 用 MurmurHash 或简化版
        let hash = seed;
        for (const ch of String(item)) {
            hash = (hash * 31 + ch.charCodeAt(0)) % this.size;
        }
        return hash;
    }

    _setBit(i) { this.bits[i >> 3] |= 1 << (i & 7); }
    _getBit(i) { return (this.bits[i >> 3] >> (i & 7)) & 1; }

    add(item) {
        for (let i = 0; i < this.hashCount; i++) {
            this._setBit(this._hash(item, i));
        }
    }

    contains(item) {
        for (let i = 0; i < this.hashCount; i++) {
            if (!this._getBit(this._hash(item, i))) return false;
        }
        return true;
    }
}

const bf = new BloomFilter();
bf.add('user_12345');
bf.contains('user_12345');   // true
bf.contains('user_99999');   // 几乎肯定 false,极小概率 false positive

参数选择

给定 n 个元素和期望假阳性率 p:

m = -n * ln(p) / (ln(2))^2     // 位数
k = m/n * ln(2)                  // 哈希次数

例:1 亿元素,假阳性 1%:
m ≈ 1 亿 * 9.6 = 9.6 亿位 ≈ 120 MB
k ≈ 7 个哈希

对比直接用 Set 存 1 亿字符串:几 GB。布隆过滤器省 90%+ 内存。

应用场景

• 缓存穿透:查 DB 前先查布隆 —— 不存在直接拒绝,不打 DB。Redis 4.0 内置了 RedisBloom 模块。
• 爬虫去重:已抓 URL 存布隆,新 URL 快速判重。
• HBase / Cassandra:每个 SSTable 文件配布隆,快速判断"这个 key 可能在这个文件吗"。
• 区块链:比特币 SPV 节点用布隆筛选相关交易。
• 恶意 URL 检测:浏览器查 Google Safe Browsing 数据库。

变种

• Counting Bloom Filter:位变成计数器,支持删除。但精度可能下降。
• Scalable Bloom Filter:动态扩容,适合不知道元素总量的场景。
• Cuckoo Filter:布谷鸟过滤器,支持删除且空间效率更好。RedisBloom 也支持。

HyperLogLog:基数估计

1970 年代理论,2007 年 HyperLogLog 算法。功能:估计集合中不重复元素的数量(基数),误差 ~0.81%,空间只要几 KB。

核心思想

观察:随机的二进制串里,连续 0 的最长长度大致和元素数量的对数相关。

"abc"  -> hash = 0001011010...    // 前面 3 个 0
"def"  -> hash = 0000010011...    // 前面 5 个 0
"ghi"  -> hash = 010100...         // 前面 1 个 0

# 最长 0 前缀 = 5
# 估计元素数 = 2^5 = 32

# 分桶平均:把 hash 前几位作桶索引,后面位看 0 前缀,
# 多桶平均能极大降低误差

Redis 实现

PFADD visitors "user1" "user2" "user3"
PFCOUNT visitors                     # 约 3
PFMERGE union v1 v2 v3                # 合并多个 HLL

# 实战:今日 UV
PFADD uv:20260515 user_id
PFADD uv:20260515 another_user_id
# 一天的 UV 只占 12KB,无论 100 万还是 1 亿用户都一样

# 周 UV:合并 7 天
PFMERGE uv:week uv:20260509 uv:20260510 ... uv:20260515
PFCOUNT uv:week

HLL vs Set

需求               Set                HyperLogLog
精确判断"包含"     ✅                  ❌(不支持)
基数(去重 count) ✅(精确)            ✅(0.81% 误差)
内存(1 亿元素)   几 GB                12 KB
合并多集合         ✅                  ✅(直接合并位图)

用 Set 的场景一般是"要枚举具体元素",用 HLL 是"只关心数量"。两者经常配合用 —— Set 存最近少量,HLL 估全历史。

Count-Min Sketch:频次估计

功能:估计某个元素出现了多少次。比如"某 IP 今天访问了多少次",存所有 IP 的精确计数太贵。

原理

d 行哈希表(d 个哈希函数),每行 w 列。元素来了在每行对应位置 +1。查询时取所有行的最小值。

class CountMinSketch {
    constructor(width = 1024, depth = 5) {
        this.width = width;
        this.depth = depth;
        this.counts = Array.from({length: depth}, () => new Uint32Array(width));
    }

    _hash(item, seed) {
        let h = seed;
        for (const ch of String(item)) h = (h * 31 + ch.charCodeAt(0)) % this.width;
        return Math.abs(h);
    }

    add(item, n = 1) {
        for (let i = 0; i < this.depth; i++) {
            this.counts[i][this._hash(item, i)] += n;
        }
    }

    count(item) {
        let min = Infinity;
        for (let i = 0; i < this.depth; i++) {
            min = Math.min(min, this.counts[i][this._hash(item, i)]);
        }
        return min;
    }
}

应用

• 限流:统计每个 IP / 用户的请求数。
• 热点检测:哪些 key / URL 最热。
• 异常检测:某 IP 访问数突然飙升。
• 实时统计:广告点击量近实时估算。

Count-Min 总是高估(碰撞让计数变大),但不会低估。所以适合"找超过某阈值的"场景。

Top-K 问题

"找最频繁的 K 个元素"。流式数据下用 Heavy Hitters 算法:

Lossy Counting

Manku 和 Motwani 2002 年提出。维护一个动态 map,定期清掉计数过低的。

Space Saving

固定大小的 Map,新元素来了如果不在 map 里就替换计数最小的(并把最小计数加 1)。

Heavy Keeper

2018 年提出,精度和效率更好。Redis Stream 用类似算法做"TOP K 命令"。

实战:实时反爬虫

// 用 Count-Min Sketch 统计每个 IP 的请求数
// 用 Bloom Filter 维护"已封禁的 IP 列表"
const cms = new CountMinSketch();
const blacklist = new BloomFilter();

function onRequest(ip) {
    if (blacklist.contains(ip)) {
        return reject('blacklisted');
    }

    cms.add(ip);
    const count = cms.count(ip);
    if (count > 1000) {   // 1 分钟超过 1000 次
        blacklist.add(ip);
        return reject('rate limit exceeded');
    }
    return process(...);
}

// 每分钟重置 CMS
setInterval(() => cms.reset(), 60000);

外部排序 / MapReduce

不能装进内存的数据排序 / 聚合,经典思路:

1. 分:把大文件切成内存能装的块,各自处理。
2. 处理:每块内存内做(排序 / 去重 / 聚合)。
3. 合:多路归并 / 二次聚合。

这就是 MapReduce / Spark 的核心思想。面试常问"10G 文件内存 1G 怎么排序" —— 用外部归并。

面试经典:10 亿数据 Top 100

// 不能全部装内存,但能维护一个大小为 100 的小顶堆
import { Heap } from 'heap-js';

function topK(stream, k) {
    const minHeap = new Heap((a, b) => a - b);
    for (const num of stream) {
        if (minHeap.size() < k) {
            minHeap.push(num);
        } else if (num > minHeap.peek()) {
            minHeap.pop();
            minHeap.push(num);
        }
    }
    return [...minHeap].sort((a, b) => b - a);
}
// 空间 O(k),时间 O(n log k)

实战工具

• RedisBloom:Redis 模块,提供布隆 / HLL / Count-Min / TopK 命令。
• ClickHouse:OLAP 数据库,内置 HLL / 近似聚合函数。
• Apache DataSketches:Yahoo 开源的概率数据结构集合。
• StreamLib:Java 流处理库,各种 sketch 算法。

写在最后

概率数据结构是处理"海量但精度可放松"问题的核心工具。它们用"固定空间换可控误差",在统计、监控、推荐、风控、爬虫场景都不可或缺。理解它们的原理和误差分析,你能在系统设计时大胆做出"用 12KB HLL 替代 5GB Set"这种判断,这是大数据架构师的基本素养。

一图看懂

布隆过滤器原理一图看懂:

—— 别看了 · 2026