Skip to main content

spacedb_sim/
sim.rs

1//! The simulation — a population of real CRDT replicas gossiping under the network
2//! model, driven by the deterministic event loop.
3//!
4//! Each replica owns a real [`CrdtDoc`]. The workload has every replica increment a
5//! shared PN-counter `"writes"`; the global truth is the total number of writes
6//! performed, and a replica has *converged* exactly when its counter equals that
7//! total — a strong, value-level convergence signal. Replicas reconcile with the
8//! **real two-message anti-entropy protocol** ([`SyncMessage`]): a gossip round
9//! sends a peer the sender's state vector, and the peer replies with the exact
10//! delta the sender lacks ([`CrdtDoc::encode_update_since`]). Because gossip repeats,
11//! the protocol heals dropped messages and partitions on its own.
12
13use spacedb_crdt::CrdtDoc;
14use spacedb_replica::{SyncFrame, SyncMessage};
15
16use crate::network::{NetworkModel, Partition};
17use crate::rng::Rng;
18use crate::scheduler::Scheduler;
19
20/// A window during which one replica is offline (it still writes locally —
21/// local-first — and re-syncs on return).
22#[derive(Clone, Copy, Debug)]
23pub struct OfflineSpec {
24    pub replica: usize,
25    pub at: u64,
26    pub until: u64,
27}
28
29/// A network partition window splitting `group_a` from everyone else.
30#[derive(Clone, Debug)]
31pub struct PartitionSpec {
32    pub group_a: Vec<usize>,
33    pub at: u64,
34    pub heal_at: u64,
35}
36
37/// Everything that defines a run. Same scenario + same seed ⇒ identical result.
38#[derive(Clone, Debug)]
39pub struct Scenario {
40    pub seed: u64,
41    pub replicas: usize,
42    pub horizon: u64,
43    /// Writes are generated until this time; after it the system only reconciles.
44    pub write_until: u64,
45    pub write_interval: u64,
46    pub gossip_interval: u64,
47    pub probe_interval: u64,
48    pub network: NetworkModel,
49    pub partition: Option<PartitionSpec>,
50    pub offline: Vec<OfflineSpec>,
51}
52
53impl Scenario {
54    /// A baseline scenario: `replicas` replicas on a perfect network, writing for
55    /// the first fifth of a 20 000-tick horizon.
56    pub fn new(seed: u64, replicas: usize) -> Self {
57        Self {
58            seed,
59            replicas,
60            horizon: 20_000,
61            write_until: 1_000,
62            write_interval: 10,
63            gossip_interval: 5,
64            probe_interval: 50,
65            network: NetworkModel::perfect(),
66            partition: None,
67            offline: Vec::new(),
68        }
69    }
70
71    fn heal_settled_at(&self) -> u64 {
72        self.partition.as_ref().map(|p| p.heal_at).unwrap_or(0)
73    }
74
75    fn offline_settled_at(&self) -> u64 {
76        self.offline.iter().map(|o| o.until).max().unwrap_or(0)
77    }
78}
79
80enum Event {
81    Write { replica: usize },
82    Gossip { replica: usize },
83    Deliver { to: usize, from: usize, frame: Vec<u8> },
84    SetOnline { replica: usize, online: bool },
85    Partition,
86    Heal,
87    Probe,
88}
89
90struct Replica {
91    doc: CrdtDoc,
92    online: bool,
93}
94
95/// The outcome of a run — the same for any two runs of the same scenario.
96#[derive(Clone, Debug, PartialEq, Eq)]
97pub struct SimReport {
98    pub replicas: usize,
99    pub writes: u64,
100    /// Whether every replica's counter equals the global write total.
101    pub converged: bool,
102    /// The first tick (after writes/partitions settled) at which it converged.
103    pub converged_at: Option<u64>,
104    pub messages_sent: u64,
105    pub messages_dropped: u64,
106    pub messages_delivered: u64,
107    pub sync_rounds: u64,
108    /// The largest number of writes any single replica is still missing.
109    pub worst_lag: u64,
110    /// The converged value held by replica 0 (equals `writes` on success).
111    pub final_value: i64,
112}
113
114/// A running simulation.
115pub struct Simulation {
116    scenario: Scenario,
117    rng: Rng,
118    scheduler: Scheduler<Event>,
119    replicas: Vec<Replica>,
120    partition: Option<Partition>,
121    sent: u64,
122    dropped: u64,
123    delivered: u64,
124    sync_rounds: u64,
125    writes: u64,
126    converged_at: Option<u64>,
127}
128
129impl Simulation {
130    /// Build a simulation and seed its initial events.
131    pub fn new(scenario: Scenario) -> Self {
132        let mut rng = Rng::seed(scenario.seed);
133        let replicas = (0..scenario.replicas)
134            .map(|i| Replica {
135                // Anti-entropy by state vector only: nothing drains a local-update log.
136                doc: CrdtDoc::new_unlogged(i as u64 + 1),
137                online: true,
138            })
139            .collect();
140        let mut scheduler = Scheduler::new();
141
142        // Stagger the first write/gossip per replica so they don't all fire on the
143        // same tick (deterministic: rng is consumed in index order).
144        for i in 0..scenario.replicas {
145            scheduler.schedule(1 + rng.below(scenario.write_interval), Event::Write { replica: i });
146            scheduler.schedule(1 + rng.below(scenario.gossip_interval), Event::Gossip { replica: i });
147        }
148        scheduler.schedule(scenario.probe_interval, Event::Probe);
149
150        if let Some(p) = &scenario.partition {
151            scheduler.schedule_at(p.at, Event::Partition);
152            scheduler.schedule_at(p.heal_at, Event::Heal);
153        }
154        for o in &scenario.offline {
155            scheduler.schedule_at(o.at, Event::SetOnline { replica: o.replica, online: false });
156            scheduler.schedule_at(o.until, Event::SetOnline { replica: o.replica, online: true });
157        }
158
159        Self {
160            scenario,
161            rng,
162            scheduler,
163            replicas,
164            partition: None,
165            sent: 0,
166            dropped: 0,
167            delivered: 0,
168            sync_rounds: 0,
169            writes: 0,
170            converged_at: None,
171        }
172    }
173
174    /// Run to the horizon and report.
175    pub fn run(&mut self) -> SimReport {
176        while let Some(event) = self.scheduler.pop() {
177            if self.scheduler.now() > self.scenario.horizon {
178                break;
179            }
180            self.process(event);
181            // Once converged the system is quiescent (writes have stopped, every
182            // replica is current) — stop rather than gossip pointlessly to the
183            // horizon. Deterministic: convergence is detected at a fixed tick.
184            if self.converged_at.is_some() {
185                break;
186            }
187        }
188        SimReport {
189            replicas: self.replicas.len(),
190            writes: self.writes,
191            converged: self.all_converged(),
192            converged_at: self.converged_at,
193            messages_sent: self.sent,
194            messages_dropped: self.dropped,
195            messages_delivered: self.delivered,
196            sync_rounds: self.sync_rounds,
197            worst_lag: self.worst_lag(),
198            final_value: self.replicas[0].doc.counter("writes"),
199        }
200    }
201
202    fn process(&mut self, event: Event) {
203        match event {
204            Event::Write { replica } => {
205                // Local-first: a replica writes whether or not it is online.
206                self.replicas[replica].doc.increment("writes", 1);
207                self.writes += 1;
208                if self.scheduler.now() < self.scenario.write_until {
209                    self.scheduler
210                        .schedule(self.scenario.write_interval, Event::Write { replica });
211                }
212            }
213            Event::Gossip { replica } => {
214                if self.replicas[replica].online {
215                    if let Some(peer) = self.pick_peer(replica) {
216                        let frame = SyncMessage::state_vector_frame(&self.replicas[replica].doc);
217                        self.try_send(replica, peer, frame);
218                    }
219                }
220                if self.scheduler.now() < self.scenario.horizon {
221                    self.scheduler
222                        .schedule(self.scenario.gossip_interval, Event::Gossip { replica });
223                }
224            }
225            Event::Deliver { to, from, frame } => {
226                if !self.replicas[to].online {
227                    self.dropped += 1; // can't receive while offline
228                    return;
229                }
230                self.delivered += 1;
231                match SyncMessage::decode_ref(&frame) {
232                    Ok(SyncFrame::StateVector(sv)) => {
233                        // Reply with exactly the delta `from` is missing.
234                        if let Ok(delta) = self.replicas[to].doc.encode_update_since(sv) {
235                            if !delta.is_empty() {
236                                self.sync_rounds += 1;
237                                let reply = SyncMessage::Update(delta).into_frame();
238                                self.try_send(to, from, reply);
239                            }
240                        }
241                    }
242                    Ok(SyncFrame::Update(update)) => {
243                        let _ = self.replicas[to].doc.apply_update(update);
244                    }
245                    Err(_) => {}
246                }
247            }
248            Event::SetOnline { replica, online } => {
249                self.replicas[replica].online = online;
250            }
251            Event::Partition => {
252                if let Some(p) = &self.scenario.partition {
253                    self.partition = Some(Partition::split(self.replicas.len(), &p.group_a));
254                }
255            }
256            Event::Heal => {
257                self.partition = None;
258            }
259            Event::Probe => {
260                let now = self.scheduler.now();
261                let settled = now >= self.scenario.write_until
262                    && now >= self.scenario.heal_settled_at()
263                    && now >= self.scenario.offline_settled_at();
264                if self.converged_at.is_none() && settled && self.all_online() && self.all_converged() {
265                    self.converged_at = Some(now);
266                }
267                if self.converged_at.is_none() && now < self.scenario.horizon {
268                    self.scheduler.schedule(self.scenario.probe_interval, Event::Probe);
269                }
270            }
271        }
272    }
273
274    fn try_send(&mut self, from: usize, to: usize, frame: Vec<u8>) {
275        self.sent += 1;
276        if let Some(p) = &self.partition {
277            if !p.connected(from, to) {
278                self.dropped += 1; // severed by the partition
279                return;
280            }
281        }
282        if self.scenario.network.drops(&mut self.rng) {
283            self.dropped += 1;
284            return;
285        }
286        let delay = self.scenario.network.delay(&mut self.rng);
287        self.scheduler.schedule(delay, Event::Deliver { to, from, frame });
288    }
289
290    fn pick_peer(&mut self, replica: usize) -> Option<usize> {
291        let n = self.replicas.len();
292        if n < 2 {
293            return None;
294        }
295        let mut peer = self.rng.below(n as u64) as usize;
296        if peer == replica {
297            peer = (peer + 1) % n;
298        }
299        Some(peer)
300    }
301
302    fn all_online(&self) -> bool {
303        self.replicas.iter().all(|r| r.online)
304    }
305
306    fn all_converged(&self) -> bool {
307        let target = self.writes as i64;
308        self.replicas.iter().all(|r| r.doc.counter("writes") == target)
309    }
310
311    fn worst_lag(&self) -> u64 {
312        let target = self.writes as i64;
313        self.replicas
314            .iter()
315            .map(|r| (target - r.doc.counter("writes")).max(0) as u64)
316            .max()
317            .unwrap_or(0)
318    }
319
320    /// Per-replica liveness (for building a console snapshot).
321    pub fn replica_online(&self) -> Vec<bool> {
322        self.replicas.iter().map(|r| r.online).collect()
323    }
324
325    /// The largest write-deficit across replicas, right now.
326    pub fn current_worst_lag(&self) -> u64 {
327        self.worst_lag()
328    }
329}