DataDog/sketches-go

# sketches-go [](https://pkg.go.dev/github.com/DataDog/sketches-go/ddsketch) 本代码仓库包含分布式分位数草图算法的 Go 实现。 DDSketch [1]。DDSketch 对 [0, 1] 中的任何分位数 q 都具有相对误差保证。 也就是说，如果第 q 分位数的真实值为 `x`，那么 DDSketch 会返回一个值 `y`， 使得 `|x-y| / x < e`，其中 `e` 是相对误差参数。DDSketch 也是 完全可合并的，这意味着来自分布式系统的多个草图可以在中心节点上进行组合。 我们的默认实现，通过 `NewDefaultDDSketch(relativeAccuracy)` 返回， 保证 [1] 对于任何可由尾部呈次指数分布的数据，其大小都不会过大。 我们还提供了通过 `LogCollapsingLowestDenseDDSketch(relativeAccuracy, maxNumBins)` 和 `LogCollapsingHighestDenseDDSketch(relativeAccuracy, maxNumBins)` 返回的实现， 对于不太小（或不太大）的 q，其 q 分位数将在指定的相对误差范围内保持准确。 具体来说，只要 q 分位数属于草图保留的 `m` 个桶之一，它的误差就在指定的相对误差范围内。 例如，如果值是以秒为单位的时间，`maxNumBins = 2048` 可以覆盖从 80 微秒到 1 年的时间范围。 ### 用法 ``` import "github.com/DataDog/sketches-go/ddsketch" relativeAccuracy := 0.01 sketch := ddsketch.NewDefaultDDSketch(relativeAccuracy) ``` 向草图中添加值。 ``` import "math/rand" for i := 0; i < 500; i++ { v := rand.NormFloat64() sketch.Add(v) } ``` 在 alpha 相对误差范围内查找分位数。 ``` qs := []float64{0.5, 0.75, 0.9, 1} quantiles, err := sketch.GetValuesAtQuantiles(qs) ``` 将另一个 `DDSketch` 合并到 `sketch` 中。 ``` anotherSketch := ddsketch.NewDefaultDDSketch(relativeAccuracy) for i := 0; i < 500; i++ { v := rand.NormFloat64() anotherSketch.Add(v) } sketch.MergeWith(anotherSketch) ``` `sketch` 中的分位数仍然保持在 `relativeAccuracy` 的误差范围内。 ## 参考文献 [1] Charles Masson and Jee E Rim and Homin K. Lee. DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees. PVLDB, 12(12): 2195-2205, 2019. (论文中引用的代码，包括我们 对 Greenwald-Khanna (GK) 算法的实现，可以在以下地址找到： https://github.com/DataDog/sketches-go/releases/tag/v0.0.1 )

标签：EVTX分析, 日志审计