动态数据如何做 dedup

P1 · rag

🏷 标签：dedup, simhash, minhash, data-quality

1️⃣ 考察意图

面试官真正想看的是：你能否在数据流式涌入、无法全量存储的约束下，设计一个可增量更新、低延迟、高精度的去重方案。这是典型的系统设计+工程取舍题，刁钻点在于：动态数据不能像离线批处理那样全量两两比较，必须用近似哈希或索引结构做“在线判重”。答好了能展示你对 SimHash/MinHash 的工程化理解、对精度与速度的权衡能力，以及 RAG 场景下数据质量治理的实战经验。

2️⃣ 标准答

动态数据去重的核心挑战是：数据持续到达，无法一次性全量计算，且要求 O(1) 或 O(log n) 的判重延迟。我采用分层策略，结合精确去重和近似去重，按数据敏感度分级处理。

第一层：精确去重（基于主键或内容哈希）

对结构化数据（如文档 ID、URL），直接用 Redis 或布隆过滤器（Bloom Filter）做精确判重。布隆过滤器用 3-5 个哈希函数，误判率控制在 0.1% 以下，内存占用仅为全量存储的 1/10。
坑：布隆过滤器不支持删除，动态数据中若允许“已删除文档重新加入”，需改用计数布隆过滤器（Counting Bloom Filter）或 Cuckoo Filter，后者支持删除且空间效率更高。

第二层：近似去重（SimHash + 倒排索引）

对非结构化文本（如网页正文、用户评论），用 SimHash 生成 64 位指纹。SimHash 的核心是：将文本分词后，每个词用哈希映射到 64 位向量，按词频加权累加，最后二值化。两个文档的 SimHash 值汉明距离 ≤ 3 时判定为近似重复。
加速查询：将 64 位指纹拆成 4 个 16 位块，每个块作为倒排索引的 key，存储对应指纹列表。查询时，只比较与当前文档至少有一个块相同的指纹，复杂度从 O(n) 降到 O(1)（假设块均匀分布）。
工程取舍：块数越多（如 8 块），召回率越低但速度越快；块数越少（如 2 块），召回率高但内存膨胀。一般选 4 块，汉明距离阈值 3 时召回率约 95%，误判率 < 1%。
实际落地的坑：短文本（< 50 字）SimHash 效果差，因为词频统计不充分。解法：对短文本单独用 MinHash（Jaccard 相似度），或直接降级为精确哈希比较。

第三层：批量聚类（Embedding + 向量数据库）

对需要语义去重的场景（如 RAG 中用户问题去重），用 Sentence-BERT 生成 768 维 embedding，存入 FAISS 或 Milvus 做近似最近邻搜索。阈值设为余弦相似度 0.95，每天凌晨跑一次离线聚类，将重复簇合并。
为什么这么做：SimHash 只能处理词袋级别的重复，无法识别“如何安装 Python”和“Python 安装步骤”这类语义等价。但 embedding 去重延迟高（单次查询 10-50ms），不适合在线流式，所以只做离线补充。

第四层：监控与回滚

实时监控重复率（重复文档数 / 总文档数）和大簇数量（簇内文档 > 10 的簇）。若重复率突增 20%，触发告警并回滚到上一版本的去重配置（如降低 SimHash 阈值或切换哈希函数）。

3️⃣ 答题模板（30 秒电梯版）

“这个问题我从精确去重、近似去重、语义去重三个层面回答。精确层用布隆过滤器或 Redis 做主键判重；近似层用 SimHash + 倒排索引实现 O(1) 在线判重，汉明距离阈值设为 3；语义层用 embedding 离线聚类补充。总结一句：动态去重的核心是用空间换时间，通过分块索引和分层策略平衡精度与延迟。”

4️⃣ 高频追问 & 应对

追问 1：SimHash 的汉明距离阈值怎么调？为什么是 3 不是 5？

阈值取决于数据分布和业务容忍度。通用经验：64 位 SimHash 对长文本（> 200 字）汉明距离 ≤ 3 时，召回率约 95%，误判率 < 1%；若阈值设为 5，召回率升到 99% 但误判率飙到 5%，导致大量非重复文档被误杀。实际调优时，我会采样 1000 对人工标注的重复/非重复文档，绘制 PR 曲线，选 F1 最高的点。如果业务对召回要求极高（如法律文档去重），可接受 5% 误判，阈值就设 5；如果对精度要求高（如搜索索引去重），阈值就压到 2。

追问 2：如果数据量达到 10 亿级别，SimHash 的倒排索引内存放不下怎么办？

分片 + 降维。首先，将 64 位指纹拆成 8 个 8 位块，每个块对应一个分片（Shard），用一致性哈希分布到多台机器。查询时，同时访问 8 个分片，取并集后比较汉明距离。其次，对每个分片内的指纹用布隆过滤器做预过滤，只保留可能匹配的指纹，减少内存占用。实测 10 亿数据用 8 台 32GB 机器可承载，单次查询延迟 < 5ms。

追问 3：RAG 场景中，去重应该在索引前做还是检索后做？

两个阶段都要做，但目的不同。索引前去重：用 SimHash 过滤重复文档，避免向量数据库存储膨胀和检索噪声。检索后去重：对召回的 top-k 结果用 embedding 相似度做二次去重，防止同一语义的多个片段重复输出给 LLM。工程上，索引前去重用 SimHash（低延迟），检索后去重用 embedding（高精度），两者互补。

5️⃣ 避坑 · 常见错误答法

❌ “直接用 MD5 哈希做精确去重，又快又准。” → ✅ “MD5 只能处理完全相同的文档，对近似重复（如拼写错误、格式差异）无效。动态数据中大量是近似重复，必须用 SimHash 或 MinHash 这类局部敏感哈希。”
❌ “用 embedding 相似度做在线去重，效果好。” → ✅ “Embedding 去重延迟高（单次 10-50ms），不适合流式场景。正确做法是：在线用 SimHash 快速过滤，离线用 embedding 做精细聚类。”
❌ “布隆过滤器误判率低，可以放心用。” → ✅ “布隆过滤器不支持删除，动态数据中若文档被删除后重新加入，会导致误判。必须用计数布隆过滤器或 Cuckoo Filter 支持删除操作。”

6️⃣ 简历呼应

如果你有 RAG 项目：从“索引前 SimHash 去重 + 检索后 embedding 去重”切入，强调你如何监控重复率并调优阈值，避免 LLM 输出重复内容。
如果你只做过传统 NLP：用“文本分类中的特征哈希”类比 SimHash，说明你理解哈希函数的碰撞概率和分块索引的加速原理。
如果你是校招无项目：聚焦 SimHash 论文（《Detecting Near-Duplicates for Web Crawling》）的复现 demo，展示你实现了 64 位指纹生成和倒排索引查询，并对比了不同阈值下的 PR 曲线。
《Detecting Near-Duplicates for Web Crawling》（SimHash 原始论文）
《On the Resemblance and Containment of Documents》（MinHash 原始论文）
《Cuckoo Filter: Practically Better Than Bloom》（Cuckoo Filter 论文）
FAISS 官方文档：近似最近邻搜索的索引选择指南
《RAG 系统中数据去重的最佳实践》（博客，可搜索）

—— 本场面试完 ——