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

tokio/runtime/metrics/histogram/
h2_histogram.rs
