高基数字段（user_id/device_id）的质量校验怎么做才不爆内存？

数据质量手册第 15 题约 11 分钟读完

本文目录

先说结论
传统COUNT(DISTINCT)为什么慢？
方案一：HyperLogLog（HLL）—— 近似去重的神器
方案二：BitMap —— 稠密ID集合的最优选
方案三：BloomFilter —— 「是否存在」校验
四种算法性能对比
唯一性校验的优化技巧
面试高频追问
实战踩坑：精确算法跑8小时跑不完的事故
总结

先说结论

高基数字段校验的核心是「换算法」。COUNT(DISTINCT)精确但贵；HyperLogLog近似但快1000倍；BitMap适合稠密ID集合；BloomFilter适合「是否存在」校验。每种算法都有适用边界。

质量校验不一定要100%精确。生产实践里，「不重复率99.99%」和「不重复率99.991%」对DQC告警没区别。用近似算法换性能，是工程师必备意识。

先把这段讲顺；面试官追问时，再展开下面的原理和细节。

详细讲解

「校验user_id唯一性」「统计device_id去重数」——这种看似简单的DQC规则，在亿级以上数据量下经常把集群跑挂。COUNT(DISTINCT)动辄OOM、Shuffle数据爆炸、跑8小时跑不完。这道题考的是工程优化能力。我在出海硬件公司处理过一张50亿行的事件表，user_id去重是基础DQC，普通写法跑不出来，用近似算法10秒搞定。今天聊聊高基数字段的质量校验怎么优化。

传统COUNT(DISTINCT)为什么慢？

-- 经典写法：50亿行的表
SELECT COUNT(DISTINCT user_id) FROM dwd_event WHERE dt = '20240315';
-- 在出海硬件公司Spark上跑过：
-- - Shuffle数据量：800GB+
-- - 单Reducer内存压力：5GB+ → OOM
-- - 总耗时：3小时未完成被kill

根因：COUNT(DISTINCT)需要把所有不同值汇聚到单个Reducer去重，数据量越大越慢。即使有AQE自动调优，本质上还是「全量Shuffle+全量去重」。

方案一：HyperLogLog（HLL）—— 近似去重的神器

HyperLogLog是基数估计算法，用极少内存估算唯一值数量。Spark/Presto/Hologres都内置支持：

-- Spark/Hive：approx_count_distinct
SELECT APPROX_COUNT_DISTINCT(user_id) AS uv
FROM dwd_event WHERE dt = '20240315';
-- 50亿行表，秒级返回，误差<2%
-- 默认精度RSD=0.05，可调到0.01但内存翻倍
 
-- Hologres/Doris：直接支持HLL类型
CREATE TABLE dws_user_hll (
  dt DATE,
  user_hll HLL  -- HLL类型字段
);
 
-- 增量构建HLL
INSERT INTO dws_user_hll
SELECT dt, HLL_HASH_AGG(user_id) FROM dwd_event GROUP BY dt;
 
-- 查询时跨日合并
SELECT HLL_CARDINALITY(HLL_UNION_AGG(user_hll))
FROM dws_user_hll WHERE dt BETWEEN '2024-03-01' AND '2024-03-31';

适用场景：UV、独立设备数、独立IP数等基数监控；DQC的去重率粗略估算。

不适用：精确去重场景（财务对账、监管报送）；唯一性校验（要找具体重复ID）。

方案二：BitMap —— 稠密ID集合的最优选

如果ID是连续整数（比如自增user_id 1~10亿），BitMap比HLL更精确且更快：

-- Doris/StarRocks原生支持BitMap
CREATE TABLE dws_user_bitmap (
  dt DATE,
  user_bm BITMAP  -- BitMap字段
) AGGREGATE KEY(dt);
 
-- 构建BitMap
INSERT INTO dws_user_bitmap
SELECT dt, BITMAP_AGG(user_id) FROM dwd_event GROUP BY dt;
 
-- 精确UV（无误差）
SELECT BITMAP_COUNT(BITMAP_OR_AGG(user_bm))
FROM dws_user_bitmap WHERE dt BETWEEN '2024-03-01' AND '2024-03-31';
 
-- 留存率：3月1日活跃 ∩ 3月8日活跃
SELECT BITMAP_COUNT(BITMAP_AND(
  (SELECT user_bm FROM dws_user_bitmap WHERE dt='2024-03-01'),
  (SELECT user_bm FROM dws_user_bitmap WHERE dt='2024-03-08')
))

BitMap优点：精确（不像HLL有误差）、超高性能（位运算）、支持交并差。

BitMap限制：ID必须是整数；ID范围越稠密效率越高；如果ID稀疏（比如UUID）建议先做字典编码（Hash映射成连续int）。

方案三：BloomFilter —— 「是否存在」校验

DQC经常需要校验「这批ID是否在白名单内」「这条数据是否已经处理过」——这是BloomFilter的主战场。

# 场景：校验10亿行的事件表里user_id是否都在dim_user里
# 传统方式：JOIN校验，Shuffle爆炸
# BloomFilter方式：
 
from pybloom_live import BloomFilter
 
# Step 1: 用dim_user构建BloomFilter（先放小的一边）
bf = BloomFilter(capacity=1e8, error_rate=0.001)
for uid in dim_user.collect():  # 1亿用户
    bf.add(uid)
broadcast_bf = sc.broadcast(bf)
 
# Step 2: 大表用BloomFilter快速过滤
miss_cnt = dwd_event.filter(
    lambda row: row.user_id not in broadcast_bf.value
).count()
 
# 如果miss_cnt > 0，再用JOIN精确定位miss的具体ID
if miss_cnt > 0:
    miss_users = dwd_event.join(dim_user, 'user_id', 'left_anti')

BloomFilter的妙处：先用它做快速排除（99.9%的数据都通过校验），只对剩下的0.1%可疑数据做精确JOIN。把10亿行级别的JOIN问题简化成几万行的JOIN问题。

四种算法性能对比

算法	精度	内存占用	性能	适用
COUNT(DISTINCT)	100%	极高（GB级Shuffle）	慢（数小时）	<1亿行精确去重
HyperLogLog	~98%	极低（KB-MB）	极快（秒级）	UV、独立数估算
BitMap	100%	中（取决于ID密度）	快（位运算）	整数稠密ID精确去重
BloomFilter	100%（存在判断）	低（几MB）	快（O(1)查询）	白名单/黑名单校验

唯一性校验的优化技巧

「找出所有重复的user_id」是DQC高频需求，但传统COUNT(*) GROUP BY user_id HAVING COUNT(*) > 1非常慢。两种优化：

-- 优化1：先采样找重复，再精确确认
-- Step 1: 采样1%数据快速发现重复模式
WITH sample AS (
  SELECT user_id FROM dwd_event TABLESAMPLE(1 PERCENT)
  WHERE dt = '20240315'
)
SELECT user_id, COUNT(*) FROM sample
GROUP BY user_id HAVING COUNT(*) > 1;
 
-- Step 2: 对采样发现的可疑ID精确校验
-- 比全表扫描快100倍
 
-- 优化2：用Hash分桶并行去重
-- 把10亿数据按hash(user_id) % 100分100桶
-- 每桶独立去重，最后合并
WITH bucketed AS (
  SELECT user_id, HASH(user_id) % 100 AS bucket
  FROM dwd_event WHERE dt = '20240315'
)
SELECT user_id, COUNT(*) FROM bucketed
GROUP BY user_id, bucket HAVING COUNT(*) > 1;
-- 配合AQE自动倾斜处理，性能提升5-10倍

面试高频追问

追问一：HLL的误差怎么控制？

HLL的误差和「桶数」相关。Spark的approx_count_distinct默认RSD=0.05（5%误差），桶数=2^14=16384。把RSD调到0.01（1%误差），桶数变2^18=262144，内存翻16倍但还是远比精确算法省。生产实践里我用0.02-0.05足够，DQC告警精度足够。

追问二：BitMap和HLL怎么选？

看ID类型和精度要求：①整数稠密ID + 要精确 → BitMap；②任意类型ID或巨大range或允许误差 → HLL；③需要交集（留存计算）→ BitMap强于HLL（HLL支持并集但交集需要包含-排除原理估算）。我在出海硬件公司user_id是连续int用BitMap，device_id是UUID字符串用HLL，分场景用。

追问三：实时DQC怎么做高基数校验？

Flink内置HLL支持（DISTINCT开启增量HLL状态）；BitMap可以用RoaringBitmap（压缩BitMap）落到State Backend；BloomFilter做实时白名单校验。关键是「状态TTL」——高基数字段的状态会一直膨胀，必须定期清理或分窗口存。我在某元宇宙社交应用做过实时UV，用Flink+RoaringBitmap，QPS 10万+稳定运行。

实战踩坑：精确算法跑8小时跑不完的事故

出海硬件公司有张「设备激活事件表」，单日50亿行，DQC需要校验device_id唯一性。原同学写了：

-- 原始SQL（看起来很正常）
SELECT device_id, COUNT(*) AS cnt
FROM dwd_device_activate
WHERE dt = '20240315'
GROUP BY device_id
HAVING COUNT(*) > 1;

这条SQL在Spark集群跑了8小时被超时kill，DQC一直处于「未通过」状态阻断下游。我接手后做了三步优化：

1）先用approx_count_distinct估总UV，发现约48亿——基本不重复（重复率<5%）

2）改成「先粗后细」：先采样1%找可疑pattern，再对可疑ID精确校验

3）配合AQE自动倾斜处理，最后SQL跑15分钟出结果

-- 优化后的两阶段方案
-- 阶段1: 先看「是否有重复」（HLL估算）
SELECT COUNT(*) AS total_rows,
       APPROX_COUNT_DISTINCT(device_id) AS approx_uv,
       COUNT(*) - APPROX_COUNT_DISTINCT(device_id) AS approx_dup
FROM dwd_device_activate WHERE dt = '20240315';
-- 如果approx_dup接近0，说明几乎不重复，DQC直接PASS
 
-- 阶段2: 如果approx_dup有量级，再精确找出重复
-- 用hash分桶并行处理
SELECT device_id, COUNT(*) AS cnt
FROM dwd_device_activate WHERE dt = '20240315'
GROUP BY device_id, HASH(device_id) % 200
HAVING COUNT(*) > 1;

教训：DQC不是「越精确越好」，是「在精度满足要求的前提下越快越好」。生产环境的高基数校验必须考虑算法成本，硬怼精确算法只会让DQC变成性能瓶颈。这种意识是中级到高级的分水岭。

总结

高基数字段校验：HLL（估算UV）、BitMap（稠密ID精确）、BloomFilter（存在校验）。算法选型按精度+ID类型+性能权衡。DQC不必死磕精确，先粗后细+采样+分桶是工程优化的标配。面试时把算法对比+两阶段方案+50亿行的故事讲完，工程功底立显。

下一篇聊一个数据源头治理的话题：埋点数据30%是脏的——埋点质量从SDK到数仓的端到端治理。

你们生产环境去重用什么算法？踩过什么性能坑？评论区聊聊～

关注「Wood聊大数据」| 9年大数据老兵，聊技术、聊职场、聊成长

数据质量面试通关手册

第16-20篇：Schema、契约、止损

Wood聊大数据

9年大数据老兵，聊技术、聊职场、聊成长

刷题进度保存在当前浏览器