《大规模分布式计算深入解析》5.2 count distinct 与 HyperLogLog 近似

精确去重需要保留区分真实值的能力。HyperLogLog 以误差换状态体积,适合允许近似的指标。

5.2 count distinct 与 HyperLogLog 近似

精确去重需要保留区分真实值的能力。HyperLogLog 以误差换状态体积,适合允许近似的指标。

精确与近似的分布式状态

对整数值,1000 万个 8 B 原值的载荷为 80 MB,尚未计入散列表元数据。变长值仅保留 64 位散列会引入碰撞。精确算法还可用外排,或先按 (group_key, value) 重分区再去重,让后续局部计数对应互斥值集合。

HLL 在相同精度、兼容 Hash 和编码协议下以逐寄存器最大值合并。取 p=14 时有 16384 个寄存器。教学布局每个占一字节,总计 16 KiB;产品可能用稀疏或压缩表示。经典近似的相对标准误差约为 1.04 / sqrt(16384) = 0.8125%,它描述估计分布,单次误差可超过该值。这个布局相比 80 MB 原值载荷约少 99.98%,状态开销与结果语义都要单列。对相同数据和多个基数比较精确值、近似值和实际可序列化大小。

实验与资料

下载卷六实验包 ,参照包内 README。src/ 下的 Java 8 教学模型。本章架构或流程见本章机制图 。

Trino 聚合与 NULL 语义 · Trino HyperLogLog 状态与合并

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图