tokio/runtime/metrics/histogram/
h2_histogram.rs

1use crate::runtime::metrics::batch::duration_as_u64;
2use std::cmp;
3use std::error::Error;
4use std::fmt::{Display, Formatter};
5use std::time::Duration;
6
7const DEFAULT_MIN_VALUE: Duration = Duration::from_nanos(100);
8const DEFAULT_MAX_VALUE: Duration = Duration::from_secs(60);
9
10/// Default precision is 2^-2 = 25% max error
11const DEFAULT_PRECISION: u32 = 2;
12const MAX_PRECISION: u32 = 10;
13
14/// Log Histogram
15///
16/// This implements an [H2 Histogram](https://iop.systems/blog/h2-histogram/), a histogram similar
17/// to HdrHistogram, but with better performance. It guarantees an error bound of `2^-p`.
18///
19/// Unlike a traditional H2 histogram this has two small changes:
20/// 1. The 0th bucket runs for `0..min_value`. This allows truncating a large number of buckets that
21///    would cover extremely short timescales that customers usually don't care about.
22/// 2. The final bucket runs all the way to `u64::MAX` — traditional H2 histograms would truncate
23///    or reject these values.
24///
25/// For information about the default configuration, see [`LogHistogramBuilder`].
26#[derive(Debug, Copy, Clone, PartialEq, Eq)]
27pub struct LogHistogram {
28    /// Number of buckets in the histogram
29    pub(crate) num_buckets: usize,
30
31    /// Precision of histogram. Error is bounded to 2^-p.
32    pub(crate) p: u32,
33
34    /// All buckets `idx < bucket_offset` are grouped into bucket 0.
35    ///
36    /// This increases the smallest measurable value of the histogram.
37    pub(crate) bucket_offset: usize,
38}
39
40impl Default for LogHistogram {
41    fn default() -> Self {
42        LogHistogramBuilder::default().build()
43    }
44}
45
46impl LogHistogram {
47    /// Create a Histogram configuration directly from values for `n` and `p`.
48    ///
49    /// # Panics
50    /// - If `bucket_offset` is greater than the specified number of buckets, `(n - p + 1) * 2^p`
51    fn from_n_p(n: u32, p: u32, bucket_offset: usize) -> Self {
52        assert!(n >= p, "{n} (n) must be at least as large as {p} (p)");
53        let num_buckets = ((n - p + 1) << p) as usize - bucket_offset;
54        Self {
55            num_buckets,
56            p,
57            bucket_offset,
58        }
59    }
60
61    fn truncate_to_max_value(&self, max_value: u64) -> LogHistogram {
62        let mut hist = *self;
63        while hist.max_value() >= max_value {
64            hist.num_buckets -= 1;
65        }
66        hist.num_buckets += 1;
67        hist
68    }
69
70    /// Creates a builder for [`LogHistogram`]
71    pub fn builder() -> LogHistogramBuilder {
72        LogHistogramBuilder::default()
73    }
74
75    /// The maximum value that can be stored before truncation in this histogram
76    pub fn max_value(&self) -> u64 {
77        self.bucket_range(self.num_buckets - 2).end
78    }
79
80    pub(crate) fn value_to_bucket(&self, value: u64) -> usize {
81        let index = bucket_index(value, self.p);
82        let offset_bucket = index.saturating_sub(self.bucket_offset as u64);
83        let max = self.num_buckets - 1;
84        offset_bucket.min(max as u64) as usize
85    }
86
87    pub(crate) fn bucket_range(&self, bucket: usize) -> std::ops::Range<u64> {
88        let LogHistogram {
89            p,
90            bucket_offset,
91            num_buckets,
92        } = self;
93        let input_bucket = bucket;
94        let bucket = bucket + bucket_offset;
95        let range_start_0th_bucket = match input_bucket {
96            0 => Some(0_u64),
97            _ => None,
98        };
99        let range_end_last_bucket = match input_bucket {
100            n if n == num_buckets - 1 => Some(u64::MAX),
101            _ => None,
102        };
103        if bucket < 1 << p {
104            // The first set of buckets are all size 1
105            let bucket = bucket as u64;
106            range_start_0th_bucket.unwrap_or(bucket)..range_end_last_bucket.unwrap_or(bucket + 1)
107        } else {
108            // Determine which range of buckets we're in, then determine which bucket in the range it is
109            let bucket = bucket as u64;
110            let p = *p as u64;
111            let w = (bucket >> p) - 1;
112            let base_bucket = (w + 1) * (1_u64 << p);
113            let offset = bucket - base_bucket;
114            let s = 1_u64 << (w + p);
115            let start = s + (offset << w);
116            let end = s + ((offset + 1) << w);
117
118            range_start_0th_bucket.unwrap_or(start)..range_end_last_bucket.unwrap_or(end)
119        }
120    }
121}
122
123/// Configuration for a [`LogHistogram`]
124///
125/// The log-scaled histogram implements an H2 histogram where the first bucket covers
126/// the range from 0 to [`LogHistogramBuilder::min_value`] and the final bucket covers
127/// [`LogHistogramBuilder::max_value`] to infinity. The precision is bounded to the specified
128/// [`LogHistogramBuilder::max_error`]. Specifically, the precision is the next smallest value
129/// of `2^-p` such that it is smaller than the requested max error. You can also select `p` directly
130/// with [`LogHistogramBuilder::precision_exact`].
131///
132/// Depending on the selected parameters, the number of buckets required is variable. To ensure
133/// that the histogram size is acceptable, callers may call [`LogHistogramBuilder::max_buckets`].
134/// If the resulting histogram would require more buckets, then the method will return an error.
135///
136/// ## Default values
137/// The default configuration provides the following settings:
138/// 1. `min_value`: 100ns
139/// 2. `max_value`: 68 seconds. The final bucket covers all values >68 seconds
140/// 3. `precision`: max error of 25%
141///
142/// This uses 237 64-bit buckets.
143#[derive(Default, Debug, Copy, Clone)]
144pub struct LogHistogramBuilder {
145    max_value: Option<Duration>,
146    min_value: Option<Duration>,
147    precision: Option<u32>,
148}
149
150impl From<LogHistogramBuilder> for LogHistogram {
151    fn from(value: LogHistogramBuilder) -> Self {
152        value.build()
153    }
154}
155
156impl LogHistogramBuilder {
157    /// Set the precision for this histogram
158    ///
159    /// This function determines the smallest value of `p` that would satisfy the requested precision
160    /// such that `2^-p` is less than `precision`. To set `p` directly, use
161    /// [`LogHistogramBuilder::precision_exact`].
162    ///
163    /// Precision controls the size of the "bucket groups" (consecutive buckets with identical
164    /// ranges). When `p` is 0, each bucket will be twice the size of the previous bucket. To match
165    /// the behavior of the legacy log histogram implementation, use `builder.precision_exact(0)`.
166    ///
167    /// The default value is 25% (2^-2)
168    ///
169    /// The highest supported precision is `0.0977%` `(2^-10)`. Provided values
170    /// less than this will be truncated.
171    ///
172    /// # Panics
173    /// - `max_error` <= 0
174    /// - `max_error` >= 1
175    pub fn max_error(mut self, max_error: f64) -> Self {
176        assert!(max_error > 0.0, "max_error must be greater than 0");
177        assert!(max_error < 1.0, "max_error must be less than 1");
178        let mut p = 2;
179        while 2_f64.powf(-(p as f64)) > max_error && p <= MAX_PRECISION {
180            p += 1;
181        }
182        self.precision = Some(p);
183        self
184    }
185
186    /// Sets the precision of this histogram directly.
187    ///
188    /// The precision (meaning: the ratio `n/bucket_range(n)` for some given `n`) will be `2^-p`.
189    ///
190    /// Precision controls the number consecutive buckets with identically sized ranges.
191    /// When `p` is 0, each bucket will be twice the size of the previous bucket (bucket groups are
192    /// only a single bucket wide).
193    ///
194    /// To match the behavior of the legacy implementation ([`HistogramScale::Log`]), use `builder.precision_exact(0)`.
195    ///
196    /// # Panics
197    /// - `p` > 10
198    ///
199    /// [`HistogramScale::Log`]: [crate::runtime::HistogramScale]
200    pub fn precision_exact(mut self, p: u32) -> Self {
201        assert!(p <= MAX_PRECISION, "precision must be <= {MAX_PRECISION}");
202        self.precision = Some(p);
203        self
204    }
205
206    /// Sets the minimum duration that can be accurately stored by this histogram.
207    ///
208    /// This sets the resolution. The first bucket will be no larger than
209    /// the provided duration. Setting this value will reduce the number of required buckets,
210    /// sometimes quite significantly.
211    pub fn min_value(mut self, duration: Duration) -> Self {
212        self.min_value = Some(duration);
213        self
214    }
215
216    /// Sets the maximum value that can by this histogram without truncation
217    ///
218    /// Values greater than this fall in the final bucket that stretches to `u64::MAX`.
219    ///
220    /// # Panics
221    /// The provided value is 0
222    pub fn max_value(mut self, duration: Duration) -> Self {
223        if duration.is_zero() {
224            panic!("max value must be greater than 0");
225        }
226        self.max_value = Some(duration);
227        self
228    }
229
230    /// Builds the log histogram, enforcing the max buckets requirement
231    pub fn max_buckets(
232        &mut self,
233        max_buckets: usize,
234    ) -> Result<LogHistogram, InvalidHistogramConfiguration> {
235        let histogram = self.build();
236        if histogram.num_buckets > max_buckets {
237            return Err(InvalidHistogramConfiguration::TooManyBuckets {
238                required_bucket_count: histogram.num_buckets,
239            });
240        }
241        Ok(histogram)
242    }
243
244    /// Builds the log histogram
245    pub fn build(&self) -> LogHistogram {
246        let requested_max_value = duration_as_u64(self.max_value.unwrap_or(DEFAULT_MAX_VALUE));
247        let max_value = requested_max_value.next_power_of_two();
248        let min_value = duration_as_u64(self.min_value.unwrap_or(DEFAULT_MIN_VALUE));
249        let p = self.precision.unwrap_or(DEFAULT_PRECISION);
250        // determine the bucket offset by finding the bucket for the minimum value. We need to lower
251        // this by one to ensure we are at least as granular as requested.
252        let bucket_offset = cmp::max(bucket_index(min_value, p), 1) - 1;
253        // n must be at least as large as p
254        let n = max_value.ilog2().max(p) + 1;
255        LogHistogram::from_n_p(n, p, bucket_offset as usize)
256            .truncate_to_max_value(requested_max_value)
257    }
258}
259
260/// Error constructing a histogram
261#[derive(Debug)]
262pub enum InvalidHistogramConfiguration {
263    /// This histogram required more than the specified number of buckets
264    TooManyBuckets {
265        /// The number of buckets that would have been required
266        required_bucket_count: usize,
267    },
268}
269
270impl Display for InvalidHistogramConfiguration {
271    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
272        match self {
273            InvalidHistogramConfiguration::TooManyBuckets { required_bucket_count } =>
274                write!(f, "The configuration for this histogram would have required {required_bucket_count} buckets")
275        }
276    }
277}
278
279impl Error for InvalidHistogramConfiguration {}
280
281/// Compute the index for a given value + p combination
282///
283/// This function does NOT enforce that the value is within the number of expected buckets.
284fn bucket_index(value: u64, p: u32) -> u64 {
285    // Algorithm described here: https://iop.systems/blog/h2-histogram/
286    // find the highest non-zero digit
287    if value == 0 {
288        return 0;
289    }
290    let h = 63 - value.leading_zeros();
291    if h <= p {
292        value
293    } else {
294        let w = h - p;
295        ((w + 1) * (1_u32 << p)) as u64 + ((value - (1_u64 << h)) >> w)
296    }
297}
298
299#[cfg(test)]
300mod test {
301    use super::InvalidHistogramConfiguration;
302    use crate::runtime::metrics::histogram::h2_histogram::LogHistogram;
303    use crate::runtime::metrics::histogram::HistogramType;
304
305    #[cfg(not(target_family = "wasm"))]
306    mod proptests {
307        use super::*;
308        use crate::runtime::metrics::batch::duration_as_u64;
309        use crate::runtime::metrics::histogram::h2_histogram::MAX_PRECISION;
310        use proptest::prelude::*;
311        use std::time::Duration;
312
313        fn valid_log_histogram_strategy() -> impl Strategy<Value = LogHistogram> {
314            (1..=50u32, 0..=MAX_PRECISION, 0..100usize).prop_map(|(n, p, bucket_offset)| {
315                let p = p.min(n);
316                let base = LogHistogram::from_n_p(n, p, 0);
317                LogHistogram::from_n_p(n, p, bucket_offset.min(base.num_buckets - 1))
318            })
319        }
320
321        fn log_histogram_settings() -> impl Strategy<Value = (u64, u64, u32)> {
322            (
323                duration_as_u64(Duration::from_nanos(1))..duration_as_u64(Duration::from_secs(20)),
324                duration_as_u64(Duration::from_secs(1))..duration_as_u64(Duration::from_secs(1000)),
325                0..MAX_PRECISION,
326            )
327        }
328
329        // test against a wide assortment of different histogram configurations to ensure invariants hold
330        proptest! {
331            #[test]
332            fn log_histogram_settings_maintain_invariants((min_value, max_value, p) in log_histogram_settings()) {
333                if max_value < min_value {
334                    return Ok(())
335                }
336                let (min_value, max_value) = (Duration::from_nanos(min_value), Duration::from_nanos(max_value));
337                let histogram = LogHistogram::builder().min_value(min_value).max_value(max_value).precision_exact(p).build();
338                let first_bucket_end = Duration::from_nanos(histogram.bucket_range(0).end);
339                let last_bucket_start = Duration::from_nanos(histogram.bucket_range(histogram.num_buckets - 1).start);
340                let second_last_bucket_start = Duration::from_nanos(histogram.bucket_range(histogram.num_buckets - 2).start);
341                prop_assert!(
342                    first_bucket_end  <= min_value,
343                    "first bucket {first_bucket_end:?} must be less than {min_value:?}"
344                );
345                prop_assert!(
346                    last_bucket_start > max_value,
347                    "last bucket start ({last_bucket_start:?} must be at least as big as `max_value` ({max_value:?})"
348                );
349
350                // We should have the exact right number of buckets. The second to last bucket should be strictly less than max value.
351                prop_assert!(
352                    second_last_bucket_start < max_value,
353                    "second last bucket end ({second_last_bucket_start:?} must be at least as big as `max_value` ({max_value:?})"
354                );
355            }
356
357            #[test]
358            fn proptest_log_histogram_invariants(histogram in valid_log_histogram_strategy()) {
359                // 1. Assert that the first bucket always starts at 0
360                let first_range = histogram.bucket_range(0);
361                prop_assert_eq!(first_range.start, 0, "First bucket doesn't start at 0");
362
363                // Check that bucket ranges are disjoint and contiguous
364                let mut prev_end = 0;
365                let mut prev_size = 0;
366                for bucket in 0..histogram.num_buckets {
367                    let range = histogram.bucket_range(bucket);
368                    prop_assert_eq!(range.start, prev_end, "Bucket ranges are not contiguous");
369                    prop_assert!(range.start < range.end, "Bucket range is empty or reversed");
370
371                    let size = range.end - range.start;
372
373                    // 2. Assert that the sizes of the buckets are always powers of 2
374                    if bucket > 0 && bucket < histogram.num_buckets - 1 {
375                        prop_assert!(size.is_power_of_two(), "Bucket size is not a power of 2");
376                    }
377
378                    if bucket > 1 {
379                        // Assert that the sizes of the buckets are monotonically increasing
380                        // (after the first bucket, which may be smaller than the 0 bucket)
381                        prop_assert!(size >= prev_size, "Bucket sizes are not monotonically increasing: This size {size} (previous: {prev_size}). Bucket: {bucket}");
382                    }
383
384
385                    // 4. Assert that the size of the buckets is always within the error bound of 2^-p
386                    if bucket > 0 && bucket < histogram.num_buckets - 1 {
387                        let p = histogram.p as f64;
388                        let error_bound = 2.0_f64.powf(-p);
389                        // the most it could be wrong is by the length of the range / 2
390                        let relative_error = ((size as f64 - 1.0) / 2.0) / range.start as f64;
391                        prop_assert!(
392                            relative_error <= error_bound,
393                            "Bucket size error exceeds bound: {:?} > {:?} ({range:?})",
394                            relative_error,
395                            error_bound
396                        );
397                    }
398
399                    prev_end = range.end;
400                    prev_size = size;
401                }
402                prop_assert_eq!(prev_end, u64::MAX, "Last bucket should end at u64::MAX");
403
404                // Check bijection between value_to_bucket and bucket_range
405                for bucket in 0..histogram.num_buckets {
406                    let range = histogram.bucket_range(bucket);
407                    for value in [range.start, range.end - 1] {
408                        prop_assert_eq!(
409                            histogram.value_to_bucket(value),
410                            bucket,
411                            "value_to_bucket is not consistent with bucket_range"
412                        );
413                    }
414                }
415            }
416        }
417    }
418
419    #[test]
420    fn bucket_ranges_are_correct() {
421        let p = 2;
422        let config = HistogramType::H2(LogHistogram {
423            num_buckets: 1024,
424            p,
425            bucket_offset: 0,
426        });
427
428        // check precise buckets. There are 2^(p+1) precise buckets
429        for i in 0..2_usize.pow(p + 1) {
430            assert_eq!(
431                config.value_to_bucket(i as u64),
432                i,
433                "{i} should be in bucket {i}"
434            );
435        }
436
437        let mut value = 2_usize.pow(p + 1);
438        let current_bucket = value;
439        while value < current_bucket * 2 {
440            assert_eq!(
441                config.value_to_bucket(value as u64),
442                current_bucket + ((value - current_bucket) / 2),
443                "bucket for {value}"
444            );
445            value += 1;
446        }
447    }
448
449    // test buckets against known values
450    #[test]
451    fn bucket_computation_spot_check() {
452        let p = 9;
453        let config = HistogramType::H2(LogHistogram {
454            num_buckets: 4096,
455            p,
456            bucket_offset: 0,
457        });
458        struct T {
459            v: u64,
460            bucket: usize,
461        }
462        let tests = [
463            T { v: 1, bucket: 1 },
464            T {
465                v: 1023,
466                bucket: 1023,
467            },
468            T {
469                v: 1024,
470                bucket: 1024,
471            },
472            T {
473                v: 2048,
474                bucket: 1536,
475            },
476            T {
477                v: 2052,
478                bucket: 1537,
479            },
480        ];
481        for test in tests {
482            assert_eq!(config.value_to_bucket(test.v), test.bucket);
483        }
484    }
485
486    #[test]
487    fn last_bucket_goes_to_infinity() {
488        let conf = HistogramType::H2(LogHistogram::from_n_p(16, 3, 10));
489        assert_eq!(conf.bucket_range(conf.num_buckets() - 1).end, u64::MAX);
490    }
491
492    #[test]
493    fn bucket_offset() {
494        // skip the first 10 buckets
495        let conf = HistogramType::H2(LogHistogram::from_n_p(16, 3, 10));
496        for i in 0..10 {
497            assert_eq!(conf.value_to_bucket(i), 0);
498        }
499        // There are 16 1-element buckets. We skipped 10 of them. The first 2 element bucket starts
500        // at 16
501        assert_eq!(conf.value_to_bucket(10), 0);
502        assert_eq!(conf.value_to_bucket(16), 6);
503        assert_eq!(conf.value_to_bucket(17), 6);
504        assert_eq!(conf.bucket_range(6), 16..18);
505    }
506
507    #[test]
508    fn max_buckets_enforcement() {
509        let error = LogHistogram::builder()
510            .max_error(0.001)
511            .max_buckets(5)
512            .expect_err("this produces way more than 5 buckets");
513        let num_buckets = match error {
514            InvalidHistogramConfiguration::TooManyBuckets {
515                required_bucket_count,
516            } => required_bucket_count,
517        };
518        assert_eq!(num_buckets, 27291);
519    }
520
521    #[test]
522    fn default_configuration_size() {
523        let conf = LogHistogram::builder().build();
524        assert_eq!(conf.num_buckets, 119);
525    }
526}
tokio/runtime/metrics/histogram/h2_histogram.rs

tokio/runtime/metrics/histogram/
h2_histogram.rs
