Saga pattern

Deep dive

How it works

Parts:

• steps T1..Tn — local transactions, idempotent per (saga id, step).
• undos C1..Cn — Ci semantically reverses Ti; idempotent, a no-op if Ti never ran.
• coordinator — orchestrator (state machine sending commands, reading replies) or choreography (services react to each other's events).
• saga log — durable Start, Done(i), Failed(k), Compensated(i), Committed, Aborted.
• pivot — the step after which undo is impossible (money paid out, parcel shipped); later steps are retriable.

1. Order: compensable steps (likeliest failures first), then the pivot, then retriable steps.
2. Forward: log Start; send Ti, on success log Done(i); after Tn log Committed.
3. Fail before the pivot: log Failed(k), run Ck..C1 in reverse, logging each Compensated(i), then Aborted.
4. Fail after the pivot: retry with backoff until it succeeds (forward recovery).
5. Crash: a new coordinator reads the log and resends the next step or undo; duplicates are harmless.
6. Isolation countermeasures (other sagas see half-done states): semantic lock (a PENDING flag; refuse or wait), commutative updates (deltas, not overwrites), reread value before writing and abort if changed, version file (log operations, apply in order), pessimistic view (reorder steps).

 T1 -> T2 -> T3(pivot) -> T4 -> T5 -> Committed     (T4, T5 retried until done)
        | fail
        v
 C2 -> C1 -> Aborted                                 (each Ci retried until done)
 log: Start Done1 Done2 Failed3 Comp2 Comp1 Aborted

use std::collections::{BTreeSet, HashMap};

#[derive(Clone, Copy, PartialEq, Debug)]
pub enum Rec { Start, Done(usize), Failed(usize), Compensated(usize), Committed, Aborted }
#[derive(PartialEq, Debug)]
pub enum Outcome { Committed, Aborted }
#[derive(Debug)]
pub struct Crash;

/// All participant services: free capacity per resource, what this saga holds.
#[derive(Default)]
pub struct World { pub free: HashMap<&'static str, u32>, pub held: BTreeSet<&'static str>, pub calls: (u32, u32) }

impl World {
    /// Ti. A repeat (lost reply, retry) is a no-op.
    fn apply(&mut self, s: &'static str) -> bool {
        self.calls.0 += 1;
        if self.held.contains(s) { return true; }
        match self.free.get_mut(s) { Some(n) if *n > 0 => { *n -= 1; self.held.insert(s); true } _ => false }
    }
    /// Ci. Twice, or when Ti never ran: no-op.
    fn undo(&mut self, s: &'static str) {
        self.calls.1 += 1;
        if self.held.remove(s) { *self.free.get_mut(s).unwrap() += 1; }
    }
}
/// Test hooks: crash after the effect, before its log record.
#[derive(Default)]
pub struct Faults { pub after_apply: Option<usize>, pub after_undo: Option<usize> }

/// Orchestrator. Its only state is `log`; after a crash call again with it.
pub fn run(steps: &[&'static str], w: &mut World, log: &mut Vec<Rec>, f: &mut Faults) -> Result<Outcome, Crash> {
    match log.last() {
        Some(Rec::Committed) => return Ok(Outcome::Committed),
        Some(Rec::Aborted) => return Ok(Outcome::Aborted),
        None => log.push(Rec::Start), // forced write
        _ => {}
    }
    let mut failed = log.iter().find_map(|r| if let Rec::Failed(k) = r { Some(*k) } else { None });
    let mut next = log.iter().filter(|r| matches!(r, Rec::Done(_))).count();
    while failed.is_none() && next < steps.len() {
        let ok = w.apply(steps[next]);
        if f.after_apply.take_if(|k| *k == next).is_some() { return Err(Crash); } // effect done, record lost
        if ok { log.push(Rec::Done(next)); next += 1; } else { log.push(Rec::Failed(next)); failed = Some(next); }
    }
    let Some(k) = failed else { log.push(Rec::Committed); return Ok(Outcome::Committed) };
    // Backward recovery, reverse order. Ck too: a timeout does not say if Tk applied.
    for j in (0..=k).rev() {
        if log.contains(&Rec::Compensated(j)) { continue; }
        w.undo(steps[j]);
        if f.after_undo.take_if(|x| *x == j).is_some() { return Err(Crash); }
        log.push(Rec::Compensated(j));
    }
    log.push(Rec::Aborted);
    Ok(Outcome::Aborted)
}

#[cfg(test)]
mod tests {
    use super::*;
    const S: [&str; 4] = ["flight", "hotel", "car", "payment"];
    fn world(sold_out: Option<usize>) -> World {
        let mut w = World::default();
        for (i, s) in S.iter().enumerate() { w.free.insert(s, if Some(i) == sold_out { 0 } else { 1 }); }
        w
    }
    fn go(w: &mut World, log: &mut Vec<Rec>, mut f: Faults) -> Outcome {
        for _ in 0..4 { if let Ok(o) = run(&S, w, log, &mut f) { return o; } } // restart per crash
        panic!("did not finish");
    }
    #[test]
    fn every_failure_and_crash_point() {
        for sold_out in [None, Some(0), Some(1), Some(2), Some(3)] {
            for a in [None, Some(0), Some(1), Some(2), Some(3)] {
                for u in [None, Some(0), Some(1), Some(2), Some(3)] {
                    let (mut w, mut log) = (world(sold_out), vec![]);
                    let out = go(&mut w, &mut log, Faults { after_apply: a, after_undo: u });
                    match sold_out {
                        None => { assert_eq!(out, Outcome::Committed); assert_eq!(w.held.len(), 4); }
                        Some(k) => {
                            assert_eq!(out, Outcome::Aborted);
                            assert!(w.held.is_empty());
                            assert!(w.free.iter().all(|(s, n)| *n == (*s != S[k]) as u32)); // restored
                            let comp: Vec<usize> = log.iter().filter_map(|r| if let Rec::Compensated(j) = r { Some(*j) } else { None }).collect();
                            assert_eq!(comp, (0..=k).rev().collect::<Vec<_>>()); // reverse, once each
                        }
                    }
                    let n = log.len();
                    run(&S, &mut w, &mut log, &mut Faults::default()).unwrap();
                    assert_eq!(log.len(), n); // finished: re-run does nothing
                }
            }
        }
    }
    #[test]
    fn message_counts() {
        let (mut w, mut log) = (world(None), vec![]);
        go(&mut w, &mut log, Faults::default());
        assert_eq!((w.calls, log.len()), ((4, 0), 6));
        let (mut w, mut log) = (world(Some(2)), vec![]);
        go(&mut w, &mut log, Faults::default());
        assert_eq!((w.calls, log.len()), ((3, 3), 8));
    }
}

A crash after apply leaves an effect without a Done; the restart repeats it harmlessly.

Complexity and constants

• Success: n commands (2n messages with replies), n+2 log records. Failure at step k: k forward plus k undo commands (test: 3+3, log of 8 for k=3).
• Latency: n sequential round trips plus log forces; no cross-service lock waits.

Efficiency

Cost: one saga of n steps = n local commits, n+2 log records, 2n messages (counted, not timed). A forced write is order of 0.05-10 ms (see two-phase commit); bound: n sequential round trips plus forced writes.

Levers:

• Likeliest failures first — failure at step k costs 2k commands, so k=1 instead of k=4 saves 6 of 8 (my counters) — uneven failure odds.
• Parallel independent steps — latency drops from the sum to the longest branch (arithmetic) — flight and hotel.
• Lazy Done and Committed records — forced writes n+2 down to about 2 (my reasoning: a lost record only repeats an idempotent step; Start and Failed stay forced) — all steps idempotent.
• Choreography — about n messages instead of 2n (arithmetic) — few services; loses the single view of progress.
• Share one force across sagas (group commit) — per-saga cost approaches 1/batch — many sagas per coordinator.

Naive → standard → state of the art:

• Cross-service two-phase commit · 4n messages, locks through prepare, blocks if the coordinator is lost
• Orchestrator, forced record per transition · n+2 forced writes, n round trips, no cross-service locks
• Engine with parallel branches, early-failing order, lazy records · critical-path round trips, about 2 forced writes

Implementation notes

• Save the saga state and the next command in one local transaction (transactional outbox); otherwise a crash between them loses the message.
• Key commands and undos by (saga id, step); the participant stores the key and replays the old result (idempotency keys, event deduplication).
• An undo may arrive before its step: store a tombstone so the late step is rejected. A timeout is not a failure: send the undo anyway.
• Cap retries, then a dead-letter queue and an alert; a stuck undo needs a human.

Pitfalls

• Dirty read: a reader sees the booked flight before the hotel fails. Expose PENDING.
• Lost update: saga A overwrites a balance saga B changed before A's undo. Use deltas or reread-and-compare.
• An undo that cannot be exact (email sent, cash paid out): make that step the pivot.
• A dropped failed undo orphans resources (a VM without its VPC): retry, then alert.
• Choreography grows cyclic event dependencies; nobody sees where order 17 is.

Variants and alternatives

In production

• E-commerce: order, payment and stock services via Eventuate Tram Sagas (the microservices.io example).
• Travel and cloud: Temporal's Go sample; AWS Prescriptive Guidance on saga orchestration with Step Functions.
• Banking and telecom: Camunda BPMN compensation events; Apache Seata Saga mode; MassTransit and Axon persisted saga state.

Implementations

Sources

• Hector Garcia-Molina, Kenneth Salem, Sagas, ACM SIGMOD 1987, pp. 249-259. paper
• Chris Richardson, Pattern: Saga; Microservices Patterns, Manning 2018, ch. 4.
• Microsoft, Saga pattern (compensable, pivot, retryable) · Compensating Transaction
• AWS Prescriptive Guidance: orchestration · choreography
• Temporal · Camunda · Seata · MassTransit · Axon