Skip to main content

spacedb_sim/
strong.rs

1//! Strong tier under partition, with budgeted agents — the linearizability twin.
2//!
3//! A quorum of members backs uniqueness keys (usernames) and a finite seat pool.
4//! Budgeted agents contend for them over time while the network partitions: a window
5//! takes a minority-making set of members offline, so the coordinator can't reach a
6//! majority and **must refuse** (`Unavailable`).
7//!
8//! The simulation asserts the safety guarantees hold *regardless* of the chaos:
9//! a username is never owned by two agents, seats are never oversold, and the
10//! quorum never commits without a majority — it fails safe. It also checks the
11//! money backstop: an agent's [`Budget`] is charged per attempt and, once spent,
12//! the agent simply stops — it can never overspend. Same scenario + seed ⇒ identical
13//! [`StrongReport`].
14
15use std::collections::hash_map::Entry;
16use std::collections::HashMap;
17
18use spacedb_consistency::{QuorumGroup, StrongResult};
19use spacedb_meter::Budget;
20
21use crate::rng::Rng;
22use crate::scheduler::Scheduler;
23
24/// Everything that defines a strong-tier stress run.
25#[derive(Clone, Debug)]
26pub struct StrongScenario {
27    pub seed: u64,
28    pub members: usize,
29    pub clients: usize,
30    pub usernames: usize,
31    pub seats: u64,
32    pub horizon: u64,
33    pub op_interval: u64,
34    pub partition_interval: u64,
35    pub partition_duration: u64,
36    /// How many members a partition takes offline (≥ members − majority + 1 forces
37    /// loss of quorum).
38    pub partition_size: usize,
39    pub budget_per_client: u64,
40    pub op_cost: u64,
41}
42
43impl StrongScenario {
44    /// A 5-member quorum, 8 budgeted agents contending for 6 usernames and 20 seats,
45    /// with recurring quorum-breaking partitions.
46    pub fn new(seed: u64) -> Self {
47        Self {
48            seed,
49            members: 5,
50            clients: 8,
51            usernames: 6,
52            seats: 20,
53            horizon: 15_000,
54            op_interval: 25,
55            partition_interval: 1_500,
56            partition_duration: 400,
57            partition_size: 3, // 5 − 3 = 2 reachable < majority 3 → Unavailable
58            budget_per_client: 400_000,
59            op_cost: 1_000,
60        }
61    }
62}
63
64enum SEvent {
65    Op { client: usize },
66    Partition,
67    Heal,
68}
69
70/// The outcome of a strong-tier stress run.
71#[derive(Clone, Debug, PartialEq, Eq)]
72pub struct StrongReport {
73    pub members: usize,
74    pub commits: u64,
75    pub rejects: u64,
76    pub unavailables: u64,
77    pub seats_pool: u64,
78    pub seats_committed: u64,
79    pub final_seats_remaining: u64,
80    /// A username was committed to two different owners (must never happen).
81    pub uniqueness_violation: bool,
82    /// More seats were committed than existed (must never happen).
83    pub oversell: bool,
84    pub budget_total: u64,
85    pub total_charged: u64,
86    /// Any agent spent past its budget (must never happen).
87    pub overspend: bool,
88    pub clients_exhausted: u64,
89}
90
91struct Client {
92    budget: Budget,
93}
94
95/// A running strong-tier stress simulation.
96pub struct StrongSim {
97    scenario: StrongScenario,
98    rng: Rng,
99    scheduler: Scheduler<SEvent>,
100    quorum: QuorumGroup,
101    clients: Vec<Client>,
102    owners: HashMap<String, String>,
103    /// `agent{i}`, `user{i}` and `m{i}`, formatted once instead of per op.
104    agent_names: Vec<String>,
105    user_keys: Vec<String>,
106    member_names: Vec<String>,
107    commits: u64,
108    rejects: u64,
109    unavailables: u64,
110    seats_committed: u64,
111    uniqueness_violation: bool,
112    total_charged: u64,
113}
114
115impl StrongSim {
116    pub fn new(scenario: StrongScenario) -> Self {
117        let mut rng = Rng::seed(scenario.seed);
118        let member_names: Vec<String> = (0..scenario.members).map(|i| format!("m{i}")).collect();
119        let mut quorum = QuorumGroup::new(member_names.iter().cloned());
120        let agent_names = (0..scenario.clients).map(|i| format!("agent{i}")).collect();
121        let user_keys = (0..scenario.usernames).map(|i| format!("user{i}")).collect();
122        quorum.init_seats("seats", scenario.seats);
123
124        let clients = (0..scenario.clients)
125            .map(|_| Client {
126                budget: Budget::new(scenario.budget_per_client),
127            })
128            .collect();
129
130        let mut scheduler = Scheduler::new();
131        for i in 0..scenario.clients {
132            scheduler.schedule(1 + rng.below(scenario.op_interval), SEvent::Op { client: i });
133        }
134        scheduler.schedule(scenario.partition_interval, SEvent::Partition);
135
136        Self {
137            scenario,
138            rng,
139            scheduler,
140            quorum,
141            clients,
142            owners: HashMap::new(),
143            agent_names,
144            user_keys,
145            member_names,
146            commits: 0,
147            rejects: 0,
148            unavailables: 0,
149            seats_committed: 0,
150            uniqueness_violation: false,
151            total_charged: 0,
152        }
153    }
154
155    pub fn run(&mut self) -> StrongReport {
156        while let Some(event) = self.scheduler.pop() {
157            if self.scheduler.now() > self.scenario.horizon {
158                break;
159            }
160            self.process(event);
161        }
162
163        // Heal everything before the final read so the seat count is observable.
164        for i in 0..self.scenario.members {
165            self.quorum.heal(&self.member_names[i]);
166        }
167        let final_seats_remaining = self.quorum.seats_remaining("seats").unwrap_or(0);
168
169        let budget_total = self.scenario.budget_per_client * self.scenario.clients as u64;
170        let spent: u64 = self
171            .clients
172            .iter()
173            .map(|c| self.scenario.budget_per_client - c.budget.remaining())
174            .sum();
175        let clients_exhausted = self
176            .clients
177            .iter()
178            .filter(|c| !c.budget.can_afford(self.scenario.op_cost))
179            .count() as u64;
180
181        StrongReport {
182            members: self.scenario.members,
183            commits: self.commits,
184            rejects: self.rejects,
185            unavailables: self.unavailables,
186            seats_pool: self.scenario.seats,
187            seats_committed: self.seats_committed,
188            final_seats_remaining,
189            uniqueness_violation: self.uniqueness_violation,
190            oversell: self.seats_committed > self.scenario.seats,
191            budget_total,
192            total_charged: self.total_charged,
193            // charges must reconcile exactly with what budgets actually lost.
194            overspend: self.total_charged != spent || self.total_charged > budget_total,
195            clients_exhausted,
196        }
197    }
198
199    fn process(&mut self, event: SEvent) {
200        match event {
201            SEvent::Op { client } => {
202                let cost = self.scenario.op_cost;
203                if !self.clients[client].budget.can_afford(cost) {
204                    return; // budget spent — the agent stops (the backstop)
205                }
206                self.clients[client].budget.charge(cost).expect("affordable");
207                self.total_charged += cost;
208
209                let owner = &self.agent_names[client];
210                if self.rng.chance(0.5) {
211                    let key = &self.user_keys[self.rng.below(self.scenario.usernames as u64) as usize];
212                    match self.quorum.claim_unique(key, owner.as_bytes()) {
213                        StrongResult::Committed => {
214                            self.commits += 1;
215                            // Owned copies only for a commit, not for every op.
216                            match self.owners.entry(key.clone()) {
217                                Entry::Occupied(mut prev) => {
218                                    if prev.get() != owner {
219                                        self.uniqueness_violation = true;
220                                    }
221                                    prev.insert(owner.clone());
222                                }
223                                Entry::Vacant(slot) => {
224                                    slot.insert(owner.clone());
225                                }
226                            }
227                        }
228                        StrongResult::Rejected(_) => self.rejects += 1,
229                        StrongResult::Unavailable(_) => self.unavailables += 1,
230                    }
231                } else {
232                    match self.quorum.acquire_seat("seats") {
233                        StrongResult::Committed => {
234                            self.commits += 1;
235                            self.seats_committed += 1;
236                        }
237                        StrongResult::Rejected(_) => self.rejects += 1,
238                        StrongResult::Unavailable(_) => self.unavailables += 1,
239                    }
240                }
241
242                if self.scheduler.now() < self.scenario.horizon {
243                    let delay = self.jitter(self.scenario.op_interval);
244                    self.scheduler.schedule(delay, SEvent::Op { client });
245                }
246            }
247            SEvent::Partition => {
248                for i in 0..self.scenario.partition_size.min(self.scenario.members) {
249                    self.quorum.partition(&self.member_names[i]);
250                }
251                self.scheduler
252                    .schedule(self.scenario.partition_duration, SEvent::Heal);
253            }
254            SEvent::Heal => {
255                for i in 0..self.scenario.members {
256                    self.quorum.heal(&self.member_names[i]);
257                }
258                if self.scheduler.now() < self.scenario.horizon {
259                    self.scheduler
260                        .schedule(self.scenario.partition_interval, SEvent::Partition);
261                }
262            }
263        }
264    }
265
266    fn jitter(&mut self, base: u64) -> u64 {
267        1 + base / 2 + self.rng.below(base.max(1))
268    }
269}