Documentation
¶
Overview ¶
Package sketch implements a hand-rolled DDSketch specialised for request latency aggregation, as decided in ADR-0001.
DDSketch is a quantile sketch with a provable relative-error bound and an exact, associative merge. Both properties are load-bearing for mAPI-ng: merge lets latency roll up (instances into a service, 10s windows into minutes into hours) without accumulating error, and the relative-error bound makes percentile estimates accurate across services whose latencies span microseconds to tens of seconds with zero tuning.
Mapping ¶
This implementation uses the standard logarithmic mapping with a frozen growth factor Gamma = 1.01. A latency v (in seconds) maps to bucket index
index(v) = ceil(log(v) / log(Gamma))
and a bucket index i is estimated back to the value
value(i) = 2 * Gamma^i / (Gamma + 1)
which is the geometric midpoint of the bucket. The guaranteed relative accuracy is (Gamma-1)/(Gamma+1) (~0.4975% for Gamma=1.01): the value returned for a quantile is within that relative error of the true value at that rank.
Storage ¶
The value domain is clamped to [MinValue, MaxValue] = [1e-6, 60.0] seconds. Buckets are held in a fixed-size array (no map) so Add is allocation-free on the hot path. Index i is stored at buckets[i-minIndex]. Values outside the domain are clamped to the domain before mapping, so they always land in the edge buckets and never index out of bounds.
Wire format ¶
Buckets and FromBuckets convert to and from a sparse map keyed by the absolute bucket index, matching the proto map<int32,uint64> on the wire. SketchFormatVersion identifies this bucket layout; Gamma and the value domain are a wire contract and must not change without a format migration.
Index ¶
Constants ¶
const ( MinValue = 1e-6 MaxValue = 60.0 )
MinValue and MaxValue bound the latency domain in seconds (1µs..60s). Values outside this range are clamped before mapping.
const Gamma = 1.01
Gamma is the frozen bucket-growth factor of the logarithmic mapping. It is a wire contract: changing it changes every bucket index and is a breaking format migration.
const SketchFormatVersion uint32 = 1
SketchFormatVersion identifies this bucket layout on the wire. Bump it only alongside a format migration (a change to Gamma or the value domain).
Variables ¶
This section is empty.
Functions ¶
func QuantileFromBuckets ¶
QuantileFromBuckets estimates quantile q in [0, 1] directly from a sparse absolute-index bucket map, mirroring the ClickHouse percentile query so client and server share one definition. It uses the same rank convention as DDSketch.Quantile (rank = ceil(q * total), clamped to [1, total]) and agrees exactly on the same data. It returns 0 for an empty map.
Types ¶
type DDSketch ¶
type DDSketch struct {
// contains filtered or unexported fields
}
DDSketch is a fixed-array DDSketch over the latency domain. The zero value is not usable; construct one with New.
func FromBuckets ¶
FromBuckets reconstructs a sketch from a sparse absolute-index map, the inverse of Buckets. Indices outside the domain are clamped into the edge buckets so reconstruction never panics.
func (*DDSketch) Add ¶
Add records one latency observation in seconds. Values are clamped to [MinValue, MaxValue]; NaN, Inf, and non-positive values are folded to MinValue. Add performs no allocation.
func (*DDSketch) Buckets ¶
Buckets returns the non-zero buckets as a sparse map keyed by absolute bucket index, ready for the wire (proto map<int32,uint64>). Zero buckets are omitted.
func (*DDSketch) Merge ¶
Merge adds another sketch into this one, bucket by bucket. The operation is exact and associative: merging is equivalent to feeding all observations to a single sketch.
func (*DDSketch) Quantile ¶
Quantile returns the estimated value in seconds for quantile q in [0, 1]. It returns 0 for an empty sketch. q is clamped to [0, 1].
The rank convention is rank = ceil(q * count) clamped to [1, count]: the returned bucket is the smallest whose cumulative count reaches that rank. QuantileFromBuckets uses the same convention and agrees exactly.
Source Files