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 状态与合并
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。