1use std::sync::atomic::{AtomicBool, AtomicU8, AtomicUsize, Ordering};
34
35pub const MIN_WINDOW: usize = 64;
37
38pub const MAX_WINDOW: usize = 8_192;
40
41pub const DEFAULT_Z: f32 = 1.645;
44
45const VALID: u8 = 0b001;
47const APPLIED: u8 = 0b010;
49const SUCCESS: u8 = 0b100;
51
52#[derive(Debug, Clone, Copy, PartialEq)]
54pub struct MonitorConfig {
55 pub window: usize,
58 pub min_applied: u32,
61 pub min_kept: u32,
64 pub max_drop: f32,
67 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 fn settled(self) -> MonitorConfig {
89 let window = self.window.clamp(MIN_WINDOW, MAX_WINDOW);
90 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#[derive(Debug, Clone, Copy, PartialEq)]
113pub struct Estimate {
114 pub applied: u32,
116 pub applied_successes: u32,
118 pub kept: u32,
120 pub kept_successes: u32,
122 pub drop: f32,
125 pub drop_lower_bound: f32,
127}
128
129#[derive(Debug, Clone, Copy, PartialEq)]
131pub enum Verdict {
132 Warming {
134 applied: u32,
136 kept: u32,
138 },
139 Healthy(Estimate),
141 Degraded(Estimate),
143}
144
145#[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 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 pub fn config(&self) -> &MonitorConfig {
180 &self.config
181 }
182
183 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 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 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 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 pub fn tripped(&self) -> bool {
263 self.tripped.load(Ordering::Relaxed)
264 }
265
266 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 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 fn chance(&mut self, p: f32) -> bool {
307 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 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 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 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 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}