Something went wrong. Try again.
Metric and Time-Series Engine: A Minimal Archiving Time Series Storage Service
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198package query
import ( "math")
// DownsampleOptions specifies parameters for server-side query downsampling.type DownsampleOptions struct { MaxPoints int // Target maximum number of points (0 = unlimited / raw) StepMS int64 // Time-bucket step in milliseconds (0 = disabled) Method string // Downsampling method: "lttb" (default), "avg", "min", "max", "sum", "count", "none"}
// Downsample reduces the density of a time-series according to the specified options.func Downsample(ts []int64, vals []float64, opts DownsampleOptions) ([]int64, []float64) { if len(ts) <= 2 { return ts, vals }
// 1. Time-bucket step aggregation takes precedence if specified if opts.StepMS > 0 { method := opts.Method if method == "" || method == "lttb" { method = "avg" } return AggregateBuckets(ts, vals, opts.StepMS, method) }
// 2. Maximum point count threshold downsampling if opts.MaxPoints > 0 && len(ts) > opts.MaxPoints { switch opts.Method { case "none", "raw": return ts, vals case "min", "max", "avg", "sum", "count": span := ts[len(ts)-1] - ts[0] step := span / int64(opts.MaxPoints) if step > 0 { return AggregateBuckets(ts, vals, step, opts.Method) } return DownsampleLTTB(ts, vals, opts.MaxPoints) default: // "lttb" return DownsampleLTTB(ts, vals, opts.MaxPoints) } }
return ts, vals}
// DownsampleLTTB implements the Largest Triangle Three Buckets (LTTB) downsampling algorithm.// It downsamples a series of N points down to threshold points while preserving visual shape,// peaks, valleys, and trends. Linear time O(N).func DownsampleLTTB(ts []int64, vals []float64, threshold int) ([]int64, []float64) { n := len(ts) if threshold >= n || threshold <= 0 { return ts, vals } if threshold == 1 { return []int64{ts[0]}, []float64{vals[0]} } if threshold == 2 { return []int64{ts[0], ts[n-1]}, []float64{vals[0], vals[n-1]} }
sampledTS := make([]int64, threshold) sampledVals := make([]float64, threshold)
// Bucket size: divide intermediate points (1 to n-2) into (threshold - 2) buckets every := float64(n-2) / float64(threshold-2)
// First point is always selected sampledTS[0] = ts[0] sampledVals[0] = vals[0] a := 0 // index of previous selected point
for i := 0; i < threshold-2; i++ { // Calculate point average for the next bucket (i + 1) nextStart := int(math.Floor(float64(i+1)*every)) + 1 nextEnd := min(int(math.Floor(float64(i+2)*every))+1, n)
var avgX float64 var avgY float64 nextCount := nextEnd - nextStart if nextCount > 0 { var sumX float64 var sumY float64 for j := nextStart; j < nextEnd; j++ { sumX += float64(ts[j]) sumY += vals[j] } avgX = sumX / float64(nextCount) avgY = sumY / float64(nextCount) } else { avgX = float64(ts[nextStart]) avgY = vals[nextStart] }
// Find point in current bucket i that maximizes triangle area with point a and next bucket average curStart := int(math.Floor(float64(i)*every)) + 1 curEnd := min(int(math.Floor(float64(i+1)*every))+1, n)
ax := float64(ts[a]) ay := vals[a]
maxArea := -1.0 maxIdx := curStart
for j := curStart; j < curEnd; j++ { // Area of triangle: 0.5 * |(Ax - AvgX)*(Y_j - Ay) - (Ax - X_j)*(AvgY - Ay)| // Factor of 0.5 can be omitted as it does not affect the argmax area := math.Abs((ax-avgX)*(vals[j]-ay) - (ax-float64(ts[j]))*(avgY-ay)) if area > maxArea { maxArea = area maxIdx = j } }
sampledTS[i+1] = ts[maxIdx] sampledVals[i+1] = vals[maxIdx] a = maxIdx }
// Last point is always selected sampledTS[threshold-1] = ts[n-1] sampledVals[threshold-1] = vals[n-1]
return sampledTS, sampledVals}
// AggregateBuckets divides the series into fixed time buckets of stepMS duration and// aggregates points within each bucket using method ("avg", "min", "max", "sum", "count").func AggregateBuckets(ts []int64, vals []float64, stepMS int64, method string) ([]int64, []float64) { if len(ts) == 0 || stepMS <= 0 { return ts, vals }
var outTS []int64 var outVals []float64
currentBucket := (ts[0] / stepMS) * stepMS bucketCount := 0 bucketSum := 0.0 bucketMin := vals[0] bucketMax := vals[0]
flushBucket := func() { if bucketCount == 0 { return } var finalVal float64 switch method { case "min": finalVal = bucketMin case "max": finalVal = bucketMax case "sum": finalVal = bucketSum case "count": finalVal = float64(bucketCount) default: // "avg", "mean" finalVal = bucketSum / float64(bucketCount) } outTS = append(outTS, currentBucket) outVals = append(outVals, finalVal) }
for i, t := range ts { b := (t / stepMS) * stepMS if b != currentBucket { flushBucket() currentBucket = b bucketCount = 0 bucketSum = 0.0 bucketMin = vals[i] bucketMax = vals[i] } v := vals[i] bucketSum += v if bucketCount == 0 || v < bucketMin { bucketMin = v } if bucketCount == 0 || v > bucketMax { bucketMax = v } bucketCount++ } flushBucket()
return outTS, outVals}
// Downsample downsamples the SeriesResult points in place according to opts.func (s *SeriesResult) Downsample(opts DownsampleOptions) { if len(s.Timestamps) <= 2 { return } s.Timestamps, s.Values = Downsample(s.Timestamps, s.Values, opts)}