Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/src/dist/resolve.rs

17.6 KiB, 31 runs

created by r1870400018:67185, 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//! The resolver seam: the application's rule for which value a record holds.
2//!
3//! Every record that reaches an eventual table -- a local put, a
4//! `ReplicatePut`, an anti-entropy reply or push -- is offered to a
5//! [`Resolver`] together with the value already held, and the engine stores
6//! only what the resolver says to. For peers to converge, `resolve` must be a
7//! function of `(held, incoming)` and the records its [`ReadView`] returns,
8//! must not depend on arrival order or on who sent the record, and must answer
9//! [`Verdict::Defer`], never [`Verdict::Refuse`], where only time or a missing
10//! record can cure the problem. [`LastVersionWins`] is the default.
11//!
12//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
13//! Anthropic Claude
14
15use super::{
16 config::{
17 DistOzoneConfig,
18 TableConfig,
19 },
20 engine::DistOzone,
21 record::{
22 Record,
23 RecordId,
24 },
25 storage::{
26 MemoryStorage,
27 Storage,
28 },
29 transport::Envelope,
30};
31use crate::{
32 kademlia::id::NodeId,
33 oam::config::OamConfig,
34};
35
36use oxedyne_fe2o3_core::prelude::*;
37
38use std::ops::Range;
39
40
41#[derive(Clone, Debug, Eq, PartialEq)]
42pub enum Verdict {
43 Take(Vec<u8>), // store these bytes: the incoming value, or a merge of held and incoming
44 Keep, // the held value stands
45 Defer, // valid once something else arrives; not stored, offered again by anti-entropy
46 Refuse(String), // invalid; not stored, the held value is untouched; the reason is for the log
47}
48
49/// Built with [`ResolveCtx::at`], so that fields can be added later.
50#[derive(Clone, Copy, Debug)]
51#[non_exhaustive]
52pub struct ResolveCtx {
53 pub now_ms: u64, // the caller's clock, in milliseconds since the Unix epoch
54}
55
56impl ResolveCtx {
57 pub fn at(now_ms: u64) -> Self {
58 Self { now_ms }
59 }
60}
61
62/// Point reads only, so a resolver cannot write.
63pub trait ReadView {
64 fn get(&self, table: &str, id: &RecordId) -> Outcome<Option<Vec<u8>>>;
65}
66
67/// What the engine passes to a resolver. It is a wrapper, not a blanket
68/// `impl ReadView for S: Storage`, which would make `get` ambiguous for a
69/// caller with both traits in scope.
70pub struct StorageView<'a, S: Storage>(pub &'a S);
71
72impl<'a, S: Storage> ReadView for StorageView<'a, S> {
73 fn get(&self, table: &str, id: &RecordId) -> Outcome<Option<Vec<u8>>> {
74 Ok(res!(self.0.get(table, id)).map(|r| r.value))
75 }
76}
77
78pub trait Resolver {
79 /// `held` is `None` on a first arrival, which is validated too. The engine
80 /// calls this under its write lock, for one record, only on a peer that
81 /// holds the record. An `Err` stores nothing and is reported in
82 /// `InboundOutcome::failed`, or returned from a local put.
83 fn resolve<V: ReadView>(
84 &self,
85 ctx: &ResolveCtx,
86 view: &V,
87 table: &str,
88 id: &RecordId,
89 held: Option<&[u8]>,
90 incoming: &[u8],
91 )
92 -> Outcome<Verdict>;
93}
94
95/// The default resolver: the greater byte string wins. It is a semilattice
96/// join, so any arrival order converges, and equal values are a [`Verdict::Keep`].
97#[derive(Clone, Copy, Debug, Default)]
98pub struct LastVersionWins;
99
100impl LastVersionWins {
101 /// A big-endian `u64` version, then the payload. Byte order then sorts by
102 /// version first and payload second.
103 pub fn value(version: u64, payload: &[u8]) -> Vec<u8> {
104 let mut v = Vec::with_capacity(8 + payload.len());
105 v.extend_from_slice(&version.to_be_bytes());
106 v.extend_from_slice(payload);
107 v
108 }
109
110 /// `None` when the value is shorter than the eight version bytes.
111 pub fn version(value: &[u8]) -> Option<u64> {
112 value.first_chunk::<8>().map(|b| u64::from_be_bytes(*b))
113 }
114}
115
116impl Resolver for LastVersionWins {
117 fn resolve<V: ReadView>(
118 &self,
119 _ctx: &ResolveCtx,
120 _view: &V,
121 _table: &str,
122 _id: &RecordId,
123 held: Option<&[u8]>,
124 incoming: &[u8],
125 )
126 -> Outcome<Verdict>
127 {
128 match held {
129 Some(h) if incoming <= h => Ok(Verdict::Keep),
130 _ => Ok(Verdict::Take(incoming.to_vec())),
131 }
132 }
133}
134
135
136/// The shape of a [`check_convergence`] run. Built with [`Convergence::new`], so that fields can
137/// be added later.
138#[derive(Clone, Debug)]
139#[non_exhaustive]
140pub struct Convergence {
141 pub peers: usize, // 2 to 5; every peer holds every record
142 pub seeds: Range<u64>, // one scatter-and-settle run per seed
143 pub now_ms: u64, // the clock every peer starts from, before its skew
144 pub max_rounds: usize, // full rounds, and post-write depth, allowed before "did not quiesce"
145 pub skew_ms: u64, // each peer's clock leads by a seeded 0 to this; each full round adds this to every clock
146}
147
148impl Convergence {
149 pub fn new(peers: usize, seeds: Range<u64>, now_ms: u64, max_rounds: usize) -> Self {
150 // Every peer reads `now_ms` for the whole run until `with_skew_ms` says otherwise.
151 Self { peers, seeds, now_ms, max_rounds, skew_ms: 0 }
152 }
153
154 /// Gives each peer a clock that leads `now_ms` by an offset drawn once per peer and seed from 0
155 /// to `skew_ms`, and moves every clock on by `skew_ms` at the start of each full round. A rule
156 /// that answers `Defer` until a time comes then converges once the clocks pass it, and one that
157 /// answers `Refuse` to that time fails, because which peer a record landed on decides its fate.
158 pub fn with_skew_ms(mut self, skew_ms: u64) -> Self {
159 self.skew_ms = skew_ms;
160 self
161 }
162}
163
164/// Does the resolver (and the application's `after` pass) make the converged
165/// state a function of the set of records alone?
166///
167/// For each seed it builds `cfg.peers` peers on [`MemoryStorage`], each holding
168/// everything, and delivers every record as a local put on a random peer in
169/// random order. Between the puts it delivers in-flight replication in random
170/// order, runs random anti-entropy exchanges and offers a deferred local put
171/// again. Whatever `after` returns for a peer's newly stored records is put on
172/// that peer, and its stores are passed to `after` in turn. It then runs full
173/// rounds (the in-flight messages, the deferred puts, and an anti-entropy
174/// exchange between every ordered pair of peers on every table) until a round
175/// stores nothing, and compares the bytes the peers hold, and each seed's final state
176/// with the first seed's. Every peer reads its own clock (see [`Convergence::with_skew_ms`]). The `Err` names the seed, the table and the first
177/// differing id; it also reports a run that is still storing after
178/// `cfg.max_rounds` ("did not quiesce"), a resolver that fails, and an `after`
179/// chain deeper than `cfg.max_rounds`.
180pub fn check_convergence<R, F, P>(
181 cfg: &Convergence,
182 tables: &[&str],
183 records: &[Record],
184 mut new_resolver: F,
185 mut after: P,
186)
187 -> Outcome<()>
188 where
189 R: Resolver,
190 F: FnMut(usize) -> R,
191 P: FnMut(usize, &DistOzone<MemoryStorage, R>, &[(String, RecordId)])
192 -> Outcome<Vec<Record>>,
193{
194 if cfg.peers < 2 || cfg.peers > 5 {
195 return Err(err!(
196 "check_convergence needs 2 to 5 peers, got {}.", cfg.peers;
197 Invalid, Input, Range));
198 }
199 if cfg.max_rounds == 0 || tables.is_empty() {
200 return Err(err!(
201 "check_convergence needs max_rounds >= 1 and at least one table.";
202 Invalid, Input, Missing));
203 }
204 let mut first: Option<(u64, Vec<Held>)> = None;
205 for seed in cfg.seeds.clone() {
206 let state = match run_seed(cfg, seed, tables, records, &mut new_resolver, &mut after) {
207 Ok(state) => state,
208 Err(e) => return Err(err!(e,
209 "check_convergence: seed {}.", seed; Test, Mismatch)),
210 };
211 match &first {
212 None => first = Some((seed, state)),
213 Some((seed0, state0)) => {
214 for (t, table) in tables.iter().enumerate() {
215 if let Some(id) = first_diff(&state0[t], &state[t]) {
216 return Err(err!(
217 "check_convergence: seed {} ends in a different state \
218 from seed {} on table '{}', first differing id {}: the \
219 converged state depends on the order of arrival.",
220 seed, seed0, table, hex(&id);
221 Test, Mismatch));
222 }
223 }
224 },
225 }
226 }
227 Ok(())
228}
229
230// What a peer holds on one table, by id: the stored bytes themselves. A content
231// digest is only a summary and two values can share one, so it is used to list
232// the ids and never to compare the values.
233type Held = Vec<(RecordId, Vec<u8>)>;
234
235// Builds the peers for one seed, drives them to quiescence and returns the
236// final bytes held on each table, after checking that every peer agrees.
237fn run_seed<R, F, P>(
238 cfg: &Convergence,
239 seed: u64,
240 tables: &[&str],
241 records: &[Record],
242 new_resolver: &mut F,
243 after: &mut P,
244)
245 -> Outcome<Vec<Held>>
246 where
247 R: Resolver,
248 F: FnMut(usize) -> R,
249 P: FnMut(usize, &DistOzone<MemoryStorage, R>, &[(String, RecordId)])
250 -> Outcome<Vec<Record>>,
251{
252 let n = cfg.peers;
253 let mut ids = Vec::with_capacity(n);
254 for i in 0..n {
255 let mut bytes = [0u8; 32];
256 bytes[31] = (i + 1) as u8;
257 ids.push(NodeId::from_bytes(bytes));
258 }
259 let mut engines = Vec::with_capacity(n);
260 for i in 0..n {
261 let mut tcs = Vec::with_capacity(tables.len());
262 for table in tables {
263 tcs.push(res!(TableConfig::eventual(*table)));
264 }
265 let others = ids.iter().copied().filter(|id| *id != ids[i]).collect();
266 let oam = res!(OamConfig::new(n as u64, n as u64));
267 let dcfg = res!(DistOzoneConfig::new(ids[i], others, oam, tcs));
268 engines.push(res!(DistOzone::with_resolver(
269 dcfg,
270 MemoryStorage::new(),
271 new_resolver(i),
272 )));
273 }
274 // Each peer's offset comes from a generator of its own, so the schedule drawn from `rng` is
275 // the same whatever the skew.
276 let mut skew = SplitMix64(seed ^ 0xC10C_5EED_0FF5_E7D5);
277 let mut clocks = Vec::with_capacity(n);
278 for _ in 0..n {
279 let offset = skew.draw() % cfg.skew_ms.saturating_add(1);
280 clocks.push(cfg.now_ms.saturating_add(offset));
281 }
282 let mut run = Run {
283 seed,
284 engines,
285 ids,
286 rng: SplitMix64(seed),
287 clocks,
288 skew_ms: cfg.skew_ms,
289 max_depth: cfg.max_rounds,
290 after,
291 flight: Vec::new(),
292 deferred: Vec::new(),
293 stored: 0,
294 };
295
296 let mut order: Vec<usize> = (0..records.len()).collect();
297 run.rng.shuffle(&mut order);
298 for i in order {
299 let peer = run.rng.below(n);
300 res!(run.local_put(peer, records[i].clone()));
301 for _ in 0..run.rng.below(3) {
302 res!(run.step(tables));
303 }
304 }
305
306 // A round that stores nothing is quiet, unless the clocks are still moving and a put is
307 // deferred past them: it will be offered again once they reach its time, and the rule may
308 // diverge then.
309 let mut quiet = false;
310 for _ in 0..cfg.max_rounds {
311 if res!(run.round(tables)) == 0 && (cfg.skew_ms == 0 || run.deferred.is_empty()) {
312 quiet = true;
313 break;
314 }
315 }
316 if !quiet && !run.deferred.is_empty() {
317 return Err(err!(
318 "check_convergence: seed {} did not quiesce: {} deferred puts still pending \
319 after {} full rounds.", seed, run.deferred.len(), cfg.max_rounds;
320 Test, LimitReached));
321 }
322 if !quiet {
323 return Err(err!(
324 "check_convergence: seed {} did not quiesce: every one of {} full \
325 rounds still stored records.", seed, cfg.max_rounds;
326 Test, LimitReached));
327 }
328
329 let mut state = Vec::with_capacity(tables.len());
330 for table in tables {
331 let mut mine = Vec::with_capacity(n);
332 for engine in &run.engines {
333 let mut d = res!(engine.storage().digests(table));
334 d.sort_by(|a, b| a.id.cmp(&b.id));
335 let mut held = Vec::with_capacity(d.len());
336 for digest in d {
337 let record = res!(engine.storage().get(table, &digest.id));
338 let record = res!(record.ok_or_else(|| err!(
339 "check_convergence: seed {}: table '{}' lists id {} in its digests \
340 but cannot read it.", seed, table, hex(&digest.id);
341 Test, Missing)));
342 held.push((digest.id, record.value));
343 }
344 mine.push(held);
345 }
346 for p in 1..n {
347 if let Some(id) = first_diff(&mine[0], &mine[p]) {
348 return Err(err!(
349 "check_convergence: seed {}: on table '{}' peer {} differs \
350 from peer 0, first differing id {}.", seed, table, p, hex(&id);
351 Test, Mismatch));
352 }
353 }
354 state.push(mine.swap_remove(0));
355 }
356 Ok(state)
357}
358
359// One seed's world: the peers, the messages in flight and the puts to offer again.
360struct Run<'a, R: Resolver, P> {
361 seed: u64,
362 engines: Vec<DistOzone<MemoryStorage, R>>,
363 ids: Vec<NodeId>,
364 rng: SplitMix64,
365 clocks: Vec<u64>, // each peer's own clock
366 skew_ms: u64, // what a full round adds to every clock
367 max_depth: usize,
368 after: &'a mut P,
369 flight: Vec<Envelope>,
370 deferred: Vec<(usize, Record)>, // a local put that answered Defer
371 stored: usize, // stores made so far, counted by the round
372}
373
374impl<'a, R, P> Run<'a, R, P>
375 where
376 R: Resolver,
377 P: FnMut(usize, &DistOzone<MemoryStorage, R>, &[(String, RecordId)])
378 -> Outcome<Vec<Record>>,
379{
380 // A local put on one peer. Its replication joins the messages in flight.
381 fn local_put(&mut self, peer: usize, record: Record) -> Outcome<()> {
382 let out = res!(self.engines[peer].put_at(record.clone(), self.clocks[peer]));
383 self.flight.extend(out.outbound);
384 match out.verdict {
385 Some(Verdict::Take(_)) => self.settle(peer, vec![(record.table, record.id)]),
386 Some(Verdict::Defer) => {
387 self.deferred.push((peer, record));
388 Ok(())
389 },
390 _ => Ok(()),
391 }
392 }
393
394 // The caller's post-write pass over what a peer has just stored, and again
395 // over what that pass stores in turn, to a depth of `max_rounds`.
396 fn settle(&mut self, peer: usize, persisted: Vec<(String, RecordId)>) -> Outcome<()> {
397 self.stored += persisted.len();
398 let mut work = vec![(peer, persisted, 0usize)];
399 while let Some((p, list, depth)) = work.pop() {
400 if list.is_empty() {
401 continue;
402 }
403 if depth >= self.max_depth {
404 return Err(err!(
405 "check_convergence: seed {} did not quiesce: the post-write \
406 pass was still storing records at depth {}.", self.seed, depth;
407 Test, LimitReached));
408 }
409 let puts = res!((self.after)(p, &self.engines[p], &list));
410 for record in puts {
411 let out = res!(self.engines[p].put_at(record.clone(), self.clocks[p]));
412 self.flight.extend(out.outbound);
413 match out.verdict {
414 Some(Verdict::Take(_)) => {
415 self.stored += 1;
416 work.push((p, vec![(record.table, record.id)], depth + 1));
417 },
418 Some(Verdict::Defer) => self.deferred.push((p, record)),
419 _ => {},
420 }
421 }
422 }
423 Ok(())
424 }
425
426 // Delivers an envelope and every reply it provokes.
427 fn deliver(&mut self, env: Envelope) -> Outcome<()> {
428 let mut pending = vec![env];
429 while let Some(e) = pending.pop() {
430 let dest = res!(self.ids.iter().position(|id| *id == e.to).ok_or_else(|| err!(
431 "check_convergence: seed {}: envelope for an unknown peer.", self.seed;
432 Invalid, Input, Missing)));
433 let out = res!(self.engines[dest].handle_envelope_at(e, self.clocks[dest]));
434 // A resolver fault is a bug in the rule under test, not a verdict.
435 if let Some((table, id, _)) = out.failed.first() {
436 return Err(err!(
437 "check_convergence: seed {}: the resolver failed on table '{}' \
438 id {}.", self.seed, table, hex(id);
439 Test, Unexpected));
440 }
441 pending.extend(out.outbound);
442 res!(self.settle(dest, out.persisted));
443 }
444 Ok(())
445 }
446
447 // One anti-entropy exchange on one table: digest, reply, push.
448 fn exchange(&mut self, a: usize, b: usize, table: &str) -> Outcome<()> {
449 let req = res!(self.engines[a].build_anti_entropy_request(table, self.ids[b]));
450 self.deliver(req)
451 }
452
453 // One random event between puts.
454 fn step(&mut self, tables: &[&str]) -> Outcome<()> {
455 let n = self.engines.len();
456 match self.rng.below(4) {
457 0 if !self.flight.is_empty() => {
458 let i = self.rng.below(self.flight.len());
459 let env = self.flight.swap_remove(i);
460 self.deliver(env)
461 },
462 1 => {
463 let a = self.rng.below(n);
464 let b = (a + 1 + self.rng.below(n - 1)) % n;
465 let t = self.rng.below(tables.len());
466 self.exchange(a, b, tables[t])
467 },
468 2 if !self.deferred.is_empty() => {
469 let i = self.rng.below(self.deferred.len());
470 let (peer, record) = self.deferred.swap_remove(i);
471 self.local_put(peer, record)
472 },
473 _ => Ok(()),
474 }
475 }
476
477 // A full round: what is in flight, the deferred puts, then every ordered
478 // pair on every table. Returns the number of stores the round made.
479 fn round(&mut self, tables: &[&str]) -> Outcome<usize> {
480 self.stored = 0;
481 for clock in &mut self.clocks {
482 *clock = clock.saturating_add(self.skew_ms);
483 }
484 while !self.flight.is_empty() {
485 let i = self.rng.below(self.flight.len());
486 let env = self.flight.swap_remove(i);
487 res!(self.deliver(env));
488 }
489 let again = std::mem::take(&mut self.deferred);
490 for (peer, record) in again {
491 res!(self.local_put(peer, record));
492 }
493 let n = self.engines.len();
494 let mut pairs = Vec::with_capacity(n * (n - 1) * tables.len());
495 for a in 0..n {
496 for b in 0..n {
497 for t in 0..tables.len() {
498 if a != b {
499 pairs.push((a, b, t));
500 }
501 }
502 }
503 }
504 self.rng.shuffle(&mut pairs);
505 for (a, b, t) in pairs {
506 res!(self.exchange(a, b, tables[t]));
507 }
508 Ok(self.stored)
509 }
510}
511
512// The first id at which two id-sorted lists differ in presence or in bytes.
513fn first_diff(a: &[(RecordId, Vec<u8>)], b: &[(RecordId, Vec<u8>)]) -> Option<RecordId> {
514 let (mut i, mut j) = (0, 0);
515 loop {
516 match (a.get(i), b.get(j)) {
517 (None, None) => return None,
518 (Some(x), None) => return Some(x.0),
519 (None, Some(y)) => return Some(y.0),
520 (Some(x), Some(y)) => {
521 if x.0 < y.0 {
522 return Some(x.0);
523 }
524 if y.0 < x.0 {
525 return Some(y.0);
526 }
527 if x.1 != y.1 {
528 return Some(x.0);
529 }
530 i += 1;
531 j += 1;
532 },
533 }
534 }
535}
536
537fn hex(id: &RecordId) -> String {
538 id.as_bytes().iter().map(|b| fmt!("{:02x}", b)).collect()
539}
540
541// The seeded generator behind every random choice, so a failing seed replays.
542struct SplitMix64(u64);
543
544impl SplitMix64 {
545 fn draw(&mut self) -> u64 {
546 self.0 = self.0.wrapping_add(0x9E3779B97F4A7C15);
547 let mut z = self.0;
548 z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
549 z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
550 z ^ (z >> 31)
551 }
552
553 // Uniform enough for scheduling; `n` is at least one.
554 fn below(&mut self, n: usize) -> usize {
555 (self.draw() % n as u64) as usize
556 }
557
558 fn shuffle<T>(&mut self, v: &mut [T]) {
559 for i in (1..v.len()).rev() {
560 let j = self.below(i + 1);
561 v.swap(i, j);
562 }
563 }
564}