Skip to main content

fetchium_core/search/
latency.rs

1//! Latency Predictor (LP) — predicts backend response times for optimal timeout tuning.
2//!
3//! Uses exponential moving average (EMA) to track per-backend latency and dynamically
4//! adjust timeouts. Fast backends get tighter timeouts; slow backends get more slack.
5//! This prevents a single slow backend from blocking the entire search.
6
7use crate::types::BackendId;
8use std::collections::HashMap;
9use std::time::Duration;
10
11/// Configuration for the latency predictor.
12#[derive(Debug, Clone)]
13pub struct LatencyConfig {
14    /// EMA smoothing factor (0.0–1.0). Higher = more weight to recent observations.
15    pub alpha: f64,
16    /// Minimum timeout for any backend.
17    pub min_timeout: Duration,
18    /// Maximum timeout for any backend.
19    pub max_timeout: Duration,
20    /// Multiplier applied to predicted latency to get timeout (headroom).
21    pub timeout_multiplier: f64,
22    /// Default predicted latency for unknown backends.
23    pub default_latency: Duration,
24}
25
26impl Default for LatencyConfig {
27    fn default() -> Self {
28        Self {
29            alpha: 0.3,
30            min_timeout: Duration::from_millis(500),
31            max_timeout: Duration::from_secs(30),
32            timeout_multiplier: 2.5,
33            default_latency: Duration::from_secs(3),
34        }
35    }
36}
37
38/// Per-backend latency statistics.
39#[derive(Debug, Clone)]
40pub struct LatencyStats {
41    /// Exponential moving average of response time.
42    pub ema_ms: f64,
43    /// Exponential moving average of variance (for percentile estimation).
44    pub ema_variance: f64,
45    /// Total number of observations recorded.
46    pub sample_count: u64,
47    /// Minimum observed latency.
48    pub min_ms: f64,
49    /// Maximum observed latency.
50    pub max_ms: f64,
51    /// Number of timeouts observed.
52    pub timeout_count: u64,
53}
54
55impl LatencyStats {
56    fn new(initial_ms: f64) -> Self {
57        Self {
58            ema_ms: initial_ms,
59            ema_variance: 0.0,
60            sample_count: 0,
61            min_ms: initial_ms,
62            max_ms: initial_ms,
63            timeout_count: 0,
64        }
65    }
66}
67
68/// Latency predictor with per-backend tracking.
69#[derive(Debug, Clone)]
70pub struct LatencyPredictor {
71    config: LatencyConfig,
72    stats: HashMap<BackendId, LatencyStats>,
73}
74
75impl LatencyPredictor {
76    /// Create a new predictor with the given configuration.
77    pub fn new(config: LatencyConfig) -> Self {
78        Self {
79            config,
80            stats: HashMap::new(),
81        }
82    }
83
84    /// Record a successful response latency for a backend.
85    pub fn record_latency(&mut self, backend: &BackendId, latency: Duration) {
86        let ms = latency.as_secs_f64() * 1000.0;
87        let alpha = self.config.alpha;
88        let default_ms = self.config.default_latency.as_secs_f64() * 1000.0;
89
90        let stats = self
91            .stats
92            .entry(backend.clone())
93            .or_insert_with(|| LatencyStats::new(default_ms));
94
95        // Update EMA
96        let prev_ema = stats.ema_ms;
97        stats.ema_ms = alpha * ms + (1.0 - alpha) * prev_ema;
98
99        // Update variance EMA (for p95 estimation)
100        let diff = ms - stats.ema_ms;
101        stats.ema_variance = alpha * (diff * diff) + (1.0 - alpha) * stats.ema_variance;
102
103        // Update extremes
104        if ms < stats.min_ms || stats.sample_count == 0 {
105            stats.min_ms = ms;
106        }
107        if ms > stats.max_ms || stats.sample_count == 0 {
108            stats.max_ms = ms;
109        }
110        stats.sample_count += 1;
111    }
112
113    /// Record a timeout for a backend.
114    pub fn record_timeout(&mut self, backend: &BackendId) {
115        let default_ms = self.config.default_latency.as_secs_f64() * 1000.0;
116        let stats = self
117            .stats
118            .entry(backend.clone())
119            .or_insert_with(|| LatencyStats::new(default_ms));
120
121        stats.timeout_count += 1;
122        // Timeouts push the EMA toward max timeout (penalty)
123        let max_ms = self.config.max_timeout.as_secs_f64() * 1000.0;
124        let alpha = self.config.alpha;
125        stats.ema_ms = alpha * max_ms + (1.0 - alpha) * stats.ema_ms;
126        stats.sample_count += 1;
127    }
128
129    /// Predict the response time for a backend.
130    pub fn predict(&self, backend: &BackendId) -> Duration {
131        match self.stats.get(backend) {
132            Some(stats) if stats.sample_count > 0 => Duration::from_secs_f64(stats.ema_ms / 1000.0),
133            _ => self.config.default_latency,
134        }
135    }
136
137    /// Compute an adaptive timeout for a backend.
138    ///
139    /// Timeout = predicted_latency * multiplier, clamped to [min, max].
140    /// Includes a p95 estimate using variance for extra headroom.
141    pub fn adaptive_timeout(&self, backend: &BackendId) -> Duration {
142        let predicted = self.predict(backend);
143        let predicted_ms = predicted.as_secs_f64() * 1000.0;
144
145        // Add variance-based headroom (approximate p95)
146        let variance_headroom = match self.stats.get(backend) {
147            Some(stats) if stats.sample_count >= 3 => stats.ema_variance.sqrt() * 1.65,
148            _ => 0.0,
149        };
150
151        let timeout_ms = (predicted_ms + variance_headroom) * self.config.timeout_multiplier;
152
153        let timeout = Duration::from_secs_f64(timeout_ms / 1000.0);
154        timeout.clamp(self.config.min_timeout, self.config.max_timeout)
155    }
156
157    /// Get statistics for a specific backend.
158    pub fn stats(&self, backend: &BackendId) -> Option<&LatencyStats> {
159        self.stats.get(backend)
160    }
161
162    /// Rank backends by predicted speed (fastest first).
163    pub fn rank_by_speed(&self, backends: &[BackendId]) -> Vec<BackendId> {
164        let mut ranked: Vec<(BackendId, Duration)> = backends
165            .iter()
166            .map(|b| (b.clone(), self.predict(b)))
167            .collect();
168        ranked.sort_by_key(|a| a.1);
169        ranked.into_iter().map(|(b, _)| b).collect()
170    }
171
172    /// Get the timeout reliability score for a backend (0.0 = always timeouts, 1.0 = never).
173    pub fn reliability(&self, backend: &BackendId) -> f64 {
174        match self.stats.get(backend) {
175            Some(stats) if stats.sample_count > 0 => {
176                1.0 - (stats.timeout_count as f64 / stats.sample_count as f64)
177            }
178            _ => 0.5, // unknown
179        }
180    }
181}
182
183impl Default for LatencyPredictor {
184    fn default() -> Self {
185        Self::new(LatencyConfig::default())
186    }
187}
188
189#[cfg(test)]
190mod tests {
191    use super::*;
192
193    #[test]
194    fn default_prediction_for_unknown() {
195        let predictor = LatencyPredictor::default();
196        let pred = predictor.predict(&BackendId::DuckDuckGo);
197        assert_eq!(pred, Duration::from_secs(3));
198    }
199
200    #[test]
201    fn ema_tracks_latency() {
202        let mut predictor = LatencyPredictor::default();
203        let backend = BackendId::Google;
204
205        // Record several fast responses
206        for _ in 0..10 {
207            predictor.record_latency(&backend, Duration::from_millis(200));
208        }
209
210        let pred = predictor.predict(&backend);
211        // Should converge toward 200ms
212        assert!(
213            pred.as_millis() < 1000,
214            "prediction should approach 200ms, got {:?}",
215            pred
216        );
217    }
218
219    #[test]
220    fn timeout_penalty_increases_prediction() {
221        let mut predictor = LatencyPredictor::default();
222        let backend = BackendId::Bing;
223
224        // Record some normal responses
225        for _ in 0..5 {
226            predictor.record_latency(&backend, Duration::from_millis(500));
227        }
228        let before = predictor.predict(&backend);
229
230        // Record timeouts
231        for _ in 0..3 {
232            predictor.record_timeout(&backend);
233        }
234        let after = predictor.predict(&backend);
235
236        assert!(after > before, "timeouts should increase prediction");
237    }
238
239    #[test]
240    fn adaptive_timeout_clamped() {
241        let config = LatencyConfig {
242            min_timeout: Duration::from_secs(1),
243            max_timeout: Duration::from_secs(10),
244            ..LatencyConfig::default()
245        };
246        let mut predictor = LatencyPredictor::new(config);
247
248        // Very fast backend
249        for _ in 0..10 {
250            predictor.record_latency(&BackendId::DuckDuckGo, Duration::from_millis(50));
251        }
252        let timeout = predictor.adaptive_timeout(&BackendId::DuckDuckGo);
253        assert!(
254            timeout >= Duration::from_secs(1),
255            "timeout below min: {:?}",
256            timeout
257        );
258
259        // Very slow backend with timeouts
260        for _ in 0..10 {
261            predictor.record_timeout(&BackendId::Arxiv);
262        }
263        let timeout = predictor.adaptive_timeout(&BackendId::Arxiv);
264        assert!(
265            timeout <= Duration::from_secs(10),
266            "timeout above max: {:?}",
267            timeout
268        );
269    }
270
271    #[test]
272    fn rank_by_speed_orders_correctly() {
273        let mut predictor = LatencyPredictor::default();
274
275        // Fast backend
276        for _ in 0..5 {
277            predictor.record_latency(&BackendId::DuckDuckGo, Duration::from_millis(100));
278        }
279        // Slow backend
280        for _ in 0..5 {
281            predictor.record_latency(&BackendId::Arxiv, Duration::from_millis(2000));
282        }
283        // Medium backend
284        for _ in 0..5 {
285            predictor.record_latency(&BackendId::Google, Duration::from_millis(500));
286        }
287
288        let ranked =
289            predictor.rank_by_speed(&[BackendId::Arxiv, BackendId::DuckDuckGo, BackendId::Google]);
290
291        assert_eq!(ranked[0], BackendId::DuckDuckGo);
292        assert_eq!(ranked[2], BackendId::Arxiv);
293    }
294
295    #[test]
296    fn reliability_tracking() {
297        let mut predictor = LatencyPredictor::default();
298        let backend = BackendId::Google;
299
300        // 8 successes, 2 timeouts = 80% reliability
301        for _ in 0..8 {
302            predictor.record_latency(&backend, Duration::from_millis(300));
303        }
304        for _ in 0..2 {
305            predictor.record_timeout(&backend);
306        }
307
308        let rel = predictor.reliability(&backend);
309        assert!(
310            (rel - 0.8).abs() < 0.01,
311            "reliability should be ~0.8, got {rel}"
312        );
313    }
314
315    #[test]
316    fn unknown_backend_reliability() {
317        let predictor = LatencyPredictor::default();
318        assert_eq!(predictor.reliability(&BackendId::Brave), 0.5);
319    }
320
321    #[test]
322    fn stats_tracking() {
323        let mut predictor = LatencyPredictor::default();
324        let backend = BackendId::DuckDuckGo;
325
326        predictor.record_latency(&backend, Duration::from_millis(100));
327        predictor.record_latency(&backend, Duration::from_millis(500));
328        predictor.record_latency(&backend, Duration::from_millis(200));
329
330        let stats = predictor.stats(&backend).unwrap();
331        assert_eq!(stats.sample_count, 3);
332        assert!(stats.min_ms <= 100.0 + 1.0);
333        assert!(stats.max_ms >= 499.0);
334    }
335
336    #[test]
337    fn variance_affects_timeout() {
338        let mut stable = LatencyPredictor::default();
339        let mut unstable = LatencyPredictor::default();
340        let backend = BackendId::Google;
341
342        // Stable: consistent 300ms
343        for _ in 0..10 {
344            stable.record_latency(&backend, Duration::from_millis(300));
345        }
346
347        // Unstable: alternating 100ms and 500ms
348        for i in 0..10 {
349            let ms = if i % 2 == 0 { 100 } else { 500 };
350            unstable.record_latency(&backend, Duration::from_millis(ms));
351        }
352
353        let stable_timeout = stable.adaptive_timeout(&backend);
354        let unstable_timeout = unstable.adaptive_timeout(&backend);
355
356        // Unstable backend should get a longer timeout due to higher variance
357        assert!(
358            unstable_timeout >= stable_timeout,
359            "unstable timeout {:?} should be >= stable {:?}",
360            unstable_timeout,
361            stable_timeout
362        );
363    }
364}