Debian Codegraph @

sdk/metric/internal/aggregate/exponential_histogram.go

raw
1 // Copyright The OpenTelemetry Authors
2 // SPDX-License-Identifier: Apache-2.0
3
4 package aggregate // import "go.opentelemetry.io/otel/sdk/metric/internal/aggregate"
5
6 import (
7 "context"
8 "errors"
9 "math"
10 "sync"
11 "sync/atomic"
12 "time"
13
14 "go.opentelemetry.io/otel"
15 "go.opentelemetry.io/otel/attribute"
16 "go.opentelemetry.io/otel/sdk/internal/x"
17 "go.opentelemetry.io/otel/sdk/metric/metricdata"
18 )
19
20 const (
21 expoMaxScale = 20
22 expoMinScale = -10
23
24 smallestNonZeroNormalFloat64 = 0x1p-1022
25 )
26
27 // expoHistogramDataPoint is a single data point in an exponential histogram.
28 type expoHistogramDataPoint[N int64 | float64] struct {
29 attrs attribute.Set
30 res FilteredExemplarReservoir[N]
31
32 minMax atomicMinMax[N]
33 sum atomicCounter[N]
34
35 maxSize int
36 noMinMax bool
37 noSum bool
38
39 scale atomic.Int32
40
41 posBuckets expoBuckets
42 negBuckets expoBuckets
43 zeroCount atomic.Uint64
44 startTime time.Time
45 }
46
47 func newExpoHistogramDataPoint[N int64 | float64](
48 attrs attribute.Set,
49 maxSize int,
50 maxScale int32,
51 noMinMax, noSum bool,
52 ) *expoHistogramDataPoint[N] { // nolint:revive // we need this control flag
53 dp := &expoHistogramDataPoint[N]{
54 attrs: attrs,
55 maxSize: maxSize,
56 noMinMax: noMinMax,
57 noSum: noSum,
58 startTime: now(),
59 }
60 dp.scale.Store(maxScale)
61 return dp
62 }
63
64 // record adds a new measurement to the histogram. It will rescale the buckets if needed.
65 func (p *expoHistogramDataPoint[N]) record(v N) {
66 if !p.noMinMax {
67 p.minMax.Update(v)
68 }
69 if !p.noSum {
70 p.sum.add(v)
71 }
72
73 absV := math.Abs(float64(v))
74
75 if float64(absV) == 0.0 {
76 p.zeroCount.Add(1)
77 return
78 }
79
80 bin := p.getBin(absV)
81
82 bucket := &p.posBuckets
83 if v < 0 {
84 bucket = &p.negBuckets
85 }
86
87 // If the new bin would make the counts larger than maxScale, we need to
88 // downscale current measurements.
89 if scaleDelta := p.scaleChange(bin, bucket.startBin, len(bucket.counts)); scaleDelta > 0 {
90 currentScale := p.scale.Load()
91 if currentScale-scaleDelta < expoMinScale {
92 // With a scale of -10 there is only two buckets for the whole range of float64 values.
93 // This can only happen if there is a max size of 1.
94 otel.Handle(errors.New("exponential histogram scale underflow"))
95 return
96 }
97 // Downscale
98 p.scale.Add(-scaleDelta)
99 p.posBuckets.downscale(scaleDelta)
100 p.negBuckets.downscale(scaleDelta)
101
102 bin = p.getBin(absV)
103 }
104
105 bucket.record(bin)
106 }
107
108 // getBin returns the bin v should be recorded into.
109 func (p *expoHistogramDataPoint[N]) getBin(v float64) int32 {
110 frac, expInt := math.Frexp(v)
111 // 11-bit exponential.
112 exp := int32(expInt) // nolint: gosec
113 scale := p.scale.Load()
114 if scale <= 0 {
115 // Because of the choice of fraction is always 1 power of two higher than we want.
116 var correction int32 = 1
117 if frac == .5 {
118 // If v is an exact power of two the frac will be .5 and the exp
119 // will be one higher than we want.
120 correction = 2
121 }
122 return (exp - correction) >> (-scale)
123 }
124 return exp<<scale + int32(math.Log(frac)*scaleFactors[scale]) - 1
125 }
126
127 // scaleFactors are constants used in calculating the logarithm index. They are
128 // equivalent to 2^index/log(2).
129 var scaleFactors = [21]float64{
130 math.Ldexp(math.Log2E, 0),
131 math.Ldexp(math.Log2E, 1),
132 math.Ldexp(math.Log2E, 2),
133 math.Ldexp(math.Log2E, 3),
134 math.Ldexp(math.Log2E, 4),
135 math.Ldexp(math.Log2E, 5),
136 math.Ldexp(math.Log2E, 6),
137 math.Ldexp(math.Log2E, 7),
138 math.Ldexp(math.Log2E, 8),
139 math.Ldexp(math.Log2E, 9),
140 math.Ldexp(math.Log2E, 10),
141 math.Ldexp(math.Log2E, 11),
142 math.Ldexp(math.Log2E, 12),
143 math.Ldexp(math.Log2E, 13),
144 math.Ldexp(math.Log2E, 14),
145 math.Ldexp(math.Log2E, 15),
146 math.Ldexp(math.Log2E, 16),
147 math.Ldexp(math.Log2E, 17),
148 math.Ldexp(math.Log2E, 18),
149 math.Ldexp(math.Log2E, 19),
150 math.Ldexp(math.Log2E, 20),
151 }
152
153 // scaleChange returns the magnitude of the scale change needed to fit bin in
154 // the bucket. If no scale change is needed 0 is returned.
155 func (p *expoHistogramDataPoint[N]) scaleChange(bin, startBin int32, length int) int32 {
156 if length == 0 {
157 // No need to rescale if there are no buckets.
158 return 0
159 }
160
161 low := int(startBin)
162 high := int(bin)
163 if startBin >= bin {
164 low = int(bin)
165 high = int(startBin) + length - 1
166 }
167
168 var count int32
169 for high-low >= p.maxSize {
170 low >>= 1
171 high >>= 1
172 count++
173 if count > expoMaxScale-expoMinScale {
174 return count
175 }
176 }
177 return count
178 }
179
180 func (p *expoHistogramDataPoint[N]) count() uint64 {
181 return p.posBuckets.count() + p.negBuckets.count() + p.zeroCount.Load()
182 }
183
184 // expoBuckets is a set of buckets in an exponential histogram.
185 type expoBuckets struct {
186 startBin int32
187 counts []atomic.Uint64
188 }
189
190 // record increments the count for the given bin, and expands the buckets if needed.
191 // Size changes must be done before calling this function.
192 func (b *expoBuckets) record(bin int32) {
193 if len(b.counts) == 0 {
194 b.counts = make([]atomic.Uint64, 1)
195 b.counts[0].Store(1)
196 b.startBin = bin
197 return
198 }
199
200 endBin := int(b.startBin) + len(b.counts) - 1
201
202 // if the new bin is inside the current range
203 if bin >= b.startBin && int(bin) <= endBin {
204 b.counts[bin-b.startBin].Add(1)
205 return
206 }
207 // if the new bin is before the current start add spaces to the counts
208 if bin < b.startBin {
209 origLen := len(b.counts)
210 newLength := endBin - int(bin) + 1
211 shift := b.startBin - bin
212
213 if newLength > cap(b.counts) {
214 b.counts = append(b.counts, make([]atomic.Uint64, newLength-len(b.counts))...)
215 }
216
217 b.counts = b.counts[:newLength]
218
219 // Shift existing elements to the right. Go's copy() doesn't work for
220 // structs like atomic.Uint64.
221 for i := origLen - 1; i >= 0; i-- {
222 b.counts[i+int(shift)].Store(b.counts[i].Load())
223 }
224
225 for i := 1; i < int(shift); i++ {
226 b.counts[i].Store(0)
227 }
228 b.startBin = bin
229 b.counts[0].Store(1)
230 return
231 }
232 // if the new is after the end add spaces to the end
233 if int(bin) > endBin {
234 if int(bin-b.startBin) < cap(b.counts) {
235 b.counts = b.counts[:bin-b.startBin+1]
236 for i := endBin + 1 - int(b.startBin); i < len(b.counts); i++ {
237 b.counts[i].Store(0)
238 }
239 b.counts[bin-b.startBin].Store(1)
240 return
241 }
242
243 end := make([]atomic.Uint64, int(bin-b.startBin)-len(b.counts)+1)
244 b.counts = append(b.counts, end...)
245 b.counts[bin-b.startBin].Store(1)
246 }
247 }
248
249 // downscale shrinks a bucket by a factor of 2*s. It will sum counts into the
250 // correct lower resolution bucket.
251 func (b *expoBuckets) downscale(delta int32) {
252 // Example
253 // delta = 2
254 // Original offset: -6
255 // Counts: [ 3, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
256 // bins: -6 -5, -4, -3, -2, -1, 0, 1, 2, 3, 4
257 // new bins:-2, -2, -1, -1, -1, -1, 0, 0, 0, 0, 1
258 // new Offset: -2
259 // new Counts: [4, 14, 30, 10]
260
261 if len(b.counts) <= 1 || delta < 1 {
262 b.startBin >>= delta
263 return
264 }
265
266 steps := int32(1) << delta
267 offset := b.startBin % steps
268 offset = (offset + steps) % steps // to make offset positive
269 for i := 1; i < len(b.counts); i++ {
270 idx := i + int(offset)
271 if idx%int(steps) == 0 {
272 b.counts[idx/int(steps)].Store(b.counts[i].Load())
273 continue
274 }
275 b.counts[idx/int(steps)].Add(b.counts[i].Load())
276 }
277
278 lastIdx := (len(b.counts) - 1 + int(offset)) / int(steps)
279 b.counts = b.counts[:lastIdx+1]
280 b.startBin >>= delta
281 }
282
283 func (b *expoBuckets) count() uint64 {
284 var total uint64
285 for i := range b.counts {
286 total += b.counts[i].Load()
287 }
288 return total
289 }
290
291 // newExponentialHistogram returns an Aggregator that summarizes a set of
292 // measurements as an exponential histogram. Each histogram is scoped by attributes
293 // and the aggregation cycle the measurements were made in.
294 func newExponentialHistogram[N int64 | float64](
295 maxSize, maxScale int32,
296 noMinMax, noSum bool,
297 limit int,
298 r func(attribute.Set) FilteredExemplarReservoir[N],
299 ) *expoHistogram[N] {
300 return &expoHistogram[N]{
301 noSum: noSum,
302 noMinMax: noMinMax,
303 maxSize: int(maxSize),
304 maxScale: maxScale,
305
306 newRes: r,
307 limit: newLimiter[expoHistogramDataPoint[N]](limit),
308 values: make(map[attribute.Distinct]*expoHistogramDataPoint[N]),
309
310 start: now(),
311 }
312 }
313
314 // expoHistogram summarizes a set of measurements as an histogram with exponentially
315 // defined buckets.
316 type expoHistogram[N int64 | float64] struct {
317 noSum bool
318 noMinMax bool
319 maxSize int
320 maxScale int32
321
322 newRes func(attribute.Set) FilteredExemplarReservoir[N]
323 limit limiter[expoHistogramDataPoint[N]]
324 values map[attribute.Distinct]*expoHistogramDataPoint[N]
325 valuesMu sync.Mutex
326
327 start time.Time
328 }
329
330 func (e *expoHistogram[N]) measure(
331 ctx context.Context,
332 value N,
333 fltrAttr attribute.Set,
334 droppedAttr []attribute.KeyValue,
335 ) {
336 // Ignore NaN and infinity.
337 if math.IsInf(float64(value), 0) || math.IsNaN(float64(value)) {
338 return
339 }
340
341 e.valuesMu.Lock()
342 defer e.valuesMu.Unlock()
343
344 v, ok := e.values[fltrAttr.Equivalent()]
345 if !ok {
346 fltrAttr = e.limit.Attributes(fltrAttr, e.values)
347 // If we overflowed, make sure we add to the existing overflow series
348 // if it already exists.
349 v, ok = e.values[fltrAttr.Equivalent()]
350 if !ok {
351 v = newExpoHistogramDataPoint[N](fltrAttr, e.maxSize, e.maxScale, e.noMinMax, e.noSum)
352 v.res = e.newRes(fltrAttr)
353
354 e.values[fltrAttr.Equivalent()] = v
355 }
356 }
357 v.record(value)
358 v.res.Offer(ctx, value, droppedAttr)
359 }
360
361 func (e *expoHistogram[N]) delta(
362 dest *metricdata.Aggregation, //nolint:gocritic // The pointer is needed for the ComputeAggregation interface
363 ) int {
364 t := now()
365
366 // If *dest is not a metricdata.ExponentialHistogram, memory reuse is missed.
367 // In that case, use the zero-value h and hope for better alignment next cycle.
368 h, _ := (*dest).(metricdata.ExponentialHistogram[N])
369 h.Temporality = metricdata.DeltaTemporality
370
371 e.valuesMu.Lock()
372 defer e.valuesMu.Unlock()
373
374 n := len(e.values)
375 hDPts := reset(h.DataPoints, n, n)
376
377 var i int
378 for _, val := range e.values {
379 hDPts[i].Attributes = val.attrs
380 hDPts[i].StartTime = e.start
381 hDPts[i].Time = t
382 hDPts[i].Count = val.count()
383 hDPts[i].Scale = val.scale.Load()
384 hDPts[i].ZeroCount = val.zeroCount.Load()
385 hDPts[i].ZeroThreshold = 0.0
386
387 hDPts[i].PositiveBucket.Offset = val.posBuckets.startBin
388 hDPts[i].PositiveBucket.Counts = reset(
389 hDPts[i].PositiveBucket.Counts,
390 len(val.posBuckets.counts),
391 len(val.posBuckets.counts),
392 )
393 for j := range val.posBuckets.counts {
394 hDPts[i].PositiveBucket.Counts[j] = val.posBuckets.counts[j].Load()
395 }
396
397 hDPts[i].NegativeBucket.Offset = val.negBuckets.startBin
398 hDPts[i].NegativeBucket.Counts = reset(
399 hDPts[i].NegativeBucket.Counts,
400 len(val.negBuckets.counts),
401 len(val.negBuckets.counts),
402 )
403 for j := range val.negBuckets.counts {
404 hDPts[i].NegativeBucket.Counts[j] = val.negBuckets.counts[j].Load()
405 }
406
407 if !e.noSum {
408 hDPts[i].Sum = val.sum.load()
409 }
410 if !e.noMinMax {
411 if val.minMax.set.Load() {
412 hDPts[i].Min = metricdata.NewExtrema(val.minMax.minimum.Load())
413 hDPts[i].Max = metricdata.NewExtrema(val.minMax.maximum.Load())
414 }
415 }
416
417 collectExemplars(&hDPts[i].Exemplars, val.res.Collect)
418
419 i++
420 }
421 // Unused attribute sets do not report.
422 clear(e.values)
423
424 e.start = t
425 h.DataPoints = hDPts
426 *dest = h
427 return n
428 }
429
430 func (e *expoHistogram[N]) cumulative(
431 dest *metricdata.Aggregation, //nolint:gocritic // The pointer is needed for the ComputeAggregation interface
432 ) int {
433 t := now()
434
435 // If *dest is not a metricdata.ExponentialHistogram, memory reuse is missed.
436 // In that case, use the zero-value h and hope for better alignment next cycle.
437 h, _ := (*dest).(metricdata.ExponentialHistogram[N])
438 h.Temporality = metricdata.CumulativeTemporality
439
440 e.valuesMu.Lock()
441 defer e.valuesMu.Unlock()
442
443 n := len(e.values)
444 hDPts := reset(h.DataPoints, n, n)
445
446 perSeriesStartTimeEnabled := x.PerSeriesStartTimestamps.Enabled()
447
448 var i int
449 for _, val := range e.values {
450 hDPts[i].Attributes = val.attrs
451
452 startTime := e.start
453 if perSeriesStartTimeEnabled {
454 startTime = val.startTime
455 }
456 hDPts[i].StartTime = startTime
457 hDPts[i].Time = t
458 hDPts[i].Count = val.count()
459 hDPts[i].Scale = val.scale.Load()
460 hDPts[i].ZeroCount = val.zeroCount.Load()
461 hDPts[i].ZeroThreshold = 0.0
462
463 hDPts[i].PositiveBucket.Offset = val.posBuckets.startBin
464 hDPts[i].PositiveBucket.Counts = reset(
465 hDPts[i].PositiveBucket.Counts,
466 len(val.posBuckets.counts),
467 len(val.posBuckets.counts),
468 )
469 for j := range val.posBuckets.counts {
470 hDPts[i].PositiveBucket.Counts[j] = val.posBuckets.counts[j].Load()
471 }
472
473 hDPts[i].NegativeBucket.Offset = val.negBuckets.startBin
474 hDPts[i].NegativeBucket.Counts = reset(
475 hDPts[i].NegativeBucket.Counts,
476 len(val.negBuckets.counts),
477 len(val.negBuckets.counts),
478 )
479 for j := range val.negBuckets.counts {
480 hDPts[i].NegativeBucket.Counts[j] = val.negBuckets.counts[j].Load()
481 }
482
483 if !e.noSum {
484 hDPts[i].Sum = val.sum.load()
485 }
486 if !e.noMinMax {
487 if val.minMax.set.Load() {
488 hDPts[i].Min = metricdata.NewExtrema(val.minMax.minimum.Load())
489 hDPts[i].Max = metricdata.NewExtrema(val.minMax.maximum.Load())
490 }
491 }
492
493 collectExemplars(&hDPts[i].Exemplars, val.res.Collect)
494
495 i++
496 // TODO (#3006): This will use an unbounded amount of memory if there
497 // are unbounded number of attribute sets being aggregated. Attribute
498 // sets that become "stale" need to be forgotten so this will not
499 // overload the system.
500 }
501
502 h.DataPoints = hDPts
503 *dest = h
504 return n
505 }