Skip to main content

spacedb_sim/
causal.rs

1//! Causal+ under reordered propagation — the session-consistency twin.
2//!
3//! A session writes a monotonically-increasing counter on its home replica and
4//! reads from random replicas, while the home's updates propagate to the others
5//! with varied (and therefore reordering) delays. The simulation asserts the two
6//! session guarantees the causal tier promises:
7//!
8//! - **read-your-writes** — a read of the home (which holds every write the session
9//!   made) is always served and current; and
10//! - **monotonic reads** — a served read never returns a value older than one the
11//!   session already saw.
12//!
13//! And it checks the honesty contract is doing real work: reads of a lagging replica
14//! come back `Stale`, not silently old. Same scenario + seed ⇒ identical
15//! [`CausalReport`].
16
17use spacedb_consistency::{CausalSession, Outcome, Tier};
18use spacedb_crdt::CrdtDoc;
19
20use crate::rng::Rng;
21use crate::scheduler::Scheduler;
22
23/// Everything that defines a causal stress run.
24#[derive(Clone, Debug)]
25pub struct CausalScenario {
26    pub seed: u64,
27    pub replicas: usize,
28    pub horizon: u64,
29    pub write_interval: u64,
30    pub read_interval: u64,
31    pub prop_base: u64,
32    pub prop_jitter: u64,
33}
34
35impl CausalScenario {
36    /// Five replicas, frequent reads, propagation slow and jittery enough to
37    /// reorder and to leave non-home replicas lagging.
38    pub fn new(seed: u64) -> Self {
39        Self {
40            seed,
41            replicas: 5,
42            horizon: 10_000,
43            write_interval: 20,
44            read_interval: 9,
45            prop_base: 15,
46            prop_jitter: 40,
47        }
48    }
49}
50
51enum CEvent {
52    Write,
53    Read,
54    Deliver { to: usize, update: Vec<u8> },
55}
56
57/// The outcome of a causal stress run.
58#[derive(Clone, Debug, PartialEq, Eq)]
59pub struct CausalReport {
60    pub writes: u64,
61    pub home_reads: u64,
62    pub reads_fresh: u64,
63    pub reads_stale: u64,
64    /// A home read was not current (must never happen).
65    pub ryw_violation: bool,
66    /// A served read went backwards (must never happen).
67    pub monotonic_violation: bool,
68    pub final_value: i64,
69}
70
71/// A running causal-consistency stress simulation.
72pub struct CausalSim {
73    scenario: CausalScenario,
74    rng: Rng,
75    scheduler: Scheduler<CEvent>,
76    replicas: Vec<CrdtDoc>,
77    session: CausalSession,
78    writes: u64,
79    home_reads: u64,
80    reads_fresh: u64,
81    reads_stale: u64,
82    last_fresh_value: i64,
83    ryw_violation: bool,
84    monotonic_violation: bool,
85}
86
87impl CausalSim {
88    pub fn new(scenario: CausalScenario) -> Self {
89        let replicas = (0..scenario.replicas)
90            // Full-state propagation only: nothing drains a local-update log.
91            .map(|i| CrdtDoc::new_unlogged(i as u64 + 1))
92            .collect();
93        let mut scheduler = Scheduler::new();
94        scheduler.schedule(scenario.write_interval, CEvent::Write);
95        scheduler.schedule(scenario.read_interval, CEvent::Read);
96        Self {
97            rng: Rng::seed(scenario.seed),
98            scenario,
99            scheduler,
100            replicas,
101            session: CausalSession::new(),
102            writes: 0,
103            home_reads: 0,
104            reads_fresh: 0,
105            reads_stale: 0,
106            last_fresh_value: 0,
107            ryw_violation: false,
108            monotonic_violation: false,
109        }
110    }
111
112    pub fn run(&mut self) -> CausalReport {
113        while let Some(event) = self.scheduler.pop() {
114            if self.scheduler.now() > self.scenario.horizon {
115                break;
116            }
117            self.process(event);
118        }
119        CausalReport {
120            writes: self.writes,
121            home_reads: self.home_reads,
122            reads_fresh: self.reads_fresh,
123            reads_stale: self.reads_stale,
124            ryw_violation: self.ryw_violation,
125            monotonic_violation: self.monotonic_violation,
126            final_value: self.replicas[0].counter("v"),
127        }
128    }
129
130    fn process(&mut self, event: CEvent) {
131        match event {
132            CEvent::Write => {
133                // the session writes on its home replica (0) and records it
134                self.replicas[0].increment("v", 1);
135                self.session.record_write(&self.replicas[0]);
136                self.writes += 1;
137                // propagate the home's state to the others with reordering delays
138                let update = self.replicas[0].encode_full();
139                for to in 1..self.replicas.len() {
140                    let delay = self.scenario.prop_base + self.rng.below(self.scenario.prop_jitter + 1);
141                    self.scheduler
142                        .schedule(delay, CEvent::Deliver { to, update: update.clone() });
143                }
144                if self.scheduler.now() < self.scenario.horizon {
145                    self.scheduler.schedule(self.scenario.write_interval, CEvent::Write);
146                }
147            }
148            CEvent::Deliver { to, update } => {
149                let _ = self.replicas[to].apply_update(&update);
150            }
151            CEvent::Read => {
152                let r = self.rng.below(self.replicas.len() as u64) as usize;
153                let outcome = self.session.read(&self.replicas[r]);
154                match outcome {
155                    Outcome::Committed(Tier::Causal) => {
156                        self.reads_fresh += 1;
157                        let value = self.replicas[r].counter("v");
158                        // monotonic reads: never serve a value older than one seen
159                        if value < self.last_fresh_value {
160                            self.monotonic_violation = true;
161                        }
162                        self.last_fresh_value = value;
163                        // read-your-writes: the home holds every write, so a home
164                        // read is always current
165                        if r == 0 {
166                            self.home_reads += 1;
167                            if value != self.replicas[0].counter("v") {
168                                self.ryw_violation = true;
169                            }
170                        }
171                    }
172                    Outcome::Stale { .. } => self.reads_stale += 1,
173                    _ => {}
174                }
175                // a home read that came back anything but fresh breaks read-your-writes
176                if r == 0 && !matches!(outcome, Outcome::Committed(Tier::Causal)) {
177                    self.ryw_violation = true;
178                    self.home_reads += 1;
179                }
180                if self.scheduler.now() < self.scenario.horizon {
181                    self.scheduler.schedule(self.scenario.read_interval, CEvent::Read);
182                }
183            }
184        }
185    }
186}