zenkey_fleet/model/
bounded.rs

1//! The bound every long-lived table in this crate shares (RFC 09 §5.1 O6).
2//!
3//! An explorer that runs for hours accumulates: per-key statistics, key
4//! projections, watch state. Every one of those tables needs the same three
5//! things — a ceiling, an eviction that amortises, and a *count* of what the
6//! ceiling cost — and two of them ([`StatsTable`](crate::model::stats::StatsTable)
7//! and [`FactsCache`](crate::model::facts::FactsCache)) had shipped a
8//! byte-identical copy of the mechanism: same evict fraction, same batch
9//! scan, same `len - target` batch, differing only in the recency *type*.
10//!
11//! So the mechanism lives here, once, and the policy stays with each holder:
12//! `BoundedLru::admit` returns how many entries it dropped, and the caller
13//! adds that to its own ledger. "Evicted under the bound", "retired because
14//! nothing watches it any more" and "never projected in the first place" are
15//! different facts, and one counter over several of them is exactly what O6
16//! forbids.
17//!
18//! Recency is the caller's too: `StatsTable` orders by an injected
19//! `last_seen: Instant`, `FactsCache` by a monotone observation counter, and
20//! `BoundedLru::admit` takes whichever as a projection out of the value.
21
22use std::collections::HashMap;
23
24/// Default key bound. Large enough that no ordinary fleet reaches it — the
25/// reference application's whole telemetry fan is a few thousand keys — and
26/// small enough that a runaway key family cannot exhaust memory.
27pub const DEFAULT_MAX_KEYS: usize = 50_000;
28
29/// Fraction of the table dropped when the bound is hit.
30///
31/// Evicting in batches amortises the O(n) scan for the oldest entries across
32/// many inserts; evicting one key per insert would make every sample past the
33/// bound a full table scan.
34const EVICT_FRACTION: usize = 16;
35
36/// A map bounded at `max_keys` entries, evicting the least-recently-seen in
37/// batches — the mechanism behind both this module's [`StatsTable`] and
38/// [`FactsCache`](crate::model::facts::FactsCache), which carried a byte-identical
39/// copy of it (deep review: same [`EVICT_FRACTION`], same batch scan, same
40/// `len - target` batch; only the recency *type* differed).
41///
42/// It owns the bound and the eviction, and deliberately **not** the ledger:
43/// [`admit`](Self::admit) returns how many entries it dropped and each holder
44/// adds that to its own counters. "Evicted under the bound", "retired because
45/// nothing watches it any more" and "never projected in the first place" are
46/// different facts, and one counter over several of them is exactly what
47/// RFC 09 §5.1 O6 forbids.
48///
49/// Recency is the caller's too: `StatsTable` orders by the injected
50/// `last_seen: Instant`, `FactsCache` by a monotone observation counter, and
51/// [`admit`](Self::admit) takes whichever as a projection out of the value.
52///
53/// It lives here rather than in a module of its own because this is where the
54/// bound was first argued — [`DEFAULT_MAX_KEYS`], [`EVICT_FRACTION`] and the
55/// amortisation note `facts.rs` cites verbatim are all in this file.
56#[derive(Debug)]
57pub(crate) struct BoundedLru<K, V> {
58    entries: HashMap<K, V>,
59    max_keys: usize,
60}
61
62impl<K: std::hash::Hash + Eq + Clone, V> BoundedLru<K, V> {
63    /// A map bounded at `max_keys` entries; zero is clamped to one rather than
64    /// accepted, so eviction always has somewhere to stop.
65    pub(crate) fn with_capacity(max_keys: usize) -> Self {
66        BoundedLru {
67            entries: HashMap::new(),
68            max_keys: max_keys.max(1),
69        }
70    }
71
72    /// The bound in force.
73    pub(crate) fn max_keys(&self) -> usize {
74        self.max_keys
75    }
76
77    /// Make room for one further key: if the bound is already reached, drop
78    /// the least-recently-seen batch, ordering by `recency`. Returns how many
79    /// entries were dropped — zero on the ordinary path — which the caller
80    /// adds to its own ledger.
81    ///
82    /// Evicting in batches amortises the O(n) scan across many inserts;
83    /// evicting one key per insert would make every insert past the bound a
84    /// full scan.
85    pub(crate) fn admit<R, F>(&mut self, mut recency: F) -> usize
86    where
87        R: Ord,
88        F: FnMut(&V) -> R,
89    {
90        if self.entries.len() < self.max_keys {
91            return 0;
92        }
93        let target = self.max_keys - (self.max_keys / EVICT_FRACTION).max(1);
94        let mut seen: Vec<(R, K)> = self
95            .entries
96            .iter()
97            .map(|(k, v)| (recency(v), k.clone()))
98            .collect();
99        // Oldest first.
100        seen.sort_unstable_by(|(a, _), (b, _)| a.cmp(b));
101        let doomed = self.entries.len() - target;
102        let mut dropped = 0;
103        for (_, key) in seen.into_iter().take(doomed) {
104            if self.entries.remove(&key).is_some() {
105                dropped += 1;
106            }
107        }
108        dropped
109    }
110
111    pub(crate) fn insert(&mut self, key: K, value: V) -> Option<V> {
112        self.entries.insert(key, value)
113    }
114
115    pub(crate) fn len(&self) -> usize {
116        self.entries.len()
117    }
118
119    pub(crate) fn is_empty(&self) -> bool {
120        self.entries.is_empty()
121    }
122
123    pub(crate) fn clear(&mut self) {
124        self.entries.clear();
125    }
126
127    pub(crate) fn keys(&self) -> impl Iterator<Item = &K> {
128        self.entries.keys()
129    }
130
131    pub(crate) fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
132        self.entries.iter()
133    }
134
135    pub(crate) fn values(&self) -> impl Iterator<Item = &V> {
136        self.entries.values()
137    }
138
139    pub(crate) fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
140        self.entries.values_mut()
141    }
142
143    /// Borrowed lookup: `&str` against `String` keys, no per-sample
144    /// allocation on the hot hit path (module header).
145    pub(crate) fn get<Q>(&self, key: &Q) -> Option<&V>
146    where
147        K: std::borrow::Borrow<Q>,
148        Q: std::hash::Hash + Eq + ?Sized,
149    {
150        self.entries.get(key)
151    }
152
153    pub(crate) fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
154    where
155        K: std::borrow::Borrow<Q>,
156        Q: std::hash::Hash + Eq + ?Sized,
157    {
158        self.entries.get_mut(key)
159    }
160
161    pub(crate) fn remove<Q>(&mut self, key: &Q) -> Option<V>
162    where
163        K: std::borrow::Borrow<Q>,
164        Q: std::hash::Hash + Eq + ?Sized,
165    {
166        self.entries.remove(key)
167    }
168}
zenkey_fleet/model/bounded.rs

zenkey_fleet/model/
bounded.rs
