1mod exit_view;
13mod installation;
14mod validation;
15
16pub use installation::ActivationTicket;
17pub use validation::ValidationTicket;
18
19use std::time::Duration;
20
21use ozzy_proto::NodeId;
22
23use crate::wire::Control;
24use crate::{
25 Admission, Configuration, Digest, InstallingView, JournalGeneration, LogSource, NormalReplica,
26 OpNumber, Prefix, PreparedOperation, PromiseTicket, ReplicaSnapshot, ReplicationError, Scope,
27 SelectedView, StartView, Status, SyncTicket, ViewChange, ViewChangeError, WriteTicket,
28};
29
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct Timing {
33 pub heartbeat: Duration,
35 pub primary_timeout: Duration,
37 pub retransmit: Duration,
39 pub election_timeout: Duration,
41 pub max_election_timeout: Duration,
43}
44
45impl Timing {
46 fn validate(self, now: Duration) -> Result<(), DriverError> {
47 if self.heartbeat.is_zero()
48 || self.retransmit.is_zero()
49 || self.heartbeat >= self.primary_timeout
50 || self.retransmit >= self.election_timeout
51 || self.election_timeout > self.max_election_timeout
52 {
53 return Err(DriverError::InvalidTiming);
54 }
55 if now
56 .checked_add(self.max_election_timeout.max(self.primary_timeout))
57 .is_none()
58 {
59 return Err(DriverError::TimeExhausted);
60 }
61 Ok(())
62 }
63}
64
65#[derive(Debug, Clone, Copy, PartialEq, Eq)]
67pub enum Action {
68 Broadcast(Control),
70 Send {
72 to: NodeId,
74 message: Control,
76 },
77 PersistPromise(PromiseTicket),
79}
80
81#[derive(Debug)]
83#[expect(
84 clippy::large_enum_variant,
85 reason = "move preallocated roles without boxing"
86)]
87pub enum Role {
88 Normal(NormalReplica),
90 ViewChanging(ViewChange),
92 Installing(InstallingView),
94}
95
96#[derive(Debug)]
101pub struct ReplicaDriver {
102 role: Option<Role>,
103 configuration: Configuration,
104 local: NodeId,
105 timing: Timing,
106 now: Duration,
107 contact_deadline: Duration,
108 progress_deadline: Duration,
109 persistence_deadline: Duration,
110 election_deadline: Duration,
111 election_delay: Duration,
112 retry_at: Duration,
113 start_pending: bool,
114 report_pending: bool,
115 commit_pending: bool,
116 activation_pending: u8,
119 exit_votes: u8,
121 exit_retry_at: Option<Duration>,
123 exit_echo: Option<(Scope, u8)>,
126 exit_echo_at: [Duration; 3],
128}
129
130impl ReplicaDriver {
131 pub fn from_normal(
134 normal: NormalReplica,
135 now: Duration,
136 timing: Timing,
137 ) -> Result<Self, DriverError> {
138 let (configuration, local) = normal.driver_identity();
139 Self::new(Role::Normal(normal), configuration, local, now, timing)
140 }
141
142 pub fn from_view_change(
145 changing: ViewChange,
146 now: Duration,
147 timing: Timing,
148 ) -> Result<Self, DriverError> {
149 let configuration = changing.configuration;
150 let local = configuration.voters()[changing.local];
151 Self::new(
152 Role::ViewChanging(changing),
153 configuration,
154 local,
155 now,
156 timing,
157 )
158 }
159
160 fn new(
161 role: Role,
162 configuration: Configuration,
163 local: NodeId,
164 now: Duration,
165 timing: Timing,
166 ) -> Result<Self, DriverError> {
167 timing.validate(now)?;
168 let changing = matches!(role, Role::ViewChanging(_));
169 let activating =
170 matches!(&role, Role::Normal(normal) if !normal.snapshot().ready_for_appends);
171 Ok(Self {
172 role: Some(role),
173 configuration,
174 local,
175 timing,
176 now,
177 contact_deadline: now + timing.primary_timeout,
178 persistence_deadline: now + timing.primary_timeout,
179 progress_deadline: now
180 + if activating {
181 timing.election_timeout
182 } else {
183 timing.primary_timeout
184 },
185 election_deadline: now + timing.election_timeout,
186 election_delay: timing.election_timeout,
187 retry_at: now
188 + if changing {
189 timing.retransmit
190 } else {
191 timing.heartbeat
192 },
193 start_pending: changing,
194 report_pending: changing,
195 commit_pending: false,
196 activation_pending: 0,
197 exit_votes: 0,
198 exit_retry_at: None,
199 exit_echo: None,
200 exit_echo_at: [Duration::ZERO; 3],
201 })
202 }
203
204 pub fn normal(&self) -> Option<&NormalReplica> {
206 match self.role.as_ref().expect("owned role") {
207 Role::Normal(normal) => Some(normal),
208 Role::ViewChanging(_) | Role::Installing(_) => None,
209 }
210 }
211
212 pub fn election_needs_sync(&self) -> bool {
214 let Some(Role::ViewChanging(changing)) = &self.role else {
215 return false;
216 };
217 let journal = changing.normal_snapshot().journal;
218 journal.written == journal.accepted && journal.written > journal.durable
219 }
220
221 pub fn scope(&self) -> Scope {
223 match self.role.as_ref().expect("owned role") {
224 Role::Normal(normal) => normal.snapshot().scope,
225 Role::ViewChanging(changing) => changing.scope(),
226 Role::Installing(installing) => installing.requested_scope(),
227 }
228 }
229
230 pub fn into_role(self) -> Role {
233 self.role.expect("owned role")
234 }
235
236 pub fn poll(&mut self, now: Duration) -> Result<Option<Action>, DriverError> {
239 self.observe_time(now)?;
240 if let Some(Role::Installing(installing)) = &self.role {
241 installing.require_pending()?;
242 if let Some(action) = self.exit_echo_action() {
243 return Ok(Some(action));
244 }
245 if now >= self.election_deadline {
246 self.request_exit()?;
247 }
248 return Ok(self.exit_action());
250 }
251 if let Some(Role::ViewChanging(changing)) = &self.role
252 && changing.normal_snapshot().status == Status::Faulted
253 {
254 return Err(ViewChangeError::Faulted.into());
255 }
256 if let Some(action) = self.exit_echo_action() {
257 return Ok(Some(action));
258 }
259 if let Some(normal) = self.normal() {
260 let snapshot = normal.snapshot();
261 if snapshot.status != Status::Normal {
262 return Err(ReplicationError::NotNormal.into());
263 }
264 let primary = self.configuration.primary(snapshot.scope.view) == self.local;
265 let outstanding =
266 snapshot.accepted != snapshot.committed || !snapshot.ready_for_appends;
267 if self.normal_timed_out(&snapshot) {
268 self.request_exit()?;
269 if self.normal().is_some() {
270 return Ok(self.exit_action());
271 }
272 } else {
273 self.withdraw_exit();
274 if !outstanding {
275 self.progress_deadline = now + self.timing.primary_timeout;
276 }
277 if primary && self.commit_pending {
278 self.commit_pending = false;
279 let message = self.normal().expect("normal role").announcement()?;
280 return Ok(Some(Action::Broadcast(Control::Commit(message))));
281 }
282 if primary && let Some(action) = self.activation_action()? {
283 return Ok(Some(action));
284 }
285 if primary && now >= self.retry_at {
286 self.retry_at = now + self.timing.heartbeat;
287 if let Some(start) = self.normal().expect("normal role").start_view()? {
288 self.commit_pending = true;
289 return Ok(Some(Action::Broadcast(Control::StartView(start))));
290 }
291 let message = self.normal().expect("normal role").announcement()?;
292 return Ok(Some(Action::Broadcast(Control::Commit(message))));
293 }
294 return Ok(None);
295 }
296 } else if now >= self.election_deadline {
297 self.request_exit()?;
298 }
299 if let Some(action) = self.exit_action() {
300 return Ok(Some(action));
301 }
302 if now >= self.retry_at {
303 self.start_pending = true;
304 self.report_pending = true;
305 self.retry_at = now + self.timing.retransmit;
306 }
307 let Role::ViewChanging(changing) = self.role.as_mut().expect("owned role") else {
308 unreachable!("normal path returned or entered election");
309 };
310 if changing.promised_view() != changing.scope().view {
311 return match changing.begin_promise() {
312 Ok(ticket) => Ok(Some(Action::PersistPromise(ticket))),
313 Err(ViewChangeError::StoragePending | ViewChangeError::PromisePending) => Ok(None),
314 Err(error) => Err(error.into()),
315 };
316 }
317 if self.start_pending {
318 let message = changing.start_message()?;
319 self.start_pending = false;
320 return Ok(Some(Action::Broadcast(Control::StartViewChange(message))));
321 }
322 if self.report_pending {
323 match changing.report() {
324 Ok(report) => {
325 self.report_pending = false;
326 let to = self.configuration.primary(report.scope.view);
327 if to != self.local {
328 return Ok(Some(Action::Send {
329 to,
330 message: Control::DoViewChange(report),
331 }));
332 }
333 }
334 Err(ViewChangeError::StartQuorumMissing) => {}
335 Err(error) => return Err(error.into()),
336 }
337 }
338 Ok(None)
339 }
340
341 pub fn receive(
354 &mut self,
355 from: NodeId,
356 message: Control,
357 now: Duration,
358 ) -> Result<Option<StartView>, DriverError> {
359 self.observe_time(now)?;
360 let voter = self.configuration.voter_index(from)?;
361 if from == self.local {
362 return Err(ReplicationError::WrongRole.into());
363 }
364 let scope = message.scope();
365 if scope
366 != (Scope {
367 view: scope.view,
368 ..self.configuration.scope()
369 })
370 {
371 return Err(ReplicationError::ScopeMismatch.into());
372 }
373 if let Control::ExitView(_) = message {
374 self.receive_exit(voter, scope)?;
375 return Ok(None);
376 }
377 if scope.view < self.scope().view {
378 return Ok(None);
379 }
380 let primary = self.configuration.primary(scope.view);
381 match message {
382 Control::Commit(_) | Control::StartView(_) if from != primary => {
383 return Err(ReplicationError::WrongRole.into());
384 }
385 Control::PrepareOk { .. }
386 | Control::PrepareRetained { .. }
387 | Control::DoViewChange(_)
388 if self.local != primary =>
389 {
390 return Err(ReplicationError::WrongRole.into());
391 }
392 _ => {}
393 }
394 if let Control::StartViewChange(_) = message {
395 match self.role.as_ref().expect("owned role") {
396 Role::Normal(normal) if normal.snapshot().status == Status::Faulted => {
397 return Err(ViewChangeError::Faulted.into());
398 }
399 Role::ViewChanging(changing)
400 if changing.normal_snapshot().status == Status::Faulted =>
401 {
402 return Err(ViewChangeError::Faulted.into());
403 }
404 Role::Installing(installing) => installing.require_pending()?,
405 Role::Normal(_) | Role::ViewChanging(_) => {}
406 }
407 if scope.view > self.scope().view {
410 self.change_view(scope.view)?;
411 }
412 if scope.view != self.scope().view {
413 return Ok(None);
414 }
415 }
416 if scope.view > self.scope().view {
417 self.change_view(scope.view)?;
418 }
419 match self.role.as_mut().expect("owned role") {
420 Role::Normal(normal) => {
421 let committed = normal.snapshot().committed;
422 match message {
423 Control::Commit(commit) => {
424 normal.receive_commit(from, commit)?;
425 self.contact_deadline = now + self.timing.primary_timeout;
426 }
427 Control::PrepareOk { ack, .. } => normal.receive_ack(from, ack)?,
428 Control::PrepareRetained { ack, .. } => {
429 normal.receive_retained_ack(from, ack)?;
430 }
431 Control::StartView(start) => {
432 normal.observe_installed_start(from, start)?;
433 self.contact_deadline = now + self.timing.primary_timeout;
434 }
435 _ => return Ok(None),
436 }
437 if let Some(prefix) = message.acknowledged()
438 && let Some(start) = normal.start_view()?
439 && prefix == start.accepted
440 && start.accepted.op < normal.snapshot().committed.op
441 {
442 self.activation_pending |= 1 << voter;
445 }
446 if normal.snapshot().committed != committed {
447 self.progress_deadline = now + self.progress_timeout();
448 }
449 }
450 Role::ViewChanging(changing) => match message {
451 Control::StartViewChange(start) => changing.receive_start(from, start)?,
452 Control::DoViewChange(report) => changing.receive_report(from, report)?,
453 Control::StartView(start) => return Ok(Some(start)),
454 Control::Commit(_)
455 | Control::PrepareOk { .. }
456 | Control::PrepareRetained { .. }
457 | Control::ExitView(_) => {}
458 },
459 Role::Installing(installing) => installing.observe_view(from, scope)?,
460 }
461 Ok(None)
462 }
463
464 pub fn complete_promise(&mut self, ticket: PromiseTicket) -> Result<(), DriverError> {
466 self.changing()?.complete_promise(ticket)?;
467 Ok(())
468 }
469
470 pub fn fail_promise(&mut self, ticket: PromiseTicket) -> Result<(), DriverError> {
472 self.changing()?.fail_promise(ticket)?;
473 Ok(())
474 }
475
476 pub fn prepare(
480 &mut self,
481 from: NodeId,
482 scope: Scope,
483 operations: &[PreparedOperation],
484 now: Duration,
485 ) -> Result<Admission, DriverError> {
486 self.observe_time(now)?;
487 self.configuration.voter_index(from)?;
488 if scope
489 != (Scope {
490 view: scope.view,
491 ..self.configuration.scope()
492 })
493 {
494 return Err(ReplicationError::ScopeMismatch.into());
495 }
496 if from != self.configuration.primary(scope.view) {
497 return Err(ReplicationError::WrongRole.into());
498 }
499 if scope.view > self.scope().view {
500 self.change_view(scope.view)?;
501 }
502 let Role::Normal(normal) = self.role.as_mut().expect("owned role") else {
503 return Err(ReplicationError::NotNormal.into());
504 };
505 let previous = normal.snapshot();
506 let admitted = normal.prepare(from, scope, operations)?;
507 if normal.snapshot().accepted != previous.accepted
508 && previous.accepted == previous.committed
509 && previous.ready_for_appends
510 {
511 self.progress_deadline = now + self.timing.primary_timeout;
512 }
513 if normal.snapshot().accepted != previous.accepted
514 && previous.accepted.op == self.storage_progress(&previous)
515 {
516 self.persistence_deadline = now + self.timing.primary_timeout;
517 }
518 self.contact_deadline = now + self.timing.primary_timeout;
519 Ok(admitted)
520 }
521
522 pub fn complete_write(&mut self, ticket: WriteTicket) -> Result<(), DriverError> {
525 match self.role.as_mut().expect("owned role") {
526 Role::Normal(normal) => normal.complete_write(ticket)?,
527 Role::ViewChanging(changing) => changing.complete_write(ticket)?,
528 Role::Installing(_) => return Err(ReplicationError::WrongRole.into()),
529 }
530 Ok(())
531 }
532
533 pub fn complete_buffered_write(
536 &mut self,
537 ticket: WriteTicket,
538 now: Duration,
539 ) -> Result<(), DriverError> {
540 if self.configuration.policy() != crate::QuorumPolicy::Replicated {
541 return Err(ReplicationError::PolicyMismatch.into());
542 }
543 self.observe_time(now)?;
544 let previous = self.normal().map(NormalReplica::snapshot);
545 self.complete_write(ticket)?;
546 if let Some(previous) = previous {
547 self.observe_normal_progress(&previous, now);
548 }
549 Ok(())
550 }
551
552 pub fn complete_durable_write(
554 &mut self,
555 ticket: WriteTicket,
556 now: Duration,
557 ) -> Result<(), DriverError> {
558 self.observe_time(now)?;
559 match self.role.as_mut().expect("owned role") {
560 Role::Normal(normal) => {
561 let previous = normal.snapshot();
562 normal.complete_durable_write(ticket)?;
563 self.observe_normal_progress(&previous, now);
564 }
565 Role::ViewChanging(changing) => changing.normal.complete_durable_write(ticket)?,
566 Role::Installing(_) => return Err(ReplicationError::WrongRole.into()),
567 }
568 Ok(())
569 }
570
571 pub fn apply_through(&mut self, through: Prefix) -> Result<(), DriverError> {
574 let Role::Normal(normal) = self.role.as_mut().expect("owned role") else {
575 return Err(ReplicationError::NotNormal.into());
576 };
577 let was_ready = normal.snapshot().ready_for_appends;
578 normal.apply_through(through)?;
579 if !was_ready && normal.snapshot().ready_for_appends {
580 self.progress_deadline = self.now + self.timing.primary_timeout;
581 self.election_delay = self.timing.election_timeout;
582 }
583 Ok(())
584 }
585
586 pub fn fail_io(&mut self, generation: JournalGeneration) -> Result<(), DriverError> {
588 match self.role.as_mut().expect("owned role") {
589 Role::Normal(normal) => normal.fail_io(generation)?,
590 Role::ViewChanging(changing) => changing.fail_io(generation)?,
591 Role::Installing(installing) => {
592 let ticket = installing.ticket();
593 if generation != ticket.generation() {
594 return Err(ViewChangeError::StaleInstallation.into());
595 }
596 installing.fail(ticket)?;
597 }
598 }
599 Ok(())
600 }
601
602 pub fn begin_sync(&self) -> Result<SyncTicket, DriverError> {
604 match self.role.as_ref().expect("owned role") {
605 Role::Normal(normal) => Ok(normal.begin_sync()?),
606 Role::ViewChanging(changing) => Ok(changing.begin_sync()?),
607 Role::Installing(_) => Err(ReplicationError::WrongRole.into()),
608 }
609 }
610
611 pub fn complete_sync(&mut self, ticket: SyncTicket, now: Duration) -> Result<(), DriverError> {
614 self.observe_time(now)?;
615 match self.role.as_mut().expect("owned role") {
616 Role::Normal(normal) => {
617 let previous = normal.snapshot();
618 normal.complete_sync(ticket)?;
619 self.observe_normal_progress(&previous, now);
620 }
621 Role::ViewChanging(changing) => changing.complete_sync(ticket)?,
622 Role::Installing(_) => return Err(ReplicationError::WrongRole.into()),
623 }
624 Ok(())
625 }
626
627 pub fn select(
630 &mut self,
631 lookup: impl FnMut(LogSource, OpNumber) -> Option<Digest>,
632 ) -> Result<SelectedView, DriverError> {
633 Ok(self.changing()?.select(lookup)?)
634 }
635
636 fn changing(&mut self) -> Result<&mut ViewChange, DriverError> {
637 match self.role.as_mut().expect("owned role") {
638 Role::ViewChanging(changing) => Ok(changing),
639 Role::Normal(_) | Role::Installing(_) => Err(ReplicationError::WrongRole.into()),
640 }
641 }
642
643 fn observe_time(&mut self, now: Duration) -> Result<(), DriverError> {
644 if now < self.now {
645 return Err(DriverError::ClockRegressed);
646 }
647 self.timing.validate(now)?;
648 self.now = now;
649 Ok(())
650 }
651
652 fn progress_timeout(&self) -> Duration {
653 if self
654 .normal()
655 .is_some_and(|normal| normal.snapshot().ready_for_appends)
656 {
657 self.timing.primary_timeout
658 } else {
659 self.election_delay
660 }
661 }
662
663 fn observe_normal_progress(&mut self, previous: &ReplicaSnapshot, now: Duration) {
664 let current = self.normal().expect("normal completion").snapshot();
665 if current.committed != previous.committed {
666 self.progress_deadline = now + self.progress_timeout();
667 }
668 if self.storage_progress(¤t) > self.storage_progress(previous) {
669 self.persistence_deadline = now + self.timing.primary_timeout;
670 }
671 }
672
673 fn normal_timed_out(&self, snapshot: &ReplicaSnapshot) -> bool {
674 let primary = self.configuration.primary(snapshot.scope.view) == self.local;
675 let outstanding = snapshot.accepted != snapshot.committed || !snapshot.ready_for_appends;
676 (!primary && self.now >= self.contact_deadline)
677 || (outstanding && self.now >= self.progress_deadline)
678 || (snapshot.accepted.op > self.storage_progress(snapshot)
679 && self.now >= self.persistence_deadline)
680 }
681
682 fn storage_progress(&self, snapshot: &ReplicaSnapshot) -> OpNumber {
683 match self.configuration.policy() {
684 crate::QuorumPolicy::Durable => snapshot.journal.durable,
685 crate::QuorumPolicy::Replicated => snapshot.journal.written,
686 }
687 }
688
689 fn next_view(&mut self) -> Result<(), DriverError> {
690 let view = self
691 .scope()
692 .view
693 .checked_add(1)
694 .ok_or(ViewChangeError::ViewExhausted)?;
695 self.change_view(view)
696 }
697
698 fn change_view(&mut self, view: u64) -> Result<(), DriverError> {
699 if let Some(Role::ViewChanging(changing)) = self.role.as_mut() {
700 changing.advance_view(view)?;
701 } else if let Some(Role::Installing(installing)) = self.role.as_mut() {
702 installing.request_view(view)?;
703 } else {
704 if self.normal().expect("normal role").snapshot().status == Status::Faulted {
705 return Err(ViewChangeError::Faulted.into());
706 }
707 let Role::Normal(normal) = self.role.take().expect("owned role") else {
708 unreachable!("normal branch");
709 };
710 self.role = Some(Role::ViewChanging(
711 normal
712 .into_view_change(view)
713 .expect("healthy role and higher view"),
714 ));
715 }
716 self.exit_votes = 0;
717 self.exit_retry_at = None;
718 self.election_deadline = self.now + self.election_delay;
719 self.retry_at = self.now + self.timing.retransmit;
720 self.start_pending = true;
721 self.report_pending = true;
722 self.commit_pending = false;
723 self.activation_pending = 0;
724 Ok(())
725 }
726}
727
728#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
730pub enum DriverError {
731 #[error("invalid replica timing intervals")]
733 InvalidTiming,
734 #[error("replica clock regressed")]
736 ClockRegressed,
737 #[error("replica clock exhausted")]
739 TimeExhausted,
740 #[error("stale replica application validation")]
742 StaleValidation,
743 #[error(transparent)]
745 Replication(#[from] ReplicationError),
746 #[error(transparent)]
748 ViewChange(#[from] ViewChangeError),
749}