技术小册

主题

海量数据处理 ​

一句话：数据量超过内存时，用分治把大问题拆小、用位图压缩标记、用近似算法换空间，代价是精度、可枚举性或额外的一到两轮 IO。

适用：Redis 7.x（Bitmap/HyperLogLog）、RedisBloom 2.x；算法误差为理论值，实际受哈希质量影响。

为什么需要 ​

10 亿个整数按 4 字节存要 4GB，10 亿条 URL 按 50 字节算要 50GB，普通服务进程放不下。全量加载会 OOM，逐条查数据库又把 IO 打满。

海量数据问题通常不是「算得快不快」，而是「在有限内存里，允不允许近似、允不允许两遍扫描」。先把这两个前提定下来，方案基本就确定了。

核心机制 ​

分治：让相同的 key 落到同一个分区 ​

对数据做 hash(key) % N，拆成 N 个文件或分区。相同的 key 一定进同一个分区，所以每个分区可以独立统计，最后只合并各分区的候选结果，不需要跨分区合并计数。

分区数要满足「单个分区能放进内存」。如果还放不下，就增加分区数或做二级分治。

TopK：小顶堆 ​

维护一个大小为 K 的小顶堆，堆顶是当前候选集中最小的。流式扫描数据：堆未满就入堆；满了就比较堆顶，比堆顶大就替换并调整。

时间复杂度 O(N log K)，空间 O(K)。数据在磁盘上也可以顺序扫描，不需要一次读进内存。

text
伪代码：
heap = min_heap()
for x in stream:
    if len(heap) < K: push(heap, x)
    elif x > heap[0]: heap[0] = x; heapify_down(heap, 0)
return heap

如果每个分区先算出本地 TopK，最后把 N × K 条候选再跑一次小顶堆，就能得到全局 TopK。注意是合并候选，不是合并所有计数。

Bitmap：用一位表示一个整数是否存在 ​

适合「整数 ID 稠密、范围有界」的场景。把第 i 位置 1 表示整数 i 存在：

text
置位：bitmap[i / 8] |= 1 << (i % 8)
查询：(bitmap[i / 8] >> (i % 8)) & 1

32 位无符号整数的全集需要 2^32 位 = 512 MiB。这个数字只在「范围是 0 到 2^32-1」时成立；如果 ID 是稀疏的 64 位值，直接开位图会浪费巨大空间，应该用 Roaring Bitmap 或先做 ID 映射。

布隆过滤器：只能判断「可能存在/一定不存在」 ​

布隆过滤器用 m 位的位图和 k 个哈希函数。插入时把 k 个位置置 1；查询时只要有任意一位是 0，就说明一定没出现过；全是 1，只能说明可能出现过。

误判率近似为 (1 - e^(-kn/m))^k，最优哈希个数约为 (m/n) ln 2。例如目标误判率 1% 时，每个元素大约需要 9.6 位。

三个边界必须记住：

  • 不能输出去重集合。它不保存元素，只能对单个 key 回答「可能/一定没有」。
  • 标准布隆过滤器不能删除。删一个元素会影响其他元素的位；需要删除时用计数布隆或 Cuckoo Filter。
  • 误判会把新元素当成旧元素。做 URL 去重时，可以先用它快速判断「一定没出现」，命中的再查精确集合；如果只靠它，少量新 URL 会被误丢。

所以「10 亿 URL 去重」如果要求得到精确的唯一集合，正确做法是哈希分治 + 每分区用 Set/排序去重，布隆只能做前置过滤。

HyperLogLog：只估基数，不存元素 ​

HyperLogLog 用哈希值的前导零位数估计集合大小。Redis 的实现用 16384 个 6 位寄存器，共 12 KB，标准误差约 1.04 / sqrt(16384) = 0.81%。

它只能回答「大约有多少个不同元素」，不能回答「有哪些元素」，也不能做 TopK。多个 HLL 可以 PFMERGE 合并，适合按天统计 UV 再合并成周/月。

其他结构 ​

  • Count-Min Sketch：估算元素出现频率，只会高估不会低估；适合热点检测，不适合精确计数。
  • 外部排序：数据在磁盘且需要有序结果时，分块排序后多路归并。
  • 倒排/列式：需要按维度过滤和聚合时，先把数据组织成可裁剪的结构，比现场扫描更有效。

最小上手 ​

bash
# HyperLogLog：12KB 估 UV，可合并
redis-cli PFADD uv:2026-10-24 u1 u2 u3
redis-cli PFCOUNT uv:2026-10-24
redis-cli PFMERGE uv:week uv:2026-10-24 uv:2026-10-25

# Bitmap：按整数 offset 标记
redis-cli SETBIT sign:2026-10-24 1001 1
redis-cli BITCOUNT sign:2026-10-24

# 布隆过滤器需要 RedisBloom 模块（redis-stack-server 自带）
redis-cli BF.RESERVE urls 0.01 1000000
redis-cli BF.ADD urls https://example.com
redis-cli BF.EXISTS urls https://example.com

BF.RESERVE urls 0.01 1000000 表示目标误判率 0.01、预计 100 万个元素；实际容量超出后误判率会上升，需要扩容或重建。

生产动作 ​

  • 先估内存：Bitmap 按最大 offset 算；布隆按 n × bits_per_element 算；HLL 每个 key 固定约 12 KB。
  • 布隆容量：按峰值元素数预留，监控实际插入量；超过容量后误判率上升，要重建或使用可扩展布隆。
  • HLL 精度：0.81% 是理论标准误差，不是上限；小基数时相对误差更明显，必要时改用精确集合。
  • Bitmap 稀疏性：避免 SETBIT 到极大的 offset，会一次性分配大量内存；先做 ID 压缩。
  • 分治倾斜：检查各分区大小，热点 key 会让单个分区过大；必要时加盐或换哈希。
  • 结果标注：近似结果要在接口和报表里标明「估算值」，不要让下游当成精确值做对账。

边界 ​

  • 布隆过滤器不能枚举、不能删除、不能输出去重后的集合；需要这些能力就换精确结构。
  • HyperLogLog 不能判断某个元素是否存在，也不能求 TopK；集合交并差只能近似，误差会累积。
  • Bitmap 只适合稠密整数域；稀疏、超大的 ID 空间会浪费内存。
  • 小顶堆适合 K 远小于 N；K 接近 N 时，排序或快速选择更合适。
  • 分治不是免费的：多一轮磁盘读写，分区越多，小文件和管理开销越大。

讲清楚 ​

海量数据先看内存和精度要求。能流式扫描的 TopK 用大小为 K 的小顶堆，空间只有 O(K)；放不下内存就按 key 哈希分治，保证相同 key 进同一分区，各分区独立统计后再合并候选。判断整数是否存在用 Bitmap，但只适合稠密有界范围；判断「可能出现过」用布隆过滤器，它只能说「一定不存在/可能存在」，不能枚举、不能删除、也不能输出去重集合。统计 UV 用 HyperLogLog，12KB 换约 0.81% 误差，只能估数量，不能查成员。选型的关键是明确业务到底要精确集合、精确次数，还是一个可接受的估计值。

把一门技术讲透到既懂也会用

技术小册 · 持续更新