Oregami
Repositories/oxedyne/fe2o3

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
13use oxedyne_fe2o3_core::prelude::*;
14use 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
46use std::{
47 collections::{
48 BTreeSet,
49 HashMap,
50 },
51 time::Duration,
52};
53
54
55const MIB: usize = 1024 * 1024;
56
57fn 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.
64fn 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
71fn idx(id: &RecordId) -> u16 {
72 let b = id.as_bytes();
73 ((b[0] as u16) << 8) | b[1] as u16
74}
75
76fn 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.
81struct Rule {
82 below: u16,
83}
84
85impl 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
104type Peer = DistOzone<MemoryStorage, Rule>;
105
106fn 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.
114fn 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
121fn held(e: &Peer) -> Outcome<BTreeSet<u16>> {
122 Ok(res!(e.storage().digests("identity")).iter().map(|d| idx(&d.id)).collect())
123}
124
125fn 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.
134struct 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.
145fn 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.
153fn 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.
186const 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.
190fn 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]
207fn 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]
253fn 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]
276fn 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]
297fn 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]
324fn 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}