tokio/runtime/metrics/
histogram.rs

1mod h2_histogram;
2
3pub use h2_histogram::{InvalidHistogramConfiguration, LogHistogram, LogHistogramBuilder};
4
5use crate::util::metric_atomics::MetricAtomicU64;
6use std::sync::atomic::Ordering::Relaxed;
7
8use crate::runtime::metrics::batch::duration_as_u64;
9use std::cmp;
10use std::ops::Range;
11use std::time::Duration;
12
13#[derive(Debug)]
14pub(crate) struct Histogram {
15    /// The histogram buckets
16    buckets: Box<[MetricAtomicU64]>,
17
18    /// The type of the histogram
19    ///
20    /// This handles `fn(bucket) -> Range` and `fn(value) -> bucket`
21    histogram_type: HistogramType,
22}
23
24#[derive(Debug, Clone)]
25pub(crate) struct HistogramBuilder {
26    pub(crate) histogram_type: HistogramType,
27    pub(crate) legacy: Option<LegacyBuilder>,
28}
29
30#[derive(Debug, Clone)]
31pub(crate) struct LegacyBuilder {
32    pub(crate) resolution: u64,
33    pub(crate) scale: HistogramScale,
34    pub(crate) num_buckets: usize,
35}
36
37impl Default for LegacyBuilder {
38    fn default() -> Self {
39        Self {
40            resolution: 100_000,
41            num_buckets: 10,
42            scale: HistogramScale::Linear,
43        }
44    }
45}
46
47#[derive(Debug)]
48pub(crate) struct HistogramBatch {
49    buckets: Box<[u64]>,
50    configuration: HistogramType,
51}
52
53cfg_unstable! {
54    /// Whether the histogram used to aggregate a metric uses a linear or
55    /// logarithmic scale.
56    #[derive(Debug, Copy, Clone, Eq, PartialEq)]
57    #[non_exhaustive]
58    pub enum HistogramScale {
59        /// Linear bucket scale
60        Linear,
61
62        /// Logarithmic bucket scale
63        Log,
64    }
65
66    /// Configuration for the poll count histogram
67    #[derive(Debug, Clone)]
68    pub struct HistogramConfiguration {
69        pub(crate) inner: HistogramType
70    }
71
72    impl HistogramConfiguration {
73        /// Create a linear bucketed histogram
74        ///
75        /// # Arguments
76        ///
77        /// * `bucket_width`: The width of each bucket
78        /// * `num_buckets`: The number of buckets
79        pub fn linear(bucket_width: Duration, num_buckets: usize) -> Self {
80            Self {
81                inner: HistogramType::Linear(LinearHistogram {
82                    num_buckets,
83                    bucket_width: duration_as_u64(bucket_width),
84                }),
85            }
86        }
87
88        /// Creates a log-scaled bucketed histogram
89        ///
90        /// See [`LogHistogramBuilder`] for information about configuration & defaults
91        pub fn log(configuration: impl Into<LogHistogram>) -> Self {
92            Self {
93                inner: HistogramType::H2(configuration.into()),
94            }
95        }
96    }
97}
98
99#[derive(Debug, Clone, Copy, Eq, PartialEq)]
100pub(crate) enum HistogramType {
101    /// Linear histogram with fixed width buckets
102    Linear(LinearHistogram),
103
104    /// Old log histogram where each bucket doubles in size
105    LogLegacy(LegacyLogHistogram),
106
107    /// Log histogram implementation based on H2 Histograms
108    H2(LogHistogram),
109}
110
111impl HistogramType {
112    pub(crate) fn num_buckets(&self) -> usize {
113        match self {
114            HistogramType::Linear(linear) => linear.num_buckets,
115            HistogramType::LogLegacy(log) => log.num_buckets,
116            HistogramType::H2(h2) => h2.num_buckets,
117        }
118    }
119    fn value_to_bucket(&self, value: u64) -> usize {
120        match self {
121            HistogramType::Linear(LinearHistogram {
122                num_buckets,
123                bucket_width,
124            }) => {
125                let max = num_buckets - 1;
126                cmp::min(value / *bucket_width, max as u64) as usize
127            }
128            HistogramType::LogLegacy(LegacyLogHistogram {
129                num_buckets,
130                first_bucket_width,
131            }) => {
132                let max = num_buckets - 1;
133                if value < *first_bucket_width {
134                    0
135                } else {
136                    let significant_digits = 64 - value.leading_zeros();
137                    let bucket_digits = 64 - (first_bucket_width - 1).leading_zeros();
138                    cmp::min(significant_digits as usize - bucket_digits as usize, max)
139                }
140            }
141            HistogramType::H2(log_histogram) => log_histogram.value_to_bucket(value),
142        }
143    }
144
145    fn bucket_range(&self, bucket: usize) -> Range<u64> {
146        match self {
147            HistogramType::Linear(LinearHistogram {
148                num_buckets,
149                bucket_width,
150            }) => Range {
151                start: bucket_width * bucket as u64,
152                end: if bucket == num_buckets - 1 {
153                    u64::MAX
154                } else {
155                    bucket_width * (bucket as u64 + 1)
156                },
157            },
158            HistogramType::LogLegacy(LegacyLogHistogram {
159                num_buckets,
160                first_bucket_width,
161            }) => Range {
162                start: if bucket == 0 {
163                    0
164                } else {
165                    first_bucket_width << (bucket - 1)
166                },
167                end: if bucket == num_buckets - 1 {
168                    u64::MAX
169                } else {
170                    first_bucket_width << bucket
171                },
172            },
173            HistogramType::H2(log) => log.bucket_range(bucket),
174        }
175    }
176}
177
178#[derive(Debug, Copy, Clone, Eq, PartialEq)]
179pub(crate) struct LinearHistogram {
180    num_buckets: usize,
181    bucket_width: u64,
182}
183
184#[derive(Debug, Copy, Clone, Eq, PartialEq)]
185pub(crate) struct LegacyLogHistogram {
186    num_buckets: usize,
187    first_bucket_width: u64,
188}
189
190impl Histogram {
191    pub(crate) fn num_buckets(&self) -> usize {
192        self.buckets.len()
193    }
194
195    cfg_64bit_metrics! {
196        pub(crate) fn get(&self, bucket: usize) -> u64 {
197            self.buckets[bucket].load(Relaxed)
198        }
199    }
200
201    pub(crate) fn bucket_range(&self, bucket: usize) -> Range<u64> {
202        self.histogram_type.bucket_range(bucket)
203    }
204}
205
206impl HistogramBatch {
207    pub(crate) fn from_histogram(histogram: &Histogram) -> HistogramBatch {
208        let buckets = vec![0; histogram.buckets.len()].into_boxed_slice();
209
210        HistogramBatch {
211            buckets,
212            configuration: histogram.histogram_type,
213        }
214    }
215
216    pub(crate) fn measure(&mut self, value: u64, count: u64) {
217        self.buckets[self.value_to_bucket(value)] += count;
218    }
219
220    pub(crate) fn submit(&self, histogram: &Histogram) {
221        debug_assert_eq!(self.configuration, histogram.histogram_type);
222        debug_assert_eq!(self.buckets.len(), histogram.buckets.len());
223
224        for i in 0..self.buckets.len() {
225            histogram.buckets[i].store(self.buckets[i], Relaxed);
226        }
227    }
228
229    fn value_to_bucket(&self, value: u64) -> usize {
230        self.configuration.value_to_bucket(value)
231    }
232}
233
234impl HistogramBuilder {
235    pub(crate) fn new() -> HistogramBuilder {
236        HistogramBuilder {
237            histogram_type: HistogramType::Linear(LinearHistogram {
238                num_buckets: 10,
239                bucket_width: 100_000,
240            }),
241            legacy: None,
242        }
243    }
244
245    pub(crate) fn legacy_mut(&mut self, f: impl Fn(&mut LegacyBuilder)) {
246        let legacy = self.legacy.get_or_insert_with(|| LegacyBuilder::default());
247        f(legacy);
248    }
249
250    pub(crate) fn build(&self) -> Histogram {
251        let histogram_type = match &self.legacy {
252            Some(legacy) => {
253                assert!(legacy.resolution > 0);
254                match legacy.scale {
255                    HistogramScale::Linear => HistogramType::Linear(LinearHistogram {
256                        num_buckets: legacy.num_buckets,
257                        bucket_width: legacy.resolution,
258                    }),
259                    HistogramScale::Log => HistogramType::LogLegacy(LegacyLogHistogram {
260                        num_buckets: legacy.num_buckets,
261                        first_bucket_width: legacy.resolution.next_power_of_two(),
262                    }),
263                }
264            }
265            None => self.histogram_type,
266        };
267        let num_buckets = histogram_type.num_buckets();
268
269        Histogram {
270            buckets: (0..num_buckets)
271                .map(|_| MetricAtomicU64::new(0))
272                .collect::<Vec<_>>()
273                .into_boxed_slice(),
274            histogram_type,
275        }
276    }
277}
278
279impl Default for HistogramBuilder {
280    fn default() -> HistogramBuilder {
281        HistogramBuilder::new()
282    }
283}
284
285#[cfg(all(test, target_has_atomic = "64"))]
286mod test {
287    use super::*;
288
289    macro_rules! assert_bucket_eq {
290        ($h:expr, $bucket:expr, $val:expr) => {{
291            assert_eq!($h.buckets[$bucket], $val);
292        }};
293    }
294
295    fn linear(resolution: u64, num_buckets: usize) -> Histogram {
296        HistogramBuilder {
297            histogram_type: HistogramType::Linear(LinearHistogram {
298                bucket_width: resolution,
299                num_buckets,
300            }),
301            legacy: None,
302        }
303        .build()
304    }
305
306    #[test]
307    fn test_legacy_builder() {
308        let mut builder = HistogramBuilder::new();
309        builder.legacy_mut(|b| b.num_buckets = 20);
310        assert_eq!(builder.build().num_buckets(), 20);
311    }
312
313    #[test]
314    fn log_scale_resolution_1() {
315        let h = HistogramBuilder {
316            histogram_type: HistogramType::LogLegacy(LegacyLogHistogram {
317                first_bucket_width: 1,
318                num_buckets: 10,
319            }),
320            legacy: None,
321        }
322        .build();
323
324        assert_eq!(h.bucket_range(0), 0..1);
325        assert_eq!(h.bucket_range(1), 1..2);
326        assert_eq!(h.bucket_range(2), 2..4);
327        assert_eq!(h.bucket_range(3), 4..8);
328        assert_eq!(h.bucket_range(9), 256..u64::MAX);
329
330        let mut b = HistogramBatch::from_histogram(&h);
331
332        b.measure(0, 1);
333        assert_bucket_eq!(b, 0, 1);
334        assert_bucket_eq!(b, 1, 0);
335
336        b.measure(1, 1);
337        assert_bucket_eq!(b, 0, 1);
338        assert_bucket_eq!(b, 1, 1);
339        assert_bucket_eq!(b, 2, 0);
340
341        b.measure(2, 1);
342        assert_bucket_eq!(b, 0, 1);
343        assert_bucket_eq!(b, 1, 1);
344        assert_bucket_eq!(b, 2, 1);
345
346        b.measure(3, 1);
347        assert_bucket_eq!(b, 0, 1);
348        assert_bucket_eq!(b, 1, 1);
349        assert_bucket_eq!(b, 2, 2);
350
351        b.measure(4, 1);
352        assert_bucket_eq!(b, 0, 1);
353        assert_bucket_eq!(b, 1, 1);
354        assert_bucket_eq!(b, 2, 2);
355        assert_bucket_eq!(b, 3, 1);
356
357        b.measure(100, 1);
358        assert_bucket_eq!(b, 7, 1);
359
360        b.measure(128, 1);
361        assert_bucket_eq!(b, 8, 1);
362
363        b.measure(4096, 1);
364        assert_bucket_eq!(b, 9, 1);
365
366        b.measure(u64::MAX, 1);
367        assert_bucket_eq!(b, 9, 2);
368    }
369
370    #[test]
371    fn log_scale_resolution_2() {
372        let h = HistogramBuilder {
373            histogram_type: HistogramType::LogLegacy(LegacyLogHistogram {
374                num_buckets: 10,
375                first_bucket_width: 2,
376            }),
377            legacy: None,
378        }
379        .build();
380
381        assert_eq!(h.bucket_range(0), 0..2);
382        assert_eq!(h.bucket_range(1), 2..4);
383        assert_eq!(h.bucket_range(2), 4..8);
384        assert_eq!(h.bucket_range(3), 8..16);
385        assert_eq!(h.bucket_range(9), 512..u64::MAX);
386
387        let mut b = HistogramBatch::from_histogram(&h);
388
389        b.measure(0, 1);
390        assert_bucket_eq!(b, 0, 1);
391        assert_bucket_eq!(b, 1, 0);
392
393        b.measure(1, 1);
394        assert_bucket_eq!(b, 0, 2);
395        assert_bucket_eq!(b, 1, 0);
396
397        b.measure(2, 1);
398        assert_bucket_eq!(b, 0, 2);
399        assert_bucket_eq!(b, 1, 1);
400        assert_bucket_eq!(b, 2, 0);
401
402        b.measure(3, 1);
403        assert_bucket_eq!(b, 0, 2);
404        assert_bucket_eq!(b, 1, 2);
405        assert_bucket_eq!(b, 2, 0);
406
407        b.measure(4, 1);
408        assert_bucket_eq!(b, 0, 2);
409        assert_bucket_eq!(b, 1, 2);
410        assert_bucket_eq!(b, 2, 1);
411
412        b.measure(5, 1);
413        assert_bucket_eq!(b, 0, 2);
414        assert_bucket_eq!(b, 1, 2);
415        assert_bucket_eq!(b, 2, 2);
416
417        b.measure(6, 1);
418        assert_bucket_eq!(b, 0, 2);
419        assert_bucket_eq!(b, 1, 2);
420        assert_bucket_eq!(b, 2, 3);
421
422        b.measure(7, 1);
423        assert_bucket_eq!(b, 0, 2);
424        assert_bucket_eq!(b, 1, 2);
425        assert_bucket_eq!(b, 2, 4);
426
427        b.measure(8, 1);
428        assert_bucket_eq!(b, 0, 2);
429        assert_bucket_eq!(b, 1, 2);
430        assert_bucket_eq!(b, 2, 4);
431        assert_bucket_eq!(b, 3, 1);
432
433        b.measure(100, 1);
434        assert_bucket_eq!(b, 6, 1);
435
436        b.measure(128, 1);
437        assert_bucket_eq!(b, 7, 1);
438
439        b.measure(4096, 1);
440        assert_bucket_eq!(b, 9, 1);
441
442        for bucket in h.buckets.iter() {
443            assert_eq!(bucket.load(Relaxed), 0);
444        }
445
446        b.submit(&h);
447
448        for i in 0..h.buckets.len() {
449            assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
450        }
451
452        b.submit(&h);
453
454        for i in 0..h.buckets.len() {
455            assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
456        }
457    }
458
459    #[test]
460    fn linear_scale_resolution_1() {
461        let h = linear(1, 10);
462
463        assert_eq!(h.bucket_range(0), 0..1);
464        assert_eq!(h.bucket_range(1), 1..2);
465        assert_eq!(h.bucket_range(2), 2..3);
466        assert_eq!(h.bucket_range(3), 3..4);
467        assert_eq!(h.bucket_range(9), 9..u64::MAX);
468
469        let mut b = HistogramBatch::from_histogram(&h);
470
471        b.measure(0, 1);
472        assert_bucket_eq!(b, 0, 1);
473        assert_bucket_eq!(b, 1, 0);
474
475        b.measure(1, 1);
476        assert_bucket_eq!(b, 0, 1);
477        assert_bucket_eq!(b, 1, 1);
478        assert_bucket_eq!(b, 2, 0);
479
480        b.measure(2, 1);
481        assert_bucket_eq!(b, 0, 1);
482        assert_bucket_eq!(b, 1, 1);
483        assert_bucket_eq!(b, 2, 1);
484        assert_bucket_eq!(b, 3, 0);
485
486        b.measure(3, 1);
487        assert_bucket_eq!(b, 0, 1);
488        assert_bucket_eq!(b, 1, 1);
489        assert_bucket_eq!(b, 2, 1);
490        assert_bucket_eq!(b, 3, 1);
491
492        b.measure(5, 1);
493        assert_bucket_eq!(b, 5, 1);
494
495        b.measure(4096, 1);
496        assert_bucket_eq!(b, 9, 1);
497
498        for bucket in h.buckets.iter() {
499            assert_eq!(bucket.load(Relaxed), 0);
500        }
501
502        b.submit(&h);
503
504        for i in 0..h.buckets.len() {
505            assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
506        }
507
508        b.submit(&h);
509
510        for i in 0..h.buckets.len() {
511            assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
512        }
513    }
514
515    #[test]
516    fn linear_scale_resolution_100() {
517        let h = linear(100, 10);
518
519        assert_eq!(h.bucket_range(0), 0..100);
520        assert_eq!(h.bucket_range(1), 100..200);
521        assert_eq!(h.bucket_range(2), 200..300);
522        assert_eq!(h.bucket_range(3), 300..400);
523        assert_eq!(h.bucket_range(9), 900..u64::MAX);
524
525        let mut b = HistogramBatch::from_histogram(&h);
526
527        b.measure(0, 1);
528        assert_bucket_eq!(b, 0, 1);
529        assert_bucket_eq!(b, 1, 0);
530
531        b.measure(50, 1);
532        assert_bucket_eq!(b, 0, 2);
533        assert_bucket_eq!(b, 1, 0);
534
535        b.measure(100, 1);
536        assert_bucket_eq!(b, 0, 2);
537        assert_bucket_eq!(b, 1, 1);
538        assert_bucket_eq!(b, 2, 0);
539
540        b.measure(101, 1);
541        assert_bucket_eq!(b, 0, 2);
542        assert_bucket_eq!(b, 1, 2);
543        assert_bucket_eq!(b, 2, 0);
544
545        b.measure(200, 1);
546        assert_bucket_eq!(b, 0, 2);
547        assert_bucket_eq!(b, 1, 2);
548        assert_bucket_eq!(b, 2, 1);
549
550        b.measure(299, 1);
551        assert_bucket_eq!(b, 0, 2);
552        assert_bucket_eq!(b, 1, 2);
553        assert_bucket_eq!(b, 2, 2);
554
555        b.measure(222, 1);
556        assert_bucket_eq!(b, 0, 2);
557        assert_bucket_eq!(b, 1, 2);
558        assert_bucket_eq!(b, 2, 3);
559
560        b.measure(300, 1);
561        assert_bucket_eq!(b, 0, 2);
562        assert_bucket_eq!(b, 1, 2);
563        assert_bucket_eq!(b, 2, 3);
564        assert_bucket_eq!(b, 3, 1);
565
566        b.measure(888, 1);
567        assert_bucket_eq!(b, 8, 1);
568
569        b.measure(4096, 1);
570        assert_bucket_eq!(b, 9, 1);
571
572        for bucket in h.buckets.iter() {
573            assert_eq!(bucket.load(Relaxed), 0);
574        }
575
576        b.submit(&h);
577
578        for i in 0..h.buckets.len() {
579            assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
580        }
581
582        b.submit(&h);
583
584        for i in 0..h.buckets.len() {
585            assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
586        }
587    }
588
589    #[test]
590    fn inc_by_more_than_one() {
591        let h = linear(100, 10);
592
593        let mut b = HistogramBatch::from_histogram(&h);
594
595        b.measure(0, 3);
596        assert_bucket_eq!(b, 0, 3);
597        assert_bucket_eq!(b, 1, 0);
598
599        b.measure(50, 5);
600        assert_bucket_eq!(b, 0, 8);
601        assert_bucket_eq!(b, 1, 0);
602
603        b.measure(100, 2);
604        assert_bucket_eq!(b, 0, 8);
605        assert_bucket_eq!(b, 1, 2);
606        assert_bucket_eq!(b, 2, 0);
607
608        b.measure(101, 19);
609        assert_bucket_eq!(b, 0, 8);
610        assert_bucket_eq!(b, 1, 21);
611        assert_bucket_eq!(b, 2, 0);
612
613        for bucket in h.buckets.iter() {
614            assert_eq!(bucket.load(Relaxed), 0);
615        }
616
617        b.submit(&h);
618
619        for i in 0..h.buckets.len() {
620            assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
621        }
622
623        b.submit(&h);
624
625        for i in 0..h.buckets.len() {
626            assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
627        }
628    }
629}
tokio/runtime/metrics/histogram.rs

tokio/runtime/metrics/
histogram.rs
