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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

//! The acceptance script for stage B's fired signal (PRD 0019 stage A,
//! ruling R-17): across parallel per-kind maps, a kind reassignment was
//! three deltas on three pairs with an unclosable stale-subtree window. On
//! the one-pair node it is *one covered delta*: the fresh tag write rides a
//! context that also supersedes everything observed under the node, so a
//! peer's state steps from the old kind to the new kind atomically, whatever
//! the delivery order does around it.

use crate::metis::{Dotted, Kind, KindPlurality, NodeContent};

use super::super::{Author, TestNode};
use super::{add, page_with, seq_block, sync, tag_block};

/// The exclusive re-kind, as the write discipline documents it: one
/// [`compose_super`](crate::metis::Composer::compose_super) whose store is
/// the fresh tag write and whose supersede read is everything observed under
/// the block at the moment of the write.
fn rekind(author: &mut Author, key: u8, kind: Kind) -> Dotted<TestNode> {
    let (_, delta) = author.compose_super(
        |dot| page_with(key, tag_block(dot, kind)),
        |held| {
            held.children()
                .get(&key)
                .map(TestNode::observed)
                .unwrap_or_default()
        },
    );
    delta
}

#[test]
fn test_a_kind_reassignment_is_one_covered_delta_with_no_window() {
    let mut writer = Author::new(1);
    let mut peer = Author::new(2);

    // The block: kind Sequence, two woven elements, fully synced.
    let _ = add(&mut writer, |dot| {
        page_with(7, tag_block(dot, Kind::Sequence))
    });
    let _ = add(&mut writer, |dot| page_with(7, seq_block(dot, 1)));
    let _ = add(&mut writer, |dot| page_with(7, seq_block(dot, 2)));
    sync(&writer, &mut peer);

    let before = peer.state().store().children().get(&7).expect("alive");
    assert!(matches!(
        before.sole(),
        Ok(Some(NodeContent::Sequence(seq))) if seq.visible_len() == 2
    ));

    // The reassignment: ONE covered delta.
    let delta = rekind(&mut writer, 7, Kind::Register);

    // The peer absorbs exactly that delta and nothing else. There is no
    // intermediate state to classify: before the absorb the block is the old
    // kind whole, after it the new kind whole. The three-delta window of the
    // parallel-maps recipe does not exist here.
    let _ = peer.absorb(1, &delta);
    let block = peer.state().store().children().get(&7).expect("alive");
    let kinds = block.kinds_present();
    assert_eq!(kinds.len(), 1, "no stale evidence survives the one delta");
    assert!(kinds.contains(Kind::Register));
    assert!(matches!(
        block.sole(),
        Ok(Some(NodeContent::Register(reg))) if reg.is_empty()
    ));

    // The superseded kind's content is dead; what remains of it is ordering
    // residue (the grow-only skeleton, the Rhapsody posture), which is not
    // evidence and awaits the retention face.
    assert_eq!(block.sequence().visible_len(), 0);
    assert_eq!(block.sequence().skeleton_len(), 2);
    assert_eq!(writer.state(), peer.state(), "converged on the one delta");
}

#[test]
fn test_a_concurrent_edit_survives_a_reassignment_and_surfaces() {
    // The composite law's other half: exclusivity is a WRITE discipline, so
    // an edit the re-kinding writer never observed must survive the merge
    // (the survivor law; nothing discarded) and must surface as plurality
    // (the read; the machine chooses nothing). Resolution is a later write.
    let mut writer = Author::new(1);
    let mut editor = Author::new(2);

    let _ = add(&mut writer, |dot| {
        page_with(7, tag_block(dot, Kind::Sequence))
    });
    let _ = add(&mut writer, |dot| page_with(7, seq_block(dot, 1)));
    sync(&writer, &mut editor);

    // Concurrent: the editor extends the sequence while the writer re-kinds.
    let _ = add(&mut editor, |dot| page_with(7, seq_block(dot, 2)));
    let rekind_delta = rekind(&mut writer, 7, Kind::Register);

    let _ = editor.absorb(1, &rekind_delta);
    sync(&editor, &mut writer);
    assert_eq!(writer.state(), editor.state(), "converged");

    let block = writer.state().store().children().get(&7).expect("alive");
    let kinds = block.kinds_present();
    assert_eq!(
        kinds.len(),
        2,
        "the unobserved concurrent edit survives and is surfaced"
    );
    assert!(kinds.contains(Kind::Register) && kinds.contains(Kind::Sequence));
    assert!(matches!(block.sole(), Err(KindPlurality { .. })));
    assert_eq!(
        block.sequence().visible_len(),
        1,
        "exactly the edit the writer never saw; the observed content is gone"
    );

    // Resolution is another honest write: re-kind again, now observing the
    // straggler, and the plurality closes in one more covered delta.
    let settle = rekind(&mut writer, 7, Kind::Register);
    let _ = editor.absorb(1, &settle);
    let block = editor.state().store().children().get(&7).expect("alive");
    assert_eq!(block.kinds_present().len(), 1);
    assert!(matches!(
        block.sole(),
        Ok(Some(NodeContent::Register(reg))) if reg.is_empty()
    ));
}

#[test]
fn test_anti_entropy_heals_a_rekind_that_outran_the_content() {
    // The S190 gate-review scenario, at node grade: the one-covered-delta
    // re-kind conveys coverage of the block's sequence dots bare (no loci),
    // so a peer it outruns must still be healable by anti-entropy, tombstone
    // loci included, or an element a concurrent editor anchored to the
    // superseded dot would render at the writer and stay unreachable at the
    // peer forever. The cure is `Rhapsody::novel_to` shipping the skeleton
    // whole (the outrun-heal example at the bare seam pins the root cause).
    let mut writer = Author::new(1);
    let mut editor = Author::new(2);
    let mut peer = Author::new(3);

    let _ = add(&mut writer, |dot| {
        page_with(7, tag_block(dot, Kind::Sequence))
    });
    let (d, _) =
        writer.compose(|dot| (page_with(7, seq_block(dot, 1)), crate::metis::DotSet::new()));
    sync(&writer, &mut editor);

    // Concurrent: the editor hangs an element after d while the writer
    // re-kinds the block; then the two exchange.
    let _ = add(&mut editor, |dot| {
        let mut block = TestNode::new();
        assert!(block.weave(
            dot,
            crate::metis::Locus {
                anchor: crate::metis::Anchor::After(d.into()),
                rank: super::super::rank(9),
            }
        ));
        page_with(7, block)
    });
    let rekind_delta = rekind(&mut writer, 7, Kind::Register);
    sync(&editor, &mut writer);
    sync(&writer, &mut editor);

    // The re-kind delta outran everything else to the peer.
    let _ = peer.absorb(1, &rekind_delta);

    // Anti-entropy catch-up must equal the full state, tombstones included.
    let owed = writer.owed_to(peer.state().context());
    let _ = peer.absorb(1, &owed);
    assert_eq!(writer.state(), peer.state(), "healed whole");

    let at_writer = writer.state().store().children().get(&7).expect("alive");
    let at_peer = peer.state().store().children().get(&7).expect("alive");
    assert_eq!(
        at_writer.sequence().order(),
        at_peer.sequence().order(),
        "the surviving concurrent element is placed identically"
    );
    assert_eq!(at_writer.kinds_present(), at_peer.kinds_present());
}