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-Beta2.1 实现历史根据 README 说明该库最初的 v0.1.0 版本基于论文 Better with fewer bits: Improving the performance of cardinality estimation of large data streamsQingjun 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 CountingJason Qin、Denys Kim、Yumei Tung2016。与传统的 LogLog 系列相比LogLog-Beta 用一组预拟合的多项式函数 β(p, ez)做动态偏差校正覆盖从低到高的全部基数范围无需在不同基数段切换估算公式。在源码中可以看到完整证据pkg/../vendor/github.com/axiomhq/hyperloglog/beta.go为精度 p4 到 p18 各定义了一个betaX(ez float64)函数每个都是关于ez和zl ln(ez1)的 7 次多项式系数由 betaMap 统一索引例如 p14默认精度时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 中 m16/32/64 时分别取 0.673/0.697/0.709其余用0.7213/(11.079/m)。这一公式对零寄存器ez做了显式校正兼顾了小基数下的线性计数过渡无需单独维护线性计数分支。2.3 核心特性清单README 明确列出的当前实现关键特性在源码中均有对应特性说明源码位置Metro hash使用github.com/dgryski/go-metro的metro.Hash64(e, 1337)替代 xxhashutils.go稀疏表示低基数时使用tmpSetcompressedList类似 HyperLogLogsparse.go、compressed.goLogLog-Beta 偏差校正全基数范围动态校正beta.go8 位寄存器每个寄存器一个 uint8实现简单regs []uint8hyperloglog.go顺序无关插入与合并结果与数据输入顺序无关Merge、Inserthyperloglog.go去除 tailcut更直接简洁见实现历史灵活精度支持 2^4 ~ 2^18 个寄存器NewSketch(precision, sparse)校验 p∈[4,18]hyperloglog.go三、精度与内存2^4 到 2^18 寄存器的取舍README 给出了明确的内存标尺因为每个寄存器固定为 1 字节精度 p寄存器数内存最小值 p42^4 1616 字节默认值 p142^14 1638416 KB最大值 p182^18 262144256 KB从源码看内存模型因稀疏/稠密两种形态而异稠密形态regs []uint8直接分配m字节hyperloglog.go内存严格等于寄存器数。稀疏形态tmpSet基于intmap.Set[uint32]的哈希集合sparse.gocompressedList变长整数压缩列表compressed.go。低基数时元素很少稀疏形态占用远小于稠密形态。精度选择的工程意义p 每增加 1寄存器数量翻倍内存翻倍但标准误差按1.04/√m比例下降这是 HyperLogLog 家族的通用误差特性README 与源码均未给出更精确的误差承诺此处为算法公理层面的推断。Loki 在实际使用中默认选择 p1416 KB / sketch见下文调用场景。四、两种表示形态与自动转换机制4.1 稀疏形态Sparse创建时若sparsetrueSketch持有tmpSet和sparseListhyperloglog.go。插入时元素先进tmpSetInsertHash哈希编码函数encodeHash将 64 位哈希压缩为 32 位键sparse.go前缀 p 位作索引若中间位全零则记录首个 1 的位置 r编码为idx7 | r1 | 1否则仅存idx1。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其中pp25、mp2^25是稀疏阶段的虚拟寄存器规模。稠密形态下走 LogLog-Beta 公式并四舍五入uint64(est 0.5)。五、顺序无关合并Merge与克隆Clone顺序无关特性是 HyperLogLog 能被用于分布式日志系统的前提。源码中Merge(other *Sketch)hyperloglog.go要求两个 sketch 精度相等p必须一致否则返回precisions must be equal然后按四种组合处理双方稀疏合并tmpSet遍历对方sparseList加入自身tmpSet再触发maybeToNormalhyperloglog.go自身稠密对方稀疏先把自身转稠密再把对方tmpSet/sparseList逐个decodeHash后insert双方稠密逐寄存器取maxhyperloglog.go。由于合并本质是逐位取最大值/并集与元素插入顺序无关因此任意分片、任意顺序聚合后估算结果一致。Clone()hyperloglog.go则提供深拷贝保证共享 sketch 时的隔离性。六、二进制序列化网络传输与持久化的基础Loki 需要把 sketch 从查询分片传回前端合并因此序列化是硬需求。Sketch实现了encoding.BinaryMarshaler与encoding.BinaryAppenderhyperloglog.goAppendBinary采用零拷贝追加式写入配合slices.Grow预分配减少不必要的分配与拷贝。二进制布局大端序[0] version (当前为 2) | [1] p | [2] b(预留) | [3] sparse 标志(1稀疏) 稀疏形态: [tmpSet: 4B 大小 每元素 4B] [sparseList: 4B count 4B last 4B 字节数 变长字节流] 稠密形态: [4B 寄存器数] [m 字节寄存器数组]UnmarshalBinaryhyperloglog.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() // 约等于 37.3 序列化往返data, err : sk.MarshalBinary() // 或 sk.AppendBinary(buf[:0]) 追加写入已有缓冲 restored : hyperloglog.New() if err : restored.UnmarshalBinary(data); err ! nil { // 处理 ErrorTooShort 等错误 }7.4 使用建议基于源码事实默认足够Loki 内部普遍使用New()p1416 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.SketchL33-L37沿查询链路各分片构建 sketch →CountDistinctSketchVector.Merge按分组标签用Sketch.Merge合并L44-L67跨节点传输时通过MarshalBinary序列化为logproto.CountDistinctSketchSample.HyperloglogL184-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 的宽度getCMSWidthL44-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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考