use std::collections::VecDeque;
use std::sync::Arc;
use std::time::{Duration, Instant};
use crate::model::bounded::{BoundedLru, DEFAULT_MAX_KEYS};
use crate::model::tree::{TreeRow, TreeRows};
use crate::report::{LatencyReport, LatencySummary};
const LAT_WINDOW: usize = 256;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum StampClass {
SelfStamped,
Foreign,
Unattributable,
}
const MAX_STAMPERS: usize = 4;
const SN_RESET_WINDOW: u32 = u32::MAX / 2;
#[derive(Debug, Clone)]
pub struct KeyStats {
pub count: u64,
pub bytes: u64,
pub rate_hz: f64,
pub last_seen: Instant,
pub sn_gaps: u64,
pub sn_resets: u64,
pub unstamped: u64,
last_sn: Option<u32>,
lat: VecDeque<(i64, StampClass)>,
stampers: std::collections::BTreeSet<zenoh::time::TimestampId>,
stampers_dropped: u64,
}
impl KeyStats {
pub fn latency(&self) -> Option<LatencyReport> {
if self.lat.is_empty() {
return None;
}
let of = |class: StampClass| {
summarise(
self.lat
.iter()
.filter(|(_, c)| *c == class)
.map(|(us, _)| *us),
)
};
Some(LatencyReport {
self_stamped: of(StampClass::SelfStamped),
foreign: of(StampClass::Foreign),
unattributable: of(StampClass::Unattributable),
stampers: self.stampers.iter().map(|id| id.to_string()).collect(),
stampers_dropped: self.stampers_dropped,
})
}
}
fn note_stamper(
set: &mut std::collections::BTreeSet<zenoh::time::TimestampId>,
dropped: &mut u64,
stamper: Option<zenoh::time::TimestampId>,
) {
let Some(id) = stamper else { return };
if set.contains(&id) {
return;
}
if set.len() >= MAX_STAMPERS {
*dropped += 1;
return;
}
set.insert(id);
}
fn summarise(values: impl Iterator<Item = i64>) -> Option<LatencySummary> {
let mut sorted: Vec<i64> = values.collect();
if sorted.is_empty() {
return None;
}
sorted.sort_unstable();
let at = |q: f64| sorted[((sorted.len() - 1) as f64 * q) as usize];
Some(LatencySummary {
min_us: sorted[0],
median_us: at(0.5),
p95_us: at(0.95),
max_us: *sorted.last().expect("non-empty"),
samples: sorted.len(),
})
}
#[derive(Debug)]
pub struct StatsTable {
keys: BoundedLru<Arc<str>, KeyStats>,
evicted: u64,
unwatched: u64,
}
impl Default for StatsTable {
fn default() -> Self {
StatsTable::with_capacity(DEFAULT_MAX_KEYS)
}
}
const TAU: Duration = Duration::from_secs(2);
impl StatsTable {
pub fn new() -> Self {
Self::default()
}
pub fn with_capacity(max_keys: usize) -> Self {
StatsTable {
keys: BoundedLru::with_capacity(max_keys),
evicted: 0,
unwatched: 0,
}
}
pub fn evicted(&self) -> u64 {
self.evicted
}
pub fn max_keys(&self) -> usize {
self.keys.max_keys()
}
pub fn unwatched(&self) -> u64 {
self.unwatched
}
pub fn retire_unwatched(&mut self, gone: &str, kept: &[String]) -> usize {
use zenoh::key_expr::keyexpr;
let Ok(gone) = keyexpr::new(gone) else {
return 0;
};
let kept: Vec<&keyexpr> = kept
.iter()
.filter_map(|k| keyexpr::new(k.as_str()).ok())
.collect();
let doomed: Vec<Arc<str>> = self
.keys
.keys()
.filter(|key| match keyexpr::new(&***key) {
Ok(ke) => gone.intersects(ke) && !kept.iter().any(|k| k.intersects(ke)),
Err(_) => false,
})
.cloned()
.collect();
for key in &doomed {
self.keys.remove(&**key);
}
self.unwatched += doomed.len() as u64;
doomed.len()
}
pub fn record(
&mut self,
key: &str,
payload_len: usize,
sn: Option<u32>,
now: Instant,
latency: Option<(i64, StampClass)>,
stamper: Option<zenoh::time::TimestampId>,
) {
if let Some(s) = self.keys.get_mut(key) {
let dt = now.saturating_duration_since(s.last_seen).as_secs_f64();
if dt > 0.0 {
let alpha = 1.0 - (-dt / TAU.as_secs_f64()).exp();
let instant_rate = 1.0 / dt;
s.rate_hz += alpha * (instant_rate - s.rate_hz);
}
s.count += 1;
s.bytes += payload_len as u64;
s.last_seen = now;
if let (Some(prev), Some(cur)) = (s.last_sn, sn) {
let delta = cur.wrapping_sub(prev);
if delta > SN_RESET_WINDOW {
s.sn_resets += 1;
} else if delta > 1 {
s.sn_gaps += u64::from(delta - 1);
}
}
s.last_sn = sn;
match latency {
Some(observed) => {
if s.lat.len() >= LAT_WINDOW {
s.lat.pop_front();
}
s.lat.push_back(observed);
}
None => s.unstamped += 1,
}
note_stamper(&mut s.stampers, &mut s.stampers_dropped, stamper);
} else {
self.evicted += self.keys.admit(|s| s.last_seen) as u64;
self.keys.insert(
Arc::from(key),
KeyStats {
count: 1,
bytes: payload_len as u64,
rate_hz: 0.0,
last_seen: now,
sn_gaps: 0,
sn_resets: 0,
unstamped: u64::from(latency.is_none()),
last_sn: sn,
lat: latency.into_iter().collect(),
stampers: {
let mut set = std::collections::BTreeSet::new();
let mut dropped = 0;
note_stamper(&mut set, &mut dropped, stamper);
set
},
stampers_dropped: 0,
},
);
}
}
pub fn get(&self, key: &str) -> Option<&KeyStats> {
self.keys.get(key)
}
pub fn iter(&self) -> impl Iterator<Item = (&str, &KeyStats)> {
self.keys.iter().map(|(k, v)| (&**k, v))
}
pub fn rows(&self) -> TreeRows {
TreeRows {
rows: self
.keys
.iter()
.map(|(key, s)| TreeRow {
key: Arc::clone(key),
count: s.count,
bytes: s.bytes,
rate_hz: s.rate_hz,
last_seen: s.last_seen,
})
.collect(),
keys: self.keys.len(),
evicted: self.evicted,
unwatched: self.unwatched,
}
}
pub fn len(&self) -> usize {
self.keys.len()
}
pub fn is_empty(&self) -> bool {
self.keys.is_empty()
}
pub fn totals(&self) -> (u64, u64, f64) {
self.keys.values().fold((0, 0, 0.0), |(c, b, r), s| {
(c + s.count, b + s.bytes, r + s.rate_hz)
})
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn the_table_is_bounded() {
let mut t = StatsTable::with_capacity(100);
let now = Instant::now();
for i in 0..1000 {
t.record(&format!("demo/k{i}"), 4, None, now, None, None);
}
assert!(t.len() <= 100, "len {} exceeds the bound", t.len());
assert!(t.evicted() > 0);
assert_eq!(t.len() as u64 + t.evicted(), 1000);
}
#[test]
fn eviction_drops_the_least_recently_seen() {
let mut t = StatsTable::with_capacity(10);
let t0 = Instant::now();
for i in 0..10 {
t.record(
&format!("old/k{i}"),
4,
None,
t0 + Duration::from_millis(i),
None,
None,
);
}
let fresh = t0 + Duration::from_secs(60);
t.record("old/k0", 4, None, fresh, None, None);
for i in 1..=5 {
t.record(
&format!("new/k{i}"),
4,
None,
fresh + Duration::from_millis(i),
None,
None,
);
}
assert!(
t.get("old/k0").is_some(),
"a key that is still publishing must survive"
);
assert!(
t.get("old/k1").is_none(),
"a key that went quiet should have been evicted first"
);
}
#[test]
fn latency_is_summarised_and_unstamped_is_counted_not_defaulted() {
let mut t = StatsTable::new();
let now = Instant::now();
for us in [1000, -200, 5000, 3000] {
t.record("k", 4, None, now, Some((us, StampClass::SelfStamped)), None);
}
t.record("k", 4, None, now, None, None);
let s = t.get("k").unwrap();
assert_eq!(s.unstamped, 1);
let lat = s.latency().unwrap();
let own = lat
.self_stamped
.expect("the publisher stamped these itself");
assert_eq!(own.min_us, -200, "negative skew is shown, not clamped");
assert_eq!(own.max_us, 5000);
assert_eq!(own.samples, 4);
assert!(own.median_us >= -200 && own.median_us <= 5000);
assert!(lat.foreign.is_none(), "nothing else stamped anything");
assert!(lat.stampers.is_empty(), "no third party to name");
t.record("quiet", 4, None, now, None, None);
assert!(t.get("quiet").unwrap().latency().is_none());
assert_eq!(t.get("quiet").unwrap().unstamped, 1);
}
#[test]
fn repeated_keys_never_trigger_eviction() {
let mut t = StatsTable::with_capacity(4);
let t0 = Instant::now();
for i in 0..1000 {
t.record(
"demo/one",
4,
None,
t0 + Duration::from_millis(i),
None,
None,
);
}
assert_eq!(t.len(), 1);
assert_eq!(t.evicted(), 0);
assert_eq!(t.get("demo/one").unwrap().count, 1000);
}
#[test]
fn a_capacity_of_one_still_works() {
let mut t = StatsTable::with_capacity(1);
let now = Instant::now();
t.record("a", 1, None, now, None, None);
t.record("b", 1, None, now, None, None);
assert_eq!(t.len(), 1);
assert_eq!(t.evicted(), 1);
assert_eq!(StatsTable::with_capacity(0).max_keys(), 1);
}
#[test]
fn rates_converge_and_gaps_count() {
let mut t = StatsTable::new();
let t0 = Instant::now();
for i in 0..100u32 {
t.record(
"v1/h-a/telemetry/x/m",
8,
Some(i),
t0 + Duration::from_millis(100 * u64::from(i)),
None,
None,
);
}
let s = t.get("v1/h-a/telemetry/x/m").unwrap();
assert_eq!(s.count, 100);
assert_eq!(s.bytes, 800);
assert!((s.rate_hz - 10.0).abs() < 1.0, "rate {}", s.rate_hz);
assert_eq!(s.sn_gaps, 0);
t.record(
"v1/h-a/telemetry/x/m",
8,
Some(105),
t0 + Duration::from_millis(10_100),
None,
None,
);
assert_eq!(t.get("v1/h-a/telemetry/x/m").unwrap().sn_gaps, 5);
}
#[test]
fn totals_aggregate() {
let mut t = StatsTable::new();
let now = Instant::now();
t.record("a", 10, None, now, None, None);
t.record("b", 20, None, now, None, None);
let (count, bytes, _) = t.totals();
assert_eq!((count, bytes), (2, 30));
assert_eq!(t.len(), 2);
}
#[test]
fn retire_unwatched_respects_remaining_coverage() {
let mut t = StatsTable::new();
let now = Instant::now();
t.record("v1/h-a/telemetry/x/m1", 4, None, now, None, None);
t.record("v1/h-a/state/x/health", 4, None, now, None, None);
t.record("v1/h-b/telemetry/y/m2", 4, None, now, None, None);
let retired = t.retire_unwatched("v1/*/telemetry/**", &["v1/h-a/**".to_string()]);
assert_eq!(retired, 1, "only h-b's telemetry loses coverage");
assert!(
t.get("v1/h-a/telemetry/x/m1").is_some(),
"still covered by kept"
);
assert!(t.get("v1/h-b/telemetry/y/m2").is_none());
assert_eq!(t.unwatched(), 1);
let retired = t.retire_unwatched("**", &[]);
assert_eq!(retired, 2);
assert_eq!(t.len(), 0);
assert_eq!(t.unwatched(), 3);
}
#[test]
fn retire_unwatched_tolerates_bad_selectors() {
let mut t = StatsTable::new();
t.record("a/b", 1, None, Instant::now(), None, None);
assert_eq!(t.retire_unwatched("", &[]), 0);
assert_eq!(t.len(), 1);
}
#[test]
fn two_stampers_are_never_folded_into_one_median() {
let mut t = StatsTable::new();
let now = Instant::now();
let router = zenoh::time::TimestampId::rand();
for us in [100, 120, 140, 160] {
t.record("k", 4, None, now, Some((us, StampClass::SelfStamped)), None);
}
for us in [9000, 9500, 10_000] {
t.record(
"k",
4,
None,
now,
Some((us, StampClass::Foreign)),
Some(router),
);
}
let lat = t
.get("k")
.unwrap()
.latency()
.expect("something was stamped");
let own = lat.self_stamped.expect("the publisher-stamped population");
let far = lat.foreign.expect("the router-stamped population");
assert_eq!(own.samples, 4);
assert_eq!(far.samples, 3);
assert_eq!(own.max_us, 160);
assert_eq!(far.min_us, 9000);
assert!(
own.median_us < far.median_us,
"two populations, two medians: {} vs {}",
own.median_us,
far.median_us
);
assert_eq!(
lat.stampers,
vec![router.to_string()],
"the third-party stamper is named, not averaged away"
);
assert!(lat.unattributable.is_none());
let orphan = zenoh::time::TimestampId::rand();
t.record(
"u",
4,
None,
now,
Some((7, StampClass::Unattributable)),
Some(orphan),
);
let u = t.get("u").unwrap().latency().unwrap();
assert!(u.unattributable.is_some());
assert!(u.foreign.is_none(), "unknown is not foreign");
}
#[test]
fn the_stamper_set_is_bounded_and_says_what_it_dropped() {
let mut t = StatsTable::new();
let now = Instant::now();
for _ in 0..(MAX_STAMPERS + 3) {
t.record(
"k",
4,
None,
now,
Some((10, StampClass::Foreign)),
Some(zenoh::time::TimestampId::rand()),
);
}
let lat = t.get("k").unwrap().latency().unwrap();
assert_eq!(lat.stampers.len(), MAX_STAMPERS);
assert_eq!(lat.stampers_dropped, 3, "the bound reports its cost");
}
#[test]
fn the_caveat_names_the_clock_it_measured_from() {
let self_only = LatencyReport {
self_stamped: Some(LatencySummary {
min_us: 1,
median_us: 2,
p95_us: 3,
max_us: 4,
samples: 4,
}),
..LatencyReport::default()
};
assert!(
self_only.caveat().contains("the publisher's own HLC"),
"{}",
self_only.caveat()
);
let router_only = LatencyReport {
foreign: self_only.self_stamped,
stampers: vec!["abcd".into()],
..LatencyReport::default()
};
let note = router_only.caveat();
assert!(
note.contains("stamped in transit, not the publisher's"),
"{note}"
);
assert!(note.contains("abcd"), "the stamper is named: {note}");
let both = LatencyReport {
self_stamped: self_only.self_stamped,
foreign: self_only.self_stamped,
..LatencyReport::default()
};
assert!(both.caveat().contains("kept apart"), "{}", both.caveat());
}
}