oxedyne/fe2o3/fe2o3_o3db_sync/tests/dist_paging.rs
11.7 KiB, 1 run
created by r1870400018:67682, 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 | //! Paged anti-entropy over many pages (A2 QA fix round, A1-F1). |
| 3 | //! |
| 4 | //! Every envelope here goes through `Envelope::encode` and `decode`, as a real transport runs |
| 5 | //! it, and must stay under the codec's bound. The tables are tens of 1 MiB records, so a reply or |
| 6 | //! a push is cut at 12 MiB and an exchange moves eleven. A bulk reply carries a cursor, `next`, |
| 7 | //! that the dialler sends back as `after`; a decoded difference and the dialler's push carry it |
| 8 | //! too, so a record a peer keeps refusing cannot hold up the records behind it. |
| 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::{ |
| 15 | dist::{ |
| 16 | codec::MAX_ENVELOPE_BYTES, |
| 17 | config::{ |
| 18 | Consistency, |
| 19 | DistOzoneConfig, |
| 20 | TableConfig, |
| 21 | }, |
| 22 | engine::DistOzone, |
| 23 | record::{ |
| 24 | Record, |
| 25 | RecordId, |
| 26 | }, |
| 27 | resolve::{ |
| 28 | ReadView, |
| 29 | ResolveCtx, |
| 30 | Resolver, |
| 31 | Verdict, |
| 32 | }, |
| 33 | storage::{ |
| 34 | MemoryStorage, |
| 35 | Storage, |
| 36 | }, |
| 37 | transport::{ |
| 38 | Envelope, |
| 39 | MsgKind, |
| 40 | }, |
| 41 | }, |
| 42 | kademlia::id::NodeId, |
| 43 | oam::config::OamConfig, |
| 44 | }; |
| 45 | |
| 46 | use std::{ |
| 47 | collections::{ |
| 48 | BTreeSet, |
| 49 | HashMap, |
| 50 | }, |
| 51 | time::Duration, |
| 52 | }; |
| 53 | |
| 54 | |
| 55 | const MIB: usize = 1024 * 1024; |
| 56 | |
| 57 | fn node(b: u8) -> NodeId { |
| 58 | let mut bytes = [0u8; 32]; |
| 59 | bytes[31] = b; |
| 60 | NodeId::from_bytes(bytes) |
| 61 | } |
| 62 | |
| 63 | // Ids sort by their index. |
| 64 | fn rid(i: u16) -> RecordId { |
| 65 | let mut bytes = [0u8; 32]; |
| 66 | bytes[0] = (i >> 8) as u8; |
| 67 | bytes[1] = i as u8; |
| 68 | RecordId::from_bytes(bytes) |
| 69 | } |
| 70 | |
| 71 | fn idx(id: &RecordId) -> u16 { |
| 72 | let b = id.as_bytes(); |
| 73 | ((b[0] as u16) << 8) | b[1] as u16 |
| 74 | } |
| 75 | |
| 76 | fn rec(i: u16, len: usize) -> Record { |
| 77 | Record::new(rid(i), "identity", vec![(i % 251) as u8 + 1; len]) |
| 78 | } |
| 79 | |
| 80 | // Takes whatever arrives, except an id below the line, which it refuses. |
| 81 | struct Rule { |
| 82 | below: u16, |
| 83 | } |
| 84 | |
| 85 | impl Resolver for Rule { |
| 86 | fn resolve<V: ReadView>( |
| 87 | &self, |
| 88 | _ctx: &ResolveCtx, |
| 89 | _view: &V, |
| 90 | _table: &str, |
| 91 | id: &RecordId, |
| 92 | _held: Option<&[u8]>, |
| 93 | incoming: &[u8], |
| 94 | ) |
| 95 | -> Outcome<Verdict> |
| 96 | { |
| 97 | if idx(id) < self.below { |
| 98 | return Ok(Verdict::Refuse("below the line".to_string())); |
| 99 | } |
| 100 | Ok(Verdict::Take(incoming.to_vec())) |
| 101 | } |
| 102 | } |
| 103 | |
| 104 | type Peer = DistOzone<MemoryStorage, Rule>; |
| 105 | |
| 106 | fn cfg(local: u8, remote: u8, cells: usize) -> Outcome<DistOzoneConfig> { |
| 107 | let oam = res!(OamConfig::new(2, 2)); |
| 108 | let table = res!(TableConfig::new("identity", Consistency::Eventual, Duration::from_secs(30), cells)); |
| 109 | DistOzoneConfig::new(node(local), vec![node(remote)], oam, vec![table]) |
| 110 | } |
| 111 | |
| 112 | // Peer 1 (the dialler) and peer 2 (the listener), on a table whose sketch has `cells` cells. Each |
| 113 | // refuses the ids below its own line. |
| 114 | fn pair(cells: usize, d_below: u16, l_below: u16) -> Outcome<(Peer, Peer)> { |
| 115 | Ok(( |
| 116 | res!(DistOzone::with_resolver(res!(cfg(1, 2, cells)), MemoryStorage::new(), Rule { below: d_below })), |
| 117 | res!(DistOzone::with_resolver(res!(cfg(2, 1, cells)), MemoryStorage::new(), Rule { below: l_below })), |
| 118 | )) |
| 119 | } |
| 120 | |
| 121 | fn held(e: &Peer) -> Outcome<BTreeSet<u16>> { |
| 122 | Ok(res!(e.storage().digests("identity")).iter().map(|d| idx(&d.id)).collect()) |
| 123 | } |
| 124 | |
| 125 | fn same_bytes(a: &Peer, b: &Peer) -> Outcome<bool> { |
| 126 | let mut x: Vec<_> = res!(a.storage().digests("identity")).into_iter().map(|d| (d.id, d.content)).collect(); |
| 127 | let mut y: Vec<_> = res!(b.storage().digests("identity")).into_iter().map(|d| (d.id, d.content)).collect(); |
| 128 | x.sort(); |
| 129 | y.sort(); |
| 130 | Ok(x == y) |
| 131 | } |
| 132 | |
| 133 | // What one exchange carried. |
| 134 | struct Leg { |
| 135 | after: Option<RecordId>, // the digest's cursor |
| 136 | next: Option<RecordId>, // where the reply stopped |
| 137 | bulk: bool, |
| 138 | replied: Vec<u16>, // the records in the reply |
| 139 | pushed: Vec<u16>, // the records in the dialler's push |
| 140 | refused: Vec<u16>, // the records either side refused |
| 141 | biggest: usize, // the longest envelope written |
| 142 | } |
| 143 | |
| 144 | // An envelope as the wire carries it, held to the codec's bound. |
| 145 | fn carry(env: Envelope, biggest: &mut usize) -> Outcome<Envelope> { |
| 146 | let bytes = res!(env.encode()); |
| 147 | assert!(bytes.len() <= MAX_ENVELOPE_BYTES, "an envelope of {} bytes passed the bound", bytes.len()); |
| 148 | *biggest = (*biggest).max(bytes.len()); |
| 149 | Envelope::decode(&bytes) |
| 150 | } |
| 151 | |
| 152 | // One whole exchange, the dialler's digest to the listener, its reply and the dialler's push. |
| 153 | fn wire(d: &Peer, l: &Peer) -> Outcome<Leg> { |
| 154 | let mut biggest = 0; |
| 155 | let req = res!(carry(res!(d.build_anti_entropy_request("identity", node(2))), &mut biggest)); |
| 156 | let after = match &req.body { |
| 157 | MsgKind::AntiEntropyDigest { after, .. } => *after, |
| 158 | other => return Err(err!("Expected an AntiEntropyDigest, got {:?}.", other; Test, Mismatch)), |
| 159 | }; |
| 160 | let mut got = res!(l.handle_envelope_at(req, 1_000)); |
| 161 | assert_eq!(got.outbound.len(), 1); |
| 162 | let reply = res!(carry(got.outbound.remove(0), &mut biggest)); |
| 163 | let (next, bulk, replied) = match &reply.body { |
| 164 | MsgKind::AntiEntropyReply { next, bulk, records, .. } => |
| 165 | (*next, *bulk, records.iter().map(|r| idx(&r.id)).collect::<Vec<_>>()), |
| 166 | other => return Err(err!("Expected an AntiEntropyReply, got {:?}.", other; Test, Mismatch)), |
| 167 | }; |
| 168 | let mut mine = res!(d.handle_envelope_at(reply, 1_000)); |
| 169 | assert!(mine.failed.is_empty(), "the dialler failed a record: {:?}", mine.failed); |
| 170 | let mut refused: Vec<u16> = mine.refused.iter().map(|r| idx(&r.1)).collect(); |
| 171 | let mut pushed = Vec::new(); |
| 172 | for p in std::mem::take(&mut mine.outbound) { |
| 173 | let p = res!(carry(p, &mut biggest)); |
| 174 | match &p.body { |
| 175 | MsgKind::AntiEntropyPush { records, .. } => pushed.extend(records.iter().map(|r| idx(&r.id))), |
| 176 | other => return Err(err!("Expected an AntiEntropyPush, got {:?}.", other; Test, Mismatch)), |
| 177 | } |
| 178 | let landed = res!(l.handle_envelope_at(p, 1_000)); |
| 179 | assert!(landed.failed.is_empty(), "the listener failed a record: {:?}", landed.failed); |
| 180 | refused.extend(landed.refused.iter().map(|r| idx(&r.1))); |
| 181 | } |
| 182 | Ok(Leg { after, next, bulk, replied, pushed, refused, biggest }) |
| 183 | } |
| 184 | |
| 185 | // A full page of 1 MiB records is eleven, since the twelfth would pass 12 MiB. |
| 186 | const PAGE: usize = 11; |
| 187 | |
| 188 | // Exchanges until both peers hold `total` records, at most `cap`. The records are counted and |
| 189 | // not hashed, since the sketch already hashes every value, and this is a debug build. |
| 190 | fn run(d: &Peer, l: &Peer, total: usize, cap: usize) -> Outcome<Vec<Leg>> { |
| 191 | let mut legs = Vec::new(); |
| 192 | for _ in 0..cap { |
| 193 | legs.push(res!(wire(d, l))); |
| 194 | if res!(d.storage().len()) == total && res!(l.storage().len()) == total { |
| 195 | break; |
| 196 | } |
| 197 | } |
| 198 | assert!(res!(same_bytes(d, l)), "the peers did not converge in {} exchanges", legs.len()); |
| 199 | Ok(legs) |
| 200 | } |
| 201 | |
| 202 | |
| 203 | // 26 x 1 MiB at the listener, nothing at the dialler, and a 6-cell sketch that stays overloaded |
| 204 | // until the last page. Each exchange moves one page, `next` of one is `after` of the next, and the |
| 205 | // last page, which ends the table, clears the cursor. |
| 206 | #[test] |
| 207 | fn bulk_reply_pages_and_the_cursor_advances() -> Outcome<()> { |
| 208 | let (d, l) = res!(pair(6, 0, 0)); |
| 209 | for i in 0..26u16 { |
| 210 | res!(l.storage().put(&rec(i, MIB))); |
| 211 | } |
| 212 | let legs = res!(run(&d, &l, 26, 6)); |
| 213 | assert_eq!(res!(held(&d)).len(), 26); |
| 214 | assert_eq!(legs.len(), 3, "26 records of 1 MiB are three pages of at most {}", PAGE); |
| 215 | assert_eq!(legs[0].after, None); |
| 216 | let mut seen = 0; |
| 217 | let mut last: Option<RecordId> = None; |
| 218 | for (k, leg) in legs.iter().enumerate() { |
| 219 | assert!(leg.bulk, "exchange {} was not a bulk reply", k); |
| 220 | assert!(leg.replied.len() <= PAGE, "exchange {} carried {} records", k, leg.replied.len()); |
| 221 | assert!(leg.biggest <= MAX_ENVELOPE_BYTES); |
| 222 | if k + 1 < legs.len() { |
| 223 | assert_eq!(leg.replied.len(), PAGE, "exchange {} did not fill its page", k); |
| 224 | assert!(leg.biggest > 11 * MIB, "exchange {} wrote only {} bytes", k, leg.biggest); |
| 225 | } |
| 226 | if k > 0 { |
| 227 | assert_eq!(leg.after, last, "exchange {} did not resume where {} stopped", k, k - 1); |
| 228 | } |
| 229 | if k + 1 < legs.len() { |
| 230 | let n = res!(leg.next.ok_or_else(|| err!("exchange {} ended the table early.", k; Test, Missing))); |
| 231 | if let Some(prev) = last { |
| 232 | assert!(n > prev, "the cursor did not advance at exchange {}", k); |
| 233 | } |
| 234 | last = Some(n); |
| 235 | } else { |
| 236 | assert_eq!(leg.next, None, "the last page names a next"); |
| 237 | } |
| 238 | seen += leg.replied.len(); |
| 239 | } |
| 240 | assert_eq!(seen, 26); |
| 241 | // What arrived is what was sent, byte for byte. |
| 242 | for i in 0..26u16 { |
| 243 | let got = res!(d.storage().get("identity", &rid(i))); |
| 244 | let got = res!(got.ok_or_else(|| err!("record {} is missing.", i; Test, Missing))); |
| 245 | assert_eq!(got.value, rec(i, MIB).value, "record {} came back at other bytes", i); |
| 246 | } |
| 247 | Ok(()) |
| 248 | } |
| 249 | |
| 250 | // The dialler holds records too, so its push is paged to the range of the listener's page. In |
| 251 | // the interleaved case each side holds half of 30 records, and every page both sends and pushes. |
| 252 | #[test] |
| 253 | fn dialler_also_holds_records_interleaved() -> Outcome<()> { |
| 254 | let (d, l) = res!(pair(6, 0, 0)); |
| 255 | for i in 0..30u16 { |
| 256 | if i % 2 == 0 { |
| 257 | res!(d.storage().put(&rec(i, MIB))); |
| 258 | } else { |
| 259 | res!(l.storage().put(&rec(i, MIB))); |
| 260 | } |
| 261 | } |
| 262 | let legs = res!(run(&d, &l, 30, 8)); |
| 263 | assert_eq!(res!(held(&d)).len(), 30); |
| 264 | assert_eq!(res!(held(&l)).len(), 30); |
| 265 | assert!(legs.len() > 1, "15 MiB each way cannot cross in one exchange"); |
| 266 | assert!(legs.iter().any(|g| !g.pushed.is_empty()), "the dialler never pushed"); |
| 267 | for leg in &legs { |
| 268 | assert!(leg.pushed.len() <= PAGE && leg.replied.len() <= PAGE); |
| 269 | } |
| 270 | Ok(()) |
| 271 | } |
| 272 | |
| 273 | // The listener's own page is tiny and ends the table, so the dialler's 26 x 1 MiB cannot cross in |
| 274 | // its one push. The push stops at eleven, and the dialler asks again from the last id it sent. |
| 275 | #[test] |
| 276 | fn dialler_push_is_paged_and_resumes_after_its_last_id() -> Outcome<()> { |
| 277 | let (d, l) = res!(pair(6, 0, 0)); |
| 278 | res!(l.storage().put(&rec(0, 100))); |
| 279 | res!(l.storage().put(&rec(1_000, 100))); |
| 280 | for i in 100..126u16 { |
| 281 | res!(d.storage().put(&rec(i, MIB))); |
| 282 | } |
| 283 | let legs = res!(run(&d, &l, 28, 8)); |
| 284 | assert_eq!(res!(held(&l)).len(), 28); |
| 285 | assert_eq!(legs[0].pushed.len(), PAGE, "the first push is one page"); |
| 286 | assert_eq!(legs[0].pushed, (100..100 + PAGE as u16).collect::<Vec<_>>(), "the push is in id order"); |
| 287 | assert_eq!(legs[1].after, Some(rid(100 + PAGE as u16 - 1)), "the dialler resumes after the last id it pushed"); |
| 288 | assert!(legs.iter().all(|g| g.pushed.len() <= PAGE)); |
| 289 | Ok(()) |
| 290 | } |
| 291 | |
| 292 | // 26 x 1 MiB at the listener, a sketch that decodes, and a dialler that refuses the first 12 ids. |
| 293 | // A decoded reply is paged and the refused records stay in the difference, so unless the cursor |
| 294 | // moves past them the first page is the same 11 refused records on every exchange and the |
| 295 | // records behind never arrive. The refused are offered again on the next lap. |
| 296 | #[test] |
| 297 | fn refusing_dialler_does_not_block_the_records_behind() -> Outcome<()> { |
| 298 | let (d, l) = res!(pair(256, 12, 0)); |
| 299 | for i in 0..26u16 { |
| 300 | res!(l.storage().put(&rec(i, MIB))); |
| 301 | } |
| 302 | let mut tries: HashMap<u16, usize> = HashMap::new(); |
| 303 | let mut legs = Vec::new(); |
| 304 | for _ in 0..6 { |
| 305 | let leg = res!(wire(&d, &l)); |
| 306 | for i in &leg.refused { |
| 307 | *tries.entry(*i).or_insert(0) += 1; |
| 308 | } |
| 309 | legs.push(leg); |
| 310 | } |
| 311 | assert!(legs.iter().all(|g| !g.bulk), "the sketch should decode"); |
| 312 | let want: BTreeSet<u16> = (12..26).collect(); |
| 313 | assert_eq!(res!(held(&d)), want, "the records after the refused ones did not all arrive"); |
| 314 | for i in 0..12u16 { |
| 315 | assert!(tries.get(&i).copied().unwrap_or(0) >= 2, "refused record {} was not offered again", i); |
| 316 | } |
| 317 | assert!(legs.iter().all(|g| g.biggest <= MAX_ENVELOPE_BYTES)); |
| 318 | Ok(()) |
| 319 | } |
| 320 | |
| 321 | // The mirror: the dialler holds 26 x 1 MiB and the listener refuses the first 12. The dialler's |
| 322 | // push is paged, and its cursor must pass the refused records for the rest to land. |
| 323 | #[test] |
| 324 | fn refusing_listener_does_not_block_the_push() -> Outcome<()> { |
| 325 | let (d, l) = res!(pair(256, 0, 12)); |
| 326 | for i in 0..26u16 { |
| 327 | res!(d.storage().put(&rec(i, MIB))); |
| 328 | } |
| 329 | let mut tries: HashMap<u16, usize> = HashMap::new(); |
| 330 | for _ in 0..6 { |
| 331 | let leg = res!(wire(&d, &l)); |
| 332 | for i in &leg.refused { |
| 333 | *tries.entry(*i).or_insert(0) += 1; |
| 334 | } |
| 335 | } |
| 336 | let want: BTreeSet<u16> = (12..26).collect(); |
| 337 | assert_eq!(res!(held(&l)), want, "the records after the refused ones did not all arrive"); |
| 338 | for i in 0..12u16 { |
| 339 | assert!(tries.get(&i).copied().unwrap_or(0) >= 2, "refused record {} was not offered again", i); |
| 340 | } |
| 341 | Ok(()) |
| 342 | } |