Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/tests/dist_symmetric.rs

17.7 KiB, 13 runs

created by r1870400018:67492, 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//! Symmetric anti-entropy (A2 R3, A1 QA 2-F3).
3//!
4//! The sketch is keyed on a record's id followed by its content hash, with an empty value, so a
5//! record held at other bytes is a different key and decodes as one entry on each side. One
6//! exchange then offers every differing record to both peers, whether the sketch decodes or
7//! overloads, and a record held at the same bytes on both sides is never sent.
8//!
9//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
10//! Anthropic Claude
11
12use oxedyne_fe2o3_core::prelude::*;
13use oxedyne_fe2o3_data::iblt::{
14 Iblt,
15 IbltConfig,
16};
17use oxedyne_fe2o3_o3db_sync::{
18 dist::{
19 config::{
20 Consistency,
21 DistOzoneConfig,
22 TableConfig,
23 },
24 engine::DistOzone,
25 record::{
26 Record,
27 RecordDigest,
28 RecordId,
29 },
30 resolve::{
31 LastVersionWins,
32 ReadView,
33 ResolveCtx,
34 Resolver,
35 Verdict,
36 },
37 storage::{
38 MemoryStorage,
39 Storage,
40 },
41 transport::{
42 Envelope,
43 MsgKind,
44 },
45 },
46 kademlia::id::NodeId,
47 oam::config::OamConfig,
48};
49
50use std::{
51 collections::BTreeSet,
52 sync::{
53 Mutex,
54 atomic::{
55 AtomicUsize,
56 Ordering,
57 },
58 },
59 time::Duration,
60};
61
62
63fn node(b: u8) -> NodeId {
64 let mut bytes = [0u8; 32];
65 bytes[31] = b;
66 NodeId::from_bytes(bytes)
67}
68
69fn rid(b: u8) -> RecordId {
70 RecordId::from_bytes([b; 32])
71}
72
73fn rec(id: RecordId, value: &[u8]) -> Record {
74 Record::new(id, "identity", value.to_vec())
75}
76
77/// A value the stock resolver orders by its version.
78fn ver(version: u64, text: &[u8]) -> Vec<u8> {
79 LastVersionWins::value(version, text)
80}
81
82fn ids(records: &[Record]) -> BTreeSet<RecordId> {
83 records.iter().map(|r| r.id).collect()
84}
85
86fn cfg(local: u8, remote: u8, cells: usize) -> Outcome<DistOzoneConfig> {
87 let oam = res!(OamConfig::new(2, 2));
88 let table = res!(TableConfig::new("identity", Consistency::Eventual, Duration::from_secs(30), cells));
89 DistOzoneConfig::new(node(local), vec![node(remote)], oam, vec![table])
90}
91
92/// Peer 1 and peer 2, each holding everything, on a table whose sketch has `cells` cells.
93fn pair<S: Storage>(cells: usize, s1: S, s2: S) -> Outcome<(DistOzone<S>, DistOzone<S>)> {
94 Ok((
95 res!(DistOzone::new(res!(cfg(1, 2, cells)), s1)),
96 res!(DistOzone::new(res!(cfg(2, 1, cells)), s2)),
97 ))
98}
99
100fn put<S: Storage, R: Resolver>(e: &DistOzone<S, R>, id: RecordId, value: &[u8]) -> Outcome<()> {
101 e.storage().put(&rec(id, value))
102}
103
104fn stored<S: Storage, R: Resolver>(e: &DistOzone<S, R>, id: RecordId) -> Outcome<Option<Vec<u8>>> {
105 Ok(res!(e.storage().get("identity", &id)).map(|r| r.value))
106}
107
108fn table_ids<S: Storage, R: Resolver>(e: &DistOzone<S, R>) -> Outcome<BTreeSet<RecordId>> {
109 Ok(res!(e.storage().digests("identity")).into_iter().map(|d| d.id).collect())
110}
111
112/// A storage that logs the id of every write.
113struct Counting {
114 inner: MemoryStorage,
115 puts: Mutex<Vec<RecordId>>,
116}
117
118impl Counting {
119 fn new() -> Self {
120 Self { inner: MemoryStorage::new(), puts: Mutex::new(Vec::new()) }
121 }
122
123 /// The ids written since the last call.
124 fn take_puts(&self) -> Outcome<BTreeSet<RecordId>> {
125 let mut log = lock_mutex!(self.puts);
126 Ok(std::mem::take(&mut *log).into_iter().collect())
127 }
128}
129
130impl Storage for Counting {
131 fn put(&self, record: &Record) -> Outcome<()> {
132 lock_mutex!(self.puts).push(record.id);
133 self.inner.put(record)
134 }
135
136 fn get(&self, table: &str, id: &RecordId) -> Outcome<Option<Record>> {
137 self.inner.get(table, id)
138 }
139
140 fn delete(&self, table: &str, id: &RecordId) -> Outcome<bool> {
141 self.inner.delete(table, id)
142 }
143
144 fn digests(&self, table: &str) -> Outcome<Vec<RecordDigest>> {
145 self.inner.digests(table)
146 }
147}
148
149/// Takes whatever arrives, and counts the calls.
150struct CountCalls {
151 calls: AtomicUsize,
152}
153
154impl Resolver for CountCalls {
155 fn resolve<V: ReadView>(
156 &self,
157 _ctx: &ResolveCtx,
158 _view: &V,
159 _table: &str,
160 _id: &RecordId,
161 _held: Option<&[u8]>,
162 incoming: &[u8],
163 )
164 -> Outcome<Verdict>
165 {
166 self.calls.fetch_add(1, Ordering::SeqCst);
167 Ok(Verdict::Take(incoming.to_vec()))
168 }
169}
170
171/// What each leg of one exchange carried.
172struct Legs {
173 records: Vec<Record>, // the listener's reply
174 requested: Vec<RecordId>, // the ids the reply asked for
175 bulk: bool,
176 pushed: Vec<Record>, // the dialler's push, empty when there was none
177 pushes: usize, // how many push envelopes the dialler sent
178}
179
180/// One whole exchange on "identity", the dialler's digest to the listener, the listener's reply
181/// and the dialler's push, every leg delivered and recorded.
182fn exchange<S1: Storage, S2: Storage>(
183 dialler: &DistOzone<S1>,
184 listener: &DistOzone<S2>,
185 listener_id: u8,
186)
187 -> Outcome<Legs>
188{
189 let req = res!(dialler.build_anti_entropy_request("identity", node(listener_id)));
190 let mut got = res!(listener.handle_envelope_at(req, 1_000));
191 assert_eq!(got.outbound.len(), 1);
192 let reply = got.outbound.remove(0);
193 let (records, requested, bulk) = match &reply.body {
194 MsgKind::AntiEntropyReply { records, requested_ids, bulk, .. } =>
195 (records.clone(), requested_ids.clone(), *bulk),
196 other => return Err(err!("Expected an AntiEntropyReply, got {:?}.", other; Test, Mismatch)),
197 };
198 let mut mine = res!(dialler.handle_envelope_at(reply, 1_000));
199 assert!(mine.failed.is_empty(), "the dialler failed a record: {:?}", mine.failed);
200 let mut pushed = Vec::new();
201 let mut pushes = 0;
202 for p in std::mem::take(&mut mine.outbound) {
203 match &p.body {
204 MsgKind::AntiEntropyPush { records, .. } => {
205 pushes += 1;
206 pushed.extend(records.clone());
207 },
208 other => return Err(err!("Expected an AntiEntropyPush, got {:?}.", other; Test, Mismatch)),
209 }
210 let landed = res!(listener.handle_envelope_at(p, 1_000));
211 assert!(landed.failed.is_empty(), "the listener failed a record: {:?}", landed.failed);
212 }
213 Ok(Legs { records, requested, bulk, pushed, pushes })
214}
215
216/// The sketch the engine is expected to send: the id and the content hash as the key, no value.
217fn sketch_cfg(cells: usize) -> Outcome<IbltConfig> {
218 let table = res!(TableConfig::new("identity", Consistency::Eventual, Duration::from_secs(30), cells));
219 Ok(IbltConfig {
220 num_cells: cells,
221 num_hashes: TableConfig::IBLT_NUM_HASHES,
222 key_len: 64,
223 value_len: 0,
224 seed: table.iblt_seed(),
225 })
226}
227
228fn digest_envelope(from: u8, to: u8, sketch: Vec<u8>) -> Envelope {
229 Envelope::new(node(from), node(to), MsgKind::AntiEntropyDigest {
230 table: "identity".to_string(),
231 sketch,
232 after: None,
233 })
234}
235
236
237// One id at two values among twenty shared records: the sketch decodes, the reply is not bulk,
238// and it carries that one record and asks for that one id. The dialler resolves, so both peers end
239// on the newer value; the push carries it only when the dialler held it, and is empty when it took
240// the listener's own bytes.
241#[test]
242fn value_divergence_decodes_without_bulk() -> Outcome<()> {
243 let v1 = ver(1, b"old");
244 let v2 = ver(2, b"new");
245 for dialler_newer in [true, false] {
246 let (d, l) = res!(pair(256, MemoryStorage::new(), MemoryStorage::new()));
247 for i in 1..=20u8 {
248 let v = ver(1, &[i]);
249 res!(put(&d, rid(i), &v));
250 res!(put(&l, rid(i), &v));
251 }
252 let (dv, lv) = if dialler_newer { (&v2, &v1) } else { (&v1, &v2) };
253 res!(put(&d, rid(100), dv));
254 res!(put(&l, rid(100), lv));
255
256 let legs = res!(exchange(&d, &l, 2));
257 let who = if dialler_newer { "dialler newer" } else { "listener newer" };
258 assert!(!legs.bulk, "{}: a value difference made the exchange bulk", who);
259 assert_eq!(legs.records, vec![rec(rid(100), lv)], "{}: the reply", who);
260 assert_eq!(legs.requested, vec![rid(100)], "{}: the ids asked for", who);
261 // The push offers the listener the dialler's value only when the listener lacks it:
262 // when the listener's own newer bytes were taken, they are not sent back.
263 let (pushes, pushed) = if dialler_newer { (1, vec![rec(rid(100), &v2)]) } else { (0, Vec::new()) };
264 assert_eq!(legs.pushes, pushes, "{}: the pushes", who);
265 assert_eq!(legs.pushed, pushed, "{}: the push", who);
266 assert_eq!(res!(stored(&d, rid(100))), Some(v2.clone()), "{}: the dialler", who);
267 assert_eq!(res!(stored(&l, rid(100))), Some(v2.clone()), "{}: the listener", who);
268 assert_eq!(res!(table_ids(&d)).len(), 21);
269 assert_eq!(res!(table_ids(&l)).len(), 21);
270 }
271 Ok(())
272}
273
274// A sketch of six cells cannot hold the difference, so the reply is bulk. The dialler takes what
275// it lacks and pushes back everything the listener lacks or holds at other bytes, and nothing
276// else: after one exchange both hold the same forty records with the newer X.
277#[test]
278fn bulk_exchange_repairs_both_sides() -> Outcome<()> {
279 let v1 = ver(1, b"old");
280 let v2 = ver(2, b"new");
281 for dialler_newer in [true, false] {
282 let (d, l) = res!(pair(6, MemoryStorage::new(), MemoryStorage::new()));
283 let dialler_only: BTreeSet<RecordId> = (1..=30u8).map(rid).collect();
284 let listener_only: BTreeSet<RecordId> = (31..=35u8).map(rid).collect();
285 let shared: BTreeSet<RecordId> = (36..=39u8).map(rid).collect();
286 for i in 1..=39u8 {
287 let v = ver(1, &[i]);
288 if i <= 30 || i >= 36 {
289 res!(put(&d, rid(i), &v));
290 }
291 if i >= 31 {
292 res!(put(&l, rid(i), &v));
293 }
294 }
295 let (dv, lv) = if dialler_newer { (&v2, &v1) } else { (&v1, &v2) };
296 res!(put(&d, rid(100), dv));
297 res!(put(&l, rid(100), lv));
298
299 let legs = res!(exchange(&d, &l, 2));
300 let who = if dialler_newer { "dialler newer" } else { "listener newer" };
301 assert!(legs.bulk, "{}: six cells decoded a difference of thirty-seven", who);
302 assert!(legs.requested.is_empty(), "{}: a bulk reply asked for {:?}", who, legs.requested);
303 let mut reply: BTreeSet<RecordId> = listener_only.union(&shared).copied().collect();
304 reply.insert(rid(100));
305 assert_eq!(ids(&legs.records), reply, "{}: the bulk reply is the listener's whole table", who);
306
307 // The push is the dialler's thirty, and X only while it differs from the listener's copy.
308 let mut push = dialler_only.clone();
309 if dialler_newer {
310 push.insert(rid(100));
311 }
312 assert_eq!(legs.pushes, 1, "{}: the pushes", who);
313 assert_eq!(legs.pushed.len(), push.len(), "{}: the push repeats a record", who);
314 assert_eq!(ids(&legs.pushed), push, "{}: the push", who);
315
316 let mut all: BTreeSet<RecordId> = dialler_only.union(&listener_only).copied().collect();
317 all.extend(shared.iter().copied());
318 all.insert(rid(100));
319 assert_eq!(all.len(), 40);
320 assert_eq!(res!(table_ids(&d)), all, "{}: the dialler's table", who);
321 assert_eq!(res!(table_ids(&l)), all, "{}: the listener's table", who);
322 assert_eq!(res!(stored(&d, rid(100))), Some(v2.clone()), "{}: the dialler's X", who);
323 assert_eq!(res!(stored(&l, rid(100))), Some(v2.clone()), "{}: the listener's X", who);
324 for id in &all {
325 assert_eq!(res!(stored(&d, *id)), res!(stored(&l, *id)), "{}: the peers differ at {:?}", who, id);
326 }
327 }
328 Ok(())
329}
330
331// A record held at the same bytes on both sides crosses no leg and is written nowhere, whether
332// the sketch decodes an empty difference, a real one, or an empty one again.
333#[test]
334fn same_bytes_never_sent() -> Outcome<()> {
335 let shared: BTreeSet<RecordId> = (1..=20u8).map(rid).collect();
336 let (d, l) = res!(pair(256, Counting::new(), Counting::new()));
337 for i in 1..=20u8 {
338 let v = ver(1, &[i]);
339 res!(put(&d, rid(i), &v));
340 res!(put(&l, rid(i), &v));
341 }
342 res!(d.storage().take_puts());
343 res!(l.storage().take_puts());
344
345 // Identical tables: an empty reply, no push, no write.
346 let legs = res!(exchange(&d, &l, 2));
347 assert!(legs.records.is_empty() && legs.requested.is_empty() && !legs.bulk, "identical tables: a reply");
348 assert_eq!(legs.pushes, 0, "identical tables: a push");
349 assert!(res!(d.storage().take_puts()).is_empty() && res!(l.storage().take_puts()).is_empty());
350
351 // Three only the dialler holds, two only the listener holds, and X at two values.
352 for i in 50..=52u8 {
353 res!(put(&d, rid(i), &ver(1, &[i])));
354 }
355 for i in 60..=61u8 {
356 res!(put(&l, rid(i), &ver(1, &[i])));
357 }
358 res!(put(&d, rid(100), &ver(2, b"new")));
359 res!(put(&l, rid(100), &ver(1, b"old")));
360 res!(d.storage().take_puts());
361 res!(l.storage().take_puts());
362
363 let legs = res!(exchange(&d, &l, 2));
364 assert!(!legs.bulk);
365 let sent: BTreeSet<RecordId> = ids(&legs.records).union(&ids(&legs.pushed)).copied().collect();
366 assert!(sent.is_disjoint(&shared), "a shared record crossed a leg: {:?}", sent);
367 let want_l: BTreeSet<RecordId> = [50u8, 51, 52, 100].into_iter().map(rid).collect();
368 let want_d: BTreeSet<RecordId> = [60u8, 61].into_iter().map(rid).collect();
369 assert_eq!(res!(l.storage().take_puts()), want_l, "the listener's writes");
370 assert_eq!(res!(d.storage().take_puts()), want_d, "the dialler's writes");
371
372 // Now equal: nothing crosses and nothing is written, in either direction.
373 for (a, b, to) in [(&d, &l, 2u8), (&l, &d, 1u8)] {
374 let legs = res!(exchange(a, b, to));
375 assert!(legs.records.is_empty() && legs.requested.is_empty() && !legs.bulk, "second exchange: a reply");
376 assert_eq!(legs.pushes, 0, "second exchange: a push");
377 }
378 assert!(res!(d.storage().take_puts()).is_empty() && res!(l.storage().take_puts()).is_empty());
379 Ok(())
380}
381
382// A reply that repeats a requested id and a record is acted on once for each: the push holds each
383// requested record once, and the resolver sees each distinct record once.
384#[test]
385fn duplicate_requests_and_records_applied_once() -> Outcome<()> {
386 let oam = res!(OamConfig::new(2, 2));
387 let table = res!(TableConfig::eventual("identity"));
388 let c = res!(DistOzoneConfig::new(node(1), vec![node(2)], oam, vec![table]));
389 let e = res!(DistOzone::with_resolver(c, MemoryStorage::new(), CountCalls { calls: AtomicUsize::new(0) }));
390 res!(put(&e, rid(7), b"y"));
391 res!(put(&e, rid(8), b"z"));
392
393 let r = rec(rid(9), b"r");
394 let q = rec(rid(10), b"q");
395 let env = Envelope::new(node(2), node(1), MsgKind::AntiEntropyReply {
396 table: "identity".to_string(),
397 records: vec![r.clone(), r.clone(), q.clone(), r.clone()],
398 requested_ids: vec![rid(7), rid(7), rid(8), rid(7), rid(8)],
399 bulk: false,
400 after: None,
401 next: None,
402 });
403 let out = res!(e.handle_envelope_at(env, 1_000));
404 assert_eq!(e.resolver().calls.load(Ordering::SeqCst), 2, "the resolver saw a repeated record");
405 assert_eq!(out.persisted.len(), 2, "persisted: {:?}", out.persisted);
406 assert_eq!(res!(stored(&e, rid(9))), Some(b"r".to_vec()));
407 assert_eq!(res!(stored(&e, rid(10))), Some(b"q".to_vec()));
408 assert_eq!(out.outbound.len(), 1);
409 match &out.outbound[0].body {
410 MsgKind::AntiEntropyPush { records, .. } => {
411 assert_eq!(records.len(), 2, "the push repeats a record: {:?}", records);
412 assert_eq!(ids(records), [rid(7), rid(8)].into_iter().collect::<BTreeSet<_>>());
413 },
414 other => panic!("expected an AntiEntropyPush, got {:?}", other),
415 }
416 Ok(())
417}
418
419// In a bulk reply an id the sender also asked for is pushed once, not once for the request and
420// once for the difference.
421#[test]
422fn bulk_push_names_each_record_once() -> Outcome<()> {
423 let (e, _) = res!(pair(256, MemoryStorage::new(), MemoryStorage::new()));
424 res!(put(&e, rid(1), &ver(1, b"a"))); // the sender lacks it, and asks for it
425 res!(put(&e, rid(2), &ver(1, b"c"))); // the sender lacks it
426 res!(put(&e, rid(3), &ver(2, b"b"))); // the sender holds it at an older value
427 res!(put(&e, rid(4), &ver(1, b"d"))); // the sender holds it at the same bytes
428 let env = Envelope::new(node(2), node(1), MsgKind::AntiEntropyReply {
429 table: "identity".to_string(),
430 records: vec![rec(rid(3), &ver(1, b"b")), rec(rid(4), &ver(1, b"d"))],
431 requested_ids: vec![rid(1), rid(1)],
432 bulk: true,
433 after: None,
434 next: None,
435 });
436 let out = res!(e.handle_envelope_at(env, 1_000));
437 assert_eq!(out.outbound.len(), 1);
438 match &out.outbound[0].body {
439 MsgKind::AntiEntropyPush { records, .. } => {
440 assert_eq!(records.len(), 3, "the push repeats or omits a record: {:?}", records);
441 assert_eq!(ids(records), [rid(1), rid(2), rid(3)].into_iter().collect::<BTreeSet<_>>());
442 let kept = records.iter().find(|r| r.id == rid(3)).map(|r| r.value.clone());
443 assert_eq!(kept, Some(ver(2, b"b")), "the push offers the sender's older value");
444 },
445 other => panic!("expected an AntiEntropyPush, got {:?}", other),
446 }
447 Ok(())
448}
449
450// A hand-made sketch that holds one id under two contents asks for that id once.
451#[test]
452fn hostile_sketch_naming_one_id_twice_requests_it_once() -> Outcome<()> {
453 let (_, l) = res!(pair(256, MemoryStorage::new(), MemoryStorage::new()));
454 let mut theirs = res!(Iblt::new(res!(sketch_cfg(256))));
455 for content in [[1u8; 32], [2u8; 32]] {
456 let mut key = rid(5).as_bytes().to_vec();
457 key.extend_from_slice(&content);
458 res!(theirs.insert(&key, &[]));
459 }
460 let mut got = res!(l.handle_envelope_at(digest_envelope(1, 2, theirs.to_bytes()), 1_000));
461 assert_eq!(got.outbound.len(), 1);
462 match got.outbound.remove(0).body {
463 MsgKind::AntiEntropyReply { records, requested_ids, bulk, .. } => {
464 assert!(records.is_empty() && !bulk);
465 assert_eq!(requested_ids, vec![rid(5)], "the same id was asked for twice");
466 },
467 other => panic!("expected an AntiEntropyReply, got {:?}", other),
468 }
469 Ok(())
470}
471
472// The sketch on the wire is the key `id ‖ content` with no value, and a sketch of the old shape
473// (the id as the key, the content as the value) is refused with Mismatch and writes nothing.
474#[test]
475fn old_shape_sketch_is_refused() -> Outcome<()> {
476 let (d, l) = res!(pair(256, MemoryStorage::new(), MemoryStorage::new()));
477 res!(put(&d, rid(1), &ver(1, b"a")));
478 let req = res!(d.build_anti_entropy_request("identity", node(2)));
479 match &req.body {
480 MsgKind::AntiEntropyDigest { sketch, .. } => {
481 let wire = res!(Iblt::from_bytes(sketch)).config();
482 assert_eq!(wire, res!(sketch_cfg(256)), "the sketch on the wire");
483 },
484 other => panic!("expected an AntiEntropyDigest, got {:?}", other),
485 }
486
487 let old_cfg = IbltConfig { key_len: 32, value_len: 32, ..res!(sketch_cfg(256)) };
488 let mut old = res!(Iblt::new(old_cfg));
489 res!(old.insert(rid(2).as_bytes(), &[7u8; 32]));
490 match l.handle_envelope_at(digest_envelope(1, 2, old.to_bytes()), 1_000) {
491 Ok(out) => panic!("an old-shape sketch was accepted: {:?}", out.outbound),
492 Err(e) => assert!(e.tags().contains(&ErrTag::Mismatch), "the refusal does not say Mismatch: {:?}", e),
493 }
494 assert!(res!(table_ids(&l)).is_empty());
495 Ok(())
496}