UV 去重三方案：HyperLogLog、RoaringBitmap 与精确集合，在 2 亿事件下的精度、内存与并集口径取舍

站在指标体系视角，对比三种去重计数方案的误差、内存、并集口径一致性，给一个可复现的选型决策。

一、现象与背景

接手一个内容型 App 的数据团队，日均埋点 2.3 亿条事件，覆盖 6 条产品线。核心指标是「日活 UV」，去重 key 为 (app_id, device_id)，单日唯一 device 约 3800 万。

接手第一周就撞墙：增长看板、产品看板、数据仓库三个口径的「7 日 UV」分别是 1.42 亿 / 1.51 亿 / 1.38 亿，差了 9%。不是噪声——是「怎么去重」这件事，三个团队用了三种实现：

增长：Redis PFADD（HyperLogLog，14-bit）
产品：ClickHouse 23.8 uniqCombined64（也是 HLL 变体，但精度参数不同）
数仓：StarRocks 3.1 物化视图，COUNT(DISTINCT device_id) 精确集合

三个数对不上，业务方直接拍桌子。

二、原理与根因：为什么「去重」会分叉

去重计数的本质是基数估计 vs 精确集合。三套方案的根本差异在于：

HyperLogLog（HLL）：用 128/256/…个 6-bit 寄存器存「每个哈希桶里最大前导零」，并集 = 逐寄存器取 max。误差率 ≈ 1.04 / sqrt(m)，m 是寄存器数。
- 7-bit（128 寄存器）：误差 ≈ 9.2%，单分片 1.6 KB
- 14-bit（16384 寄存器）：误差 ≈ 0.08%，单分片 128 KB
- 关键坑：HLL 的并集是「近似并集」，误差随并集次数累积——7 日并集后误差可达单日误差的 1.4~1.8 倍。
RoaringBitmap：把 device_id 哈希成 32-bit 整数，按高 16 位分桶、桶内用 bitmap/array/hybrid 三种编码。并集 = 桶级 OR，结果精确。内存取决于基数分布：3800 万基数、均匀分布下约 180~250 MB；如果 device_id 集中（大量模拟器、爬虫），可能压到 80 MB，偏斜严重时涨到 400 MB。
精确集合（COUNT DISTINCT）：把 device_id 全存下来再 count。3800 万 × 8 字节 ≈ 304 MB / 天，30 天 ≈ 9 GB——这是单分区，多分区后线性膨胀。

根因一句话：HLL 是「估计器」，RoaringBitmap 是「精确集合的压缩」，精确集合是「不压缩的精确集合」。三个团队用了三种，口径自然对不上。

三、具体做法：一套可复现的选型

我们的最终方案：RoaringBitmap 做主口径，HLL 做实时趋势兜底，精确集合做抽样校验。

1. RoaringBitmap 主口径（Flink 1.17 + StarRocks 3.1）

Flink 侧：把 (app_id, device_id) 哈希成 32-bit，按 app_id 分桶写 RoaringBitmap，按 ds（日）+ app_id 落 StarRocks。

-- StarRocks 建表：按日分区，bitmap 列
CREATE TABLE dws_uv (
  ds         DATE,
  app_id     TINYINT,
  uv_bitmap  BITMAP,
  uv_count   INT
)
PARTITION BY date_trunc('day', ds)
DISTRIBUTED BY HASH(app_id) BUCKETS 8;

-- 7 日 UV（精确并集）
SELECT bitmap_count(bitmap_union_agg(uv_bitmap)) AS uv_7d
FROM dws_uv
WHERE ds BETWEEN '2024-06-01' AND '2024-06-07'
  AND app_id = 1;

实测：7 日 UV 查询 P99 180 ms（vs 现算 2.3 亿事件 P99 8.4 s），结果与精确集合一致（误差 0）。

2. HLL 实时趋势兜底（Redis 7.2）

对「实时大盘」用 Redis PFADD，14-bit（PFADD 默认 14-bit，误差 ≈ 0.08%）。每天 24 个 1 小时分片，PFCOUNT 取并集。

# 14-bit HLL，每个分片 128 KB，24 分片 = 3 MB / 天
PFADD uv:{app_id}:{ds}:{hour} {hash1} {hash2} ...
PFCOUNT uv:{app_id}:{ds}:0 uv:{app_id}:{ds}:1 ... uv:{app_id}:{ds}:23

代价：7 日并集误差实测 1.6%~2.3%（vs 单日 0.08%），趋势够用、绝对值不够。

3. 精确集合抽样校验

每天抽 1% 的 device_id（约 38 万），用 COUNT(DISTINCT) 跑精确值，与 RoaringBitmap 对比。连续 30 天 0 偏差（RoaringBitmap 本来就是精确的，这一步是兜底 Flink 侧哈希冲突）。

四、踩过的坑与反直觉

HLL 并集误差会累积，不是恒定的：单 0.08% → 7 日并集 1.6%~2.3%，不是简单的 7×0.08%。这是因为「逐寄存器取 max」操作会放大小寄存器端的方差，并集次数越多、小基数端贡献越大，误差越被放大。
RoaringBitmap 的内存不是「基数 × 1 bit」：均匀分布下 3800 万 ≈ 200 MB，但 device_id 分布偏斜（模拟器、爬虫集中）时能压到 80 MB，也可能涨到 400 MB。上线前必须用真实分布跑一次，别拍脑袋。
哈希冲突是精确集合和 RoaringBitmap 共同的坑：32-bit 哈希在 3800 万基数下，生日悖论期望冲突 ≈ 3800万² / 2 / 2³² ≈ 1700 次——意味着每天约 1700 个 device 会被「合并」，UV 少算 1700。业务方要精确到个位时，必须用 64-bit 哈希（uniqCombined64）。
StarRocks 的 bitmap_union_agg 不支持跨分区流式聚合：跨 30 天分区时内存会爆，必须分天聚合再合并，或换 ClickHouse groupBitmapAndMerge 做流式合并。
「口径一致」不等于「实现一致」：HLL 和 RoaringBitmap 都是「去重」，但并集行为不同——同一个 7 日 UV，两个方案差 1.6%~2.3%。业务方看到的「口径」是并集后的数，不是单日的数。

五、结论与可复用清单

选型决策树：

需要精确绝对值（对账、结算、对外披露）→ RoaringBitmap 或精确集合
需要实时趋势（秒级刷新大盘）→ HLL（14-bit）
需要多日并集且误差 < 0.5% → RoaringBitmap
需要内存 < 100 MB 且能接受 1% 误差 → HLL

可复用清单：

上线前用真实 device_id 分布跑一次 RoaringBitmap 内存，别用均匀分布估算；
HLL 并集误差会累积，7 日并集误差 ≈ 单日的 1.4~1.8 倍，写进口径文档；
32-bit 哈希在千万级基数下期望冲突 ≈ 千次，精确到个位必须 64-bit；
COUNT(DISTINCT) 不是「数个数」，是大集合扫描——3800 万基数下 P99 秒级，别用做实时；
三个口径对不上时，先查「并集行为」再查「精度参数」——90% 的口径漂移来自并集，不是来自单日误差。

赞 0 · 收藏 0 · 评论 0 · 浏览 0

暂无评论。