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 | |
| 13 | use oxedyne_fe2o3_core::prelude::*; |
| 14 | use 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 | |
| 30 | use std::{ |
| 31 | collections::BTreeSet, |
| 32 | sync::{ |
| 33 | Arc, |
| 34 | Mutex, |
| 35 | }, |
| 36 | }; |
| 37 | |
| 38 | |
| 39 | const NOW: u64 = 1_000; |
| 40 | |
| 41 | fn 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. |
| 48 | fn 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)] |
| 54 | struct 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 | |
| 59 | impl TimeGate { |
| 60 | fn new(refuse: bool) -> Self { |
| 61 | Self { refuse, seen: Arc::new(Mutex::new(Vec::new())) } |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | impl 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). |
| 96 | fn 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] |
| 117 | fn 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] |
| 130 | fn 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] |
| 166 | fn 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] |
| 175 | fn 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 | } |