hashiverse_lib/client/caching/
cache_radius_tracker.rs

1//! # Cache-radius tracker for DHT walk pruning
2//!
3//! Records, per-location and with a TTL, how far out in the DHT (measured in
4//! [`crate::tools::tools::LeadingAgreementBits`]) we've already seen cached copies of a
5//! given bundle. Subsequent DHT walks for the same location consult the tracker and skip
6//! peers that are closer than the recorded radius — those peers are almost certainly
7//! already cached — and instead try wider. This spreads cache load outward over time and
8//! relieves the small set of "closest" peers from being hammered for every read.
9//!
10//! Uses `parking_lot::RwLock` because the tracker is read on every timeline walk but
11//! written only when a new cached hit comes back.
12
13use crate::tools::time::{DurationMillis, TimeMillis};
14use crate::tools::tools::LeadingAgreementBits;
15use crate::tools::types::Id;
16use parking_lot::RwLock;
17use std::collections::HashMap;
18
19/// Per-location TTL store of the walk's cache radius.
20///
21/// The cache radius is the minimum `LeadingAgreementBits` of all servers that returned data
22/// during the previous walk. It represents how far out caching has propagated: all servers
23/// with LAB ≥ radius are likely to already hold cached data, so future walks can try a little further out, thereby alleviating load.
24pub struct CacheRadiusTracker {
25    radii: RwLock<HashMap<Id, (LeadingAgreementBits, TimeMillis)>>,
26    ttl: DurationMillis,
27}
28
29impl CacheRadiusTracker {
30    pub fn new(ttl: DurationMillis) -> Self {
31        Self {
32            radii: RwLock::new(HashMap::new()),
33            ttl,
34        }
35    }
36
37    /// Returns the cached radius if it has not expired.
38    pub fn get(&self, location_id: Id, now: TimeMillis) -> Option<LeadingAgreementBits> {
39        let radii = self.radii.read();
40        if let Some(&(radius, stored_at)) = radii.get(&location_id) {
41            if (now - stored_at) < self.ttl {
42                return Some(radius);
43            }
44        }
45        None
46    }
47
48    /// Replaces the stored radius unconditionally (each walk produces a fresh observation).
49    pub fn update(&self, location_id: Id, radius: LeadingAgreementBits, now: TimeMillis) {
50        self.radii.write().insert(location_id, (radius, now));
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57    use crate::tools::time::{DurationMillis, TimeMillis};
58    use crate::tools::types::Id;
59
60    #[test]
61    fn test_get_returns_none_when_empty() {
62        let tracker = CacheRadiusTracker::new(DurationMillis(60_000));
63        let id = Id::random();
64        let now = TimeMillis(1_000_000);
65        assert_eq!(None, tracker.get(id, now));
66    }
67
68    #[test]
69    fn test_update_and_get() {
70        let tracker = CacheRadiusTracker::new(DurationMillis(60_000));
71        let id = Id::random();
72        let now = TimeMillis(1_000_000);
73        tracker.update(id, 10, now);
74        assert_eq!(Some(10), tracker.get(id, now));
75        assert_eq!(Some(10), tracker.get(id, TimeMillis(1_000_000 + 59_999)));
76    }
77
78    #[test]
79    fn test_get_returns_none_after_ttl() {
80        let tracker = CacheRadiusTracker::new(DurationMillis(60_000));
81        let id = Id::random();
82        let now = TimeMillis(1_000_000);
83        tracker.update(id, 10, now);
84        assert_eq!(None, tracker.get(id, TimeMillis(1_000_000 + 60_000)));
85        assert_eq!(None, tracker.get(id, TimeMillis(1_000_000 + 120_000)));
86    }
87
88    #[test]
89    fn test_update_overwrites() {
90        let tracker = CacheRadiusTracker::new(DurationMillis(60_000));
91        let id = Id::random();
92        let now = TimeMillis(1_000_000);
93        tracker.update(id, 10, now);
94        tracker.update(id, 20, now);
95        assert_eq!(Some(20), tracker.get(id, now));
96    }
97
98    #[test]
99    fn test_different_locations_independent() {
100        let tracker = CacheRadiusTracker::new(DurationMillis(60_000));
101        let id1 = Id::random();
102        let id2 = Id::random();
103        let now = TimeMillis(1_000_000);
104        tracker.update(id1, 10, now);
105        assert_eq!(Some(10), tracker.get(id1, now));
106        assert_eq!(None, tracker.get(id2, now));
107    }
108}
hashiverse_lib/client/caching/cache_radius_tracker.rs

hashiverse_lib/client/caching/
cache_radius_tracker.rs
