hopr_protocol_session/processing/
reorder.rs1use std::{
4 collections::VecDeque,
5 sync::Arc,
6 time::{Duration, Instant},
7};
8
9use crate::protocol::FrameId;
10
11const REORDER_MEMORY: Duration = Duration::from_secs(60);
17
18const REORDER_FACTOR: u32 = 2;
20
21pub(crate) const REORDER_FLOOR: Duration = Duration::from_millis(250);
23
24pub(crate) const ABANDONED_MEMORY: usize = 64;
26
27const MIN_SAMPLES: u32 = 8;
36const MIN_OBSERVATION: Duration = Duration::from_secs(5);
37
38#[derive(Debug, Default)]
56struct ReorderWindow {
57 deepest: VecDeque<(Instant, Duration)>,
61 counts: VecDeque<(Instant, u32)>,
64 last: Option<Instant>,
67 abandoned: VecDeque<(FrameId, Instant)>,
68}
69
70impl ReorderWindow {
71 fn forget_before(&mut self, now: Instant) {
72 let gone = |at: &Instant| now.saturating_duration_since(*at) > REORDER_MEMORY;
73 while self.deepest.front().is_some_and(|(at, _)| gone(at)) {
74 self.deepest.pop_front();
75 }
76 while self.counts.front().is_some_and(|(at, _)| gone(at)) {
77 self.counts.pop_front();
78 }
79 }
80
81 fn seen_enough(&self) -> bool {
86 self.counts.iter().map(|(_, count)| *count).sum::<u32>() >= MIN_SAMPLES
87 && self
88 .counts
89 .front()
90 .zip(self.last)
91 .is_some_and(|((first, _), last)| last.saturating_duration_since(*first) >= MIN_OBSERVATION)
92 }
93}
94
95#[derive(Clone, Debug, Default)]
97pub(crate) struct SharedReorder(Arc<parking_lot::Mutex<ReorderWindow>>);
98
99impl SharedReorder {
100 pub(crate) fn record(&self, now: Instant, sample: Duration) {
102 let mut window = self.0.lock();
103 window.forget_before(now);
104 while window.deepest.back().is_some_and(|(_, deepest)| *deepest <= sample) {
106 window.deepest.pop_back();
107 }
108 window.deepest.push_back((now, sample));
109 match window.counts.back_mut() {
110 Some((second, count)) if now.saturating_duration_since(*second) < Duration::from_secs(1) => *count += 1,
111 _ => window.counts.push_back((now, 1)),
112 }
113 window.last = window.last.max(Some(now));
114 }
115
116 pub(crate) fn wait(&self, now: Instant, max_wait: Duration) -> Duration {
118 let mut window = self.0.lock();
119 window.forget_before(now);
120 if !window.seen_enough() {
121 return max_wait;
122 }
123 window
124 .deepest
125 .front()
126 .map(|(_, deepest)| *deepest)
127 .map_or(max_wait, |deepest| {
128 deepest
129 .saturating_mul(REORDER_FACTOR)
130 .clamp(REORDER_FLOOR.min(max_wait), max_wait)
131 })
132 }
133
134 pub(crate) fn note_abandoned(&self, id: FrameId, behind_since: Instant) {
137 let mut window = self.0.lock();
138 if window.abandoned.len() == ABANDONED_MEMORY {
139 window.abandoned.pop_front();
140 }
141 window.abandoned.push_back((id, behind_since));
142 }
143
144 #[cfg(test)]
147 pub(crate) fn warmed() -> Self {
148 let window = Self::default();
149 let now = Instant::now();
150 let first = now
151 .checked_sub(MIN_OBSERVATION + Duration::from_secs(1))
152 .expect("monotonic clock older than the observation");
153 for i in 0..MIN_SAMPLES {
154 window.record(
155 first + MIN_OBSERVATION * i / (MIN_SAMPLES - 1),
156 Duration::from_millis(1),
157 );
158 }
159 window
160 }
161
162 pub(crate) fn late(&self, id: FrameId, now: Instant) -> Option<Duration> {
164 self.0
165 .lock()
166 .abandoned
167 .iter()
168 .find(|(abandoned, _)| *abandoned == id)
169 .map(|(_, behind_since)| now.duration_since(*behind_since))
170 }
171}
172
173#[cfg(test)]
174mod tests {
175 use super::*;
176
177 #[test]
178 fn the_wait_should_be_max_wait_before_any_sample() {
179 let window = SharedReorder::default();
180 assert_eq!(
181 Duration::from_secs(3),
182 window.wait(Instant::now(), Duration::from_secs(3))
183 );
184 }
185
186 fn warmed(window: &SharedReorder, start: Instant) -> Instant {
189 for i in 0..MIN_SAMPLES {
190 window.record(
191 start + MIN_OBSERVATION * i / (MIN_SAMPLES - 1),
192 Duration::from_millis(1),
193 );
194 }
195 start + MIN_OBSERVATION
196 }
197
198 #[test]
202 fn the_wait_should_stay_at_max_wait_until_enough_samples_span_enough_time() {
203 let window = SharedReorder::default();
204 let start = Instant::now();
205 let max_wait = Duration::from_secs(3);
206
207 for i in 0..100u32 {
208 window.record(start + Duration::from_millis(u64::from(i)), Duration::from_millis(20));
209 }
210 assert_eq!(
211 max_wait,
212 window.wait(start + Duration::from_secs(1), max_wait),
213 "many, but within a second"
214 );
215 assert_eq!(
216 max_wait,
217 window.wait(start + MIN_OBSERVATION, max_wait),
218 "many, and long ago, but all within a second: a Session that went quiet"
219 );
220
221 let few = SharedReorder::default();
222 few.record(start, Duration::from_millis(20));
223 few.record(start + MIN_OBSERVATION, Duration::from_millis(20));
224 assert_eq!(
225 max_wait,
226 few.wait(start + MIN_OBSERVATION, max_wait),
227 "long enough, but too few"
228 );
229
230 window.record(start + MIN_OBSERVATION, Duration::from_millis(20));
231 assert_eq!(
232 REORDER_FLOOR,
233 window.wait(start + MIN_OBSERVATION, max_wait),
234 "enough of both"
235 );
236 }
237
238 #[test]
239 fn the_wait_should_be_twice_the_deepest_sample_within_its_bounds() {
240 let window = SharedReorder::default();
241 let now = warmed(&window, Instant::now());
242 let max_wait = Duration::from_secs(3);
243
244 window.record(now, Duration::from_millis(50));
245 assert_eq!(REORDER_FLOOR, window.wait(now, max_wait), "floored");
246
247 window.record(now, Duration::from_millis(400));
248 window.record(now, Duration::from_millis(300));
249 assert_eq!(
250 Duration::from_millis(800),
251 window.wait(now, max_wait),
252 "the deepest counts"
253 );
254
255 window.record(now, Duration::from_secs(2));
256 assert_eq!(max_wait, window.wait(now, max_wait), "capped");
257
258 assert_eq!(
259 Duration::from_millis(100),
260 window.wait(now, Duration::from_millis(100)),
261 "a max_wait under the floor is kept"
262 );
263 }
264
265 #[test]
266 fn a_sample_should_be_forgotten_after_the_memory() {
267 let window = SharedReorder::default();
268 let then = warmed(&window, Instant::now());
269 let max_wait = Duration::from_secs(3);
270
271 window.record(then, Duration::from_millis(400));
272 assert_eq!(Duration::from_millis(800), window.wait(then, max_wait));
273 let later = then + REORDER_MEMORY + Duration::from_secs(1);
274 assert_eq!(max_wait, window.wait(later, max_wait), "nothing left in the memory");
275
276 warmed(&window, later);
277 window.record(later + MIN_OBSERVATION, Duration::from_millis(200));
278 assert_eq!(
279 Duration::from_millis(400),
280 window.wait(later + MIN_OBSERVATION, max_wait),
281 "only the fresh one"
282 );
283 }
284
285 #[test]
287 fn the_window_should_keep_only_samples_that_can_still_be_the_deepest() {
288 let window = SharedReorder::default();
289 let start = Instant::now();
290 let max_wait = Duration::from_secs(3);
291
292 for i in 0..5u64 {
294 window.record(start + Duration::from_millis(i), Duration::from_millis(500 - 100 * i));
295 }
296 assert_eq!(5, window.0.lock().deepest.len());
297 window.record(start + Duration::from_millis(10), Duration::from_millis(600));
299 assert_eq!(1, window.0.lock().deepest.len());
300
301 for i in 0..100_000u64 {
302 window.record(
303 start + Duration::from_millis(20 + i / 100),
304 Duration::from_millis(i % 7),
305 );
306 }
307 assert!(window.0.lock().deepest.len() <= 8, "{}", window.0.lock().deepest.len());
308 let spanned = start + MIN_OBSERVATION + Duration::from_secs(2);
311 window.record(spanned, Duration::from_millis(1));
312 assert_eq!(Duration::from_millis(1200), window.wait(spanned, max_wait));
313
314 let later = start + Duration::from_millis(10) + REORDER_MEMORY + Duration::from_millis(1);
316 assert_eq!(REORDER_FLOOR, window.wait(later, max_wait));
317 }
318
319 #[test]
320 fn an_abandoned_gap_should_be_remembered_for_a_bounded_number_of_gaps() {
321 let window = SharedReorder::default();
322 let then = Instant::now();
323 for id in 1..=(ABANDONED_MEMORY as FrameId + 1) {
324 window.note_abandoned(id, then);
325 }
326 let now = then + Duration::from_millis(700);
327 assert_eq!(None, window.late(1, now), "the oldest is dropped");
328 assert_eq!(Some(Duration::from_millis(700)), window.late(2, now));
329 assert_eq!(None, window.late(1000, now), "never abandoned");
330 }
331}