企业官网建设流程全解析

Grafana Loki 中 HyperLogLog 基数估算库的算法原理与 Go 实现解析

【免费下载链接】lokiLike Prometheus, but for logs.项目地址: https://gitcode.com/GitHub_Trending/lok/loki

导读：本文聚焦 Loki 仓库 vendored 的 axiomhq/hyperloglog Go 实现，讲解其基于 LogLog-Beta 算法的基数估算（count-distinct）原理、稀疏表示与稠密表示的内存模型、精度与内存的取舍关系，并结合源码展示它在 Loki 的 LogQL 近似去重、detected fields 等真实场景中如何被调用。读完你将理解 HyperLogLog 的完整实现链路，掌握如何在本项目中选择精度、进行合并与序列化，以及它为何能支撑 Loki 的海量日志基数统计。

一、HyperLogLog 是什么：count-distinct 问题的近似解法

在日志与指标系统中，"某个时间窗口内一共有多少个不同的取值"（即基数、cardinality）是最常见也最难精确回答的问题之一。精确解法（HashSet）随元素个数线性增长，在海量数据下既不省内存也不易并行合并。HyperLogLog 是解决 count-distinct 问题的经典概率算法：它用固定大小的寄存器数组去近似一个多重集合中的去重元素数量，用很少的内存换取可接受的精度误差。

Loki 仓库将 axiomhq/hyperloglog 作为第三方依赖引入（位于 vendor 目录），并在 pkg/logql/approx_count_distinct.go、pkg/logql/count_min_sketch.go、pkg/logql/sketch/topk.go、pkg/storage/detected/fields.go 等多处使用它。理解这个库，就等于理解 Loki 做近似去重统计的底层引擎。

二、算法演进：从 tailcut 到 LogLog-Beta

2.1 实现历史

根据 README 说明，该库最初的 v0.1.0 版本基于论文 "Better with fewer bits: Improving the performance of cardinality estimation of large data streams"（Qingjun Xiao、You Zhou、Shigang Chen）实现，使用tailcut方法。而当前实现已彻底演化，移除了 tailcut 方法，改采更直接、更简洁的路线。

2.2 当前核心：LogLog-Beta 算法

当前实现基于 LogLog-Beta 算法（论文LogLog-Beta and More: A New Algorithm for Cardinality Estimation Based on LogLog Counting，Jason Qin、Denys Kim、Yumei Tung，2016）。与传统的 LogLog 系列相比，LogLog-Beta 用一组预拟合的多项式函数 β(p, ez)做动态偏差校正，覆盖从低到高的全部基数范围，无需在不同基数段切换估算公式。

在源码中可以看到完整证据：pkg/../vendor/github.com/axiomhq/hyperloglog/beta.go为精度 p=4 到 p=18 各定义了一个betaX(ez float64)函数，每个都是关于ez和zl = ln(ez+1)的 7 次多项式，系数由 betaMap 统一索引，例如 p=14（默认精度）时：

func beta14(ez float64) float64 { zl := math.Log(ez + 1) return -0.371009760230692*ez + 0.00978811941207509*zl + 0.185796293324165*math.Pow(zl, 2) + 0.203015527328432*math.Pow(zl, 3) + -0.116710521803686*math.Pow(zl, 4) + 0.0431106699492820*math.Pow(zl, 5) + -0.00599583540511831*math.Pow(zl, 6) + 0.000449704299509437*math.Pow(zl, 7) }

估算公式在 hyperloglog.go 的Estimate()中直接体现：

est := sk.alpha * m * (m - ez) / (sum + beta(sk.p, ez))

其中sum = Σ 2^(-reg[i])，ez是值为 0 的寄存器数量，m = 2^p为寄存器总数，alpha为对应精度的校正常数（utils.go 中 m=16/32/64 时分别取 0.673/0.697/0.709，其余用0.7213/(1+1.079/m)）。这一公式对零寄存器（ez）做了显式校正，兼顾了小基数下的线性计数过渡，无需单独维护线性计数分支。

2.3 核心特性清单

README 明确列出的当前实现关键特性，在源码中均有对应：

三、精度与内存：2^4 到 2^18 寄存器的取舍

README 给出了明确的内存标尺，因为每个寄存器固定为 1 字节：

从源码看，内存模型因稀疏/稠密两种形态而异：

• 稠密形态：regs []uint8直接分配m字节（hyperloglog.go），内存严格等于寄存器数。
• 稀疏形态：tmpSet（基于intmap.Set[uint32]的哈希集合，sparse.go）+compressedList（变长整数压缩列表，compressed.go）。低基数时元素很少，稀疏形态占用远小于稠密形态。

精度选择的工程意义：p 每增加 1，寄存器数量翻倍，内存翻倍，但标准误差按1.04/√m比例下降（这是 HyperLogLog 家族的通用误差特性，README 与源码均未给出更精确的误差承诺，此处为算法公理层面的推断）。Loki 在实际使用中默认选择 p=14（16 KB / sketch），见下文调用场景。

四、两种表示形态与自动转换机制

4.1 稀疏形态（Sparse）

创建时若sparse=true，Sketch持有tmpSet和sparseList（hyperloglog.go）。插入时元素先进tmpSet（InsertHash），哈希编码函数encodeHash将 64 位哈希压缩为 32 位键（sparse.go）：前缀 p 位作索引，若中间位全零则记录首个 1 的位置 r，编码为idx<<7 | r<<1 | 1，否则仅存idx<<1。

4.2 稠密形态（Dense）

当元素增多后，maybeToNormal()（hyperloglog.go）触发转换条件：tmpSet大小超过m/100时先合并稀疏列表，若稀疏列表长度仍超过m则调用toNormal()（hyperloglog.go）一次性转为稠密regs数组。此后插入走getPosVal计算寄存器索引与 rho 值，直接regs[i] = max(r, regs[i])（hyperloglog.go）。

4.3 估算

• 稀疏形态下：先mergeSparse()落盘，再用线性计数linearCount(mp, mp-count)估算（hyperloglog.go、utils.go），其中pp=25、mp=2^25是稀疏阶段的虚拟寄存器规模。
• 稠密形态下：走 LogLog-Beta 公式并四舍五入（uint64(est + 0.5)）。

五、顺序无关：合并（Merge）与克隆（Clone）

顺序无关特性是 HyperLogLog 能被用于分布式日志系统的前提。源码中Merge(other *Sketch)（hyperloglog.go）要求两个 sketch 精度相等（p必须一致，否则返回"precisions must be equal"），然后按四种组合处理：

• 双方稀疏：合并tmpSet，遍历对方sparseList加入自身tmpSet，再触发maybeToNormal（hyperloglog.go）；
• 自身稠密对方稀疏：先把自身转稠密，再把对方tmpSet/sparseList逐个decodeHash后insert；
• 双方稠密：逐寄存器取max（hyperloglog.go）。

由于合并本质是"逐位取最大值/并集"，与元素插入顺序无关，因此任意分片、任意顺序聚合后估算结果一致。Clone()（hyperloglog.go）则提供深拷贝，保证共享 sketch 时的隔离性。

六、二进制序列化：网络传输与持久化的基础

Loki 需要把 sketch 从查询分片传回前端合并，因此序列化是硬需求。Sketch实现了encoding.BinaryMarshaler与encoding.BinaryAppender（hyperloglog.go），AppendBinary采用零拷贝追加式写入，配合slices.Grow预分配，减少不必要的分配与拷贝。

二进制布局（大端序）：

[0] version (当前为 2) | [1] p | [2] b(预留) | [3] sparse 标志(1=稀疏) 稀疏形态: [tmpSet: 4B 大小 + 每元素 4B] + [sparseList: 4B count + 4B last + 4B 字节数 + 变长字节流] 稠密形态: [4B 寄存器数] + [m 字节寄存器数组]

UnmarshalBinary（hyperloglog.go）兼容 v1（半字节打包寄存器）与 v2（每寄存器 1 字节）两种格式，ErrorTooShort用于防御截断数据（hyperloglog.go）。

七、快速上手：API 使用全景

7.1 构造

import "github.com/axiomhq/hyperloglog" sk := hyperloglog.New() // 等价于 New14()，2^14 寄存器 + 稀疏 sk14 := hyperloglog.New14() // 2^14 寄存器 sk16 := hyperloglog.New16() // 2^16 寄存器 skNS := hyperloglog.NewNoSparse() // 2^14 寄存器，不使用稀疏表示 sk16NS := hyperloglog.New16NoSparse() // 任意精度 + 可选稀疏，p 必须在 [4, 18] sk, err := hyperloglog.NewSketch(10, true)

构造函数族定义在 hyperloglog.go。注意NewSketch会校验精度范围，返回"p has to be >= 4 and <= 18"错误（hyperloglog.go）。

7.2 插入、估算、合并

sk.Insert([]byte("user-1")) sk.Insert([]byte("user-2")) sk.InsertHash(1337) // 或直接插入预计算好的 64 位哈希 count := sk.Estimate() // uint64 近似基数 // 分布式合并：要求双方精度一致 other := hyperloglog.New() other.Insert([]byte("user-2")) other.Insert([]byte("user-3")) if err := sk.Merge(other); err != nil { // 处理 "precisions must be equal" } merged := sk.Estimate() // 约等于 3

7.3 序列化往返

data, err := sk.MarshalBinary() // 或 sk.AppendBinary(buf[:0]) 追加写入已有缓冲 restored := hyperloglog.New() if err := restored.UnmarshalBinary(data); err != nil { // 处理 ErrorTooShort 等错误 }

7.4 使用建议（基于源码事实）

• 默认足够：Loki 内部普遍使用New()（p=14，16 KB/sketch），在该精度下 1.04/√2^14 ≈ 0.81% 的理论标准误差是 HyperLogLog 家族通用特性；
• 更高精度：当基数极大且内存充裕时用New16()（64 KB）或NewSketch(18, ...)（256 KB）；
• 省内存：低基数高并发场景可用NewNoSparse()省去稀疏层的哈希集合开销，但低基数下内存不再按实际元素数伸缩；
• 合并前先对齐精度：不同精度的 sketch 无法直接合并，分布式场景务必统一精度参数。

八、Loki 中的真实应用：LogQL 近似去重与 detected fields

该库在 Loki 中并非孤立存在，而是构成多项查询能力的底座（均为仓库内可验证的实现事实）。

8.1 LogQL 的 count distinct 近似查询

pkg/logql/approx_count_distinct.go 中，countDistinctSketch(samples)（L332-L338）对每个时间窗内的浮点采样值调用hyperloglog.New14()并InsertHash(math.Float64bits(sample.F))构建 sketch。这些 sketch 被封装进CountDistinctSketchSample（字段F *hyperloglog.Sketch，L33-L37），沿查询链路：

• 各分片构建 sketch →CountDistinctSketchVector.Merge按分组标签用Sketch.Merge合并（L44-L67）；
• 跨节点传输时通过MarshalBinary序列化为logproto.CountDistinctSketchSample.Hyperloglog（L184-L198），接收端用hyperloglog.New14()+UnmarshalBinary还原（L201-L218）；
• 最终Estimate()转成普通采样向量输出（L121-L131）。

整个链路恰好完整使用了本库的插入、合并、序列化、估算四大能力，这正是"顺序无关合并"在分布式查询中的价值体现。相关测试见 pkg/logql/approx_count_distinct_test.go。

8.2 TopK 近似统计中的基数锚点

pkg/logql/sketch/topk.go 的Topk结构将*hyperloglog.Sketch作为expectedCardinality的估算器：先用 HLL 估算事件基数，再据此挑选 Count-Min Sketch 的宽度（getCMSWidth，L44-L60），实现"按基数自适应分配 sketch 尺寸"的省内存策略。

8.3 Detected Fields 的基数统计

pkg/storage/detected/fields.go 为每个 detected field 维护一个*hyperloglog.Sketch（用hyperloglog.New()创建），用于统计日志字段的取值基数；pkg/querier/queryrange/detected_fields.go 与 pkg/dataobj/internal/dataset/column_stats.go 同样引用该库做基数统计，相关测试见 pkg/storage/detected/fields_test.go。

九、小结

axiomhq/hyperloglog 用 LogLog-Beta 算法替代了传统的 tailcut 方案，以 Metro hash 提供高质量哈希、以稀疏+稠密双形态在低基数与高基数间自动切换、以 8 位寄存器和 [4,18] 的灵活精度让使用者按 16B ~ 256KB 的内存预算自由取舍。结合 Loki 的源码可以看到，它的"顺序无关合并 + 二进制序列化"能力，正是分布式日志查询中近似去重、TopK 统计与字段基数分析得以落地的基础。需要深入源码的读者可继续阅读 hyperloglog.go（核心 Sketch 与估算）、beta.go（偏差校正多项式）、sparse.go（稀疏编码）与 compressed.go（变长压缩列表）。

【免费下载链接】lokiLike Prometheus, but for logs.项目地址: https://gitcode.com/GitHub_Trending/lok/loki