题干与适用场景
这是数据工程和流处理面试题。事件量达到数十亿，查询维度包含小时、租户、地区，结果允许约 1% 的相对误差，但账单、配额和审计仍要求精确值。你需要先问清楚误差预算、时间窗口、迟到范围、是否要集合交并差，以及数据是否包含可识别用户标识。
题库中已有流处理、热点分区和批流架构题；本题聚焦“可合并的基数草图如何改变分布式去重成本”，不把某个数据库产品当作答案。
面试官考察点
- 能否区分 cardinality、membership 和 frequency，避免把 HLL 当成 Bloom filter 或 Count-Min Sketch。
- 能否解释每个分片产生固定大小草图，查询时用逐寄存器最大值合并，而不是汇总局部计数。
- 能否把误差、迟到、重置、隐私和业务精确性转成可验证的契约。
普通回答只说“用 Redis HLL，内存很小”。强回答会先给精确基线，再说明近似方案的失效边界，并定义回放、抽样和漂移监控。
回答前需要澄清的问题
- 结果允许多大误差？ 约 1% 的分析看板可以使用草图；计费或合规报表必须走精确路径或校准流程。
- 查询是固定窗口还是任意时间范围？ 固定小时可保存小时草图；任意范围需要可合并的时间桶，并定义桶边界和保留期。
- 迟到事件最多晚多久？ 迟到范围决定是否重开桶、保留原始事件，或只接受最终化水位线。
- 是否需要交集、差集或列出用户？ HLL 的强项是并集基数；需要成员、交集或删除时要换集合、Theta 等结构或精确补算。
30 秒回答框架
“我先用精确集合作为正确性基线，但它的内存、网络洗牌和跨分片合并成本随唯一用户数增长。若看板允许约 1% 误差，我让每个分片按小时、租户和地区维护固定精度的 HyperLogLog，查询时对同一维度的寄存器取最大值，再用统一估计器输出结果。草图只解决并集基数，不能回答某个用户是否存在，也不能可靠删除。迟到事件按水位线重开有限窗口，超过窗口的修正进入精确回放。最后用全量小样本与精确集合对账，监控相对误差、空桶、重复事件、草图合并和隐私风险。”
分步骤深入解答
第一步：建立精确基线。
对每个 (hour, tenant, region) 保存用户 ID 集合，结果是精确的，但分片必须发送大量 ID 或执行全局 shuffle。若同一用户跨多个分片，局部 COUNT(DISTINCT) 相加会重复计算。
第二步：说明 HLL 的核心状态。
将稳定哈希拆成寄存器索引和前导零长度。每个输入只更新对应寄存器的最大值；估计器由所有寄存器的调和平均类统计量推导，并用小范围修正降低偏差。工程回答不应凭空承诺固定误差，精度由寄存器数量、哈希实现和估计范围共同决定。
第三步：解释分布式合并。
同一维度的草图必须使用相同寄存器数量、哈希规范和编码。合并不是把估计值相加，而是逐寄存器取最大值，因此先按分钟聚合再合并到小时仍能避免原始 ID shuffle。
for each event(user_id, bucket, tenant, region):
i, rank = hash_and_rank(user_id, precision)
sketch[bucket, tenant, region][i] = max(sketch[...][i], rank)
merged[i] = max(sketch_a[i], sketch_b[i])
estimate = hll_estimator(merged)第四步：处理迟到和窗口。
以事件时间分桶，并用水位线标记可最终化的桶。只在最大迟到范围内接受更新；超过范围的事件进入原始日志回放或精确修正表。不能从 HLL 中删除单个用户，因此“撤销一条事件”需要重建受影响桶。
第五步：把近似结果和业务正确性分开。
对账作业随机抽取已关闭桶，用精确集合或离线 SQL 计算真值，记录相对误差、偏差方向和异常维度。计费、配额、隐私删除等路径保留精确账本，草图只作为低成本观测或预估。
第六步：控制成本和隐私。
限制维度组合、桶保留期和每租户草图数量，避免高基数标签生成海量状态。哈希输入应使用受控规范化和密钥轮换策略，访问草图需授权；草图不是匿名化保证，仍可能泄露群体规模。
高质量示范回答
“我会先问结果能不能近似。精确集合适合账单和审计，但在数十亿事件、多个分片和长窗口下会带来内存和 shuffle 压力。看板允许约 1% 误差时，我让每个分片按固定时间桶和维度维护同配置的 HLL。事件经过稳定哈希后更新一个寄存器，查询阶段对各分片寄存器取最大值，再运行同一估计器；绝不能把局部估计值相加。
我会用事件时间和水位线关闭桶，保留有限迟到窗口。窗口外的更正进入原始日志回放，因为 HLL 不能删除单个元素。每个版本记录精度、哈希规范和桶边界，避免不同草图不可合并。监控草图大小、合并延迟、重复事件率和相对误差；抽样桶用精确集合对账。计费和合规删除仍走精确存储，HLL 只是分析加速层。”
常见错误
- 错误表现：把每个分片的估计值相加 → 失败原因：同一用户可能出现在多个分片 → 修正方法：合并寄存器后只估计一次。
- 错误表现：说 HLL 能判断某个用户是否访问过 → 失败原因：它只保留统计摘要 → 修正方法：需要成员查询时使用集合或 Bloom filter，并说明误报。
- 错误表现：迟到或删除事件直接从草图扣除 → 失败原因：寄存器最大值无法逆向定位贡献者 → 修正方法：重建桶或走精确修正表。
- 错误表现：用任意精度和哈希混合合并 → 失败原因：寄存器语义不一致 → 修正方法：把精度、哈希、编码和版本写入草图元数据。
- 错误表现：把草图当作隐私保护 → 失败原因：聚合规模仍可能泄露群体信息 → 修正方法：授权、最小维度、保留期和隐私评估一起设计。
追问及应对
追问一：业务要求查询任意 37 天窗口，怎么组织桶？
按分钟保存会产生较多状态，但查询可以合并连续分钟草图；再用小时和天级草图降低长窗口读取量。多级桶必须明确边界，不能重复包含同一时间段；查询规划器选择不重叠的最粗粒度组合，并在跨层边界用细粒度桶补齐。
追问二：同一用户的删除请求必须在 24 小时内生效，HLL 还能用吗？
HLL 不能执行按用户删除。保留可删除的精确事件索引或加密映射，删除时重建受影响桶并在看板层屏蔽旧版本；草图只作为非权威近似缓存。若法规要求证明删除完成，必须以精确删除账本和回放校验为证据。
追问三：合并后误差突然从 1% 变成 8%，先查什么？
先比较草图元数据：精度、哈希种子、寄存器编码和版本是否一致；再检查某个分片是否把估计值当寄存器、是否重复合并、是否出现异常高频哈希输入。最后用可复现的小集合逐步构造单片、双片和合并结果，定位估计器或序列化错误。