Debian Codegraph @

sdk/metric/exemplar/fixed_size_reservoir.go

raw
1 // Copyright The OpenTelemetry Authors
2 // SPDX-License-Identifier: Apache-2.0
3
4 package exemplar // import "go.opentelemetry.io/otel/sdk/metric/exemplar"
5
6 import (
7 "context"
8 "math"
9 "math/rand/v2"
10 "sync"
11 "sync/atomic"
12 "time"
13
14 "go.opentelemetry.io/otel/attribute"
15 "go.opentelemetry.io/otel/sdk/metric/internal/reservoir"
16 )
17
18 // FixedSizeReservoirProvider returns a provider of [FixedSizeReservoir].
19 func FixedSizeReservoirProvider(k int) ReservoirProvider {
20 return func(attribute.Set) Reservoir {
21 return NewFixedSizeReservoir(k)
22 }
23 }
24
25 // NewFixedSizeReservoir returns a [FixedSizeReservoir] that samples at most
26 // k exemplars. If there are k or less measurements made, the Reservoir will
27 // sample each one. If there are more than k, the Reservoir will then randomly
28 // sample all additional measurement with a decreasing probability.
29 func NewFixedSizeReservoir(k int) *FixedSizeReservoir {
30 if k < 0 {
31 k = 0
32 }
33 // Use math.MaxInt32 instead of math.MaxUint32 to prevent overflowing int
34 // on 32-bit systems.
35 if k > math.MaxInt32 {
36 k = math.MaxInt32
37 }
38 return &FixedSizeReservoir{
39 storage: newStorage(k),
40 // Above we ensure k is positive, and less than MaxInt32.
41 nextTracker: newNextTracker(uint32(k)), // nolint: gosec
42 }
43 }
44
45 var _ Reservoir = &FixedSizeReservoir{}
46
47 // FixedSizeReservoir is a [Reservoir] that samples at most k exemplars. If
48 // there are k or less measurements made, the Reservoir will sample each one.
49 // If there are more than k, the Reservoir will then randomly sample all
50 // additional measurement with a decreasing probability.
51 type FixedSizeReservoir struct {
52 reservoir.ConcurrentSafe
53 *storage
54 *nextTracker
55 }
56
57 // Offer accepts the parameters associated with a measurement. The
58 // parameters will be stored as an exemplar if the Reservoir decides to
59 // sample the measurement.
60 //
61 // The passed ctx needs to contain any baggage or span that were active
62 // when the measurement was made. This information may be used by the
63 // Reservoir in making a sampling decision.
64 //
65 // The time t is the time when the measurement was made. The v and a
66 // parameters are the value and dropped (filtered) attributes of the
67 // measurement respectively.
68 func (r *FixedSizeReservoir) Offer(ctx context.Context, t time.Time, n Value, a []attribute.KeyValue) {
69 // The following algorithm is "Algorithm L" from Li, Kim-Hung (4 December
70 // 1994). "Reservoir-Sampling Algorithms of Time Complexity
71 // O(n(1+log(N/n)))". ACM Transactions on Mathematical Software. 20 (4):
72 // 481–493 (https://dl.acm.org/doi/10.1145/198429.198435).
73 //
74 // A high-level overview of "Algorithm L":
75 // 0) Pre-calculate the random count greater than the storage size when
76 // an exemplar will be replaced.
77 // 1) Accept all measurements offered until the configured storage size is
78 // reached.
79 // 2) Loop:
80 // a) When the pre-calculate count is reached, replace a random
81 // existing exemplar with the offered measurement.
82 // b) Calculate the next random count greater than the existing one
83 // which will replace another exemplars
84 //
85 // The way a "replacement" count is computed is by looking at `n` number of
86 // independent random numbers each corresponding to an offered measurement.
87 // Of these numbers the smallest `k` (the same size as the storage
88 // capacity) of them are kept as a subset. The maximum value in this
89 // subset, called `w` is used to weight another random number generation
90 // for the next count that will be considered.
91 //
92 // By weighting the next count computation like described, it is able to
93 // perform a uniformly-weighted sampling algorithm based on the number of
94 // samples the reservoir has seen so far. The sampling will "slow down" as
95 // more and more samples are offered so as to reduce a bias towards those
96 // offered just prior to the end of the collection.
97 //
98 // This algorithm is preferred because of its balance of simplicity and
99 // performance. It will compute three random numbers (the bulk of
100 // computation time) for each item that becomes part of the reservoir, but
101 // it does not spend any time on items that do not. In particular it has an
102 // asymptotic runtime of O(k(1 + log(n/k)) where n is the number of
103 // measurements offered and k is the reservoir size.
104 //
105 // See https://en.wikipedia.org/wiki/Reservoir_sampling for an overview of
106 // this and other reservoir sampling algorithms. See
107 // https://github.com/MrAlias/reservoir-sampling for a performance
108 // comparison of reservoir sampling algorithms.
109
110 count, next := r.incrementCount()
111 if count < r.k {
112 r.store(ctx, int(count), t, n, a)
113 } else if count == next {
114 // Overwrite a random existing measurement with the one offered.
115 idx := rand.IntN(int(r.k))
116 r.store(ctx, idx, t, n, a)
117 r.wMu.Lock()
118 defer r.wMu.Unlock()
119 newCount, newNext := r.loadCountAndNext()
120 if newNext < next || newCount < count {
121 // This Observe() raced with Collect(), and r.reset() has been
122 // called since r.incrementCount(). Skip the call to advance in
123 // this case because our exemplar may have been collected in the
124 // previous interval.
125 return
126 }
127 r.advance()
128 }
129 }
130
131 // Collect returns all the held exemplars.
132 //
133 // The Reservoir state is preserved after this call.
134 func (r *FixedSizeReservoir) Collect(dest *[]Exemplar) {
135 r.storage.Collect(dest)
136 // Call reset here even though it will reset r.count and restart the random
137 // number series. This will persist any old exemplars as long as no new
138 // measurements are offered, but it will also prioritize those new
139 // measurements that are made over the older collection cycle ones.
140 r.reset()
141 }
142
143 func newNextTracker(k uint32) *nextTracker {
144 nt := &nextTracker{k: k}
145 nt.reset()
146 return nt
147 }
148
149 type nextTracker struct {
150 // countAndNext holds the current counts in the lower 32 bits and the next
151 // value in the upper 32 bits.
152 countAndNext atomic.Uint64
153 // w is the largest random number in a distribution that is used to compute
154 // the next next.
155 w float64
156 // wMu ensures w is kept consistent with next during advance and reset.
157 wMu sync.Mutex
158 // k is the number of measurements that can be stored in the reservoir.
159 k uint32
160 }
161
162 // reset resets r to the initial state.
163 func (r *nextTracker) reset() {
164 r.wMu.Lock()
165 defer r.wMu.Unlock()
166 // This resets the number of exemplars known.
167 // Random index inserts should only happen after the storage is full.
168 r.setCountAndNext(0, r.k)
169
170 // Initial random number in the series used to generate r.next.
171 //
172 // This is set before r.advance to reset or initialize the random number
173 // series. Without doing so it would always be 0 or never restart a new
174 // random number series.
175 //
176 // This maps the uniform random number in (0,1) to a geometric distribution
177 // over the same interval. The mean of the distribution is inversely
178 // proportional to the storage capacity.
179 r.w = math.Exp(math.Log(randomFloat64()) / float64(r.k))
180
181 r.advance()
182 }
183
184 // incrementCount increments the count. It returns the count before the
185 // increment and the current next value.
186 func (r *nextTracker) incrementCount() (uint32, uint32) {
187 n := r.countAndNext.Add(1)
188 // Both count and next are stored in the upper and lower 32 bits, and thus
189 // can't overflow.
190 return uint32(n&((1<<32)-1) - 1), uint32(n >> 32) // nolint: gosec
191 }
192
193 // incrementNext increments the next value.
194 func (r *nextTracker) incrementNext(inc uint32) {
195 r.countAndNext.Add(uint64(inc) << 32)
196 }
197
198 // setCountAndNext sets the count and next values.
199 func (r *nextTracker) setCountAndNext(count, next uint32) {
200 r.countAndNext.Store(uint64(next)<<32 + uint64(count))
201 }
202
203 func (r *nextTracker) loadCountAndNext() (uint32, uint32) {
204 n := r.countAndNext.Load()
205 // Both count and next are stored in the upper and lower 32 bits, and thus
206 // can't overflow.
207 return uint32(n&((1<<32)-1) - 1), uint32(n >> 32) // nolint: gosec
208 }
209
210 // advance updates the count at which the offered measurement will overwrite an
211 // existing exemplar.
212 func (r *nextTracker) advance() {
213 // Calculate the next value in the random number series.
214 //
215 // The current value of r.w is based on the max of a distribution of random
216 // numbers (i.e. `w = max(u_1,u_2,...,u_k)` for `k` equal to the capacity
217 // of the storage and each `u` in the interval (0,w)). To calculate the
218 // next r.w we use the fact that when the next exemplar is selected to be
219 // included in the storage an existing one will be dropped, and the
220 // corresponding random number in the set used to calculate r.w will also
221 // be replaced. The replacement random number will also be within (0,w),
222 // therefore the next r.w will be based on the same distribution (i.e.
223 // `max(u_1,u_2,...,u_k)`). Therefore, we can sample the next r.w by
224 // computing the next random number `u` and take r.w as `w * u^(1/k)`.
225 r.w *= math.Exp(math.Log(randomFloat64()) / float64(r.k))
226 // Use the new random number in the series to calculate the count of the
227 // next measurement that will be stored.
228 //
229 // Given 0 < r.w < 1, each iteration will result in subsequent r.w being
230 // smaller. This translates here into the next next being selected against
231 // a distribution with a higher mean (i.e. the expected value will increase
232 // and replacements become less likely)
233 //
234 // Important to note, the new r.next will always be at least 1 more than
235 // the last r.next.
236 r.incrementNext(uint32(math.Log(randomFloat64())/math.Log(1-r.w)) + 1)
237 }
238
239 // randomFloat64 returns, as a float64, a uniform pseudo-random number in the
240 // open interval (0.0,1.0).
241 func randomFloat64() float64 {
242 // TODO: Use an algorithm that avoids rejection sampling. For example:
243 //
244 // const precision = 1 << 53 // 2^53
245 // // Generate an integer in [1, 2^53 - 1]
246 // v := rand.Uint64() % (precision - 1) + 1
247 // return float64(v) / float64(precision)
248 f := rand.Float64()
249 for f == 0 {
250 f = rand.Float64()
251 }
252 return f
253 }