| 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 |
} |