hypercall/rsm/
bounded_idempotence_cache.rs

1//! Bounded idempotence cache for request_id deduplication.
2//!
3//! Provides a FIFO cache with O(1) lookups that prevents unbounded memory growth
4//! while maintaining efficient duplicate detection.
5
6use std::collections::{HashSet, VecDeque};
7use uuid::Uuid;
8
9/// Default capacity for the idempotence cache.
10/// ~3.2 MB memory for 32-byte average request_ids.
11pub const DEFAULT_CAPACITY: usize = 100_000;
12
13/// A bounded FIFO cache for idempotency checking.
14///
15/// Uses a ring buffer (VecDeque) for eviction order and HashSet for fast membership checks.
16/// When capacity is reached, the oldest entries are evicted to make room for new ones.
17pub struct BoundedIdempotenceCache {
18    /// Ring buffer storing request_ids in insertion order (oldest at front)
19    order: VecDeque<Uuid>,
20    /// Fast O(1) membership lookup
21    set: HashSet<Uuid>,
22    /// Maximum capacity
23    capacity: usize,
24}
25
26impl BoundedIdempotenceCache {
27    /// Create a new cache with the specified capacity.
28    pub fn with_capacity(capacity: usize) -> Self {
29        Self {
30            order: VecDeque::with_capacity(capacity),
31            set: HashSet::with_capacity(capacity),
32            capacity,
33        }
34    }
35
36    /// Create a new cache with the default capacity (100,000 entries).
37    pub fn new() -> Self {
38        Self::with_capacity(DEFAULT_CAPACITY)
39    }
40
41    /// Insert a request_id into the cache.
42    ///
43    /// If the request_id already exists, this is a no-op.
44    /// If the cache is at capacity, the oldest entry is evicted first.
45    pub fn insert(&mut self, request_id: Uuid) {
46        if self.set.contains(&request_id) {
47            return; // Already present
48        }
49
50        // Evict oldest if at capacity
51        if self.order.len() >= self.capacity {
52            if let Some(oldest) = self.order.pop_front() {
53                self.set.remove(&oldest);
54            }
55        }
56
57        self.order.push_back(request_id);
58        self.set.insert(request_id);
59    }
60
61    /// Check if a request_id is in the cache.
62    pub fn contains(&self, request_id: &Uuid) -> bool {
63        self.set.contains(request_id)
64    }
65
66    /// Return the number of entries in the cache.
67    pub fn len(&self) -> usize {
68        self.set.len()
69    }
70
71    /// Check if the cache is empty.
72    pub fn is_empty(&self) -> bool {
73        self.set.is_empty()
74    }
75
76    /// Return the capacity of the cache.
77    pub fn capacity(&self) -> usize {
78        self.capacity
79    }
80
81    /// Extend the cache from an iterator of request_ids.
82    ///
83    /// This is useful for bulk loading (e.g., from database at startup).
84    /// Items are inserted in order, so the last items in the iterator
85    /// will be the most recent (least likely to be evicted).
86    pub fn extend<I: IntoIterator<Item = Uuid>>(&mut self, iter: I) {
87        for request_id in iter {
88            self.insert(request_id);
89        }
90    }
91}
92
93impl Default for BoundedIdempotenceCache {
94    fn default() -> Self {
95        Self::new()
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn test_basic_insert_and_contains() {
105        let mut cache = BoundedIdempotenceCache::with_capacity(10);
106
107        let req1 = Uuid::new_v4();
108        let req2 = Uuid::new_v4();
109
110        cache.insert(req1);
111        cache.insert(req2);
112
113        assert!(cache.contains(&req1));
114        assert!(cache.contains(&req2));
115        assert!(!cache.contains(&Uuid::new_v4()));
116        assert_eq!(cache.len(), 2);
117    }
118
119    #[test]
120    fn test_duplicate_insert_is_noop() {
121        let mut cache = BoundedIdempotenceCache::with_capacity(10);
122
123        let req1 = Uuid::new_v4();
124        cache.insert(req1);
125        cache.insert(req1);
126        cache.insert(req1);
127
128        assert_eq!(cache.len(), 1);
129        assert!(cache.contains(&req1));
130    }
131
132    #[test]
133    fn test_eviction_at_capacity() {
134        let mut cache = BoundedIdempotenceCache::with_capacity(3);
135
136        let req1 = Uuid::new_v4();
137        let req2 = Uuid::new_v4();
138        let req3 = Uuid::new_v4();
139        let req4 = Uuid::new_v4();
140        cache.insert(req1);
141        cache.insert(req2);
142        cache.insert(req3);
143
144        assert_eq!(cache.len(), 3);
145        assert!(cache.contains(&req1));
146        assert!(cache.contains(&req2));
147        assert!(cache.contains(&req3));
148
149        // Insert 4th element, should evict req1 (oldest)
150        cache.insert(req4);
151
152        assert_eq!(cache.len(), 3);
153        assert!(!cache.contains(&req1)); // Evicted
154        assert!(cache.contains(&req2));
155        assert!(cache.contains(&req3));
156        assert!(cache.contains(&req4));
157    }
158
159    #[test]
160    fn test_eviction_order() {
161        let mut cache = BoundedIdempotenceCache::with_capacity(2);
162
163        let first = Uuid::new_v4();
164        let second = Uuid::new_v4();
165        let third = Uuid::new_v4();
166        let fourth = Uuid::new_v4();
167        cache.insert(first);
168        cache.insert(second);
169        cache.insert(third); // Evicts first
170        cache.insert(fourth); // Evicts second
171
172        assert!(!cache.contains(&first));
173        assert!(!cache.contains(&second));
174        assert!(cache.contains(&third));
175        assert!(cache.contains(&fourth));
176    }
177
178    #[test]
179    fn test_duplicate_does_not_affect_eviction_order() {
180        let mut cache = BoundedIdempotenceCache::with_capacity(2);
181
182        let first = Uuid::new_v4();
183        let second = Uuid::new_v4();
184        let third = Uuid::new_v4();
185        cache.insert(first);
186        cache.insert(second);
187        cache.insert(first); // Duplicate, no-op
188        cache.insert(third); // Should evict first not second
189
190        assert!(!cache.contains(&first)); // Evicted
191        assert!(cache.contains(&second));
192        assert!(cache.contains(&third));
193    }
194
195    #[test]
196    fn test_extend() {
197        let mut cache = BoundedIdempotenceCache::with_capacity(5);
198
199        let req1 = Uuid::new_v4();
200        let req2 = Uuid::new_v4();
201        let req3 = Uuid::new_v4();
202        cache.extend(vec![req1, req2, req3]);
203
204        assert_eq!(cache.len(), 3);
205        assert!(cache.contains(&req1));
206        assert!(cache.contains(&req2));
207        assert!(cache.contains(&req3));
208    }
209
210    #[test]
211    fn test_extend_with_overflow() {
212        let mut cache = BoundedIdempotenceCache::with_capacity(3);
213
214        let req1 = Uuid::new_v4();
215        let req2 = Uuid::new_v4();
216        let req3 = Uuid::new_v4();
217        let req4 = Uuid::new_v4();
218        let req5 = Uuid::new_v4();
219        cache.extend(vec![req1, req2, req3, req4, req5]);
220
221        // Only the last 3 should remain
222        assert_eq!(cache.len(), 3);
223        assert!(!cache.contains(&req1));
224        assert!(!cache.contains(&req2));
225        assert!(cache.contains(&req3));
226        assert!(cache.contains(&req4));
227        assert!(cache.contains(&req5));
228    }
229
230    #[test]
231    fn test_is_empty() {
232        let cache = BoundedIdempotenceCache::with_capacity(10);
233        assert!(cache.is_empty());
234
235        let mut cache = BoundedIdempotenceCache::with_capacity(10);
236        cache.insert(Uuid::new_v4());
237        assert!(!cache.is_empty());
238    }
239
240    #[test]
241    fn test_default_capacity() {
242        let cache = BoundedIdempotenceCache::new();
243        assert_eq!(cache.capacity(), DEFAULT_CAPACITY);
244    }
245}
hypercall/rsm/bounded_idempotence_cache.rs

hypercall/rsm/
bounded_idempotence_cache.rs
