Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/tests/dist_skew.rs

5.5 KiB, 1 run

created by r1870400018:67490, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1#![cfg(feature = "dist")]
2//! Tests for the per-peer clock skew of [`check_convergence`] (A1 QA finding 2-F5).
3//!
4//! With one clock for every peer, a rule that answers `Refuse` to a time it has not
5//! yet reached passes the check, although it makes the converged state depend on
6//! which peer a record landed on. `Convergence::with_skew_ms` gives each peer a
7//! seeded offset, and every full round moves every clock on by `skew_ms`, so that
8//! `Defer` until the time comes cures and `Refuse` is reported.
9//!
10//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
11//! Anthropic Claude
12
13use oxedyne_fe2o3_core::prelude::*;
14use oxedyne_fe2o3_o3db_sync::dist::{
15 record::{
16 Record,
17 RecordId,
18 },
19 resolve::{
20 Convergence,
21 LastVersionWins,
22 ReadView,
23 ResolveCtx,
24 Resolver,
25 Verdict,
26 check_convergence,
27 },
28};
29
30use std::{
31 collections::BTreeSet,
32 sync::{
33 Arc,
34 Mutex,
35 },
36};
37
38
39const NOW: u64 = 1_000;
40
41fn rid(b: u8) -> RecordId {
42 let mut bytes = [0u8; 32];
43 bytes[0] = b;
44 RecordId::from_bytes(bytes)
45}
46
47/// `n` records on "identity", each stamped with this version.
48fn stamped(n: u8, stamp: u64) -> Vec<Record> {
49 (1..=n).map(|i| Record::new(rid(i), "identity", LastVersionWins::value(stamp, &[i]))).collect()
50}
51
52/// Last-version-wins, except that a record stamped after the clock is not yet valid.
53#[derive(Clone)]
54struct TimeGate {
55 refuse: bool, // answer Refuse where a sound rule answers Defer
56 seen: Arc<Mutex<Vec<u64>>>, // every clock this rule was asked with, in order
57}
58
59impl TimeGate {
60 fn new(refuse: bool) -> Self {
61 Self { refuse, seen: Arc::new(Mutex::new(Vec::new())) }
62 }
63}
64
65impl Resolver for TimeGate {
66 fn resolve<V: ReadView>(
67 &self,
68 ctx: &ResolveCtx,
69 view: &V,
70 table: &str,
71 id: &RecordId,
72 held: Option<&[u8]>,
73 incoming: &[u8],
74 )
75 -> Outcome<Verdict>
76 {
77 {
78 let mut seen = lock_mutex!(self.seen);
79 seen.push(ctx.now_ms);
80 }
81 if let Some(stamp) = LastVersionWins::version(incoming) {
82 if stamp > ctx.now_ms {
83 return Ok(if self.refuse {
84 Verdict::Refuse(fmt!("stamp {} is after the clock {}", stamp, ctx.now_ms))
85 } else {
86 Verdict::Defer
87 });
88 }
89 }
90 LastVersionWins.resolve(ctx, view, table, id, held, incoming)
91 }
92}
93
94/// Runs the check and returns the clocks each peer's rule was asked with, one list
95/// per peer per seed, in the order the harness built them (seed by seed, peer by peer).
96fn run(cfg: &Convergence, records: &[Record], refuse: bool) -> Outcome<(Outcome<()>, Vec<Vec<u64>>)> {
97 let mut gates: Vec<TimeGate> = Vec::new();
98 let result = check_convergence(
99 cfg,
100 &["identity"],
101 records,
102 |_| {
103 let g = TimeGate::new(refuse);
104 gates.push(g.clone());
105 g
106 },
107 |_, _, _| Ok(Vec::new()),
108 );
109 let mut clocks = Vec::new();
110 for g in &gates {
111 clocks.push(lock_mutex!(g.seen).clone());
112 }
113 Ok((result, clocks))
114}
115
116#[test]
117fn without_skew_every_peer_reads_the_one_clock() -> Outcome<()> {
118 let cfg = Convergence::new(3, 0..4, NOW, 8);
119 let (result, clocks) = res!(run(&cfg, &stamped(6, 1), false));
120 res!(result);
121 assert_eq!(clocks.len(), 12);
122 for log in &clocks {
123 assert!(!log.is_empty());
124 assert!(log.iter().all(|c| *c == NOW), "a clock moved with no skew: {:?}", log);
125 }
126 Ok(())
127}
128
129#[test]
130fn skewed_clocks_differ_by_peer_but_are_seeded_and_never_run_back() -> Outcome<()> {
131 let (step, rounds) = (500u64, 8usize);
132 let cfg = Convergence::new(3, 0..8, NOW, rounds).with_skew_ms(step);
133 let (result, clocks) = res!(run(&cfg, &stamped(8, 1), false));
134 res!(result);
135 let mut offsets = BTreeSet::new();
136 for log in &clocks {
137 assert!(!log.is_empty());
138 // Each full round moves a clock on by `step`, so the remainder is the peer's own offset.
139 let offset = (log[0] - NOW) % step;
140 offsets.insert(offset);
141 for w in log.windows(2) {
142 assert!(w[0] <= w[1], "a clock ran back: {:?}", log);
143 }
144 for c in log {
145 assert!(*c >= NOW);
146 assert_eq!((*c - NOW) % step, offset, "a peer's offset changed: {:?}", log);
147 assert!(*c <= NOW + step * (rounds as u64 + 1), "clock {} is out of range", c);
148 }
149 }
150 assert!(offsets.len() > 1, "every peer has the same offset: {:?}", offsets);
151 // The offset is drawn per peer, not per seed: peers of one seed differ in some seed.
152 let mut mixed = false;
153 for seed_peers in clocks.chunks(3) {
154 let own: BTreeSet<u64> = seed_peers.iter().map(|log| (log[0] - NOW) % step).collect();
155 mixed = mixed || own.len() > 1;
156 }
157 assert!(mixed, "no seed gave its peers different offsets");
158 // The same seeds draw the same offsets.
159 let (again, replay) = res!(run(&cfg, &stamped(8, 1), false));
160 res!(again);
161 assert_eq!(clocks, replay);
162 Ok(())
163}
164
165#[test]
166fn defer_until_the_clock_passes_converges_under_skew() -> Outcome<()> {
167 // A stamp inside the spread of the clocks: some peers are behind it at first.
168 let cfg = Convergence::new(3, 0..16, NOW, 8).with_skew_ms(400);
169 let (result, _) = res!(run(&cfg, &stamped(6, NOW + 200), false));
170 res!(result);
171 Ok(())
172}
173
174#[test]
175fn refuse_on_a_time_passes_one_clock_and_fails_under_skew() -> Outcome<()> {
176 let records = stamped(6, NOW + 200);
177 // One clock for every peer: all refuse alike, so the check cannot see the fault.
178 let one_clock = Convergence::new(3, 0..16, NOW, 8);
179 let (result, _) = res!(run(&one_clock, &records, true));
180 res!(result);
181 // Skewed: the state depends on which peer a record landed on, and the check says so.
182 let skewed = Convergence::new(3, 0..16, NOW, 8).with_skew_ms(400);
183 let (result, _) = res!(run(&skewed, &records, true));
184 let text = match result {
185 Ok(()) => String::new(),
186 Err(e) => fmt!("{}", e),
187 };
188 assert!(text.contains("differ"), "the skewed run was not reported as divergent: {}", text);
189 Ok(())
190}