minerva 0.2.0

Causal ordering for distributed systems
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

extern crate alloc;

use alloc::collections::{BTreeMap, BTreeSet};
use alloc::vec::Vec;

use crate::metis::{Dot, DotMap, DotSet, Dotted};
use proptest::prelude::*;

mod convergence;
mod delta;
mod disjoint;
mod merge;
mod restriction;

/// Caller keys over bare presence dots: observed-remove composition.
type Doc = Dotted<DotMap<u8, DotSet>>;

/// A simulated replica step. Replica `i` writes as station `i`.
#[derive(Clone, Debug)]
enum Op {
    Add { replica: usize, key: u8 },
    Remove { replica: usize, key: u8 },
    Gossip { from: usize, to: usize },
}

const REPLICAS: usize = 3;

fn arb_ops() -> impl Strategy<Value = Vec<Op>> {
    let op = prop_oneof![
        (0..REPLICAS, 0u8..3).prop_map(|(replica, key)| Op::Add { replica, key }),
        (0..REPLICAS, 0u8..3).prop_map(|(replica, key)| Op::Remove { replica, key }),
        (0..REPLICAS, 0..REPLICAS).prop_map(|(from, to)| Op::Gossip { from, to }),
    ];
    prop::collection::vec(op, 0..24)
}

/// Dots minted by the run, plus those later superseded by an observed removal.
struct Record {
    minted: BTreeMap<Dot, u8>,
    expelled: BTreeSet<Dot>,
}

/// Replays a history through the documented write flow.
fn run(ops: &[Op]) -> (Vec<Doc>, Record) {
    let mut live: Vec<Doc> = (0..REPLICAS).map(|_| Dotted::new()).collect();
    let mut record = Record {
        minted: BTreeMap::new(),
        expelled: BTreeSet::new(),
    };
    for op in ops {
        match *op {
            Op::Add { replica, key } => {
                let station = u32::try_from(replica).unwrap();
                let fresh = live[replica].next_dot(station);
                let mut held = DotSet::new();
                assert!(held.insert(fresh));
                let delta = Dotted::from_store(DotMap::singleton(key, held));
                live[replica] = live[replica].merge(&delta);
                let _ = record.minted.insert(fresh, key);
            }
            Op::Remove { replica, key } => {
                let observed = live[replica].store().get(&key).cloned().unwrap_or_default();
                for dot in observed.difference(&DotSet::new()) {
                    let _ = record.expelled.insert(dot);
                }
                let delta = Dotted::from_context(observed);
                live[replica] = live[replica].merge(&delta);
            }
            Op::Gossip { from, to } => {
                let learned = live[to].merge(&live[from]);
                live[to] = learned;
            }
        }
    }
    (live, record)
}

/// Per key, exactly the assigned dots no observed removal superseded.
fn expected(record: &Record) -> DotMap<u8, DotSet> {
    let mut store = DotMap::new();
    for (&minted, &key) in &record.minted {
        if record.expelled.contains(&minted) {
            continue;
        }
        let mut held: DotSet = store.get(&key).cloned().unwrap_or_default();
        assert!(held.insert(minted));
        let _ = store.insert(key, held);
    }
    store
}