Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/tests/dist_resolve.rs

47.0 KiB, 11 runs

created by r1870400018:67187, 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//! Integration tests for the resolver seam of the distributed-Ozone engine.
3//!
4//! Every record that reaches an eventual table is offered to a [`Resolver`],
5//! and the engine stores only what the verdict says. The tests drive the four
6//! ways a record arrives (a local put, `ReplicatePut`, an anti-entropy reply
7//! and an anti-entropy push) with small resolvers that refuse, keep, defer,
8//! merge, fail or record, and check what reaches storage, what is sent, and
9//! which of `persisted`, `deferred`, `refused` and `failed` lists each record.
10//!
11//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
12//! Anthropic Claude
13
14use oxedyne_fe2o3_core::prelude::*;
15use oxedyne_fe2o3_o3db_sync::kademlia::id::NodeId;
16use oxedyne_fe2o3_o3db_sync::oam::config::OamConfig;
17use oxedyne_fe2o3_o3db_sync::dist::{
18 cohort,
19 config::{
20 Consistency,
21 DistOzoneConfig,
22 TableConfig,
23 },
24 engine::{
25 DistOzone,
26 InboundOutcome,
27 },
28 peer_set::PeerSet,
29 record::{
30 Record,
31 RecordDigest,
32 RecordId,
33 },
34 resolve::{
35 Convergence,
36 LastVersionWins,
37 ReadView,
38 ResolveCtx,
39 Resolver,
40 Verdict,
41 check_convergence,
42 },
43 storage::{
44 MemoryStorage,
45 Storage,
46 },
47 transport::{
48 Envelope,
49 MsgKind,
50 },
51};
52
53use std::{
54 collections::HashMap,
55 sync::{
56 Arc,
57 Mutex,
58 atomic::{
59 AtomicBool,
60 AtomicU64,
61 AtomicUsize,
62 Ordering,
63 },
64 mpsc,
65 },
66 thread,
67 time::Duration,
68};
69
70
71fn node(b: u8) -> NodeId {
72 let mut bytes = [0u8; 32];
73 bytes[31] = b;
74 NodeId::from_bytes(bytes)
75}
76
77fn rid(b: u8) -> RecordId {
78 let mut bytes = [0u8; 32];
79 bytes[0] = b;
80 RecordId::from_bytes(bytes)
81}
82
83fn s(text: &str) -> String {
84 text.to_string()
85}
86
87fn rec(table: &str, id: RecordId, value: &[u8]) -> Record {
88 Record::new(id, table, value.to_vec())
89}
90
91/// Two peers that both hold everything (replication equals network size), or
92/// one peer that holds nothing (replication 0).
93fn engine<S: Storage, R: Resolver>(
94 local: u8,
95 remote: u8,
96 replication: u64,
97 network_size: u64,
98 storage: S,
99 resolver: R,
100)
101 -> Outcome<DistOzone<S, R>>
102{
103 let oam = res!(OamConfig::new(replication, network_size));
104 let tables = vec![
105 res!(TableConfig::eventual("identity")),
106 res!(TableConfig::eventual("escrow")),
107 ];
108 let cfg = res!(DistOzoneConfig::new(node(local), vec![node(remote)], oam, tables));
109 DistOzone::with_resolver(cfg, storage, resolver)
110}
111
112fn holder<S: Storage, R: Resolver>(
113 local: u8,
114 remote: u8,
115 storage: S,
116 resolver: R,
117)
118 -> Outcome<DistOzone<S, R>>
119{
120 engine(local, remote, 2, 2, storage, resolver)
121}
122
123fn stored<S: Storage, R: Resolver>(
124 e: &DistOzone<S, R>,
125 table: &str,
126 id: RecordId,
127)
128 -> Outcome<Option<Vec<u8>>>
129{
130 Ok(res!(e.storage().get(table, &id)).map(|r| r.value))
131}
132
133fn replicate(from: u8, to: u8, record: Record) -> Envelope {
134 Envelope::new(node(from), node(to), MsgKind::ReplicatePut { record })
135}
136
137fn reply(from: u8, to: u8, table: &str, records: Vec<Record>) -> Envelope {
138 Envelope::new(node(from), node(to), MsgKind::AntiEntropyReply {
139 table: s(table),
140 records,
141 requested_ids: Vec::new(),
142 bulk: false,
143 after: None,
144 next: None,
145 })
146}
147
148fn push(from: u8, to: u8, table: &str, records: Vec<Record>) -> Envelope {
149 Envelope::new(node(from), node(to), MsgKind::AntiEntropyPush {
150 table: s(table),
151 records,
152 })
153}
154
155/// All four lists empty.
156fn nothing_listed(out: &InboundOutcome) -> bool {
157 out.persisted.is_empty()
158 && out.deferred.is_empty()
159 && out.refused.is_empty()
160 && out.failed.is_empty()
161}
162
163/// One full anti-entropy round on one table: the dialler sends its digest, the
164/// listener replies, and the dialler applies the reply and answers any request
165/// with a push. Returns what the dialler's engine made of the reply.
166fn round<S1: Storage, R1: Resolver, S2: Storage, R2: Resolver>(
167 dialler: &DistOzone<S1, R1>,
168 listener: &DistOzone<S2, R2>,
169 listener_id: u8,
170 table: &str,
171 now_ms: u64,
172)
173 -> Outcome<InboundOutcome>
174{
175 let req = res!(dialler.build_anti_entropy_request(table, node(listener_id)));
176 let mut got = res!(listener.handle_envelope_at(req, now_ms));
177 assert_eq!(got.outbound.len(), 1);
178 let answer = got.outbound.remove(0);
179 let mut mine = res!(dialler.handle_envelope_at(answer, now_ms));
180 for p in std::mem::take(&mut mine.outbound) {
181 res!(listener.handle_envelope_at(p, now_ms));
182 }
183 Ok(mine)
184}
185
186
187// ---------------------------------------------------------------------------
188// Test storage and resolvers.
189// ---------------------------------------------------------------------------
190
191/// Counts writes and fails a write or a read of a chosen id on demand.
192struct TestStorage {
193 inner: MemoryStorage,
194 puts: AtomicUsize,
195 fail_put: Mutex<Option<RecordId>>,
196 fail_get: Mutex<Option<RecordId>>,
197}
198
199impl TestStorage {
200 fn new() -> Self {
201 Self {
202 inner: MemoryStorage::new(),
203 puts: AtomicUsize::new(0),
204 fail_put: Mutex::new(None),
205 fail_get: Mutex::new(None),
206 }
207 }
208
209 fn puts(&self) -> usize {
210 self.puts.load(Ordering::SeqCst)
211 }
212
213 fn fail_put_of(&self, id: Option<RecordId>) -> Outcome<()> {
214 *lock_mutex!(self.fail_put) = id;
215 Ok(())
216 }
217
218 fn fail_get_of(&self, id: Option<RecordId>) -> Outcome<()> {
219 *lock_mutex!(self.fail_get) = id;
220 Ok(())
221 }
222}
223
224impl Storage for TestStorage {
225 fn put(&self, record: &Record) -> Outcome<()> {
226 if *lock_mutex!(self.fail_put) == Some(record.id) {
227 return Err(err!("Injected write fault."; IO, Write));
228 }
229 self.puts.fetch_add(1, Ordering::SeqCst);
230 self.inner.put(record)
231 }
232
233 fn get(&self, table: &str, id: &RecordId) -> Outcome<Option<Record>> {
234 if *lock_mutex!(self.fail_get) == Some(*id) {
235 return Err(err!("Injected read fault."; IO, Read));
236 }
237 self.inner.get(table, id)
238 }
239
240 fn delete(&self, table: &str, id: &RecordId) -> Outcome<bool> {
241 self.inner.delete(table, id)
242 }
243
244 fn digests(&self, table: &str) -> Outcome<Vec<RecordDigest>> {
245 self.inner.digests(table)
246 }
247}
248
249/// Refuses a value that begins with "BAD", and takes any other.
250struct RefuseBad;
251
252impl Resolver for RefuseBad {
253 fn resolve<V: ReadView>(
254 &self,
255 _ctx: &ResolveCtx,
256 _view: &V,
257 _table: &str,
258 _id: &RecordId,
259 _held: Option<&[u8]>,
260 incoming: &[u8],
261 )
262 -> Outcome<Verdict>
263 {
264 if incoming.starts_with(b"BAD") {
265 return Ok(Verdict::Refuse(s("marked bad")));
266 }
267 Ok(Verdict::Take(incoming.to_vec()))
268 }
269}
270
271/// Answers the same verdict whatever it is offered.
272struct Fixed(Verdict);
273
274impl Resolver for Fixed {
275 fn resolve<V: ReadView>(
276 &self,
277 _ctx: &ResolveCtx,
278 _view: &V,
279 _table: &str,
280 _id: &RecordId,
281 _held: Option<&[u8]>,
282 _incoming: &[u8],
283 )
284 -> Outcome<Verdict>
285 {
286 Ok(self.0.clone())
287 }
288}
289
290/// Always takes the incoming bytes, even where they equal the held bytes.
291struct TakeIncoming;
292
293impl Resolver for TakeIncoming {
294 fn resolve<V: ReadView>(
295 &self,
296 _ctx: &ResolveCtx,
297 _view: &V,
298 _table: &str,
299 _id: &RecordId,
300 _held: Option<&[u8]>,
301 incoming: &[u8],
302 )
303 -> Outcome<Verdict>
304 {
305 Ok(Verdict::Take(incoming.to_vec()))
306 }
307}
308
309/// A merge: the stored value is held, a plus sign, then the incoming value.
310struct Concat;
311
312impl Resolver for Concat {
313 fn resolve<V: ReadView>(
314 &self,
315 _ctx: &ResolveCtx,
316 _view: &V,
317 _table: &str,
318 _id: &RecordId,
319 held: Option<&[u8]>,
320 incoming: &[u8],
321 )
322 -> Outcome<Verdict>
323 {
324 match held {
325 Some(h) => {
326 let mut merged = h.to_vec();
327 merged.push(b'+');
328 merged.extend_from_slice(incoming);
329 Ok(Verdict::Take(merged))
330 },
331 None => Ok(Verdict::Take(incoming.to_vec())),
332 }
333 }
334}
335
336/// An escrow record names its base (the id's first byte is its own first byte)
337/// and defers until that base is in the identity table.
338struct NeedsBase;
339
340impl Resolver for NeedsBase {
341 fn resolve<V: ReadView>(
342 &self,
343 _ctx: &ResolveCtx,
344 view: &V,
345 table: &str,
346 _id: &RecordId,
347 _held: Option<&[u8]>,
348 incoming: &[u8],
349 )
350 -> Outcome<Verdict>
351 {
352 if table == "escrow" {
353 let base = match incoming.first() {
354 Some(b) => rid(*b),
355 None => return Ok(Verdict::Refuse(s("empty escrow"))),
356 };
357 if res!(view.get("identity", &base)).is_none() {
358 return Ok(Verdict::Defer);
359 }
360 }
361 Ok(Verdict::Take(incoming.to_vec()))
362 }
363}
364
365/// Fails on the value "ERR" while armed, and takes anything else.
366struct Faulty(Arc<AtomicBool>);
367
368impl Resolver for Faulty {
369 fn resolve<V: ReadView>(
370 &self,
371 _ctx: &ResolveCtx,
372 _view: &V,
373 _table: &str,
374 _id: &RecordId,
375 _held: Option<&[u8]>,
376 incoming: &[u8],
377 )
378 -> Outcome<Verdict>
379 {
380 if incoming == b"ERR" && self.0.load(Ordering::SeqCst) {
381 return Err(err!("Injected resolver fault."; Invalid, Input));
382 }
383 Ok(Verdict::Take(incoming.to_vec()))
384 }
385}
386
387/// The first byte of the value picks the verdict: T takes, K keeps, D defers
388/// and R refuses.
389struct ByTag;
390
391impl Resolver for ByTag {
392 fn resolve<V: ReadView>(
393 &self,
394 _ctx: &ResolveCtx,
395 _view: &V,
396 _table: &str,
397 _id: &RecordId,
398 _held: Option<&[u8]>,
399 incoming: &[u8],
400 )
401 -> Outcome<Verdict>
402 {
403 match incoming.first() {
404 Some(b'T') => Ok(Verdict::Take(incoming.to_vec())),
405 Some(b'K') => Ok(Verdict::Keep),
406 Some(b'D') => Ok(Verdict::Defer),
407 _ => Ok(Verdict::Refuse(s("r"))),
408 }
409 }
410}
411
412#[derive(Debug)]
413struct Seen {
414 table: String,
415 id: RecordId,
416 held: Option<Vec<u8>>,
417 incoming: Vec<u8>,
418 now_ms: u64,
419 other: Option<Vec<u8>>, // identity record 200, read through the view
420}
421
422/// Records every call, reads one other record through the view, and takes.
423struct Recorder {
424 seen: Mutex<Vec<Seen>>,
425}
426
427impl Recorder {
428 fn new() -> Self {
429 Self { seen: Mutex::new(Vec::new()) }
430 }
431
432 fn calls(&self) -> Outcome<usize> {
433 Ok(lock_mutex!(self.seen).len())
434 }
435}
436
437impl Resolver for Recorder {
438 fn resolve<V: ReadView>(
439 &self,
440 ctx: &ResolveCtx,
441 view: &V,
442 table: &str,
443 id: &RecordId,
444 held: Option<&[u8]>,
445 incoming: &[u8],
446 )
447 -> Outcome<Verdict>
448 {
449 let other = res!(view.get("identity", &rid(200)));
450 lock_mutex!(self.seen).push(Seen {
451 table: table.to_string(),
452 id: *id,
453 held: held.map(|h| h.to_vec()),
454 incoming: incoming.to_vec(),
455 now_ms: ctx.now_ms,
456 other,
457 });
458 Ok(Verdict::Take(incoming.to_vec()))
459 }
460}
461
462/// A view with nothing in it, for calling a resolver directly.
463struct EmptyView;
464
465impl ReadView for EmptyView {
466 fn get(&self, _table: &str, _id: &RecordId) -> Outcome<Option<Vec<u8>>> {
467 Ok(None)
468 }
469}
470
471
472// ---------------------------------------------------------------------------
473// Verdicts.
474// ---------------------------------------------------------------------------
475
476#[test]
477fn refuse_never_persists() -> Outcome<()> {
478 let id = rid(7);
479 let held = rec("identity", id, b"good");
480 let bad = rec("identity", id, b"BAD value");
481 let refusal = vec![(s("identity"), id, s("marked bad"))];
482
483 // Every inbound path: the record is refused with its reason, the held
484 // bytes stand, and nothing is listed as stored.
485 let paths = [
486 replicate(2, 1, bad.clone()),
487 reply(2, 1, "identity", vec![bad.clone()]),
488 push(2, 1, "identity", vec![bad.clone()]),
489 ];
490 for env in paths {
491 let e = res!(holder(1, 2, MemoryStorage::new(), RefuseBad));
492 res!(e.storage().put(&held));
493 let out = res!(e.handle_envelope_at(env, 1));
494 assert_eq!(out.refused, refusal);
495 assert!(out.persisted.is_empty() && out.deferred.is_empty() && out.failed.is_empty());
496 assert!(out.outbound.is_empty());
497 assert_eq!(res!(stored(&e, "identity", id)), Some(b"good".to_vec()));
498 }
499
500 // A local put: the verdict comes back, nothing is stored or sent.
501 let e = res!(holder(1, 2, MemoryStorage::new(), RefuseBad));
502 res!(e.storage().put(&held));
503 let out = res!(e.put_at(bad, 1));
504 assert_eq!(out.verdict, Some(Verdict::Refuse(s("marked bad"))));
505 assert!(!out.local_persisted);
506 assert!(out.outbound.is_empty());
507 assert_eq!(res!(stored(&e, "identity", id)), Some(b"good".to_vec()));
508 Ok(())
509}
510
511#[test]
512fn keep_leaves_held_bytes() -> Outcome<()> {
513 let id = rid(7);
514 let held = rec("identity", id, b"X");
515 let other = rec("identity", id, b"Y");
516
517 let e = res!(holder(1, 2, MemoryStorage::new(), Fixed(Verdict::Keep)));
518 res!(e.storage().put(&held));
519 let out = res!(e.handle_envelope_at(replicate(2, 1, other.clone()), 1));
520 assert!(nothing_listed(&out));
521 assert!(out.outbound.is_empty());
522 assert_eq!(res!(stored(&e, "identity", id)), Some(b"X".to_vec()));
523
524 // A local put sends nothing, though a remote holder exists.
525 let out = res!(e.put_at(other, 1));
526 assert_eq!(out.verdict, Some(Verdict::Keep));
527 assert!(!out.local_persisted);
528 assert!(out.outbound.is_empty());
529 assert_eq!(res!(stored(&e, "identity", id)), Some(b"X".to_vec()));
530 Ok(())
531}
532
533#[test]
534fn take_stores_resolver_bytes() -> Outcome<()> {
535 let id = rid(7);
536 let held = rec("identity", id, b"A");
537 let incoming = rec("identity", id, b"B");
538
539 // Inbound: the merge is stored, not the incoming bytes.
540 let e = res!(holder(1, 2, MemoryStorage::new(), Concat));
541 res!(e.storage().put(&held));
542 let out = res!(e.handle_envelope_at(replicate(2, 1, incoming.clone()), 1));
543 assert_eq!(out.persisted, vec![(s("identity"), id)]);
544 assert_eq!(res!(stored(&e, "identity", id)), Some(b"A+B".to_vec()));
545
546 // Local: the merge is stored, and the remote holder is sent the merge.
547 let e = res!(holder(1, 2, MemoryStorage::new(), Concat));
548 res!(e.storage().put(&held));
549 let out = res!(e.put_at(incoming, 1));
550 assert_eq!(out.verdict, Some(Verdict::Take(b"A+B".to_vec())));
551 assert!(out.local_persisted);
552 assert_eq!(res!(stored(&e, "identity", id)), Some(b"A+B".to_vec()));
553 assert_eq!(out.outbound.len(), 1);
554 match &out.outbound[0].body {
555 MsgKind::ReplicatePut { record } => {
556 assert_eq!(record.value, b"A+B".to_vec());
557 assert_eq!(record.id, id);
558 assert_eq!(record.table, "identity");
559 },
560 other => panic!("Expected a ReplicatePut, got {:?}.", other),
561 }
562 assert_eq!(out.outbound[0].to, node(2));
563 Ok(())
564}
565
566#[test]
567fn take_of_held_is_keep() -> Outcome<()> {
568 let id = rid(7);
569 let held = rec("identity", id, b"X");
570
571 let e = res!(holder(1, 2, TestStorage::new(), TakeIncoming));
572 res!(e.storage().put(&held));
573 let base = e.storage().puts();
574
575 // The same bytes again: no write, nothing listed, nothing sent.
576 let out = res!(e.handle_envelope_at(replicate(2, 1, held.clone()), 1));
577 assert!(nothing_listed(&out));
578 assert!(out.outbound.is_empty());
579 assert_eq!(e.storage().puts(), base);
580 let out = res!(e.put_at(held, 1));
581 assert_eq!(out.verdict, Some(Verdict::Keep));
582 assert!(!out.local_persisted);
583 assert!(out.outbound.is_empty());
584 assert_eq!(e.storage().puts(), base);
585
586 // Control: other bytes are a real Take, so the counter does move.
587 let out = res!(e.handle_envelope_at(replicate(2, 1, rec("identity", id, b"Y")), 1));
588 assert_eq!(out.persisted, vec![(s("identity"), id)]);
589 assert_eq!(e.storage().puts(), base + 1);
590 Ok(())
591}
592
593#[test]
594fn defer_retried_by_next_round() -> Outcome<()> {
595 let base_id = rid(1);
596 let dep_id = rid(9);
597 let a = res!(holder(1, 2, MemoryStorage::new(), NeedsBase));
598 let b = res!(holder(2, 1, MemoryStorage::new(), NeedsBase));
599 res!(a.storage().put(&rec("identity", base_id, b"base")));
600 res!(a.storage().put(&rec("escrow", dep_id, &[1, b'd'])));
601
602 // The dependency is missing, so the record is deferred and not stored, and
603 // the next round offers it again with the same result.
604 for _ in 0..2 {
605 let out = res!(round(&b, &a, 1, "escrow", 1));
606 assert_eq!(out.deferred, vec![(s("escrow"), dep_id)]);
607 assert!(out.persisted.is_empty() && out.refused.is_empty() && out.failed.is_empty());
608 assert_eq!(res!(stored(&b, "escrow", dep_id)), None);
609 }
610
611 // The base arrives; the next escrow round stores the record.
612 let out = res!(round(&b, &a, 1, "identity", 2));
613 assert_eq!(out.persisted, vec![(s("identity"), base_id)]);
614 let out = res!(round(&b, &a, 1, "escrow", 3));
615 assert_eq!(out.persisted, vec![(s("escrow"), dep_id)]);
616 assert!(out.deferred.is_empty());
617 assert_eq!(res!(stored(&b, "escrow", dep_id)), Some(vec![1, b'd']));
618 Ok(())
619}
620
621#[test]
622fn resolve_err_is_failed_not_refused() -> Outcome<()> {
623 let (id1, id2, id3) = (rid(1), rid(2), rid(3));
624 let armed = Arc::new(AtomicBool::new(true));
625 let b = res!(holder(2, 1, TestStorage::new(), Faulty(armed.clone())));
626 let a = res!(holder(1, 2, MemoryStorage::new(), Faulty(Arc::new(AtomicBool::new(false)))));
627 for (id, v) in [(id1, &b"one"[..]), (id2, b"ERR"), (id3, b"three")] {
628 res!(a.storage().put(&rec("identity", id, v)));
629 }
630
631 // One record of three fails in resolve. It is failed, not refused, and not
632 // stored; the other two are applied.
633 let out = res!(b.handle_envelope_at(push(1, 2, "identity", vec![
634 rec("identity", id1, b"one"),
635 rec("identity", id2, b"ERR"),
636 rec("identity", id3, b"three"),
637 ]), 1));
638 assert_eq!(out.failed.len(), 1);
639 assert_eq!((out.failed[0].0.as_str(), out.failed[0].1), ("identity", id2));
640 assert!(out.refused.is_empty() && out.deferred.is_empty());
641 assert_eq!(out.persisted, vec![(s("identity"), id1), (s("identity"), id3)]);
642 assert_eq!(res!(stored(&b, "identity", id2)), None);
643 assert_eq!(res!(stored(&b, "identity", id3)), Some(b"three".to_vec()));
644
645 // A local put returns the Err.
646 assert!(b.put_at(rec("identity", id2, b"ERR"), 1).is_err());
647
648 // A failed read of the held value is also a per-record failure.
649 let id4 = rid(4);
650 res!(b.storage().fail_get_of(Some(id4)));
651 let out = res!(b.handle_envelope_at(push(1, 2, "identity", vec![
652 rec("identity", id4, b"four"),
653 rec("identity", rid(5), b"five"),
654 ]), 1));
655 assert_eq!(out.failed.len(), 1);
656 assert_eq!(out.failed[0].1, id4);
657 assert_eq!(out.persisted, vec![(s("identity"), rid(5))]);
658 res!(b.storage().fail_get_of(None));
659
660 // With the fault cleared the record is offered again and stored.
661 armed.store(false, Ordering::SeqCst);
662 let out = res!(round(&b, &a, 1, "identity", 2));
663 assert_eq!(out.persisted, vec![(s("identity"), id2)]);
664 assert!(out.failed.is_empty());
665 assert_eq!(res!(stored(&b, "identity", id2)), Some(b"ERR".to_vec()));
666 Ok(())
667}
668
669#[test]
670fn persisted_lists_exactly_stored() -> Outcome<()> {
671 let (t1, t2, k, d, r, t3) = (rid(1), rid(2), rid(3), rid(4), rid(5), rid(6));
672 let records = vec![
673 rec("identity", t1, b"T1"),
674 rec("identity", t2, b"T2"),
675 rec("identity", k, b"K-new"),
676 rec("identity", d, b"D"),
677 rec("identity", r, b"R"),
678 rec("identity", t3, b"T3"),
679 ];
680 for kind in 0..2 {
681 let e = res!(holder(1, 2, TestStorage::new(), ByTag));
682 res!(e.storage().put(&rec("identity", k, b"K-old")));
683 // t3 is a Take whose write fails: it is failed, never persisted.
684 res!(e.storage().fail_put_of(Some(t3)));
685 let env = if kind == 0 {
686 reply(2, 1, "identity", records.clone())
687 } else {
688 push(2, 1, "identity", records.clone())
689 };
690 let out = res!(e.handle_envelope_at(env, 1));
691
692 assert_eq!(out.persisted, vec![(s("identity"), t1), (s("identity"), t2)]);
693 assert_eq!(out.deferred, vec![(s("identity"), d)]);
694 assert_eq!(out.refused, vec![(s("identity"), r, s("r"))]);
695 assert_eq!(out.failed.len(), 1);
696 assert_eq!(out.failed[0].1, t3);
697
698 // Each of the five listed records is in one list only, and the Keep is in none.
699 let mut listed: Vec<RecordId> = out.persisted.iter().map(|x| x.1).collect();
700 listed.extend(out.deferred.iter().map(|x| x.1));
701 listed.extend(out.refused.iter().map(|x| x.1));
702 listed.extend(out.failed.iter().map(|x| x.1));
703 listed.sort();
704 let before = listed.len();
705 listed.dedup();
706 assert_eq!(before, 5);
707 assert_eq!(listed.len(), 5);
708 assert!(!listed.contains(&k));
709
710 // Storage agrees with the lists.
711 assert_eq!(res!(stored(&e, "identity", t1)), Some(b"T1".to_vec()));
712 assert_eq!(res!(stored(&e, "identity", t2)), Some(b"T2".to_vec()));
713 assert_eq!(res!(stored(&e, "identity", k)), Some(b"K-old".to_vec()));
714 for id in [d, r, t3] {
715 assert_eq!(res!(stored(&e, "identity", id)), None);
716 }
717 }
718 Ok(())
719}
720
721#[test]
722fn resolver_sees_held_and_view() -> Outcome<()> {
723 let e = res!(holder(1, 2, MemoryStorage::new(), Recorder::new()));
724 res!(e.storage().put(&rec("identity", rid(200), b"BASE")));
725 res!(e.storage().put(&rec("escrow", rid(5), b"H1")));
726
727 // A local put at a given time: the stored held value, the time and the view.
728 res!(e.put_at(rec("escrow", rid(5), b"N1"), 1234));
729 // A first arrival is validated too, with no held value.
730 res!(e.handle_envelope_at(replicate(2, 1, rec("escrow", rid(6), b"N2")), 99));
731 // A reply sees the value the put left.
732 res!(e.handle_envelope_at(reply(2, 1, "escrow", vec![rec("escrow", rid(5), b"N3")]), 100));
733
734 let seen = lock_mutex!(e.resolver().seen);
735 assert_eq!(seen.len(), 3);
736 assert_eq!(seen[0].table, "escrow");
737 assert_eq!(seen[0].id, rid(5));
738 assert_eq!(seen[0].held, Some(b"H1".to_vec()));
739 assert_eq!(seen[0].incoming, b"N1".to_vec());
740 assert_eq!(seen[0].now_ms, 1234);
741 assert_eq!(seen[0].other, Some(b"BASE".to_vec()));
742 assert_eq!(seen[1].held, None);
743 assert_eq!(seen[1].now_ms, 99);
744 assert_eq!(seen[1].other, Some(b"BASE".to_vec()));
745 assert_eq!(seen[2].held, Some(b"N1".to_vec()));
746 assert_eq!(seen[2].now_ms, 100);
747 Ok(())
748}
749
750#[test]
751fn not_holder_skips_resolver() -> Outcome<()> {
752 let r = rec("identity", rid(3), b"v");
753
754 // Replication 0: this peer holds nothing, so no path may call the resolver.
755 let e = res!(engine(1, 2, 0, 10, MemoryStorage::new(), Recorder::new()));
756 let out = res!(e.handle_envelope_at(replicate(2, 1, r.clone()), 1));
757 assert!(nothing_listed(&out));
758 let out = res!(e.handle_envelope_at(reply(2, 1, "identity", vec![r.clone()]), 1));
759 assert!(nothing_listed(&out));
760 let out = res!(e.handle_envelope_at(push(2, 1, "identity", vec![r.clone()]), 1));
761 assert!(nothing_listed(&out));
762 let out = res!(e.put_at(r.clone(), 1));
763 assert_eq!(out.verdict, None);
764 assert!(!out.local_persisted);
765 assert_eq!(res!(e.resolver().calls()), 0);
766 assert_eq!(res!(e.storage().len()), 0);
767
768 // Control: a holder calls it on each of the four paths.
769 let e = res!(holder(1, 2, MemoryStorage::new(), Recorder::new()));
770 res!(e.handle_envelope_at(replicate(2, 1, r.clone()), 1));
771 res!(e.handle_envelope_at(reply(2, 1, "identity", vec![r.clone()]), 1));
772 res!(e.handle_envelope_at(push(2, 1, "identity", vec![r.clone()]), 1));
773 res!(e.put_at(r, 1));
774 assert_eq!(res!(e.resolver().calls()), 4);
775 Ok(())
776}
777
778
779// ---------------------------------------------------------------------------
780// The default resolver.
781// ---------------------------------------------------------------------------
782
783#[test]
784fn last_version_wins_lattice() -> Outcome<()> {
785 // The value layout is a big-endian u64 version, then the payload.
786 let v = LastVersionWins::value(0x0102_0304_0506_0708, b"pay");
787 assert_eq!(&v[..8], &[1, 2, 3, 4, 5, 6, 7, 8]);
788 assert_eq!(&v[8..], b"pay");
789 assert_eq!(LastVersionWins::version(&v), Some(0x0102_0304_0506_0708));
790 assert_eq!(LastVersionWins::version(&LastVersionWins::value(0, b"")), Some(0));
791 assert_eq!(LastVersionWins::version(&v[..7]), None);
792 assert_eq!(LastVersionWins::version(&[]), None);
793 // A later version beats an earlier one whatever the payloads are.
794 assert!(LastVersionWins::value(2, b"a") > LastVersionWins::value(1, b"zzz"));
795
796 // Held and incoming, straight from the resolver.
797 let ctx = ResolveCtx::at(0);
798 let lo = LastVersionWins::value(1, b"a");
799 let hi = LastVersionWins::value(2, b"a");
800 let id = rid(1);
801 assert_eq!(
802 res!(LastVersionWins.resolve(&ctx, &EmptyView, "identity", &id, None, &lo)),
803 Verdict::Take(lo.clone()),
804 );
805 assert_eq!(
806 res!(LastVersionWins.resolve(&ctx, &EmptyView, "identity", &id, Some(&lo), &hi)),
807 Verdict::Take(hi.clone()),
808 );
809 assert_eq!(
810 res!(LastVersionWins.resolve(&ctx, &EmptyView, "identity", &id, Some(&hi), &lo)),
811 Verdict::Keep,
812 );
813 assert_eq!(
814 res!(LastVersionWins.resolve(&ctx, &EmptyView, "identity", &id, Some(&hi), &hi)),
815 Verdict::Keep,
816 );
817
818 // Through the engine, over all ordered pairs of six values, including the
819 // empty value and one too short to carry a version: the stored result is
820 // the greater of the two whatever the order, and a repeat changes nothing.
821 let values: Vec<Vec<u8>> = vec![
822 LastVersionWins::value(1, b"a"),
823 LastVersionWins::value(1, b"b"),
824 LastVersionWins::value(2, b""),
825 LastVersionWins::value(2, b"a"),
826 Vec::new(),
827 b"short".to_vec(),
828 ];
829 let settle = |first: &[u8], second: &[u8]| -> Outcome<Vec<u8>> {
830 let e = res!(DistOzone::new(
831 res!(DistOzoneConfig::new(
832 node(1),
833 Vec::new(),
834 res!(OamConfig::new(1, 1)),
835 vec![res!(TableConfig::eventual("identity"))],
836 )),
837 MemoryStorage::new(),
838 ));
839 res!(e.put_at(rec("identity", rid(1), first), 0));
840 res!(e.put_at(rec("identity", rid(1), second), 0));
841 res!(e.put_at(rec("identity", rid(1), first), 0));
842 match res!(stored(&e, "identity", rid(1))) {
843 Some(v) => Ok(v),
844 None => Err(err!("Nothing stored for the pair."; Missing)),
845 }
846 };
847 for x in &values {
848 for y in &values {
849 let xy = res!(settle(x, y));
850 let yx = res!(settle(y, x));
851 assert_eq!(xy, yx);
852 assert_eq!(&xy, std::cmp::max(x, y));
853 }
854 }
855 Ok(())
856}
857
858
859// ---------------------------------------------------------------------------
860// R2: atomicity, and the convergence helper.
861// ---------------------------------------------------------------------------
862
863/// A set of bytes, kept sorted and without repeats. A commutative merge.
864fn union(held: Option<&[u8]>, incoming: &[u8]) -> Vec<u8> {
865 let mut set = held.unwrap_or(&[]).to_vec();
866 set.extend_from_slice(incoming);
867 set.sort();
868 set.dedup();
869 set
870}
871
872/// The set union, optionally giving other threads the processor between the
873/// engine's read of the held value and its write of the merge.
874struct Union {
875 pause: bool,
876}
877
878impl Resolver for Union {
879 fn resolve<V: ReadView>(
880 &self,
881 _ctx: &ResolveCtx,
882 _view: &V,
883 _table: &str,
884 _id: &RecordId,
885 held: Option<&[u8]>,
886 incoming: &[u8],
887 )
888 -> Outcome<Verdict>
889 {
890 let merged = union(held, incoming);
891 if self.pause {
892 thread::yield_now();
893 thread::sleep(Duration::from_micros(100));
894 }
895 Ok(Verdict::Take(merged))
896 }
897}
898
899/// The first value to arrive stands. Not commutative: peers that were first
900/// given different values keep them.
901struct FirstWins;
902
903impl Resolver for FirstWins {
904 fn resolve<V: ReadView>(
905 &self,
906 _ctx: &ResolveCtx,
907 _view: &V,
908 _table: &str,
909 _id: &RecordId,
910 held: Option<&[u8]>,
911 incoming: &[u8],
912 )
913 -> Outcome<Verdict>
914 {
915 match held {
916 Some(_) => Ok(Verdict::Keep),
917 None => Ok(Verdict::Take(incoming.to_vec())),
918 }
919 }
920}
921
922/// Takes a value no peer has held before, whatever it is offered, so no round
923/// ever stores nothing.
924struct NeverSettles(Arc<AtomicU64>);
925
926impl Resolver for NeverSettles {
927 fn resolve<V: ReadView>(
928 &self,
929 _ctx: &ResolveCtx,
930 _view: &V,
931 _table: &str,
932 _id: &RecordId,
933 _held: Option<&[u8]>,
934 _incoming: &[u8],
935 )
936 -> Outcome<Verdict>
937 {
938 Ok(Verdict::Take(self.0.fetch_add(1, Ordering::SeqCst).to_be_bytes().to_vec()))
939 }
940}
941
942/// Two records may claim one token, a (token, time) pair of bytes, and the
943/// later claim loses it. The held and incoming claims are merged, then any
944/// claim an earlier claim on another record contradicts is dropped, the other
945/// record being confirmed by a point read.
946struct ClaimRule;
947
948const CLAIMANTS: [u8; 3] = [1, 2, 3];
949
950impl Resolver for ClaimRule {
951 fn resolve<V: ReadView>(
952 &self,
953 _ctx: &ResolveCtx,
954 view: &V,
955 table: &str,
956 id: &RecordId,
957 held: Option<&[u8]>,
958 incoming: &[u8],
959 )
960 -> Outcome<Verdict>
961 {
962 // Claims are pairs, so merge them as pairs.
963 let mut claims: Vec<[u8; 2]> = Vec::new();
964 for bytes in [held.unwrap_or(&[]), incoming] {
965 for pair in bytes.chunks_exact(2) {
966 claims.push([pair[0], pair[1]]);
967 }
968 }
969 claims.sort();
970 claims.dedup();
971 let mut kept = Vec::new();
972 for claim in claims {
973 let mut lost = false;
974 for other in CLAIMANTS {
975 if rid(other) == *id {
976 continue;
977 }
978 if let Some(v) = res!(view.get(table, &rid(other))) {
979 for theirs in v.chunks_exact(2) {
980 // The earlier claim, by (time, record), keeps the token.
981 if theirs[0] == claim[0] && (theirs[1], rid(other)) < (claim[1], *id) {
982 lost = true;
983 }
984 }
985 }
986 }
987 if !lost {
988 kept.extend_from_slice(&claim);
989 }
990 }
991 Ok(Verdict::Take(kept))
992 }
993}
994
995fn converge(seeds: std::ops::Range<u64>, max_rounds: usize) -> Convergence {
996 Convergence::new(3, seeds, 0, max_rounds)
997}
998
999/// The text of an error, with the seed it names.
1000fn failure_text(r: Outcome<()>) -> String {
1001 match r {
1002 Ok(()) => String::new(),
1003 Err(e) => fmt!("{}", e),
1004 }
1005}
1006
1007#[test]
1008fn resolve_and_persist_atomic() -> Outcome<()> {
1009 // Four threads each make 50 puts on one key, alternating a local put and an
1010 // inbound ReplicatePut, with a resolver that gives the processor away
1011 // between reading the held value and returning the merge. Every element is
1012 // distinct, so a lost update leaves the final set short of 200.
1013 let e = res!(holder(1, 2, MemoryStorage::new(), Union { pause: true }));
1014 let all = thread::scope(|sc| -> Outcome<()> {
1015 let mut workers = Vec::new();
1016 for t in 0..4u8 {
1017 let e = &e;
1018 workers.push(sc.spawn(move || -> Outcome<()> {
1019 for k in 0..50u8 {
1020 let record = rec("identity", rid(1), &[t * 50 + k]);
1021 if k % 2 == 0 {
1022 res!(e.put_at(record, 0));
1023 } else {
1024 res!(e.handle_envelope_at(replicate(2, 1, record), 0));
1025 }
1026 }
1027 Ok(())
1028 }));
1029 }
1030 for w in workers {
1031 match w.join() {
1032 Ok(r) => res!(r),
1033 Err(_) => return Err(err!("A worker thread panicked."; Test, Thread)),
1034 }
1035 }
1036 Ok(())
1037 });
1038 res!(all);
1039 let want: Vec<u8> = (0..200u8).collect();
1040 assert_eq!(res!(stored(&e, "identity", rid(1))), Some(want));
1041 Ok(())
1042}
1043
1044#[test]
1045fn non_commutative_fails_convergence() -> Outcome<()> {
1046 let records = vec![
1047 rec("identity", rid(1), b"x"),
1048 rec("identity", rid(1), b"y"),
1049 rec("identity", rid(1), b"z"),
1050 rec("identity", rid(2), b"p"),
1051 ];
1052 let cfg = converge(0..32, 16);
1053 // Last arrival wins: the peers pass values to each other and the final value
1054 // follows the order of the exchanges, so it never settles on one answer.
1055 let last = check_convergence(&cfg, &["identity"], &records, |_| TakeIncoming, |_, _, _| Ok(Vec::new()));
1056 assert!(last.is_err(), "last-arrival-wins passed the convergence check");
1057 // First arrival wins: the peers settle at once, on different values.
1058 let first = failure_text(check_convergence(
1059 &cfg, &["identity"], &records, |_| FirstWins, |_, _, _| Ok(Vec::new()),
1060 ));
1061 assert!(first.contains("differs from peer 0"), "first-arrival-wins: {:?}", first);
1062 assert!(first.contains("seed"), "no seed named: {:?}", first);
1063 let id1: String = rid(1).as_bytes().iter().map(|b| fmt!("{:02x}", b)).collect();
1064 assert!(first.contains(&id1), "the differing id was not named: {:?}", first);
1065 Ok(())
1066}
1067
1068#[test]
1069fn commutative_passes_convergence() -> Outcome<()> {
1070 let records = vec![
1071 rec("identity", rid(1), &[1]),
1072 rec("identity", rid(1), &[2]),
1073 rec("identity", rid(1), &[3, 9]),
1074 rec("identity", rid(2), &[4]),
1075 rec("escrow", rid(1), &[5]),
1076 rec("escrow", rid(1), &[6]),
1077 ];
1078 let cfg = converge(0..32, 16);
1079 let tables = ["identity", "escrow"];
1080 let calls = AtomicUsize::new(0);
1081 res!(check_convergence(
1082 &cfg, &tables, &records, |_| Union { pause: false },
1083 |_, _, _| {
1084 calls.fetch_add(1, Ordering::SeqCst);
1085 Ok(Vec::new())
1086 },
1087 ));
1088 // The helper ran: every seed stores at least the three keys on some peer.
1089 assert!(calls.load(Ordering::SeqCst) >= 32 * 3, "after ran {} times", calls.load(Ordering::SeqCst));
1090
1091 let versioned = vec![
1092 rec("identity", rid(1), &LastVersionWins::value(1, b"a")),
1093 rec("identity", rid(1), &LastVersionWins::value(3, b"b")),
1094 rec("identity", rid(1), &LastVersionWins::value(2, b"c")),
1095 rec("identity", rid(2), &LastVersionWins::value(7, b"d")),
1096 rec("escrow", rid(1), &LastVersionWins::value(4, b"e")),
1097 ];
1098 res!(check_convergence(&cfg, &tables, &versioned, |_| LastVersionWins, |_, _, _| Ok(Vec::new())));
1099 Ok(())
1100}
1101
1102#[test]
1103fn cross_key_needs_after_hook() -> Outcome<()> {
1104 // Records 1 and 2 both claim the token 'o'; record 1's claim is earlier. Where
1105 // record 2 arrives first, it keeps the claim, and nothing offers it to the
1106 // resolver again when record 1 turns up.
1107 let records = vec![
1108 rec("identity", rid(1), &[b'o', 1]),
1109 rec("identity", rid(2), &[b'o', 2]),
1110 rec("identity", rid(3), &[b'q', 3]),
1111 ];
1112 let cfg = converge(0..32, 16);
1113 let without = failure_text(check_convergence(
1114 &cfg, &["identity"], &records, |_| ClaimRule, |_, _, _| Ok(Vec::new()),
1115 ));
1116 assert!(without.contains("differ"), "no divergence without the pass: {:?}", without);
1117
1118 // The caller's pass: whenever a peer stores a record, offer it the current
1119 // bytes of the other claimants, so the rule runs again with the new record in view.
1120 let pass = |_peer: usize, e: &DistOzone<MemoryStorage, ClaimRule>, persisted: &[(String, RecordId)]| {
1121 let mut puts = Vec::new();
1122 for (table, id) in persisted {
1123 for other in CLAIMANTS {
1124 if rid(other) != *id {
1125 if let Some(r) = res!(e.storage().get(table, &rid(other))) {
1126 puts.push(r);
1127 }
1128 }
1129 }
1130 }
1131 Ok(puts)
1132 };
1133 res!(check_convergence(&cfg, &["identity"], &records, |_| ClaimRule, pass));
1134 Ok(())
1135}
1136
1137#[test]
1138fn convergence_bounded() -> Outcome<()> {
1139 // A resolver that always takes a new value never lets a round store nothing.
1140 // The check must report that, not run for ever: it runs on its own thread, so
1141 // that a hang fails this test rather than stopping it.
1142 let (tx, rx) = mpsc::channel();
1143 thread::spawn(move || {
1144 let counter = Arc::new(AtomicU64::new(0));
1145 let records = vec![
1146 rec("identity", rid(1), b"x"),
1147 rec("identity", rid(1), b"y"),
1148 ];
1149 let cfg = converge(0..4, 6);
1150 let r = check_convergence(
1151 &cfg,
1152 &["identity"],
1153 &records,
1154 |_| NeverSettles(counter.clone()),
1155 |_, _, _| Ok(Vec::new()),
1156 );
1157 let first = failure_text(r);
1158
1159 // The same bound holds for a post-write pass that stores something new
1160 // each time it runs.
1161 let r = check_convergence(
1162 &converge(0..1, 4),
1163 &["identity"],
1164 &records,
1165 |_| NeverSettles(counter.clone()),
1166 |_, _, _| Ok(vec![rec("identity", rid(9), b"again")]),
1167 );
1168 let _ = tx.send((first, failure_text(r)));
1169 });
1170 let (text, deep) = match rx.recv_timeout(Duration::from_secs(20)) {
1171 Ok(texts) => texts,
1172 Err(_) => return Err(err!("check_convergence did not return within 20 s."; Test, Timeout)),
1173 };
1174 assert!(text.contains("did not quiesce"), "{:?}", text);
1175 assert!(text.contains("seed 0"), "{:?}", text);
1176 assert!(deep.contains("did not quiesce") && deep.contains("post-write"), "{:?}", deep);
1177 Ok(())
1178}
1179
1180
1181// ---------------------------------------------------------------------------
1182// Post-QA fixes (2026-10-05): cohort tables, a poisoned lock, one listing per
1183// record, a failed Decide store, byte comparison and a missing dependency.
1184// ---------------------------------------------------------------------------
1185
1186/// A holder that also has a cohort table, "ledger", beside the eventual ones.
1187fn with_ledger<S: Storage, R: Resolver>(storage: S, resolver: R) -> Outcome<DistOzone<S, R>> {
1188 let oam = res!(OamConfig::new(2, 2));
1189 let tables = vec![
1190 res!(TableConfig::eventual("identity")),
1191 res!(TableConfig::eventual("escrow")),
1192 res!(TableConfig::cohort_default("ledger")),
1193 ];
1194 let cfg = res!(DistOzoneConfig::new(node(1), vec![node(2)], oam, tables));
1195 DistOzone::with_resolver(cfg, storage, resolver)
1196}
1197
1198#[test]
1199fn cohort_table_refuses_replicate_put() -> Outcome<()> {
1200 let e = res!(with_ledger(MemoryStorage::new(), LastVersionWins));
1201 // Stand in for a value a HotStuff Decide stored.
1202 res!(e.storage().put(&rec("ledger", rid(7), b"\x01decided")));
1203 let out = res!(e.handle_envelope_at(replicate(2, 1, rec("ledger", rid(7), b"\x09forged")), 0));
1204 assert_eq!(res!(stored(&e, "ledger", rid(7))), Some(b"\x01decided".to_vec()),
1205 "a ReplicatePut overwrote a cohort table's decided value; persisted={:?}", out.persisted);
1206 assert!(out.persisted.is_empty());
1207 assert_eq!(out.failed.len(), 1, "the refused record is in failed");
1208 assert_eq!((out.failed[0].0.as_str(), out.failed[0].1), ("ledger", rid(7)));
1209 Ok(())
1210}
1211
1212#[test]
1213fn cohort_table_refuses_anti_entropy_push() -> Outcome<()> {
1214 let e = res!(with_ledger(TestStorage::new(), LastVersionWins));
1215 let out = res!(e.handle_envelope_at(
1216 push(2, 1, "ledger", vec![rec("ledger", rid(8), b"undecided")]), 0));
1217 assert_eq!(res!(stored(&e, "ledger", rid(8))), None,
1218 "an AntiEntropyPush stored a never-decided record in a cohort table; persisted={:?}", out.persisted);
1219 assert!(out.persisted.is_empty());
1220 assert_eq!(out.failed.len(), 1, "the refused record is in failed");
1221 // An anti-entropy reply is the same door.
1222 let out = res!(e.handle_envelope_at(
1223 reply(2, 1, "ledger", vec![rec("ledger", rid(9), b"undecided")]), 0));
1224 assert_eq!(res!(stored(&e, "ledger", rid(9))), None);
1225 assert_eq!(out.failed.len(), 1);
1226 assert_eq!(e.storage().puts(), 0);
1227 Ok(())
1228}
1229
1230/// Panics on a value that begins with "PANIC", and takes any other.
1231struct Panicky;
1232
1233impl Resolver for Panicky {
1234 fn resolve<V: ReadView>(
1235 &self,
1236 _ctx: &ResolveCtx,
1237 _view: &V,
1238 _table: &str,
1239 _id: &RecordId,
1240 _held: Option<&[u8]>,
1241 incoming: &[u8],
1242 )
1243 -> Outcome<Verdict>
1244 {
1245 if incoming.starts_with(b"PANIC") {
1246 panic!("resolver bug on one malformed record");
1247 }
1248 Ok(Verdict::Take(incoming.to_vec()))
1249 }
1250}
1251
1252#[test]
1253fn resolver_panic_does_not_wedge_engine() -> Outcome<()> {
1254 let e = res!(holder(1, 2, MemoryStorage::new(), Panicky));
1255 let hit = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
1256 e.handle_envelope_at(replicate(2, 1, rec("identity", rid(1), b"PANIC")), 0)
1257 }));
1258 assert!(hit.is_err(), "the resolver was meant to panic");
1259 // A different, well-formed record afterwards, by each door.
1260 let later = e.put_at(rec("identity", rid(2), b"fine"), 0);
1261 assert!(later.is_ok(), "a put after one resolver panic failed: {:?}", later.err());
1262 let inbound = res!(e.handle_envelope_at(replicate(2, 1, rec("identity", rid(3), b"fine")), 0));
1263 assert!(inbound.failed.is_empty(), "inbound after one resolver panic failed: {:?}", inbound.failed);
1264 assert_eq!(inbound.persisted, vec![(s("identity"), rid(3))]);
1265 assert_eq!(res!(stored(&e, "identity", rid(1))), None);
1266 Ok(())
1267}
1268
1269/// Reads of an id fail once that id has been written.
1270struct ReadFailsAfterPut {
1271 inner: MemoryStorage,
1272 armed: Mutex<Vec<RecordId>>,
1273}
1274
1275impl Storage for ReadFailsAfterPut {
1276 fn put(&self, record: &Record) -> Outcome<()> {
1277 lock_mutex!(self.armed).push(record.id);
1278 self.inner.put(record)
1279 }
1280
1281 fn get(&self, table: &str, id: &RecordId) -> Outcome<Option<Record>> {
1282 if lock_mutex!(self.armed).contains(id) {
1283 return Err(err!("Injected read fault."; IO, Read));
1284 }
1285 self.inner.get(table, id)
1286 }
1287
1288 fn delete(&self, table: &str, id: &RecordId) -> Outcome<bool> {
1289 self.inner.delete(table, id)
1290 }
1291
1292 fn digests(&self, table: &str) -> Outcome<Vec<RecordDigest>> {
1293 self.inner.digests(table)
1294 }
1295}
1296
1297#[test]
1298fn reply_lists_each_record_at_most_once() -> Outcome<()> {
1299 let st = ReadFailsAfterPut { inner: MemoryStorage::new(), armed: Mutex::new(Vec::new()) };
1300 let e = res!(holder(1, 2, st, LastVersionWins));
1301 // An id whose content differs on the two sides is in both halves of a
1302 // decode, so it arrives in `records` and is also requested back.
1303 let out = res!(e.handle_envelope_at(
1304 reply_asking(2, 1, "identity", vec![rec("identity", rid(4), b"v")], vec![rid(4)]),
1305 0,
1306 ));
1307 assert_eq!(out.persisted, vec![(s("identity"), rid(4))]);
1308 assert!(out.failed.is_empty(),
1309 "a local read fault was blamed on the sender: persisted={:?} failed={:?}", out.persisted, out.failed);
1310 Ok(())
1311}
1312
1313/// A reply that also asks for ids back.
1314fn reply_asking(from: u8, to: u8, table: &str, records: Vec<Record>, requested_ids: Vec<RecordId>) -> Envelope {
1315 Envelope::new(node(from), node(to), MsgKind::AntiEntropyReply {
1316 table: s(table),
1317 records,
1318 requested_ids,
1319 bulk: false,
1320 after: None,
1321 next: None,
1322 })
1323}
1324
1325/// The leader and members of a cohort, by the engine's own selection.
1326fn cohort_for(ids: &[NodeId], table: &str, id: &RecordId, lambda: u64) -> Outcome<(NodeId, Vec<NodeId>)> {
1327 let local = ids[0];
1328 let mut peers = PeerSet::new();
1329 for p in ids.iter().filter(|p| **p != local) {
1330 peers.insert(*p);
1331 }
1332 let c = res!(cohort::select(table, id, &peers, &local, lambda));
1333 Ok((c.leader, c.members))
1334}
1335
1336#[test]
1337fn decide_store_fault_leaves_instance_undecided() -> Outcome<()> {
1338 let ids: Vec<NodeId> = (1..=5).map(node).collect();
1339 let mut engines: HashMap<NodeId, DistOzone<TestStorage>> = HashMap::new();
1340 for me in &ids {
1341 let peers = ids.iter().filter(|p| *p != me).copied().collect();
1342 let oam = res!(OamConfig::new(5, 5));
1343 let tables = vec![res!(TableConfig::new(
1344 "treasury",
1345 Consistency::Cohort { lambda: 5 },
1346 TableConfig::DEFAULT_AE,
1347 TableConfig::DEFAULT_IBLT_CELLS,
1348 ))];
1349 let cfg = res!(DistOzoneConfig::new(*me, peers, oam, tables));
1350 engines.insert(*me, res!(DistOzone::new(cfg, TestStorage::new())));
1351 }
1352 let id = rid(0x42);
1353 let record = rec("treasury", id, b"payload");
1354 let (leader, members) = res!(cohort_for(&ids, "treasury", &id, 5));
1355 // A follower whose store fails when the Decide reaches it.
1356 let victim = members[3];
1357 res!(engines[&victim].storage().fail_put_of(Some(id)));
1358
1359 let mut pending = res!(engines[&leader].put(record.clone())).outbound;
1360 let mut faulted: Vec<Envelope> = Vec::new();
1361 for _ in 0..64 {
1362 if pending.is_empty() {
1363 break;
1364 }
1365 let mut next = Vec::new();
1366 for env in pending.drain(..) {
1367 let to = env.to;
1368 match engines[&to].handle_envelope(env.clone()) {
1369 Ok(out) => next.extend(out.outbound),
1370 Err(_) if to == victim => faulted.push(env),
1371 Err(e) => return Err(e),
1372 }
1373 }
1374 pending = next;
1375 }
1376 assert!(!faulted.is_empty(), "the victim's store fault was never reached");
1377 assert_eq!(res!(stored(&engines[&victim], "treasury", id)), None);
1378
1379 // The replica is inert once it has emitted its Decide, so the decided record
1380 // must be held and stored again when the caller's timer fires: still failing
1381 // while the fault lasts, stored once it clears.
1382 let victim_engine = &engines[&victim];
1383 assert!(victim_engine.cohort_timeout("treasury", &id).is_err(),
1384 "a failed Decide store was forgotten, not held for a retry");
1385 res!(victim_engine.storage().fail_put_of(None));
1386 res!(victim_engine.cohort_timeout("treasury", &id));
1387 assert_eq!(res!(stored(victim_engine, "treasury", id)), Some(b"payload".to_vec()),
1388 "a failed Decide store left the replica decided with no record");
1389 // Decided now, so a further timeout is quiet.
1390 assert!(res!(victim_engine.cohort_timeout("treasury", &id)).is_empty());
1391 Ok(())
1392}
1393
1394#[test]
1395fn check_detects_trailing_zero_divergence() -> Outcome<()> {
1396 // Control: first-arrival-wins on [1] and [2] is caught.
1397 let ctl = vec![rec("identity", rid(1), &[1]), rec("identity", rid(1), &[2])];
1398 let r = check_convergence(&converge(0..32, 16), &["identity"], &ctl, |_| FirstWins, |_, _, _| Ok(Vec::new()));
1399 assert!(r.is_err(), "control: FirstWins on [1] and [2] passed");
1400
1401 // The same resolver on [1] and [1, 0]: the peers hold different bytes whose
1402 // content digests are equal, so only a comparison of the bytes sees it.
1403 let recs = vec![rec("identity", rid(1), &[1]), rec("identity", rid(1), &[1, 0])];
1404 let text = failure_text(check_convergence(
1405 &converge(0..32, 16), &["identity"], &recs, |_| FirstWins, |_, _, _| Ok(Vec::new()),
1406 ));
1407 assert!(text.contains("differs from peer 0"), "FirstWins on [1] and [1, 0] passed: {:?}", text);
1408 Ok(())
1409}
1410
1411/// An escrow record needs the identity at its own id: with it missing the rule
1412/// says Defer, or Refuse when `refuse` is set (the bug the contract warns of).
1413struct NeedsIdentity {
1414 refuse: bool,
1415}
1416
1417impl Resolver for NeedsIdentity {
1418 fn resolve<V: ReadView>(
1419 &self,
1420 ctx: &ResolveCtx,
1421 view: &V,
1422 table: &str,
1423 id: &RecordId,
1424 held: Option<&[u8]>,
1425 incoming: &[u8],
1426 )
1427 -> Outcome<Verdict>
1428 {
1429 if table == "escrow" && res!(view.get("identity", id)).is_none() {
1430 return Ok(if self.refuse {
1431 Verdict::Refuse(s("no identity"))
1432 } else {
1433 Verdict::Defer
1434 });
1435 }
1436 LastVersionWins.resolve(ctx, view, table, id, held, incoming)
1437 }
1438}
1439
1440#[test]
1441fn refuse_on_missing_dependency_fails_check() -> Outcome<()> {
1442 // The escrow is listed before its identity.
1443 let recs = vec![
1444 rec("escrow", rid(1), &LastVersionWins::value(1, b"e")),
1445 rec("identity", rid(1), &LastVersionWins::value(1, b"i")),
1446 ];
1447 let cfg = converge(0..32, 16);
1448 let tables = ["identity", "escrow"];
1449 let good = check_convergence(&cfg, &tables, &recs, |_| NeedsIdentity { refuse: false }, |_, _, _| Ok(Vec::new()));
1450 assert!(good.is_ok(), "Defer on a missing dependency failed: {:?}", good.err());
1451 let bad = failure_text(check_convergence(
1452 &cfg, &tables, &recs, |_| NeedsIdentity { refuse: true }, |_, _, _| Ok(Vec::new()),
1453 ));
1454 assert!(!bad.is_empty(), "Refuse on a missing dependency passed the check");
1455 Ok(())
1456}
1457
1458/// A mesh of `n` peers on the eventual table "identity", each holding everything.
1459fn mesh(n: usize) -> Outcome<Vec<DistOzone<MemoryStorage>>> {
1460 let ids: Vec<NodeId> = (0..n).map(|i| node((i + 1) as u8)).collect();
1461 let mut out = Vec::new();
1462 for me in &ids {
1463 let others = ids.iter().filter(|x| *x != me).copied().collect();
1464 let oam = res!(OamConfig::new(n as u64, n as u64));
1465 let cfg = res!(DistOzoneConfig::new(*me, others, oam, vec![res!(TableConfig::eventual("identity"))]));
1466 out.push(res!(DistOzone::new(cfg, MemoryStorage::new())));
1467 }
1468 Ok(out)
1469}
1470
1471/// One whole anti-entropy exchange, `a` dialling `b`.
1472fn exchange(e: &[DistOzone<MemoryStorage>], a: usize, b: usize) -> Outcome<()> {
1473 let mut pending = vec![res!(e[a].build_anti_entropy_request("identity", node((b + 1) as u8)))];
1474 while let Some(env) = pending.pop() {
1475 let to = (env.to.as_bytes()[31] - 1) as usize;
1476 let out = res!(e[to].handle_envelope_at(env, 0));
1477 assert!(out.failed.is_empty());
1478 pending.extend(out.outbound);
1479 }
1480 Ok(())
1481}
1482
1483#[test]
1484fn lww_lost_replicate_not_repaired() -> Outcome<()> {
1485 let e = res!(mesh(2));
1486 let hi = LastVersionWins::value(7, &[0xAB, 0]);
1487 let lo = LastVersionWins::value(7, &[0xAB]);
1488 // Each peer writes locally and both replications are lost.
1489 res!(e[0].put_at(rec("identity", rid(1), &hi), 0));
1490 res!(e[1].put_at(rec("identity", rid(1), &lo), 0));
1491 for _ in 0..4 {
1492 res!(exchange(&e, 0, 1));
1493 res!(exchange(&e, 1, 0));
1494 }
1495 assert_eq!(res!(stored(&e[0], "identity", rid(1))), Some(hi.clone()));
1496 assert_eq!(res!(stored(&e[1], "identity", rid(1))), Some(hi));
1497 Ok(())
1498}
1499
1500#[test]
1501fn forged_same_digest_value_never_repaired() -> Outcome<()> {
1502 // A value is a version then two 8-byte chunks. The second chunk of the
1503 // forgery is solved so the chained hash after it matches the original's.
1504 fn mix(mut x: u64) -> u64 {
1505 x = (x ^ (x >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
1506 x = (x ^ (x >> 27)).wrapping_mul(0x94D049BB133111EB);
1507 x ^ (x >> 31)
1508 }
1509 let s_ver = mix(0x9E3779B97F4A7C15u64.wrapping_add(u64::from_le_bytes(9u64.to_be_bytes())));
1510 let (p0, p1, p0f) = (0x1111_1111_1111_1111u64, 0x2222_2222_2222_2222u64, 0x3333_3333_3333_3333u64);
1511 let p1f = mix(s_ver.wrapping_add(p0)).wrapping_add(p1).wrapping_sub(mix(s_ver.wrapping_add(p0f)));
1512 let mut pa = p0.to_le_bytes().to_vec();
1513 pa.extend_from_slice(&p1.to_le_bytes());
1514 let mut pb = p0f.to_le_bytes().to_vec();
1515 pb.extend_from_slice(&p1f.to_le_bytes());
1516 let (va, vb) = (LastVersionWins::value(9, &pa), LastVersionWins::value(9, &pb));
1517 assert_ne!(va, vb);
1518
1519 let e = res!(mesh(2));
1520 res!(e[0].put_at(rec("identity", rid(1), &va), 0));
1521 res!(e[1].put_at(rec("identity", rid(1), &vb), 0));
1522 for _ in 0..4 {
1523 res!(exchange(&e, 0, 1));
1524 res!(exchange(&e, 1, 0));
1525 }
1526 assert_eq!(res!(stored(&e[0], "identity", rid(1))), res!(stored(&e[1], "identity", rid(1))));
1527 Ok(())
1528}
1529
1530#[test]
1531fn dialled_peer_not_offered_on_value_divergence() -> Outcome<()> {
1532 let e = res!(mesh(2));
1533 let v2 = LastVersionWins::value(2, b"new");
1534 let v1 = LastVersionWins::value(1, b"old");
1535 // Peer 0 holds the newer X and a Y; peer 1 missed both but holds the older X.
1536 res!(e[0].put_at(rec("identity", rid(1), &v2), 0));
1537 res!(e[0].put_at(rec("identity", rid(2), b"y"), 0));
1538 res!(e[1].put_at(rec("identity", rid(1), &v1), 0));
1539 res!(exchange(&e, 0, 1));
1540 assert_eq!(res!(stored(&e[1], "identity", rid(1))), Some(v2), "the dialled peer kept its stale X");
1541 assert_eq!(res!(stored(&e[1], "identity", rid(2))), Some(b"y".to_vec()), "the dialled peer never got Y");
1542 Ok(())
1543}