Debian Codegraph @

sdk/metric/internal/aggregate/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 "slices"
9 "sort"
10 "sync/atomic"
11 "time"
12
13 "go.opentelemetry.io/otel/attribute"
14 "go.opentelemetry.io/otel/sdk/internal/x"
15 "go.opentelemetry.io/otel/sdk/metric/metricdata"
16 )
17
18 // histogramPoint is a single histogram point, used in delta aggregations.
19 type histogramPoint[N int64 | float64] struct {
20 attrs attribute.Set
21 res FilteredExemplarReservoir[N]
22 histogramPointCounters[N]
23 }
24
25 // hotColdHistogramPoint a hot and cold histogram points, used in cumulative
26 // aggregations.
27 type hotColdHistogramPoint[N int64 | float64] struct {
28 hcwg hotColdWaitGroup
29 hotColdPoint [2]histogramPointCounters[N]
30
31 attrs attribute.Set
32 res FilteredExemplarReservoir[N]
33 startTime time.Time
34 }
35
36 // histogramPointCounters contains only the atomic counter data, and is used by
37 // both histogramPoint and hotColdHistogramPoint.
38 type histogramPointCounters[N int64 | float64] struct {
39 counts []atomic.Uint64
40 total atomicCounter[N]
41 minMax atomicMinMax[N]
42 }
43
44 func (b *histogramPointCounters[N]) loadCountsInto(into *[]uint64) uint64 {
45 // TODO (#3047): Making copies for counts incurs a large
46 // memory allocation footprint. Alternatives should be explored.
47 counts := reset(*into, len(b.counts), len(b.counts))
48 count := uint64(0)
49 for i := range b.counts {
50 c := b.counts[i].Load()
51 counts[i] = c
52 count += c
53 }
54 *into = counts
55 return count
56 }
57
58 // mergeIntoAndReset merges this set of histogram counter data into another,
59 // and resets the state of this set of counters. This is used by
60 // hotColdHistogramPoint to ensure that the cumulative counters continue to
61 // accumulate after being read.
62 func (b *histogramPointCounters[N]) mergeIntoAndReset( // nolint:revive // Intentional internal control flag
63 into *histogramPointCounters[N],
64 noMinMax, noSum bool,
65 ) {
66 for i := range b.counts {
67 into.counts[i].Add(b.counts[i].Load())
68 b.counts[i].Store(0)
69 }
70
71 if !noMinMax {
72 // Do not reset min or max because cumulative min and max only ever grow
73 // smaller or larger respectively.
74
75 if b.minMax.set.Load() {
76 into.minMax.Update(b.minMax.minimum.Load())
77 into.minMax.Update(b.minMax.maximum.Load())
78 }
79 }
80 if !noSum {
81 into.total.add(b.total.load())
82 b.total.reset()
83 }
84 }
85
86 // deltaHistogram is a histogram whose internal storage is reset when it is
87 // collected.
88 //
89 // deltaHistogram's measure is implemented without locking, even when called
90 // concurrently with collect. This is done by maintaining two separate maps:
91 // one "hot" which is concurrently updated by measure(), and one "cold", which
92 // is read and reset by collect(). The [hotcoldWaitGroup] allows collect() to
93 // swap the hot and cold maps, and wait for updates to the cold map to complete
94 // prior to reading. deltaHistogram swaps ald clears complete maps so that
95 // unused attribute sets do not report in subsequent collect() calls.
96 type deltaHistogram[N int64 | float64] struct {
97 hcwg hotColdWaitGroup
98 hotColdValMap [2]limitedSyncMap
99
100 start time.Time
101 noMinMax bool
102 noSum bool
103 bounds []float64
104 newRes func(attribute.Set) FilteredExemplarReservoir[N]
105 }
106
107 func (s *deltaHistogram[N]) measure(
108 ctx context.Context,
109 value N,
110 fltrAttr attribute.Set,
111 droppedAttr []attribute.KeyValue,
112 ) {
113 hotIdx := s.hcwg.start()
114 defer s.hcwg.done(hotIdx)
115 h := s.hotColdValMap[hotIdx].LoadOrStoreAttr(fltrAttr, func(attr attribute.Set) any {
116 hPt := &histogramPoint[N]{
117 res: s.newRes(attr),
118 attrs: attr,
119 // N+1 buckets. For example:
120 //
121 // bounds = [0, 5, 10]
122 //
123 // Then,
124 //
125 // counts = (-∞, 0], (0, 5.0], (5.0, 10.0], (10.0, +∞)
126 histogramPointCounters: histogramPointCounters[N]{counts: make([]atomic.Uint64, len(s.bounds)+1)},
127 }
128 return hPt
129 }).(*histogramPoint[N])
130
131 // This search will return an index in the range [0, len(s.bounds)], where
132 // it will return len(s.bounds) if value is greater than the last element
133 // of s.bounds. This aligns with the histogramPoint in that the length of histogramPoint
134 // is len(s.bounds)+1, with the last bucket representing:
135 // (s.bounds[len(s.bounds)-1], +∞).
136 idx := sort.SearchFloat64s(s.bounds, float64(value))
137 h.counts[idx].Add(1)
138 if !s.noMinMax {
139 h.minMax.Update(value)
140 }
141 if !s.noSum {
142 h.total.add(value)
143 }
144 h.res.Offer(ctx, value, droppedAttr)
145 }
146
147 // newDeltaHistogram returns a histogram that is reset each time it is
148 // collected.
149 func newDeltaHistogram[N int64 | float64](
150 boundaries []float64,
151 noMinMax, noSum bool,
152 limit int,
153 r func(attribute.Set) FilteredExemplarReservoir[N],
154 ) *deltaHistogram[N] {
155 // The responsibility of keeping all histogramPoint correctly associated with the
156 // passed boundaries is ultimately this type's responsibility. Make a copy
157 // here so we can always guarantee this. Or, in the case of failure, have
158 // complete control over the fix.
159 b := slices.Clone(boundaries)
160 slices.Sort(b)
161 return &deltaHistogram[N]{
162 start: now(),
163 noMinMax: noMinMax,
164 noSum: noSum,
165 bounds: b,
166 newRes: r,
167 hotColdValMap: [2]limitedSyncMap{
168 {aggLimit: limit},
169 {aggLimit: limit},
170 },
171 }
172 }
173
174 func (s *deltaHistogram[N]) collect(
175 dest *metricdata.Aggregation, //nolint:gocritic // The pointer is needed for the ComputeAggregation interface
176 ) int {
177 t := now()
178
179 // If *dest is not a metricdata.Histogram, memory reuse is missed. In that
180 // case, use the zero-value h and hope for better alignment next cycle.
181 h, _ := (*dest).(metricdata.Histogram[N])
182 h.Temporality = metricdata.DeltaTemporality
183
184 // delta always clears values on collection
185 readIdx := s.hcwg.swapHotAndWait()
186
187 // Do not allow modification of our copy of bounds.
188 bounds := slices.Clone(s.bounds)
189
190 // The len will not change while we iterate over values, since we waited
191 // for all writes to finish to the cold values and len.
192 n := s.hotColdValMap[readIdx].Len()
193 hDPts := reset(h.DataPoints, n, n)
194
195 var i int
196 s.hotColdValMap[readIdx].Range(func(_, value any) bool {
197 val := value.(*histogramPoint[N])
198
199 count := val.loadCountsInto(&hDPts[i].BucketCounts)
200 hDPts[i].Attributes = val.attrs
201 hDPts[i].StartTime = s.start
202 hDPts[i].Time = t
203 hDPts[i].Count = count
204 hDPts[i].Bounds = bounds
205
206 if !s.noSum {
207 hDPts[i].Sum = val.total.load()
208 }
209
210 if !s.noMinMax {
211 if val.minMax.set.Load() {
212 hDPts[i].Min = metricdata.NewExtrema(val.minMax.minimum.Load())
213 hDPts[i].Max = metricdata.NewExtrema(val.minMax.maximum.Load())
214 }
215 }
216
217 collectExemplars(&hDPts[i].Exemplars, val.res.Collect)
218
219 i++
220 return true
221 })
222 // Unused attribute sets do not report.
223 s.hotColdValMap[readIdx].Clear()
224 // The delta collection cycle resets.
225 s.start = t
226
227 h.DataPoints = hDPts
228 *dest = h
229
230 return n
231 }
232
233 // cumulativeHistogram summarizes a set of measurements as an histogram with explicitly
234 // defined histogramPoint.
235 //
236 // cumulativeHistogram's measure is implemented without locking, even when
237 // called concurrently with collect. This is done by maintaining two separate
238 // histogramPointCounters for each attribute set: one "hot" which is
239 // concurrently updated by measure(), and one "cold", which is read and reset
240 // by collect(). The [hotcoldWaitGroup] allows collect() to swap the hot and
241 // cold counters, and wait for updates to the cold counters to complete prior
242 // to reading. Unlike deltaHistogram, this maintains a single map so that the
243 // preserved attribute sets do not change when collect() is called.
244 type cumulativeHistogram[N int64 | float64] struct {
245 values limitedSyncMap
246
247 start time.Time
248 noMinMax bool
249 noSum bool
250 bounds []float64
251 newRes func(attribute.Set) FilteredExemplarReservoir[N]
252 }
253
254 // newCumulativeHistogram returns a histogram that accumulates measurements
255 // into a histogram data structure. It is never reset.
256 func newCumulativeHistogram[N int64 | float64](
257 boundaries []float64,
258 noMinMax, noSum bool,
259 limit int,
260 r func(attribute.Set) FilteredExemplarReservoir[N],
261 ) *cumulativeHistogram[N] {
262 // The responsibility of keeping all histogramPoint correctly associated with the
263 // passed boundaries is ultimately this type's responsibility. Make a copy
264 // here so we can always guarantee this. Or, in the case of failure, have
265 // complete control over the fix.
266 b := slices.Clone(boundaries)
267 slices.Sort(b)
268 return &cumulativeHistogram[N]{
269 start: now(),
270 noMinMax: noMinMax,
271 noSum: noSum,
272 bounds: b,
273 newRes: r,
274 values: limitedSyncMap{aggLimit: limit},
275 }
276 }
277
278 func (s *cumulativeHistogram[N]) measure(
279 ctx context.Context,
280 value N,
281 fltrAttr attribute.Set,
282 droppedAttr []attribute.KeyValue,
283 ) {
284 h := s.values.LoadOrStoreAttr(fltrAttr, func(attr attribute.Set) any {
285 hPt := &hotColdHistogramPoint[N]{
286 res: s.newRes(attr),
287 attrs: attr,
288 // N+1 buckets. For example:
289 //
290 // bounds = [0, 5, 10]
291 //
292 // Then,
293 //
294 // count = (-∞, 0], (0, 5.0], (5.0, 10.0], (10.0, +∞)
295 hotColdPoint: [2]histogramPointCounters[N]{
296 {
297 counts: make([]atomic.Uint64, len(s.bounds)+1),
298 },
299 {
300 counts: make([]atomic.Uint64, len(s.bounds)+1),
301 },
302 },
303 startTime: now(),
304 }
305 return hPt
306 }).(*hotColdHistogramPoint[N])
307
308 // This search will return an index in the range [0, len(s.bounds)], where
309 // it will return len(s.bounds) if value is greater than the last element
310 // of s.bounds. This aligns with the histogramPoint in that the length of histogramPoint
311 // is len(s.bounds)+1, with the last bucket representing:
312 // (s.bounds[len(s.bounds)-1], +∞).
313 idx := sort.SearchFloat64s(s.bounds, float64(value))
314
315 hotIdx := h.hcwg.start()
316 defer h.hcwg.done(hotIdx)
317
318 h.hotColdPoint[hotIdx].counts[idx].Add(1)
319 if !s.noMinMax {
320 h.hotColdPoint[hotIdx].minMax.Update(value)
321 }
322 if !s.noSum {
323 h.hotColdPoint[hotIdx].total.add(value)
324 }
325 h.res.Offer(ctx, value, droppedAttr)
326 }
327
328 func (s *cumulativeHistogram[N]) collect(
329 dest *metricdata.Aggregation, //nolint:gocritic // The pointer is needed for the ComputeAggregation interface
330 ) int {
331 t := now()
332
333 // If *dest is not a metricdata.Histogram, memory reuse is missed. In that
334 // case, use the zero-value h and hope for better alignment next cycle.
335 h, _ := (*dest).(metricdata.Histogram[N])
336 h.Temporality = metricdata.CumulativeTemporality
337
338 // Do not allow modification of our copy of bounds.
339 bounds := slices.Clone(s.bounds)
340
341 // Values are being concurrently written while we iterate, so only use the
342 // current length for capacity.
343 hDPts := reset(h.DataPoints, 0, s.values.Len())
344
345 perSeriesStartTimeEnabled := x.PerSeriesStartTimestamps.Enabled()
346
347 var i int
348 s.values.Range(func(_, value any) bool {
349 val := value.(*hotColdHistogramPoint[N])
350
351 startTime := s.start
352 if perSeriesStartTimeEnabled {
353 startTime = val.startTime
354 }
355 // swap, observe, and clear the point
356 readIdx := val.hcwg.swapHotAndWait()
357 var bucketCounts []uint64
358 count := val.hotColdPoint[readIdx].loadCountsInto(&bucketCounts)
359 newPt := metricdata.HistogramDataPoint[N]{
360 Attributes: val.attrs,
361 StartTime: startTime,
362 Time: t,
363 Count: count,
364 Bounds: bounds,
365 // The HistogramDataPoint field values returned need to be copies of
366 // the histogramPoint value as we will keep updating them.
367 BucketCounts: bucketCounts,
368 }
369
370 if !s.noSum {
371 newPt.Sum = val.hotColdPoint[readIdx].total.load()
372 }
373 if !s.noMinMax {
374 if val.hotColdPoint[readIdx].minMax.set.Load() {
375 newPt.Min = metricdata.NewExtrema(val.hotColdPoint[readIdx].minMax.minimum.Load())
376 newPt.Max = metricdata.NewExtrema(val.hotColdPoint[readIdx].minMax.maximum.Load())
377 }
378 }
379 // Once we've read the point, merge it back into the hot histogram
380 // point since it is cumulative.
381 hotIdx := (readIdx + 1) % 2
382 val.hotColdPoint[readIdx].mergeIntoAndReset(&val.hotColdPoint[hotIdx], s.noMinMax, s.noSum)
383
384 collectExemplars(&newPt.Exemplars, val.res.Collect)
385 hDPts = append(hDPts, newPt)
386
387 i++
388 // TODO (#3006): This will use an unbounded amount of memory if there
389 // are unbounded number of attribute sets being aggregated. Attribute
390 // sets that become "stale" need to be forgotten so this will not
391 // overload the system.
392 return true
393 })
394
395 h.DataPoints = hDPts
396 *dest = h
397
398 return i
399 }