AlignedHistogramBucketExemplarReservoir should use time-weighted sampling

[dashpole]

What are you trying to achieve?

Exemplars recorded on histograms today are skewed towards the end of the collection interval because of the spec language for AlignedHistogramBucketExemplarReservoir:

This implementation MUST keep the last seen measurement that falls within a histogram bucket.

I would like to allow implementations to use a reservoir-sampling algorithm for buckets which is time-weighted to spread exemplars out over time. This is already the case for the SimpleFixedSizeExemplarReservoir, so SDKs should already have implemented such an algorithm. Doing this does come with a performance penalty, but it seems potentially worth it to provide more useful telemetry.

I propose changing the above language to:

This implementation MUST store at most one measurement that falls within a histogram bucket, and SHOULD use a uniformly-weighted sampling algorithm based on the number of measurements the bucket has seen so far to determine if the offered measurements should be sampled. Alternatively, the implementation MAY keep the last seen measurement that falls within a histogram bucket.

Additional context.

I noticed this while working on the Go implementation of the histogram-bucket-aligned reservoir: open-telemetry/opentelemetry-go#7443.

For Go, the above change would allow us to share more of the implementation details of the reservoir implementation. The only difference between the two implementations would be how the storage index is chosen: random vs histogram-bucket aligned.

cc @open-telemetry/go-maintainers @open-telemetry/specs-metrics-approvers

[MrAlias]

Looks good to me.

I might word the alternative a bit clearer to indicate it is a separate algorithm not an extension to the time based sampling.

Alternatively, the implementation MAY instead just keep the last seen measurement that falls within a histogram bucket.

[svrnm]

@pellared and I looked at this during triage, looks good to us!