1use spacedb_crdt::CrdtDoc;
14use spacedb_replica::{SyncFrame, SyncMessage};
15
16use crate::network::{NetworkModel, Partition};
17use crate::rng::Rng;
18use crate::scheduler::Scheduler;
19
20#[derive(Clone, Copy, Debug)]
23pub struct OfflineSpec {
24 pub replica: usize,
25 pub at: u64,
26 pub until: u64,
27}
28
29#[derive(Clone, Debug)]
31pub struct PartitionSpec {
32 pub group_a: Vec<usize>,
33 pub at: u64,
34 pub heal_at: u64,
35}
36
37#[derive(Clone, Debug)]
39pub struct Scenario {
40 pub seed: u64,
41 pub replicas: usize,
42 pub horizon: u64,
43 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 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#[derive(Clone, Debug, PartialEq, Eq)]
97pub struct SimReport {
98 pub replicas: usize,
99 pub writes: u64,
100 pub converged: bool,
102 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 pub worst_lag: u64,
110 pub final_value: i64,
112}
113
114pub 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 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 doc: CrdtDoc::new_unlogged(i as u64 + 1),
137 online: true,
138 })
139 .collect();
140 let mut scheduler = Scheduler::new();
141
142 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 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 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 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; return;
229 }
230 self.delivered += 1;
231 match SyncMessage::decode_ref(&frame) {
232 Ok(SyncFrame::StateVector(sv)) => {
233 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; 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 pub fn replica_online(&self) -> Vec<bool> {
322 self.replicas.iter().map(|r| r.online).collect()
323 }
324
325 pub fn current_worst_lag(&self) -> u64 {
327 self.worst_lag()
328 }
329}