1use std::collections::BTreeMap;
15
16use thiserror::Error;
17
18use crate::{
19 BarrierResultHeads, BarrierResultHeadsError, Checkpoint, Failure, JournalHead, NodeActivation,
20 NodeActivationError, NodeAttempt, NodeAttemptHistoryError, NodeAttemptHistoryVerifier,
21 NodeAttemptOutcome, NodeAttemptStartHead, NodeAttemptStatus, NodeId, PendingNodeResult,
22 PendingNodeResultHead, RetryAdvice, RunFence, Timestamp,
23};
24
25#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
27#[non_exhaustive]
28pub enum NodeDispatchReason {
29 FirstAttempt,
31 SupersededAttempt,
33 SafeRetry,
35}
36
37#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
39#[non_exhaustive]
40pub enum RecoveryNodeKind {
41 Completed,
43 Dispatchable,
45 Deferred,
47 InFlight,
49 Failed,
51 Exhausted,
53}
54
55#[allow(clippy::large_enum_variant)]
57#[derive(Clone, Debug)]
58#[non_exhaustive]
59pub enum RecoveryNode {
60 Completed {
62 activation: NodeActivation,
64 result: PendingNodeResultHead,
66 },
67 Dispatchable {
69 activation: NodeActivation,
71 reason: NodeDispatchReason,
73 },
74 Deferred {
77 activation: NodeActivation,
79 not_before: Timestamp,
81 },
82 InFlight {
85 activation: NodeActivation,
87 attempt: NodeAttemptStartHead,
89 },
90 Failed {
92 activation: NodeActivation,
94 failure: Failure,
96 },
97 Exhausted {
99 activation: NodeActivation,
101 attempt: NodeAttemptStartHead,
103 failure: Option<Failure>,
105 },
106}
107
108impl RecoveryNode {
109 #[must_use]
111 pub const fn kind(&self) -> RecoveryNodeKind {
112 match self {
113 Self::Completed { .. } => RecoveryNodeKind::Completed,
114 Self::Dispatchable { .. } => RecoveryNodeKind::Dispatchable,
115 Self::Deferred { .. } => RecoveryNodeKind::Deferred,
116 Self::InFlight { .. } => RecoveryNodeKind::InFlight,
117 Self::Failed { .. } => RecoveryNodeKind::Failed,
118 Self::Exhausted { .. } => RecoveryNodeKind::Exhausted,
119 }
120 }
121
122 #[must_use]
124 pub const fn activation(&self) -> &NodeActivation {
125 match self {
126 Self::Completed { activation, .. }
127 | Self::Dispatchable { activation, .. }
128 | Self::Deferred { activation, .. }
129 | Self::InFlight { activation, .. }
130 | Self::Failed { activation, .. }
131 | Self::Exhausted { activation, .. } => activation,
132 }
133 }
134
135 #[must_use]
137 pub const fn dispatch_reason(&self) -> Option<NodeDispatchReason> {
138 match self {
139 Self::Dispatchable { reason, .. } => Some(*reason),
140 _ => None,
141 }
142 }
143
144 #[must_use]
146 pub const fn result(&self) -> Option<&PendingNodeResultHead> {
147 match self {
148 Self::Completed { result, .. } => Some(result),
149 _ => None,
150 }
151 }
152
153 #[must_use]
155 pub const fn not_before(&self) -> Option<Timestamp> {
156 match self {
157 Self::Deferred { not_before, .. } => Some(*not_before),
158 _ => None,
159 }
160 }
161
162 #[must_use]
164 pub const fn in_flight_attempt(&self) -> Option<&NodeAttemptStartHead> {
165 match self {
166 Self::InFlight { attempt, .. } => Some(attempt),
167 _ => None,
168 }
169 }
170
171 #[must_use]
173 pub const fn failure(&self) -> Option<&Failure> {
174 match self {
175 Self::Failed { failure, .. } => Some(failure),
176 Self::Exhausted { failure, .. } => failure.as_ref(),
177 _ => None,
178 }
179 }
180
181 #[must_use]
184 pub const fn exhausted_attempt(&self) -> Option<&NodeAttemptStartHead> {
185 match self {
186 Self::Exhausted { attempt, .. } => Some(attempt),
187 _ => None,
188 }
189 }
190}
191
192#[derive(Clone, Debug)]
194pub struct ReadyNodeRecoveryPlan {
195 checkpoint: Checkpoint,
196 fence: RunFence,
197 journal_head: JournalHead,
198 observed_at: Timestamp,
199 nodes: Box<[RecoveryNode]>,
200}
201
202impl ReadyNodeRecoveryPlan {
203 #[must_use]
205 pub const fn checkpoint(&self) -> &Checkpoint {
206 &self.checkpoint
207 }
208
209 #[must_use]
211 pub const fn fence(&self) -> &RunFence {
212 &self.fence
213 }
214
215 #[must_use]
217 pub const fn journal_head(&self) -> &JournalHead {
218 &self.journal_head
219 }
220
221 #[must_use]
223 pub const fn observed_at(&self) -> Timestamp {
224 self.observed_at
225 }
226
227 #[must_use]
229 pub const fn nodes(&self) -> &[RecoveryNode] {
230 &self.nodes
231 }
232
233 #[must_use]
235 pub fn is_barrier_ready(&self) -> bool {
236 !self.nodes.is_empty()
237 && self
238 .nodes
239 .iter()
240 .all(|node| node.kind() == RecoveryNodeKind::Completed)
241 }
242
243 pub fn barrier_result_heads(
251 &self,
252 ) -> Result<Option<BarrierResultHeads>, BarrierResultHeadsError> {
253 if !self.is_barrier_ready() {
254 return Ok(None);
255 }
256 let results = self.nodes.iter().filter_map(RecoveryNode::result).cloned();
257 BarrierResultHeads::try_new(results).map(Some)
258 }
259
260 #[must_use]
263 pub fn earliest_deferred_at(&self) -> Option<Timestamp> {
264 self.nodes.iter().filter_map(RecoveryNode::not_before).min()
265 }
266}
267
268#[derive(Clone, Debug)]
269struct RecoveryEntry {
270 activation: NodeActivation,
271 result: Option<PendingNodeResultHead>,
272 attempts: NodeAttemptHistoryVerifier,
273 attempt_count: usize,
274}
275
276#[derive(Clone, Debug)]
283pub struct ReadyNodeRecoveryPlanner {
284 checkpoint: Checkpoint,
285 fence: RunFence,
286 entries: BTreeMap<NodeId, RecoveryEntry>,
287}
288
289impl ReadyNodeRecoveryPlanner {
290 pub const MAX_ATTEMPTS_PER_NODE: usize = 64;
296
297 pub fn new(checkpoint: Checkpoint, fence: RunFence) -> Result<Self, ReadyNodeRecoveryError> {
304 if fence.tenant_id() != checkpoint.tenant_id() {
305 return Err(ReadyNodeRecoveryError::FenceTenantMismatch);
306 }
307 if fence.run_id() != checkpoint.run_id() {
308 return Err(ReadyNodeRecoveryError::FenceRunMismatch);
309 }
310 let mut entries = BTreeMap::new();
311 for node_id in checkpoint.ready_nodes().iter().cloned() {
312 let activation = NodeActivation::for_ready_root(&checkpoint, node_id.clone())
313 .map_err(ReadyNodeRecoveryError::activation)?;
314 entries.insert(
315 node_id,
316 RecoveryEntry {
317 activation,
318 result: None,
319 attempts: NodeAttemptHistoryVerifier::new(),
320 attempt_count: 0,
321 },
322 );
323 }
324 Ok(Self {
325 checkpoint,
326 fence,
327 entries,
328 })
329 }
330
331 pub fn observe_result(
340 &mut self,
341 result: &PendingNodeResult,
342 ) -> Result<(), ReadyNodeRecoveryError> {
343 let activation = result.intent().activation();
344 let Some(entry) = self.entries.get_mut(activation.node_id()) else {
345 return Err(ReadyNodeRecoveryError::UnexpectedResult {
346 node_id: activation.node_id().clone(),
347 });
348 };
349 if activation != &entry.activation {
350 return Err(ReadyNodeRecoveryError::UnexpectedResult {
351 node_id: activation.node_id().clone(),
352 });
353 }
354 if entry.result.is_some() {
355 return Err(ReadyNodeRecoveryError::DuplicateResult {
356 node_id: activation.node_id().clone(),
357 });
358 }
359 entry.result = Some(result.head());
360 Ok(())
361 }
362
363 pub fn observe_attempt(&mut self, attempt: &NodeAttempt) -> Result<(), ReadyNodeRecoveryError> {
371 let activation = attempt.start().activation();
372 let Some(entry) = self.entries.get_mut(activation.node_id()) else {
373 return Err(ReadyNodeRecoveryError::UnexpectedAttempt {
374 node_id: activation.node_id().clone(),
375 });
376 };
377 if activation != &entry.activation {
378 return Err(ReadyNodeRecoveryError::UnexpectedAttempt {
379 node_id: activation.node_id().clone(),
380 });
381 }
382 if entry.attempt_count >= Self::MAX_ATTEMPTS_PER_NODE {
383 return Err(ReadyNodeRecoveryError::AttemptLimitExceeded {
384 node_id: activation.node_id().clone(),
385 maximum: Self::MAX_ATTEMPTS_PER_NODE,
386 });
387 }
388 entry.attempts.verify_next(attempt).map_err(|source| {
389 ReadyNodeRecoveryError::AttemptHistory {
390 node_id: activation.node_id().clone(),
391 source,
392 }
393 })?;
394 entry.attempt_count += 1;
395 Ok(())
396 }
397
398 #[must_use]
404 pub fn activations(&self) -> Vec<NodeActivation> {
405 self.entries
406 .values()
407 .map(|entry| entry.activation.clone())
408 .collect()
409 }
410
411 pub fn finish(
419 self,
420 journal_head: JournalHead,
421 observed_at: Timestamp,
422 ) -> Result<ReadyNodeRecoveryPlan, ReadyNodeRecoveryError> {
423 validate_observation(&self, &journal_head, observed_at)?;
424 let mut nodes = Vec::with_capacity(self.entries.len());
425 for (node_id, entry) in self.entries {
426 nodes.push(classify_entry(node_id, entry, &self.fence, observed_at)?);
427 }
428 Ok(ReadyNodeRecoveryPlan {
429 checkpoint: self.checkpoint,
430 fence: self.fence,
431 journal_head,
432 observed_at,
433 nodes: nodes.into_boxed_slice(),
434 })
435 }
436}
437
438#[derive(Clone, Debug, Eq, Error, PartialEq)]
440#[non_exhaustive]
441pub enum ReadyNodeRecoveryError {
442 #[error("ready-node recovery fence crosses the checkpoint tenant boundary")]
444 FenceTenantMismatch,
445 #[error("ready-node recovery fence does not belong to the checkpoint run")]
447 FenceRunMismatch,
448 #[error("ready-node activation derivation failed: {source}")]
450 Activation {
451 #[source]
453 source: NodeActivationError,
454 },
455 #[error("pending result for node {node_id:?} is not part of the recovery ready set")]
457 UnexpectedResult {
458 node_id: NodeId,
460 },
461 #[error("pending result for node {node_id:?} was observed more than once")]
463 DuplicateResult {
464 node_id: NodeId,
466 },
467 #[error("physical attempt for node {node_id:?} is not part of the recovery ready set")]
469 UnexpectedAttempt {
470 node_id: NodeId,
472 },
473 #[error("physical attempt history for node {node_id:?} is invalid: {source}")]
475 AttemptHistory {
476 node_id: NodeId,
478 #[source]
480 source: NodeAttemptHistoryError,
481 },
482 #[error("physical attempt history for node {node_id:?} exceeds {maximum} records")]
484 AttemptLimitExceeded {
485 node_id: NodeId,
487 maximum: usize,
489 },
490 #[error("physical attempt history for node {node_id:?} is newer than the recovery fence")]
492 CurrentFenceBehindHistory {
493 node_id: NodeId,
495 },
496 #[error("physical attempt history for node {node_id:?} conflicts with the recovery fence")]
498 CurrentFenceConflict {
499 node_id: NodeId,
501 },
502 #[error("recovery fence reused an earlier worker attempt for node {node_id:?}")]
504 CurrentFenceAttemptReused {
505 node_id: NodeId,
507 },
508 #[error("successful physical attempt for node {node_id:?} has no pending result")]
510 SucceededWithoutResult {
511 node_id: NodeId,
513 },
514 #[error("successful physical attempt for node {node_id:?} references another result")]
516 ResultAttemptMismatch {
517 node_id: NodeId,
519 },
520 #[error("physical node failure for node {node_id:?} has unsupported retry advice")]
522 UnsupportedRetryAdvice {
523 node_id: NodeId,
525 },
526 #[error("physical node retry time for node {node_id:?} exceeds the timestamp range")]
528 RetryNotBeforeOutOfRange {
529 node_id: NodeId,
531 },
532 #[error("ready-node recovery journal observation crosses the checkpoint tenant boundary")]
534 ObservationTenantMismatch,
535 #[error("ready-node recovery journal observation does not belong to the checkpoint run")]
537 ObservationRunMismatch,
538 #[error("ready-node recovery journal observation precedes the checkpoint")]
540 ObservationBeforeCheckpoint,
541 #[error("ready-node recovery journal observation precedes durable node evidence")]
543 ObservationBeforeEvidence,
544 #[error("ready-node recovery database clock precedes its journal observation")]
546 ObservationClockRegression,
547}
548
549impl ReadyNodeRecoveryError {
550 const fn activation(source: NodeActivationError) -> Self {
551 Self::Activation { source }
552 }
553}
554
555fn classify_entry(
556 node_id: NodeId,
557 entry: RecoveryEntry,
558 current_fence: &RunFence,
559 observed_at: Timestamp,
560) -> Result<RecoveryNode, ReadyNodeRecoveryError> {
561 let RecoveryEntry {
562 activation,
563 result,
564 attempts,
565 attempt_count,
566 } = entry;
567 let latest = attempts.last();
568
569 if let Some(result) = result {
570 validate_current_fence(&node_id, result.fence(), current_fence)?;
571 if let Some(attempt) = latest {
572 let Some(completion) = attempt.completion() else {
573 return Err(ReadyNodeRecoveryError::ResultAttemptMismatch { node_id });
574 };
575 if completion.outcome().result() != Some(&result) {
576 return Err(ReadyNodeRecoveryError::ResultAttemptMismatch { node_id });
577 }
578 }
579 return Ok(RecoveryNode::Completed { activation, result });
580 }
581
582 let Some(attempt) = latest else {
583 return Ok(RecoveryNode::Dispatchable {
584 activation,
585 reason: NodeDispatchReason::FirstAttempt,
586 });
587 };
588 validate_current_fence(&node_id, attempt.start().fence(), current_fence)?;
589
590 match attempt.status() {
591 NodeAttemptStatus::Executing => {
592 if attempt.start().fence() == current_fence {
593 Ok(RecoveryNode::InFlight {
594 activation,
595 attempt: attempt.start().head(),
596 })
597 } else if attempt_count >= ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE {
598 Ok(RecoveryNode::Exhausted {
599 activation,
600 attempt: attempt.start().head(),
601 failure: None,
602 })
603 } else {
604 Ok(RecoveryNode::Dispatchable {
605 activation,
606 reason: NodeDispatchReason::SupersededAttempt,
607 })
608 }
609 }
610 NodeAttemptStatus::Succeeded => {
611 Err(ReadyNodeRecoveryError::SucceededWithoutResult { node_id })
612 }
613 NodeAttemptStatus::Failed => {
614 let completion = attempt.completion().ok_or_else(|| {
615 ReadyNodeRecoveryError::SucceededWithoutResult {
616 node_id: node_id.clone(),
617 }
618 })?;
619 let NodeAttemptOutcome::Failed { failure } = completion.outcome() else {
620 return Err(ReadyNodeRecoveryError::SucceededWithoutResult { node_id });
621 };
622 match failure.retry_advice() {
623 RetryAdvice::Never => Ok(RecoveryNode::Failed {
624 activation,
625 failure: failure.clone(),
626 }),
627 RetryAdvice::SafeAfter { delay } => {
628 if attempt_count >= ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE {
629 return Ok(RecoveryNode::Exhausted {
630 activation,
631 attempt: attempt.start().head(),
632 failure: Some(failure.clone()),
633 });
634 }
635 let not_before =
636 retry_not_before(completion.journal_head().recorded_at(), delay.as_i64())
637 .ok_or_else(|| ReadyNodeRecoveryError::RetryNotBeforeOutOfRange {
638 node_id: node_id.clone(),
639 })?;
640 if observed_at >= not_before {
641 Ok(RecoveryNode::Dispatchable {
642 activation,
643 reason: NodeDispatchReason::SafeRetry,
644 })
645 } else {
646 Ok(RecoveryNode::Deferred {
647 activation,
648 not_before,
649 })
650 }
651 }
652 RetryAdvice::ReconcileFirst => {
653 Err(ReadyNodeRecoveryError::UnsupportedRetryAdvice { node_id })
654 }
655 }
656 }
657 }
658}
659
660fn validate_observation(
661 planner: &ReadyNodeRecoveryPlanner,
662 journal_head: &JournalHead,
663 observed_at: Timestamp,
664) -> Result<(), ReadyNodeRecoveryError> {
665 if journal_head.tenant_id() != planner.checkpoint.tenant_id() {
666 return Err(ReadyNodeRecoveryError::ObservationTenantMismatch);
667 }
668 if journal_head.run_id() != planner.checkpoint.run_id() {
669 return Err(ReadyNodeRecoveryError::ObservationRunMismatch);
670 }
671 let checkpoint_head = planner.checkpoint.journal_head();
672 if journal_head.sequence() < checkpoint_head.sequence()
673 || journal_head.recorded_at() < checkpoint_head.recorded_at()
674 {
675 return Err(ReadyNodeRecoveryError::ObservationBeforeCheckpoint);
676 }
677 if observed_at < journal_head.recorded_at() {
678 return Err(ReadyNodeRecoveryError::ObservationClockRegression);
679 }
680 for entry in planner.entries.values() {
681 let result_head = entry
682 .result
683 .as_ref()
684 .map(PendingNodeResultHead::journal_head);
685 let attempt_head = entry.attempts.last().map(|attempt| {
686 attempt.completion().map_or_else(
687 || attempt.start().journal_head(),
688 |value| value.journal_head(),
689 )
690 });
691 if result_head.into_iter().chain(attempt_head).any(|evidence| {
692 evidence.sequence() > journal_head.sequence()
693 || evidence.recorded_at() > journal_head.recorded_at()
694 }) {
695 return Err(ReadyNodeRecoveryError::ObservationBeforeEvidence);
696 }
697 }
698 Ok(())
699}
700
701fn validate_current_fence(
702 node_id: &NodeId,
703 historical: &RunFence,
704 current: &RunFence,
705) -> Result<(), ReadyNodeRecoveryError> {
706 if historical.epoch() > current.epoch() {
707 return Err(ReadyNodeRecoveryError::CurrentFenceBehindHistory {
708 node_id: node_id.clone(),
709 });
710 }
711 if historical.epoch() == current.epoch() && historical.attempt_id() != current.attempt_id() {
712 return Err(ReadyNodeRecoveryError::CurrentFenceConflict {
713 node_id: node_id.clone(),
714 });
715 }
716 if historical.epoch() < current.epoch() && historical.attempt_id() == current.attempt_id() {
717 return Err(ReadyNodeRecoveryError::CurrentFenceAttemptReused {
718 node_id: node_id.clone(),
719 });
720 }
721 Ok(())
722}
723
724fn retry_not_before(failed_at: Timestamp, delay_millis: i64) -> Option<Timestamp> {
725 let micros = i128::from(failed_at.unix_micros())
726 .checked_add(i128::from(delay_millis).checked_mul(1_000)?)?;
727 let micros = i64::try_from(micros).ok()?;
728 Timestamp::from_unix_micros(micros).ok()
729}
730
731#[cfg(test)]
732mod tests {
733 use proptest::prelude::*;
734 use serde_json::from_value;
735
736 use super::*;
737 use crate::{
738 AttemptId, BudgetUsage, CheckpointId, CheckpointWrite, Digest, DurationMillis, EventId,
739 FailureCategory, FailureCode, FailureId, FailureMessage, FailureOrigin, FencingEpoch,
740 GraphNamespace, JournalHead, JournalSequence, NodeAttemptCompletion, NodeControl,
741 NodeInvocationBindings, NodeStateChange, PendingNodeResultIntent, ReadyNodes, RunId,
742 TenantId,
743 };
744
745 fn checkpoint() -> Checkpoint {
746 let fixture: serde_json::Value =
747 serde_json::from_str(include_str!("../tests/fixtures/core-checkpoint-v1.json"))
748 .unwrap();
749 from_value(fixture["checkpoints"][0].clone()).unwrap()
750 }
751
752 fn checkpoint_with_nodes(count: usize) -> Checkpoint {
753 let template = checkpoint();
754 let tenant_id = template.tenant_id().clone();
755 let run_id = RunId::generate();
756 let ready_nodes = ReadyNodes::try_new(
757 (0..count).map(|index| NodeId::new(format!("node-{index:04}")).unwrap()),
758 )
759 .unwrap();
760 let write = CheckpointWrite::initial(
761 tenant_id.clone(),
762 run_id,
763 CheckpointId::generate(),
764 template.graph().clone(),
765 template.state().clone(),
766 ready_nodes,
767 )
768 .unwrap();
769 let journal_head = JournalHead::new(
770 tenant_id,
771 run_id,
772 JournalSequence::FIRST,
773 EventId::generate(),
774 template.journal_head().recorded_at(),
775 Digest::sha256(b"property checkpoint journal"),
776 );
777 Checkpoint::commit(write, journal_head).unwrap()
778 }
779
780 fn node(name: &str) -> NodeId {
781 NodeId::new(name).unwrap()
782 }
783
784 fn activation(checkpoint: &Checkpoint, name: &str) -> NodeActivation {
785 NodeActivation::for_ready_root(checkpoint, node(name)).unwrap()
786 }
787
788 fn fence(checkpoint: &Checkpoint, epoch: u64) -> RunFence {
789 RunFence::new(
790 checkpoint.tenant_id().clone(),
791 checkpoint.run_id(),
792 AttemptId::generate(),
793 FencingEpoch::new(epoch).unwrap(),
794 )
795 }
796
797 fn journal(checkpoint: &Checkpoint, offset: u64) -> JournalHead {
798 let base = checkpoint.journal_head();
799 let sequence = JournalSequence::new(base.sequence().get() + offset).unwrap();
800 let recorded_at = Timestamp::from_unix_micros(
801 base.recorded_at().unix_micros() + i64::try_from(offset).unwrap() * 1_000_000,
802 )
803 .unwrap();
804 JournalHead::new(
805 checkpoint.tenant_id().clone(),
806 checkpoint.run_id(),
807 sequence,
808 EventId::generate(),
809 recorded_at,
810 Digest::sha256(format!("recovery journal {offset}")),
811 )
812 }
813
814 fn executing_attempt(
815 checkpoint: &Checkpoint,
816 name: &str,
817 owner: RunFence,
818 offset: u64,
819 ) -> NodeAttempt {
820 let start = crate::NodeAttemptStart::new(
821 activation(checkpoint, name),
822 AttemptId::generate(),
823 owner,
824 journal(checkpoint, offset),
825 )
826 .unwrap();
827 NodeAttempt::executing(start)
828 }
829
830 fn result(
831 checkpoint: &Checkpoint,
832 name: &str,
833 owner: RunFence,
834 offset: u64,
835 ) -> PendingNodeResult {
836 let intent = PendingNodeResultIntent::new(
837 activation(checkpoint, name),
838 NodeStateChange::Unchanged,
839 NodeControl::Continue,
840 NodeInvocationBindings::empty(),
841 )
842 .unwrap();
843 PendingNodeResult::commit(intent, owner, journal(checkpoint, offset)).unwrap()
844 }
845
846 fn succeeded_attempt(
847 checkpoint: &Checkpoint,
848 name: &str,
849 owner: RunFence,
850 start_offset: u64,
851 result_offset: u64,
852 ) -> (NodeAttempt, PendingNodeResult) {
853 let start = crate::NodeAttemptStart::new(
854 activation(checkpoint, name),
855 AttemptId::generate(),
856 owner.clone(),
857 journal(checkpoint, start_offset),
858 )
859 .unwrap();
860 let result = result(checkpoint, name, owner, result_offset);
861 let completion =
862 NodeAttemptCompletion::succeed(&start, result.head(), BudgetUsage::zero()).unwrap();
863 (
864 NodeAttempt::restore(start, Some(completion)).unwrap(),
865 result,
866 )
867 }
868
869 fn failed_attempt(
870 checkpoint: &Checkpoint,
871 name: &str,
872 owner: RunFence,
873 start_offset: u64,
874 completion_offset: u64,
875 advice: RetryAdvice,
876 ) -> NodeAttempt {
877 let start = crate::NodeAttemptStart::new(
878 activation(checkpoint, name),
879 AttemptId::generate(),
880 owner,
881 journal(checkpoint, start_offset),
882 )
883 .unwrap();
884 let completion_journal = journal(checkpoint, completion_offset);
885 let failure = Failure::new(
886 FailureId::generate(),
887 FailureCategory::DependencyUnavailable,
888 FailureCode::new("node.test_failure").unwrap(),
889 FailureOrigin::new("runtime.test").unwrap(),
890 FailureMessage::new("The deterministic test node failed.").unwrap(),
891 advice,
892 )
893 .unwrap()
894 .with_caused_by_event(completion_journal.event_id());
895 let completion =
896 NodeAttemptCompletion::fail(&start, failure, BudgetUsage::zero(), completion_journal)
897 .unwrap();
898 NodeAttempt::restore(start, Some(completion)).unwrap()
899 }
900
901 fn decision<'a>(plan: &'a ReadyNodeRecoveryPlan, name: &str) -> &'a RecoveryNode {
902 plan.nodes()
903 .iter()
904 .find(|decision| decision.activation().node_id().as_str() == name)
905 .unwrap()
906 }
907
908 #[test]
909 fn pristine_ready_set_is_dispatchable_in_canonical_order() {
910 let checkpoint = checkpoint();
911 let owner = fence(&checkpoint, 1);
912 let journal_head = journal(&checkpoint, 10);
913 let observed_at = journal_head.recorded_at();
914 let plan = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone())
915 .unwrap()
916 .finish(journal_head.clone(), observed_at)
917 .unwrap();
918
919 assert_eq!(plan.checkpoint(), &checkpoint);
920 assert_eq!(plan.fence(), &owner);
921 assert_eq!(plan.journal_head(), &journal_head);
922 assert_eq!(plan.observed_at(), observed_at);
923 assert_eq!(
924 plan.nodes()
925 .iter()
926 .map(|decision| decision.activation().node_id().as_str())
927 .collect::<Vec<_>>(),
928 ["authorize", "reserve-stock"]
929 );
930 assert!(plan.nodes().iter().all(|decision| {
931 decision.kind() == RecoveryNodeKind::Dispatchable
932 && decision.dispatch_reason() == Some(NodeDispatchReason::FirstAttempt)
933 }));
934 assert!(!plan.is_barrier_ready());
935 assert!(plan.barrier_result_heads().unwrap().is_none());
936 }
937
938 #[test]
939 fn committed_siblings_are_reused_independent_of_observation_order() {
940 let checkpoint = checkpoint();
941 let owner = fence(&checkpoint, 1);
942 let (authorize_attempt, authorize) =
943 succeeded_attempt(&checkpoint, "authorize", owner.clone(), 1, 2);
944 let (reserve_attempt, reserve) =
945 succeeded_attempt(&checkpoint, "reserve-stock", owner.clone(), 3, 4);
946 let observation = journal(&checkpoint, 10);
947
948 let mut forward = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
949 forward.observe_result(&authorize).unwrap();
950 forward.observe_result(&reserve).unwrap();
951 forward.observe_attempt(&reserve_attempt).unwrap();
952 forward.observe_attempt(&authorize_attempt).unwrap();
953 let forward = forward
954 .finish(observation.clone(), observation.recorded_at())
955 .unwrap();
956
957 let mut reverse = ReadyNodeRecoveryPlanner::new(checkpoint, owner).unwrap();
958 reverse.observe_result(&reserve).unwrap();
959 reverse.observe_result(&authorize).unwrap();
960 let reverse = reverse
961 .finish(observation.clone(), observation.recorded_at())
962 .unwrap();
963
964 assert!(forward.is_barrier_ready());
965 assert!(reverse.is_barrier_ready());
966 let forward_heads = forward.barrier_result_heads().unwrap().unwrap();
967 let reverse_heads = reverse.barrier_result_heads().unwrap().unwrap();
968 assert_eq!(forward_heads, reverse_heads);
969 assert_eq!(
970 forward_heads
971 .iter()
972 .map(|head| head.activation().node_id().as_str())
973 .collect::<Vec<_>>(),
974 ["authorize", "reserve-stock"]
975 );
976 }
977
978 #[test]
979 fn unfinished_attempt_requires_higher_fence_and_same_fence_stays_in_flight() {
980 let checkpoint = checkpoint();
981 let old_owner = fence(&checkpoint, 1);
982 let attempt = executing_attempt(&checkpoint, "authorize", old_owner.clone(), 1);
983
984 let mut same =
985 ReadyNodeRecoveryPlanner::new(checkpoint.clone(), old_owner.clone()).unwrap();
986 same.observe_attempt(&attempt).unwrap();
987 let observation = journal(&checkpoint, 10);
988 let same = same
989 .finish(observation.clone(), observation.recorded_at())
990 .unwrap();
991 assert_eq!(
992 decision(&same, "authorize").kind(),
993 RecoveryNodeKind::InFlight
994 );
995
996 let successor = fence(&checkpoint, 2);
997 let mut recovered = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), successor).unwrap();
998 recovered.observe_attempt(&attempt).unwrap();
999 let recovered = recovered
1000 .finish(observation.clone(), observation.recorded_at())
1001 .unwrap();
1002 assert_eq!(
1003 decision(&recovered, "authorize").dispatch_reason(),
1004 Some(NodeDispatchReason::SupersededAttempt)
1005 );
1006
1007 let stale_owner = fence(&checkpoint, 1);
1008 let newer_attempt = executing_attempt(&checkpoint, "authorize", fence(&checkpoint, 2), 1);
1009 let mut stale = ReadyNodeRecoveryPlanner::new(checkpoint, stale_owner).unwrap();
1010 stale.observe_attempt(&newer_attempt).unwrap();
1011 assert!(matches!(
1012 stale.finish(observation.clone(), observation.recorded_at()),
1013 Err(ReadyNodeRecoveryError::CurrentFenceBehindHistory { .. })
1014 ));
1015 }
1016
1017 #[test]
1018 fn safe_retry_uses_inclusive_database_time_and_never_failure_blocks() {
1019 let checkpoint = checkpoint();
1020 let owner = fence(&checkpoint, 1);
1021 let retry = failed_attempt(
1022 &checkpoint,
1023 "authorize",
1024 owner.clone(),
1025 1,
1026 2,
1027 RetryAdvice::SafeAfter {
1028 delay: DurationMillis::new(5_000).unwrap(),
1029 },
1030 );
1031 let failed_at = retry.completion().unwrap().journal_head().recorded_at();
1032 let retry_observation = retry.completion().unwrap().journal_head().clone();
1033 let not_before = Timestamp::from_unix_micros(failed_at.unix_micros() + 5_000_000).unwrap();
1034
1035 let mut early = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1036 early.observe_attempt(&retry).unwrap();
1037 let early = early
1038 .finish(
1039 retry_observation.clone(),
1040 Timestamp::from_unix_micros(not_before.unix_micros() - 1).unwrap(),
1041 )
1042 .unwrap();
1043 assert_eq!(
1044 decision(&early, "authorize").kind(),
1045 RecoveryNodeKind::Deferred
1046 );
1047 assert_eq!(decision(&early, "authorize").not_before(), Some(not_before));
1048 assert_eq!(early.earliest_deferred_at(), Some(not_before));
1049
1050 let mut due = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1051 due.observe_attempt(&retry).unwrap();
1052 let due = due.finish(retry_observation, not_before).unwrap();
1053 assert_eq!(
1054 decision(&due, "authorize").dispatch_reason(),
1055 Some(NodeDispatchReason::SafeRetry)
1056 );
1057
1058 let terminal = failed_attempt(
1059 &checkpoint,
1060 "authorize",
1061 owner.clone(),
1062 3,
1063 4,
1064 RetryAdvice::Never,
1065 );
1066 let terminal_observation = terminal.completion().unwrap().journal_head().clone();
1067 let mut blocked = ReadyNodeRecoveryPlanner::new(checkpoint, owner).unwrap();
1068 blocked.observe_attempt(&terminal).unwrap();
1069 let blocked = blocked.finish(terminal_observation, not_before).unwrap();
1070 assert_eq!(
1071 decision(&blocked, "authorize").kind(),
1072 RecoveryNodeKind::Failed
1073 );
1074 assert!(decision(&blocked, "authorize").failure().is_some());
1075 }
1076
1077 #[test]
1078 fn activation_drift_and_success_without_result_fail_closed() {
1079 let checkpoint = checkpoint();
1080 let owner = fence(&checkpoint, 1);
1081 let drifted = NodeActivation::new(
1082 checkpoint.head(),
1083 GraphNamespace::root(),
1084 node("authorize"),
1085 Digest::sha256(b"drifted scheduler input"),
1086 );
1087 let drifted = PendingNodeResult::commit(
1088 PendingNodeResultIntent::new(
1089 drifted,
1090 NodeStateChange::Unchanged,
1091 NodeControl::Continue,
1092 NodeInvocationBindings::empty(),
1093 )
1094 .unwrap(),
1095 owner.clone(),
1096 journal(&checkpoint, 2),
1097 )
1098 .unwrap();
1099 let mut planner = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1100 assert!(matches!(
1101 planner.observe_result(&drifted),
1102 Err(ReadyNodeRecoveryError::UnexpectedResult { .. })
1103 ));
1104
1105 let (success, _) = succeeded_attempt(&checkpoint, "authorize", owner.clone(), 1, 2);
1106 let observation = journal(&checkpoint, 10);
1107 let observed_at = observation.recorded_at();
1108 let mut missing = ReadyNodeRecoveryPlanner::new(checkpoint, owner).unwrap();
1109 missing.observe_attempt(&success).unwrap();
1110 assert!(matches!(
1111 missing.finish(observation, observed_at),
1112 Err(ReadyNodeRecoveryError::SucceededWithoutResult { .. })
1113 ));
1114
1115 let mismatched_checkpoint = self::checkpoint();
1116 let owner = fence(&mismatched_checkpoint, 1);
1117 let durable_result = result(&mismatched_checkpoint, "authorize", owner.clone(), 4);
1118 let unrelated_failure = failed_attempt(
1119 &mismatched_checkpoint,
1120 "authorize",
1121 owner.clone(),
1122 1,
1123 2,
1124 RetryAdvice::Never,
1125 );
1126 let observation = journal(&mismatched_checkpoint, 10);
1127 let mut mismatched = ReadyNodeRecoveryPlanner::new(mismatched_checkpoint, owner).unwrap();
1128 mismatched.observe_result(&durable_result).unwrap();
1129 mismatched.observe_attempt(&unrelated_failure).unwrap();
1130 assert!(matches!(
1131 mismatched.finish(observation.clone(), observation.recorded_at()),
1132 Err(ReadyNodeRecoveryError::ResultAttemptMismatch { .. })
1133 ));
1134 }
1135
1136 #[test]
1137 fn completed_result_cannot_come_from_a_future_or_conflicting_fence() {
1138 let checkpoint = checkpoint();
1139 let old = result(&checkpoint, "authorize", fence(&checkpoint, 1), 2);
1140 let successor = fence(&checkpoint, 2);
1141 let observation = journal(&checkpoint, 10);
1142 let mut reusable = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), successor).unwrap();
1143 reusable.observe_result(&old).unwrap();
1144 assert_eq!(
1145 decision(
1146 &reusable
1147 .finish(observation.clone(), observation.recorded_at())
1148 .unwrap(),
1149 "authorize",
1150 )
1151 .kind(),
1152 RecoveryNodeKind::Completed
1153 );
1154
1155 let current = fence(&checkpoint, 1);
1156 let future = result(&checkpoint, "authorize", fence(&checkpoint, 2), 2);
1157 let mut future_plan =
1158 ReadyNodeRecoveryPlanner::new(checkpoint.clone(), current.clone()).unwrap();
1159 future_plan.observe_result(&future).unwrap();
1160 assert!(matches!(
1161 future_plan.finish(observation.clone(), observation.recorded_at()),
1162 Err(ReadyNodeRecoveryError::CurrentFenceBehindHistory { .. })
1163 ));
1164
1165 let conflict = result(&checkpoint, "authorize", fence(&checkpoint, 1), 2);
1166 let mut conflict_plan = ReadyNodeRecoveryPlanner::new(checkpoint, current).unwrap();
1167 conflict_plan.observe_result(&conflict).unwrap();
1168 assert!(matches!(
1169 conflict_plan.finish(observation.clone(), observation.recorded_at()),
1170 Err(ReadyNodeRecoveryError::CurrentFenceConflict { .. })
1171 ));
1172 }
1173
1174 #[test]
1175 fn crossed_scope_is_rejected_before_planning() {
1176 let checkpoint = checkpoint();
1177 let crossed_tenant = RunFence::new(
1178 TenantId::new("another-tenant").unwrap(),
1179 checkpoint.run_id(),
1180 AttemptId::generate(),
1181 FencingEpoch::new(1).unwrap(),
1182 );
1183 assert!(matches!(
1184 ReadyNodeRecoveryPlanner::new(checkpoint.clone(), crossed_tenant),
1185 Err(ReadyNodeRecoveryError::FenceTenantMismatch)
1186 ));
1187
1188 let crossed_run = RunFence::new(
1189 checkpoint.tenant_id().clone(),
1190 RunId::generate(),
1191 AttemptId::generate(),
1192 FencingEpoch::new(1).unwrap(),
1193 );
1194 assert!(matches!(
1195 ReadyNodeRecoveryPlanner::new(checkpoint, crossed_run),
1196 Err(ReadyNodeRecoveryError::FenceRunMismatch)
1197 ));
1198 }
1199
1200 #[test]
1201 fn final_observation_cannot_precede_evidence_or_database_clock() {
1202 let checkpoint = checkpoint();
1203 let owner = fence(&checkpoint, 1);
1204 let durable_result = result(&checkpoint, "authorize", owner.clone(), 2);
1205 let mut behind_evidence =
1206 ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1207 behind_evidence.observe_result(&durable_result).unwrap();
1208 assert!(matches!(
1209 behind_evidence.finish(
1210 checkpoint.journal_head().clone(),
1211 durable_result.journal_head().recorded_at(),
1212 ),
1213 Err(ReadyNodeRecoveryError::ObservationBeforeEvidence)
1214 ));
1215
1216 let observation = journal(&checkpoint, 10);
1217 let before_observation =
1218 Timestamp::from_unix_micros(observation.recorded_at().unix_micros() - 1).unwrap();
1219 assert!(matches!(
1220 ReadyNodeRecoveryPlanner::new(checkpoint, owner)
1221 .unwrap()
1222 .finish(observation, before_observation),
1223 Err(ReadyNodeRecoveryError::ObservationClockRegression)
1224 ));
1225 }
1226
1227 #[test]
1228 fn physical_attempt_history_has_a_hard_recovery_bound() {
1229 let checkpoint = checkpoint();
1230 let owner = fence(&checkpoint, 1);
1231 let mut planner = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1232 for index in 0..ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE {
1233 let start_offset = u64::try_from(index * 2 + 1).unwrap();
1234 planner
1235 .observe_attempt(&failed_attempt(
1236 &checkpoint,
1237 "authorize",
1238 owner.clone(),
1239 start_offset,
1240 start_offset + 1,
1241 RetryAdvice::SafeAfter {
1242 delay: DurationMillis::ZERO,
1243 },
1244 ))
1245 .unwrap();
1246 }
1247 let observation = journal(&checkpoint, 200);
1248 let exhausted = planner
1249 .clone()
1250 .finish(observation.clone(), observation.recorded_at())
1251 .unwrap();
1252 assert_eq!(
1253 decision(&exhausted, "authorize").kind(),
1254 RecoveryNodeKind::Exhausted
1255 );
1256 assert!(
1257 decision(&exhausted, "authorize")
1258 .exhausted_attempt()
1259 .is_some()
1260 );
1261 let overflow_offset =
1262 u64::try_from(ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE * 2 + 1).unwrap();
1263 assert!(matches!(
1264 planner.observe_attempt(&failed_attempt(
1265 &checkpoint,
1266 "authorize",
1267 owner,
1268 overflow_offset,
1269 overflow_offset + 1,
1270 RetryAdvice::SafeAfter {
1271 delay: DurationMillis::ZERO,
1272 },
1273 )),
1274 Err(ReadyNodeRecoveryError::AttemptLimitExceeded {
1275 maximum: ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE,
1276 ..
1277 })
1278 ));
1279 }
1280
1281 proptest! {
1282 #![proptest_config(ProptestConfig::with_cases(64))]
1283
1284 #[test]
1285 fn arbitrary_result_observation_order_produces_canonical_barrier(
1286 (count, priorities) in (1_usize..=32).prop_flat_map(|count| {
1287 (Just(count), prop::collection::vec(any::<u16>(), count))
1288 }),
1289 ) {
1290 let checkpoint = checkpoint_with_nodes(count);
1291 let owner = fence(&checkpoint, 1);
1292 let results = checkpoint
1293 .ready_nodes()
1294 .iter()
1295 .enumerate()
1296 .map(|(index, node_id)| {
1297 result(
1298 &checkpoint,
1299 node_id.as_str(),
1300 owner.clone(),
1301 u64::try_from(index + 1).unwrap(),
1302 )
1303 })
1304 .collect::<Vec<_>>();
1305 let mut order = (0..count).collect::<Vec<_>>();
1306 order.sort_unstable_by_key(|index| (priorities[*index], *index));
1307
1308 let mut planner =
1309 ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner).unwrap();
1310 for index in order {
1311 planner.observe_result(&results[index]).unwrap();
1312 }
1313 let observation = journal(&checkpoint, u64::try_from(count + 1).unwrap());
1314 let plan = planner
1315 .finish(observation.clone(), observation.recorded_at())
1316 .unwrap();
1317 let expected = checkpoint
1318 .ready_nodes()
1319 .iter()
1320 .map(NodeId::as_str)
1321 .collect::<Vec<_>>();
1322 let actual = plan
1323 .nodes()
1324 .iter()
1325 .map(|decision| decision.activation().node_id().as_str())
1326 .collect::<Vec<_>>();
1327 prop_assert_eq!(actual, expected.clone());
1328 let barrier = plan.barrier_result_heads().unwrap().unwrap();
1329 let barrier_order = barrier
1330 .iter()
1331 .map(|head| head.activation().node_id().as_str())
1332 .collect::<Vec<_>>();
1333 prop_assert_eq!(barrier_order, expected);
1334 }
1335 }
1336}