mod h2_histogram; pub use h2_histogram::{InvalidHistogramConfiguration, LogHistogram, LogHistogramBuilder}; use crate::util::metric_atomics::MetricAtomicU64; use std::sync::atomic::Ordering::Relaxed; use crate::runtime::metrics::batch::duration_as_u64; use std::cmp; use std::ops::Range; use std::time::Duration; #[derive(Debug)] pub(crate) struct Histogram { /// The histogram buckets buckets: Box<[MetricAtomicU64]>, /// The type of the histogram /// /// This handles `fn(bucket) -> Range` and `fn(value) -> bucket` histogram_type: HistogramType, } #[derive(Debug, Clone)] pub(crate) struct HistogramBuilder { pub(crate) histogram_type: HistogramType, pub(crate) legacy: Option, } #[derive(Debug, Clone)] pub(crate) struct LegacyBuilder { pub(crate) resolution: u64, pub(crate) scale: HistogramScale, pub(crate) num_buckets: usize, } impl Default for LegacyBuilder { fn default() -> Self { Self { resolution: 100_000, num_buckets: 10, scale: HistogramScale::Linear, } } } #[derive(Debug)] pub(crate) struct HistogramBatch { buckets: Box<[u64]>, configuration: HistogramType, } cfg_unstable! { /// Whether the histogram used to aggregate a metric uses a linear or /// logarithmic scale. #[derive(Debug, Copy, Clone, Eq, PartialEq)] #[non_exhaustive] pub enum HistogramScale { /// Linear bucket scale Linear, /// Logarithmic bucket scale Log, } /// Configuration for the poll count histogram #[derive(Debug, Clone)] pub struct HistogramConfiguration { pub(crate) inner: HistogramType } impl HistogramConfiguration { /// Create a linear bucketed histogram /// /// # Arguments /// /// * `bucket_width`: The width of each bucket /// * `num_buckets`: The number of buckets pub fn linear(bucket_width: Duration, num_buckets: usize) -> Self { Self { inner: HistogramType::Linear(LinearHistogram { num_buckets, bucket_width: duration_as_u64(bucket_width), }), } } /// Creates a log-scaled bucketed histogram /// /// See [`LogHistogramBuilder`] for information about configuration & defaults pub fn log(configuration: impl Into) -> Self { Self { inner: HistogramType::H2(configuration.into()), } } } } #[derive(Debug, Clone, Copy, Eq, PartialEq)] pub(crate) enum HistogramType { /// Linear histogram with fixed width buckets Linear(LinearHistogram), /// Old log histogram where each bucket doubles in size LogLegacy(LegacyLogHistogram), /// Log histogram implementation based on H2 Histograms H2(LogHistogram), } impl HistogramType { pub(crate) fn num_buckets(&self) -> usize { match self { HistogramType::Linear(linear) => linear.num_buckets, HistogramType::LogLegacy(log) => log.num_buckets, HistogramType::H2(h2) => h2.num_buckets, } } fn value_to_bucket(&self, value: u64) -> usize { match self { HistogramType::Linear(LinearHistogram { num_buckets, bucket_width, }) => { let max = num_buckets - 1; cmp::min(value / *bucket_width, max as u64) as usize } HistogramType::LogLegacy(LegacyLogHistogram { num_buckets, first_bucket_width, }) => { let max = num_buckets - 1; if value < *first_bucket_width { 0 } else { let significant_digits = 64 - value.leading_zeros(); let bucket_digits = 64 - (first_bucket_width - 1).leading_zeros(); cmp::min(significant_digits as usize - bucket_digits as usize, max) } } HistogramType::H2(log_histogram) => log_histogram.value_to_bucket(value), } } fn bucket_range(&self, bucket: usize) -> Range { match self { HistogramType::Linear(LinearHistogram { num_buckets, bucket_width, }) => Range { start: bucket_width * bucket as u64, end: if bucket == num_buckets - 1 { u64::MAX } else { bucket_width * (bucket as u64 + 1) }, }, HistogramType::LogLegacy(LegacyLogHistogram { num_buckets, first_bucket_width, }) => Range { start: if bucket == 0 { 0 } else { first_bucket_width << (bucket - 1) }, end: if bucket == num_buckets - 1 { u64::MAX } else { first_bucket_width << bucket }, }, HistogramType::H2(log) => log.bucket_range(bucket), } } } #[derive(Debug, Copy, Clone, Eq, PartialEq)] pub(crate) struct LinearHistogram { num_buckets: usize, bucket_width: u64, } #[derive(Debug, Copy, Clone, Eq, PartialEq)] pub(crate) struct LegacyLogHistogram { num_buckets: usize, first_bucket_width: u64, } impl Histogram { pub(crate) fn num_buckets(&self) -> usize { self.buckets.len() } cfg_64bit_metrics! { pub(crate) fn get(&self, bucket: usize) -> u64 { self.buckets[bucket].load(Relaxed) } } pub(crate) fn bucket_range(&self, bucket: usize) -> Range { self.histogram_type.bucket_range(bucket) } } impl HistogramBatch { pub(crate) fn from_histogram(histogram: &Histogram) -> HistogramBatch { let buckets = vec![0; histogram.buckets.len()].into_boxed_slice(); HistogramBatch { buckets, configuration: histogram.histogram_type, } } pub(crate) fn measure(&mut self, value: u64, count: u64) { self.buckets[self.value_to_bucket(value)] += count; } pub(crate) fn submit(&self, histogram: &Histogram) { debug_assert_eq!(self.configuration, histogram.histogram_type); debug_assert_eq!(self.buckets.len(), histogram.buckets.len()); for i in 0..self.buckets.len() { histogram.buckets[i].store(self.buckets[i], Relaxed); } } fn value_to_bucket(&self, value: u64) -> usize { self.configuration.value_to_bucket(value) } } impl HistogramBuilder { pub(crate) fn new() -> HistogramBuilder { HistogramBuilder { histogram_type: HistogramType::Linear(LinearHistogram { num_buckets: 10, bucket_width: 100_000, }), legacy: None, } } pub(crate) fn legacy_mut(&mut self, f: impl Fn(&mut LegacyBuilder)) { let legacy = self.legacy.get_or_insert_with(|| LegacyBuilder::default()); f(legacy); } pub(crate) fn build(&self) -> Histogram { let histogram_type = match &self.legacy { Some(legacy) => { assert!(legacy.resolution > 0); match legacy.scale { HistogramScale::Linear => HistogramType::Linear(LinearHistogram { num_buckets: legacy.num_buckets, bucket_width: legacy.resolution, }), HistogramScale::Log => HistogramType::LogLegacy(LegacyLogHistogram { num_buckets: legacy.num_buckets, first_bucket_width: legacy.resolution.next_power_of_two(), }), } } None => self.histogram_type, }; let num_buckets = histogram_type.num_buckets(); Histogram { buckets: (0..num_buckets) .map(|_| MetricAtomicU64::new(0)) .collect::>() .into_boxed_slice(), histogram_type, } } } impl Default for HistogramBuilder { fn default() -> HistogramBuilder { HistogramBuilder::new() } } #[cfg(all(test, target_has_atomic = "64"))] mod test { use super::*; macro_rules! assert_bucket_eq { ($h:expr, $bucket:expr, $val:expr) => {{ assert_eq!($h.buckets[$bucket], $val); }}; } fn linear(resolution: u64, num_buckets: usize) -> Histogram { HistogramBuilder { histogram_type: HistogramType::Linear(LinearHistogram { bucket_width: resolution, num_buckets, }), legacy: None, } .build() } #[test] fn test_legacy_builder() { let mut builder = HistogramBuilder::new(); builder.legacy_mut(|b| b.num_buckets = 20); assert_eq!(builder.build().num_buckets(), 20); } #[test] fn log_scale_resolution_1() { let h = HistogramBuilder { histogram_type: HistogramType::LogLegacy(LegacyLogHistogram { first_bucket_width: 1, num_buckets: 10, }), legacy: None, } .build(); assert_eq!(h.bucket_range(0), 0..1); assert_eq!(h.bucket_range(1), 1..2); assert_eq!(h.bucket_range(2), 2..4); assert_eq!(h.bucket_range(3), 4..8); assert_eq!(h.bucket_range(9), 256..u64::MAX); let mut b = HistogramBatch::from_histogram(&h); b.measure(0, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 0); b.measure(1, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 1); assert_bucket_eq!(b, 2, 0); b.measure(2, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 1); assert_bucket_eq!(b, 2, 1); b.measure(3, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 1); assert_bucket_eq!(b, 2, 2); b.measure(4, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 1); assert_bucket_eq!(b, 2, 2); assert_bucket_eq!(b, 3, 1); b.measure(100, 1); assert_bucket_eq!(b, 7, 1); b.measure(128, 1); assert_bucket_eq!(b, 8, 1); b.measure(4096, 1); assert_bucket_eq!(b, 9, 1); b.measure(u64::MAX, 1); assert_bucket_eq!(b, 9, 2); } #[test] fn log_scale_resolution_2() { let h = HistogramBuilder { histogram_type: HistogramType::LogLegacy(LegacyLogHistogram { num_buckets: 10, first_bucket_width: 2, }), legacy: None, } .build(); assert_eq!(h.bucket_range(0), 0..2); assert_eq!(h.bucket_range(1), 2..4); assert_eq!(h.bucket_range(2), 4..8); assert_eq!(h.bucket_range(3), 8..16); assert_eq!(h.bucket_range(9), 512..u64::MAX); let mut b = HistogramBatch::from_histogram(&h); b.measure(0, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 0); b.measure(1, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 0); b.measure(2, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 1); assert_bucket_eq!(b, 2, 0); b.measure(3, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 0); b.measure(4, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 1); b.measure(5, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 2); b.measure(6, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 3); b.measure(7, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 4); b.measure(8, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 4); assert_bucket_eq!(b, 3, 1); b.measure(100, 1); assert_bucket_eq!(b, 6, 1); b.measure(128, 1); assert_bucket_eq!(b, 7, 1); b.measure(4096, 1); assert_bucket_eq!(b, 9, 1); for bucket in h.buckets.iter() { assert_eq!(bucket.load(Relaxed), 0); } b.submit(&h); for i in 0..h.buckets.len() { assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]); } b.submit(&h); for i in 0..h.buckets.len() { assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]); } } #[test] fn linear_scale_resolution_1() { let h = linear(1, 10); assert_eq!(h.bucket_range(0), 0..1); assert_eq!(h.bucket_range(1), 1..2); assert_eq!(h.bucket_range(2), 2..3); assert_eq!(h.bucket_range(3), 3..4); assert_eq!(h.bucket_range(9), 9..u64::MAX); let mut b = HistogramBatch::from_histogram(&h); b.measure(0, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 0); b.measure(1, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 1); assert_bucket_eq!(b, 2, 0); b.measure(2, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 1); assert_bucket_eq!(b, 2, 1); assert_bucket_eq!(b, 3, 0); b.measure(3, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 1); assert_bucket_eq!(b, 2, 1); assert_bucket_eq!(b, 3, 1); b.measure(5, 1); assert_bucket_eq!(b, 5, 1); b.measure(4096, 1); assert_bucket_eq!(b, 9, 1); for bucket in h.buckets.iter() { assert_eq!(bucket.load(Relaxed), 0); } b.submit(&h); for i in 0..h.buckets.len() { assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]); } b.submit(&h); for i in 0..h.buckets.len() { assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]); } } #[test] fn linear_scale_resolution_100() { let h = linear(100, 10); assert_eq!(h.bucket_range(0), 0..100); assert_eq!(h.bucket_range(1), 100..200); assert_eq!(h.bucket_range(2), 200..300); assert_eq!(h.bucket_range(3), 300..400); assert_eq!(h.bucket_range(9), 900..u64::MAX); let mut b = HistogramBatch::from_histogram(&h); b.measure(0, 1); assert_bucket_eq!(b, 0, 1); assert_bucket_eq!(b, 1, 0); b.measure(50, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 0); b.measure(100, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 1); assert_bucket_eq!(b, 2, 0); b.measure(101, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 0); b.measure(200, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 1); b.measure(299, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 2); b.measure(222, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 3); b.measure(300, 1); assert_bucket_eq!(b, 0, 2); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 3); assert_bucket_eq!(b, 3, 1); b.measure(888, 1); assert_bucket_eq!(b, 8, 1); b.measure(4096, 1); assert_bucket_eq!(b, 9, 1); for bucket in h.buckets.iter() { assert_eq!(bucket.load(Relaxed), 0); } b.submit(&h); for i in 0..h.buckets.len() { assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]); } b.submit(&h); for i in 0..h.buckets.len() { assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]); } } #[test] fn inc_by_more_than_one() { let h = linear(100, 10); let mut b = HistogramBatch::from_histogram(&h); b.measure(0, 3); assert_bucket_eq!(b, 0, 3); assert_bucket_eq!(b, 1, 0); b.measure(50, 5); assert_bucket_eq!(b, 0, 8); assert_bucket_eq!(b, 1, 0); b.measure(100, 2); assert_bucket_eq!(b, 0, 8); assert_bucket_eq!(b, 1, 2); assert_bucket_eq!(b, 2, 0); b.measure(101, 19); assert_bucket_eq!(b, 0, 8); assert_bucket_eq!(b, 1, 21); assert_bucket_eq!(b, 2, 0); for bucket in h.buckets.iter() { assert_eq!(bucket.load(Relaxed), 0); } b.submit(&h); for i in 0..h.buckets.len() { assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]); } b.submit(&h); for i in 0..h.buckets.len() { assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]); } } }