1 mod h2_histogram;
2 
3 pub use h2_histogram::{InvalidHistogramConfiguration, LogHistogram, LogHistogramBuilder};
4 
5 use crate::util::metric_atomics::MetricAtomicU64;
6 use std::sync::atomic::Ordering::Relaxed;
7 
8 use crate::runtime::metrics::batch::duration_as_u64;
9 use std::cmp;
10 use std::ops::Range;
11 use std::time::Duration;
12 
13 #[derive(Debug)]
14 pub(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)]
25 pub(crate) struct HistogramBuilder {
26     pub(crate) histogram_type: HistogramType,
27     pub(crate) legacy: Option<LegacyBuilder>,
28 }
29 
30 #[derive(Debug, Clone)]
31 pub(crate) struct LegacyBuilder {
32     pub(crate) resolution: u64,
33     pub(crate) scale: HistogramScale,
34     pub(crate) num_buckets: usize,
35 }
36 
37 impl Default for LegacyBuilder {
default() -> Self38     fn default() -> Self {
39         Self {
40             resolution: 100_000,
41             num_buckets: 10,
42             scale: HistogramScale::Linear,
43         }
44     }
45 }
46 
47 #[derive(Debug)]
48 pub(crate) struct HistogramBatch {
49     buckets: Box<[u64]>,
50     configuration: HistogramType,
51 }
52 
53 cfg_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)]
100 pub(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 
111 impl HistogramType {
num_buckets(&self) -> usize112     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     }
value_to_bucket(&self, value: u64) -> usize119     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 
bucket_range(&self, bucket: usize) -> Range<u64>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)]
179 pub(crate) struct LinearHistogram {
180     num_buckets: usize,
181     bucket_width: u64,
182 }
183 
184 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
185 pub(crate) struct LegacyLogHistogram {
186     num_buckets: usize,
187     first_bucket_width: u64,
188 }
189 
190 impl Histogram {
num_buckets(&self) -> usize191     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 
bucket_range(&self, bucket: usize) -> Range<u64>201     pub(crate) fn bucket_range(&self, bucket: usize) -> Range<u64> {
202         self.histogram_type.bucket_range(bucket)
203     }
204 }
205 
206 impl HistogramBatch {
from_histogram(histogram: &Histogram) -> HistogramBatch207     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 
measure(&mut self, value: u64, count: u64)216     pub(crate) fn measure(&mut self, value: u64, count: u64) {
217         self.buckets[self.value_to_bucket(value)] += count;
218     }
219 
submit(&self, histogram: &Histogram)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 
value_to_bucket(&self, value: u64) -> usize229     fn value_to_bucket(&self, value: u64) -> usize {
230         self.configuration.value_to_bucket(value)
231     }
232 }
233 
234 impl HistogramBuilder {
new() -> HistogramBuilder235     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 
legacy_mut(&mut self, f: impl Fn(&mut LegacyBuilder))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 
build(&self) -> Histogram250     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 
279 impl Default for HistogramBuilder {
default() -> HistogramBuilder280     fn default() -> HistogramBuilder {
281         HistogramBuilder::new()
282     }
283 }
284 
285 #[cfg(all(test, target_has_atomic = "64"))]
286 mod 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 
linear(resolution: u64, num_buckets: usize) -> Histogram295     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]
test_legacy_builder()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]
log_scale_resolution_1()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]
log_scale_resolution_2()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]
linear_scale_resolution_1()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]
linear_scale_resolution_100()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]
inc_by_more_than_one()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 }
630