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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

extern crate alloc;

use alloc::collections::BTreeSet;
use alloc::vec::Vec;

use crate::metis::{Dot, DotSet, Retired, Retirement, Stability};

use super::super::editor::{Replica, gossip_text};
use super::split_two;

#[test]
fn test_gc_bounds_the_session() {
    // Origin-anchored type/delete churn leaves sterile tombstone leaves, so an
    // honest retirement claim can collapse the skeleton completely.
    let roster = [1u32, 2u32, 3u32];
    let mut replicas: Vec<Replica> = roster.iter().map(|&s| Replica::new(s, &roster)).collect();

    let pairs_per_replica = 300usize;
    for round in 0..pairs_per_replica {
        for idx in 0..replicas.len() {
            let ch = char::from(b'a' + u8::try_from(round % 26).unwrap_or(0));
            let dot = replicas[idx].insert(ch, None);
            replicas[idx].delete(dot);
            let next = (idx + 1) % replicas.len();
            let (from, into) = split_two(&mut replicas, idx, next);
            gossip_text(from, into);
        }
    }
    for _ in 0..2 {
        for i in 0..replicas.len() {
            for j in 0..replicas.len() {
                if i != j {
                    let (from, into) = split_two(&mut replicas, i, j);
                    gossip_text(from, into);
                }
            }
        }
    }

    let total_writes = pairs_per_replica * replicas.len();
    for r in &replicas {
        assert_eq!(r.visible_len(), 0);
    }
    let skeleton_before = replicas[0].skeleton_len();
    assert_eq!(
        skeleton_before, total_writes,
        "every write is a retained tombstone before GC"
    );

    let retired = honest_retirement(&replicas);

    let mut stability = Stability::new(roster.iter().copied());
    for r in &replicas {
        r.report_into(&mut stability);
    }
    let _watermark = stability.watermark();

    let mut total_excised = 0usize;
    for r in &mut replicas {
        total_excised += r.condense(&retired);
    }
    assert!(total_excised > 0);

    for r in &replicas {
        assert_eq!(
            r.skeleton_len(),
            0,
            "origin-anchored churn leaves NO uncollectable residue: every tombstone is a sterile leaf",
        );
    }
}

#[test]
fn test_gc_residue_is_anchored_tombstone_chains() {
    // A dead span with a live tail is not sterile: the live successor anchors
    // through the tombstones, so leaf-first condense must spare them.
    let roster = [1u32];
    let mut r = Replica::new(1, &roster);

    let mut chain = Vec::new();
    let mut anchor = None;
    for i in 0..10 {
        let ch = char::from(b'a' + u8::try_from(i).unwrap_or(0));
        let dot = r.insert(ch, anchor);
        chain.push(dot);
        anchor = Some(dot);
    }
    for &dot in &chain[1..9] {
        r.delete(dot);
    }
    assert_eq!(r.visible_len(), 2);
    assert_eq!(r.skeleton_len(), 10);

    let mut retired = DotSet::new();
    for &dot in &chain[1..9] {
        let _ = retired.insert(dot);
    }
    let excised = r.condense(&Retired::trust(retired));
    assert_eq!(
        excised, 0,
        "an internally-dead span with a live tail is uncollectable by leaf-first condense"
    );
    assert_eq!(
        r.skeleton_len(),
        10,
        "the 8 dead middles are retained as anchored tombstones"
    );
    assert_eq!(r.visible_len(), 2);
}

/// Gathers an honest retirement claim through the tracker meet: every claimed
/// dot is invisible at every replica in the simulated deployment.
fn honest_retirement(replicas: &[Replica]) -> Retired {
    let mut all_dots: BTreeSet<Dot> = BTreeSet::new();
    for replica in replicas {
        for dot in replica.text_context().dots() {
            let _ = all_dots.insert(dot);
        }
    }

    let mut retirement = Retirement::new(replicas.iter().map(Replica::station));
    for replica in replicas {
        let mut applied = DotSet::new();
        for &dot in &all_dots {
            if !replica.order().contains(&dot) {
                let _ = applied.insert(dot);
            }
        }
        retirement
            .acknowledge(replica.station(), &applied)
            .expect("a replica's own station is on the roster");
    }
    retirement.retired()
}