Skip to main content

spider_optimize/
monitor.rs

1//! A tripwire on the success rate of applied edits.
2//!
3//! The gate decides from a model's estimate. Once edits are being applied,
4//! the outcomes that come back are the only evidence that the estimate still
5//! holds, and a model that has gone wrong keeps applying edits with the same
6//! confidence it had when it was right. A [`Monitor`] holds the last `window`
7//! outcomes and compares the success rate of the requests it edited with the
8//! success rate of the requests it left alone. When the edited rate is worse
9//! by more than the configured drop, with the noise of both rates taken off,
10//! it trips, and the client falls back to shadow until someone resets it.
11//!
12//! # What the comparison is and is not
13//!
14//! The two groups are not a paired trial. The gate chose which requests to
15//! edit, and it chose them because they scored well, so the edited group
16//! leans towards the sites the model likes. A drop between the two rates can
17//! be the edit doing harm, or the model choosing badly, or the two groups
18//! fetching different sites on a bad afternoon. That is why this is a
19//! tripwire and not a measurement: it stops the bleeding, and the paired
20//! rows say what happened. The bound is a one sided normal approximation on
21//! the difference of two independent proportions, which is loose at the
22//! window sizes involved and takes no account of the confounding.
23//!
24//! # Concurrency
25//!
26//! One `AtomicU8` per outcome, a head counter and a latch. An observer packs
27//! its outcome into one byte and stores it, so a verdict taken while other
28//! tasks are observing reads whole outcomes and never a mixture of two. Two
29//! observers landing on one slot at the same moment keep one of the two
30//! outcomes, which is one outcome of `window` lost. Nothing locks and nothing
31//! allocates after [`Monitor::new`].
32
33use std::sync::atomic::{AtomicBool, AtomicU8, AtomicUsize, Ordering};
34
35/// The fewest outcomes a window may hold.
36pub const MIN_WINDOW: usize = 64;
37
38/// The most outcomes a window may hold.
39pub const MAX_WINDOW: usize = 8_192;
40
41/// The one sided bound used when none is given, the 95th percentile of a
42/// standard normal.
43pub const DEFAULT_Z: f32 = 1.645;
44
45/// The slot holds an outcome.
46const VALID: u8 = 0b001;
47/// The request went out with an edit applied.
48const APPLIED: u8 = 0b010;
49/// The request got what the caller asked for.
50const SUCCESS: u8 = 0b100;
51
52/// What a monitor watches for.
53#[derive(Debug, Clone, Copy, PartialEq)]
54pub struct MonitorConfig {
55    /// How many of the latest outcomes are compared. Held between
56    /// [`MIN_WINDOW`] and [`MAX_WINDOW`].
57    pub window: usize,
58    /// The fewest applied outcomes in the window before a verdict is given.
59    /// At least one, and no more than the window.
60    pub min_applied: u32,
61    /// The fewest kept outcomes in the window before a verdict is given. At
62    /// least one, and no more than the window.
63    pub min_kept: u32,
64    /// The largest drop in success rate, kept minus applied, that is let
65    /// through. `0.02` is two points.
66    pub max_drop: f32,
67    /// How many standard errors the drop's lower bound sits under the drop.
68    /// [`DEFAULT_Z`] unless set.
69    pub z: f32,
70}
71
72impl Default for MonitorConfig {
73    fn default() -> MonitorConfig {
74        MonitorConfig {
75            window: 1_024,
76            min_applied: 100,
77            min_kept: 100,
78            max_drop: 0.02,
79            z: DEFAULT_Z,
80        }
81    }
82}
83
84impl MonitorConfig {
85    /// The configuration as the monitor will use it: the window clamped, the
86    /// minimums held between one and the window, and a bound or a drop that
87    /// is not a finite number replaced by the default.
88    fn settled(self) -> MonitorConfig {
89        let window = self.window.clamp(MIN_WINDOW, MAX_WINDOW);
90        // The window is at most 8,192, so this cast is exact.
91        let cap = window as u32;
92        let defaults = MonitorConfig::default();
93        MonitorConfig {
94            window,
95            min_applied: self.min_applied.clamp(1, cap),
96            min_kept: self.min_kept.clamp(1, cap),
97            max_drop: if self.max_drop.is_finite() {
98                self.max_drop
99            } else {
100                defaults.max_drop
101            },
102            z: if self.z.is_finite() && self.z >= 0.0 {
103                self.z
104            } else {
105                defaults.z
106            },
107        }
108    }
109}
110
111/// The two rates over the window and how far apart they are.
112#[derive(Debug, Clone, Copy, PartialEq)]
113pub struct Estimate {
114    /// How many outcomes in the window went out with an edit.
115    pub applied: u32,
116    /// How many of those succeeded.
117    pub applied_successes: u32,
118    /// How many outcomes in the window went out unedited.
119    pub kept: u32,
120    /// How many of those succeeded.
121    pub kept_successes: u32,
122    /// The kept success rate minus the applied one. Positive when edits are
123    /// doing worse.
124    pub drop: f32,
125    /// The drop less `z` standard errors of the difference of the two rates.
126    pub drop_lower_bound: f32,
127}
128
129/// What the window says.
130#[derive(Debug, Clone, Copy, PartialEq)]
131pub enum Verdict {
132    /// Too few outcomes of one kind or the other to say anything.
133    Warming {
134        /// How many applied outcomes the window holds.
135        applied: u32,
136        /// How many kept outcomes the window holds.
137        kept: u32,
138    },
139    /// The edited requests are not doing measurably worse.
140    Healthy(Estimate),
141    /// The edited requests are doing worse by more than the allowed drop.
142    Degraded(Estimate),
143}
144
145/// The last `window` outcomes and whether they have tripped it.
146///
147/// Cheap to share by reference from any number of tasks. See the module
148/// documentation for what the comparison can and cannot tell you.
149#[derive(Debug)]
150pub struct Monitor {
151    ring: Box<[AtomicU8]>,
152    head: AtomicUsize,
153    tripped: AtomicBool,
154    config: MonitorConfig,
155}
156
157impl Default for Monitor {
158    fn default() -> Monitor {
159        Monitor::new(MonitorConfig::default())
160    }
161}
162
163impl Monitor {
164    /// A monitor with this configuration, settled as [`MonitorConfig`]
165    /// describes. This is the one allocation.
166    pub fn new(config: MonitorConfig) -> Monitor {
167        let config = config.settled();
168        let mut ring = Vec::with_capacity(config.window);
169        ring.resize_with(config.window, AtomicU8::default);
170        Monitor {
171            ring: ring.into_boxed_slice(),
172            head: AtomicUsize::new(0),
173            tripped: AtomicBool::new(false),
174            config,
175        }
176    }
177
178    /// The configuration in use, after clamping.
179    pub fn config(&self) -> &MonitorConfig {
180        &self.config
181    }
182
183    /// Record one settled outcome: whether the request went out edited, and
184    /// whether it got what the caller asked for.
185    ///
186    /// The oldest outcome in the window makes room. The window is then judged,
187    /// so a monitor trips on the observation that crossed the line without
188    /// anyone asking for a [`Monitor::verdict`].
189    pub fn observe(&self, applied: bool, success: bool) {
190        let mut packed = VALID;
191        if applied {
192            packed |= APPLIED;
193        }
194        if success {
195            packed |= SUCCESS;
196        }
197        // The ring is never empty, so the remainder is always in range and
198        // the lookup always lands. The counter wraps at the end of usize,
199        // which puts one observation out of turn once in a process lifetime.
200        let at = self.head.fetch_add(1, Ordering::Relaxed) % self.ring.len();
201        if let Some(slot) = self.ring.get(at) {
202            slot.store(packed, Ordering::Relaxed);
203        }
204        if !self.tripped.load(Ordering::Relaxed) {
205            let _ = self.verdict();
206        }
207    }
208
209    /// Judge the window as it stands, and latch [`Monitor::tripped`] when it
210    /// is [`Verdict::Degraded`].
211    ///
212    /// The verdict describes the window now, so it reads healthy again once
213    /// healthy outcomes have pushed the bad ones out. The latch does not.
214    pub fn verdict(&self) -> Verdict {
215        let mut applied = 0u32;
216        let mut applied_successes = 0u32;
217        let mut kept = 0u32;
218        let mut kept_successes = 0u32;
219        for slot in &self.ring {
220            let packed = slot.load(Ordering::Relaxed);
221            if packed & VALID == 0 {
222                continue;
223            }
224            let succeeded = u32::from(packed & SUCCESS != 0);
225            if packed & APPLIED != 0 {
226                applied += 1;
227                applied_successes += succeeded;
228            } else {
229                kept += 1;
230                kept_successes += succeeded;
231            }
232        }
233        if applied < self.config.min_applied || kept < self.config.min_kept {
234            return Verdict::Warming { applied, kept };
235        }
236
237        // Both counts are at least one here, so neither rate divides by zero.
238        let applied_rate = applied_successes as f32 / applied as f32;
239        let kept_rate = kept_successes as f32 / kept as f32;
240        let drop = kept_rate - applied_rate;
241        let variance = kept_rate * (1.0 - kept_rate) / kept as f32
242            + applied_rate * (1.0 - applied_rate) / applied as f32;
243        let drop_lower_bound = drop - self.config.z * variance.max(0.0).sqrt();
244        let estimate = Estimate {
245            applied,
246            applied_successes,
247            kept,
248            kept_successes,
249            drop,
250            drop_lower_bound,
251        };
252        if drop_lower_bound > self.config.max_drop {
253            self.tripped.store(true, Ordering::Relaxed);
254            Verdict::Degraded(estimate)
255        } else {
256            Verdict::Healthy(estimate)
257        }
258    }
259
260    /// Whether a verdict has been [`Verdict::Degraded`] since the last
261    /// [`Monitor::reset`].
262    pub fn tripped(&self) -> bool {
263        self.tripped.load(Ordering::Relaxed)
264    }
265
266    /// Forget every outcome and open the latch.
267    ///
268    /// An observer running at the same time may land an outcome in a slot
269    /// this has already cleared, which is one outcome kept from before the
270    /// reset, or in one it has not reached yet, which is one outcome lost.
271    pub fn reset(&self) {
272        for slot in &self.ring {
273            slot.store(0, Ordering::Relaxed);
274        }
275        self.head.store(0, Ordering::Relaxed);
276        self.tripped.store(false, Ordering::Relaxed);
277    }
278}
279
280#[cfg(test)]
281mod tests {
282    #![allow(
283        clippy::unwrap_used,
284        clippy::expect_used,
285        clippy::panic,
286        clippy::unreachable,
287        clippy::indexing_slicing,
288        clippy::string_slice
289    )]
290    use super::*;
291
292    /// A xorshift64, so a stream is the same on every run.
293    struct Rng(u64);
294
295    impl Rng {
296        fn next(&mut self) -> u64 {
297            let mut x = self.0;
298            x ^= x << 13;
299            x ^= x >> 7;
300            x ^= x << 17;
301            self.0 = x;
302            x
303        }
304
305        /// A coin that comes up true with this chance.
306        fn chance(&mut self, p: f32) -> bool {
307            // The top 24 bits, as a fraction in [0, 1).
308            let unit = (self.next() >> 40) as f32 / (1u64 << 24) as f32;
309            unit < p
310        }
311    }
312
313    fn config(window: usize, minimum: u32) -> MonitorConfig {
314        MonitorConfig {
315            window,
316            min_applied: minimum,
317            min_kept: minimum,
318            max_drop: 0.02,
319            z: DEFAULT_Z,
320        }
321    }
322
323    #[test]
324    fn a_healthy_stream_never_trips() {
325        let monitor = Monitor::new(config(2_048, 100));
326        let mut rng = Rng(0x9e37_79b9_7f4a_7c15);
327        let mut worst = f32::NEG_INFINITY;
328        for _ in 0..10_000 {
329            let applied = rng.chance(0.5);
330            monitor.observe(applied, rng.chance(0.9));
331            if let Verdict::Healthy(estimate) = monitor.verdict() {
332                worst = worst.max(estimate.drop_lower_bound);
333            }
334            assert!(!monitor.tripped());
335        }
336        assert!(matches!(monitor.verdict(), Verdict::Healthy(_)));
337        println!("healthy stream: worst lower bound on the drop {worst:.4}");
338        assert!(worst <= 0.02);
339    }
340
341    #[test]
342    fn degradation_trips_within_the_window_and_the_losses_are_counted() {
343        const WINDOW: usize = 1_024;
344        const MIN_APPLIED: u32 = 64;
345        const KEPT_RATE: f32 = 0.9;
346        const DEGRADED_RATE: f32 = 0.6;
347        const K: usize = 3_000;
348
349        let monitor = Monitor::new(MonitorConfig {
350            min_kept: 64,
351            ..config(WINDOW, MIN_APPLIED)
352        });
353        let mut rng = Rng(0x2545_f491_4f6c_dd1d);
354        let mut tripped_at = None;
355        let mut applied_after_k = 0u32;
356        let mut applied_failures_after_k = 0u32;
357        for step in 0..K + WINDOW {
358            let applied = rng.chance(0.5);
359            let rate = if applied && step >= K {
360                DEGRADED_RATE
361            } else {
362                KEPT_RATE
363            };
364            let success = rng.chance(rate);
365            if applied && step >= K {
366                applied_after_k += 1;
367                applied_failures_after_k += u32::from(!success);
368            }
369            monitor.observe(applied, success);
370            assert!(
371                step >= K || !monitor.tripped(),
372                "tripped at {step} before {K}"
373            );
374            if monitor.tripped() {
375                tripped_at = Some(step);
376                break;
377            }
378        }
379        let tripped_at = tripped_at.expect("the drop from 0.9 to 0.6 trips the monitor");
380        let delay = tripped_at + 1 - K;
381        assert!(delay <= WINDOW, "tripped {delay} outcomes after the drop");
382
383        // What the degraded edits cost before the trip: the applied failures a
384        // kept request at the kept rate would not have suffered. The applied
385        // outcomes after the drop are at most the ones that fit in one
386        // window, plus the minimum the verdict waits for, so the excess
387        // failures are bounded by that many at the rate difference.
388        let excess = applied_failures_after_k as f32 - (1.0 - KEPT_RATE) * applied_after_k as f32;
389        let expected = (KEPT_RATE - DEGRADED_RATE) * applied_after_k as f32;
390        let bound = (KEPT_RATE - DEGRADED_RATE) * (MIN_APPLIED as f32 + WINDOW as f32);
391        println!(
392            "degradation: detected {delay} outcomes after the drop, {applied_after_k} of them applied; \
393             {applied_failures_after_k} applied failures, {excess:.1} more than the kept rate would give \
394             (expected {expected:.1}, bound {bound:.1})"
395        );
396        assert!(applied_after_k <= MIN_APPLIED + WINDOW as u32);
397        assert!(excess <= bound, "{excess} losses over the bound {bound}");
398        assert!(excess > 0.0, "the losses were counted");
399        let Verdict::Degraded(estimate) = monitor.verdict() else {
400            panic!("the window still reads degraded");
401        };
402        assert!(estimate.drop_lower_bound > 0.02);
403        assert!(estimate.drop > estimate.drop_lower_bound);
404    }
405
406    #[test]
407    fn a_tripped_monitor_stays_tripped_until_reset() {
408        let monitor = Monitor::new(config(64, 8));
409        for _ in 0..32 {
410            monitor.observe(true, false);
411            monitor.observe(false, true);
412        }
413        assert!(monitor.tripped());
414        assert!(matches!(monitor.verdict(), Verdict::Degraded(_)));
415
416        // A window of healthy outcomes reads healthy, and the latch holds.
417        for _ in 0..64 {
418            monitor.observe(true, true);
419            monitor.observe(false, true);
420        }
421        let Verdict::Healthy(estimate) = monitor.verdict() else {
422            panic!("the window is healthy");
423        };
424        assert_eq!(estimate.applied_successes, estimate.applied);
425        assert!(monitor.tripped());
426
427        monitor.reset();
428        assert!(!monitor.tripped());
429        assert_eq!(
430            monitor.verdict(),
431            Verdict::Warming {
432                applied: 0,
433                kept: 0
434            }
435        );
436        monitor.observe(true, true);
437        assert_eq!(
438            monitor.verdict(),
439            Verdict::Warming {
440                applied: 1,
441                kept: 0
442            }
443        );
444    }
445
446    #[test]
447    fn warming_below_the_minimums_never_degrades() {
448        let monitor = Monitor::new(config(64, 20));
449        // Every edit fails and every kept request succeeds, and there are
450        // still too few of one kind.
451        for _ in 0..19 {
452            monitor.observe(true, false);
453        }
454        for _ in 0..40 {
455            monitor.observe(false, true);
456        }
457        assert_eq!(
458            monitor.verdict(),
459            Verdict::Warming {
460                applied: 19,
461                kept: 40
462            }
463        );
464        assert!(!monitor.tripped());
465        monitor.observe(true, false);
466        assert!(matches!(monitor.verdict(), Verdict::Degraded(_)));
467        assert!(monitor.tripped());
468
469        // Not enough kept outcomes is warming too, whatever the edits do.
470        let monitor = Monitor::new(config(64, 20));
471        for _ in 0..40 {
472            monitor.observe(true, false);
473        }
474        for _ in 0..19 {
475            monitor.observe(false, true);
476        }
477        assert!(matches!(monitor.verdict(), Verdict::Warming { .. }));
478        assert!(!monitor.tripped());
479    }
480
481    #[test]
482    fn the_configuration_is_clamped_and_never_panics() {
483        let wild = Monitor::new(MonitorConfig {
484            window: 0,
485            min_applied: 0,
486            min_kept: u32::MAX,
487            max_drop: f32::NAN,
488            z: f32::NEG_INFINITY,
489        });
490        assert_eq!(
491            *wild.config(),
492            MonitorConfig {
493                window: MIN_WINDOW,
494                min_applied: 1,
495                min_kept: MIN_WINDOW as u32,
496                max_drop: 0.02,
497                z: DEFAULT_Z,
498            }
499        );
500        let huge = Monitor::new(MonitorConfig {
501            window: usize::MAX,
502            ..MonitorConfig::default()
503        });
504        assert_eq!(huge.config().window, MAX_WINDOW);
505        for _ in 0..(MAX_WINDOW * 2 + 1) {
506            huge.observe(true, true);
507        }
508        assert!(matches!(huge.verdict(), Verdict::Warming { .. }));
509    }
510
511    #[test]
512    fn observations_from_many_threads_leave_a_well_formed_ring() {
513        const THREADS: usize = 8;
514        const EACH: usize = 500;
515        let monitor = Monitor::new(config(256, 16));
516        std::thread::scope(|scope| {
517            for thread in 0..THREADS {
518                let monitor = &monitor;
519                scope.spawn(move || {
520                    let mut rng = Rng(0xdead_beef + thread as u64);
521                    for _ in 0..EACH {
522                        monitor.observe(rng.chance(0.5), rng.chance(0.9));
523                        let _ = monitor.verdict();
524                    }
525                });
526            }
527        });
528
529        assert_eq!(monitor.head.load(Ordering::Relaxed), THREADS * EACH);
530        let mut valid = 0;
531        for slot in &monitor.ring {
532            let packed = slot.load(Ordering::Relaxed);
533            assert_eq!(packed & !(VALID | APPLIED | SUCCESS), 0, "{packed:#b}");
534            assert_ne!(packed, 0, "every slot was written more than once");
535            valid += 1;
536        }
537        assert_eq!(valid, 256);
538        let (applied, kept) = match monitor.verdict() {
539            Verdict::Warming { applied, kept } => (applied, kept),
540            Verdict::Healthy(e) | Verdict::Degraded(e) => (e.applied, e.kept),
541        };
542        assert_eq!(applied + kept, 256);
543    }
544}