use std::{
collections::{BTreeMap, VecDeque},
time::{Duration, Instant},
};
pub(super) const QUANTILES: [f64; 7] = [0.0, 0.5, 0.9, 0.95, 0.99, 0.999, 1.0];
pub(super) const RELATIVE_ACCURACY: f64 = 0.001;
pub(super) const MAX_BUCKETS: usize = 8192;
const MIN_VALUE: f64 = 1e-9;
pub(super) const WINDOW_DURATION: Duration = Duration::from_secs(20);
pub(super) const WINDOW_COUNT: u32 = 3;
fn gamma() -> f64 {
(1.0 + RELATIVE_ACCURACY) / (1.0 - RELATIVE_ACCURACY)
}
fn bucket(value: f64) -> i32 {
(value.ln() / gamma().ln()).ceil() as i32
}
fn bucket_value(bucket: i32) -> f64 {
let gamma = gamma();
(f64::from(bucket) * gamma.ln()).exp() * 2.0 / (1.0 + gamma)
}
#[derive(Clone, Debug, Default)]
pub(super) struct Sketch {
positive: BTreeMap<i32, u64>,
negative: BTreeMap<i32, u64>,
zero: u64,
count: u64,
min: f64,
max: f64,
}
impl Sketch {
pub(super) fn add(&mut self, value: f64) {
debug_assert!(value.is_finite(), "callers only add finite samples");
if value >= MIN_VALUE {
add_to(&mut self.positive, bucket(value), 1);
} else if value <= -MIN_VALUE {
add_to(&mut self.negative, bucket(-value), 1);
} else {
self.zero += 1;
}
if self.count == 0 {
self.min = value;
self.max = value;
} else {
self.min = self.min.min(value);
self.max = self.max.max(value);
}
self.count += 1;
}
pub(super) fn merge(&mut self, other: &Sketch) {
if other.count == 0 {
return;
}
for (&bucket, &count) in &other.positive {
add_to(&mut self.positive, bucket, count);
}
for (&bucket, &count) in &other.negative {
add_to(&mut self.negative, bucket, count);
}
self.zero += other.zero;
if self.count == 0 {
self.min = other.min;
self.max = other.max;
} else {
self.min = self.min.min(other.min);
self.max = self.max.max(other.max);
}
self.count += other.count;
}
pub(super) fn quantile(&self, q: f64) -> Option<f64> {
if self.count == 0 {
return None;
}
if q <= 0.0 {
return Some(self.min);
}
if q >= 1.0 {
return Some(self.max);
}
let rank = (q * (self.count - 1) as f64) as u64;
let mut seen = 0;
for (&bucket, &count) in self.negative.iter().rev() {
seen += count;
if seen > rank {
return Some(-bucket_value(bucket));
}
}
seen += self.zero;
if seen > rank {
return Some(0.0);
}
for (&bucket, &count) in &self.positive {
seen += count;
if seen > rank {
return Some(bucket_value(bucket));
}
}
Some(self.max)
}
}
#[cfg(test)]
impl Sketch {
pub(super) fn positive_bucket_count(&self) -> usize {
self.positive.len()
}
}
fn add_to(buckets: &mut BTreeMap<i32, u64>, bucket: i32, count: u64) {
*buckets.entry(bucket).or_default() += count;
while buckets.len() > MAX_BUCKETS {
let (_, smallest) = buckets
.pop_first()
.expect("there are more than MAX_BUCKETS buckets");
*buckets
.first_entry()
.expect("there were more than MAX_BUCKETS buckets")
.get_mut() += smallest;
}
}
#[derive(Debug)]
pub(super) struct RollingSummary {
start: Instant,
windows: VecDeque<(u64, Sketch)>,
count: u64,
sum: f64,
}
impl RollingSummary {
pub(super) fn new(start: Instant) -> Self {
Self {
start,
windows: VecDeque::new(),
count: 0,
sum: 0.0,
}
}
pub(super) fn add(&mut self, value: f64, now: Instant) {
self.count += 1;
self.sum += value;
if !value.is_finite() {
return;
}
let index = self.window_index(now);
let position = self.windows.partition_point(|(window, _)| *window < index);
match self.windows.get_mut(position) {
Some((window, sketch)) if *window == index => sketch.add(value),
_ => {
let mut sketch = Sketch::default();
sketch.add(value);
self.windows.insert(position, (index, sketch));
while self.windows.len() > WINDOW_COUNT as usize {
self.windows.pop_front();
}
}
}
}
pub(super) fn recent(&self, now: Instant) -> Sketch {
let current = self.window_index(now);
let mut recent = Sketch::default();
for (index, sketch) in &self.windows {
if index + u64::from(WINDOW_COUNT) > current {
recent.merge(sketch);
}
}
recent
}
pub(super) fn count(&self) -> u64 {
self.count
}
pub(super) fn sum(&self) -> f64 {
self.sum
}
fn window_index(&self, now: Instant) -> u64 {
let elapsed = now.saturating_duration_since(self.start);
(elapsed.as_nanos() / WINDOW_DURATION.as_nanos()) as u64
}
}