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

use crate::metis::{Cut, DotStore, Dotted, Rhapsody};

use super::super::editor::Replica;
use super::readings::Readings;

/// The measured wire-byte cost of a text delta: the have-set frame of its context
/// plus the rhapsody store's own frame, both the shipped, exact `to_bytes` (S117 gave
/// the rhapsody its wire frame, so the store no longer needs a hand-estimate).
///
/// The former estimate charged a flat 41 bytes per carried dot (12 for the dot key
/// plus a hand-computed 29 for the `Locus`). The real per-locus frame is 12 for
/// the dot plus a 1-byte anchor tag plus (for a dot anchor) 12 more plus a 17-byte
/// `Kairos` frame: 42 bytes for a dot-anchored element, 30 for an origin-anchored
/// one. The estimate under-counted the `Kairos` version byte (16 payload, not the
/// full 17-byte frame) and over-counted every origin-anchored element (it always
/// charged the 12-byte anchor). It also counted only carried *store* dots, whereas
/// the real frame also carries every order tombstone in the fragment's skeleton;
/// on a fresh delta (no deletes) the two coincide. The switch is the S117 finding:
/// a dot-anchored keystroke costs 42, not 41, rhapsody bytes.
fn measured_delta_bytes(delta: &Dotted<Rhapsody>) -> usize {
    let context_bytes = delta.context().to_bytes().len();
    let store_bytes = delta.store().to_bytes().len();
    context_bytes + store_bytes
}

/// The C8 index-cost probe (S116): type a fresh N-char chain and count, per
/// keystroke, the child-index work the two `order()` strategies pay. Returns
/// `(probe_len, naive_last, cached_last, naive_total, cached_total)`.
///
/// Every count is deterministic and structural (no wall clock): the NAIVE cost
/// is the pre-S116 per-call rebuild, which regroups the whole skeleton, so at a
/// skeleton of size `k` it visits `k` entries; typing `N` chars and rendering
/// after each pays `1 + 2 + ... + N` visits (quadratic). The MAINTAINED cost is
/// the incremental bucket insert this slice added to `weave`: a `partition_point`
/// binary search over the target anchor's sibling bucket, `ceil(log2(bucket + 1))`
/// comparisons. In a typed chain each anchor has one child, so every bucket is
/// size <= 1 and the maintenance is a single comparison, near-linear in total.
pub(super) fn index_cost_probe(probe_len: usize) -> (usize, usize, usize, usize, usize) {
    let mut naive_total = 0usize;
    let mut cached_total = 0usize;
    let mut naive_last = 0usize;
    let mut cached_last = 0usize;
    for k in 0..probe_len {
        // Naive (pre-S116): the per-call rebuild regroups every locus already
        // in the skeleton plus the one being woven, so keystroke k visits k + 1.
        let naive = k + 1;
        // Maintained (S116): a typed chain searches a bucket of size <= 1 before
        // insertion, so it pays one boundary comparison per keystroke.
        let cached = 1usize;
        naive_total += naive;
        cached_total += cached;
        naive_last = naive;
        cached_last = cached;
    }
    (
        probe_len,
        naive_last,
        cached_last,
        naive_total,
        cached_total,
    )
}

/// The C8 before/after assertions (S116): the per-keystroke child-index work
/// dropped from a full skeleton regroup to a single bucket-insert comparison,
/// and the whole-probe total from quadratic to linear.
pub(super) fn assert_c8_index_costs(r: &Readings) {
    let (probe_len, naive_last, cached_last, naive_total, cached_total) =
        index_cost_probe(r.skeleton_len);
    assert!(probe_len > 0, "the probe typed a non-empty chain");
    assert_eq!(
        naive_last, probe_len,
        "naive per-call index rebuild visits the whole skeleton"
    );
    assert_eq!(
        cached_last, 1,
        "the maintained index pays one bucket-insert comparison per chain keystroke"
    );
    assert!(
        cached_last < naive_last,
        "per-keystroke index work drops with the maintained index"
    );
    assert!(
        cached_total < naive_total,
        "cached index maintenance is far below the naive quadratic rebuild total"
    );
    // The naive total is the quadratic sum 1 + 2 + ... + probe_len; the cached
    // total is linear (one comparison per keystroke).
    assert_eq!(
        naive_total,
        probe_len * (probe_len + 1) / 2,
        "naive index-construction total is quadratic in the char count"
    );
    assert_eq!(
        cached_total, probe_len,
        "cached index-maintenance total is linear in the char count"
    );
}

/// The framing-cost probe: a per-keystroke delta and a batched 50-keystroke
/// delta measured on fresh, deletion-free replicas, so the byte cost is pure
/// transport framing overhead (context frame plus store dots), uncontaminated by
/// the removal context a churned session's `delta_for` also carries.
pub(super) struct FramingProbe {
    pub(super) per_keystroke_dots: usize,
    pub(super) per_keystroke_bytes: usize,
    /// The per-keystroke delta's context frame bytes with an empty-seeded
    /// context (`text_owed_to`, the `delta_for` framing).
    pub(super) per_keystroke_context_bytes: usize,
    /// The same frame with the context floored at the peer's witnessed cut
    /// (`text_owed_since`, the `delta_for_since` framing): contiguous novelty
    /// folds into the floor, so the frame shrinks.
    pub(super) per_keystroke_floored_context_bytes: usize,
    pub(super) batch_dots: usize,
    pub(super) batch_bytes: usize,
}

pub(super) fn framing_probe() -> FramingProbe {
    let roster = [1u32, 2u32];

    // Per-keystroke: a peer holds everything up to the last char; the delta for
    // one more keystroke is exactly one store dot plus its covering context.
    let mut writer = Replica::new(1, &roster);
    let mut anchor = None;
    for _ in 0..100 {
        anchor = Some(writer.insert('a', anchor));
    }
    let prior = writer.text_context().clone();
    let peer_cut = Cut::floor_of(&prior);
    let _ = writer.insert('z', anchor);
    let per_keystroke_delta = writer.text_owed_to(&prior);
    let per_keystroke_dots = per_keystroke_delta.store().dots().count();
    let per_keystroke_bytes = measured_delta_bytes(&per_keystroke_delta);
    let per_keystroke_context_bytes = per_keystroke_delta.context().to_bytes().len();

    // A floored context must carry the whole survivor store; the measured win is
    // only the context frame.
    let per_keystroke_floored = writer.text_owed_since(&peer_cut);
    let per_keystroke_floored_context_bytes = per_keystroke_floored.context().to_bytes().len();

    // Batched: one context frame amortizes over 50 store dots.
    let mut batcher = Replica::new(2, &roster);
    let prior = batcher.text_context().clone();
    let mut anchor = None;
    for _ in 0..50 {
        anchor = Some(batcher.insert('q', anchor));
    }
    let batch_delta = batcher.text_owed_to(&prior);
    let batch_dots = batch_delta.store().dots().count();
    let batch_bytes = measured_delta_bytes(&batch_delta);

    FramingProbe {
        per_keystroke_dots,
        per_keystroke_bytes,
        per_keystroke_context_bytes,
        per_keystroke_floored_context_bytes,
        batch_dots,
        batch_bytes,
    }
}