Durable workflow execution

Deep dive

How it works

Parts:

• workflow code — deterministic function that only talks to the engine
• event history — append-only log of commands and results; the real state
• engine / task queue — appends events, dispatches workflow and activity tasks
• activities — side-effecting steps run by workers under a retry policy, at least once
• timers and signals — events appended by the engine, read by the code from the log

Operations: the numbered steps below (start, command, activity, timer or signal, replay, mismatch, saga).

1. Start: append WorkflowStarted(input). A worker runs the code.
2. Command: each engine call (activity, timer, child workflow) emits a command, which becomes events (scheduled, started, completed). The result is stored before the code sees it.
3. Activity: run by a worker outside the workflow under a retry policy (Temporal default: 1 s initial, x2 backoff, cap 100x, unlimited attempts). A worker can die after the effect and before the result is saved, so the effect may run twice: pass a stable idempotency key (workflow id + step).
4. Timers and signals are events too: the engine appends TimerFired or Signal(name, payload), and the code reads them from the log, never from the clock or a channel.
5. Replay: a fresh worker runs the code from the top. Each engine call must match the next recorded event; a match returns the saved result without executing. When the history runs out, execution is live again.
6. Mismatch (code changed, or it read the clock, random or the network itself) is a non-determinism error: the workflow stalls instead of diverging.
7. Saga: on a later failure the code runs compensating activities in reverse order (saga pattern); they are ordinary recorded steps, so they survive crashes too.

code:    reserve ─► charge ─► timer ─► wait(approve) ─► ship
history: [Done reserve][Done charge][TimerFired][Signal approve] ... crash here
replay:   reserve ✓(from log) charge ✓ timer ✓ signal ✓   ship ▶ live

Code

History is a Vec<Event>; Ctx is the only door to side effects. The test crashes between an effect and its record, then replays.

use std::cell::RefCell;
use std::collections::HashMap;

#[derive(Clone, Debug, PartialEq)]
pub enum Event {
    ActivityDone { seq: u32, name: String, result: String },
    TimerFired { seq: u32 },
    Signal { name: String, payload: String },
}
#[derive(Debug, PartialEq)]
pub enum Fail {
    Crash,                  // worker died; restart and replay
    Blocked,                // waiting for a signal event
    NonDeterminism(String), // code no longer matches the recorded history
}
pub struct Ctx<'a> {
    history: &'a mut Vec<Event>,
    pos: usize, // replay cursor
    seq: u32,   // step counter; idempotency-key suffix
    wf_id: &'a str,
    crash_before_record: Option<u32>, // test hook: die after the effect, before saving
}

impl<'a> Ctx<'a> {
    pub fn new(history: &'a mut Vec<Event>, wf_id: &'a str) -> Self {
        Ctx { history, pos: 0, seq: 0, wf_id, crash_before_record: None }
    }

    /// At-least-once activity. Replay returns the recorded result and never calls `f`.
    pub fn activity(&mut self, name: &str, f: impl FnOnce(&str) -> String) -> Result<String, Fail> {
        let seq = self.seq;
        self.seq += 1;
        if let Some(ev) = self.history.get(self.pos) {
            return match ev {
                Event::ActivityDone { seq: s, name: n, result } if *s == seq && n == name => {
                    self.pos += 1;
                    Ok(result.clone())
                }
                other => Err(Fail::NonDeterminism(format!("step {seq} {name}: {other:?}"))),
            };
        }
        let key = format!("{}-{}", self.wf_id, seq); // identical on every retry of this step
        let result = f(&key);
        if self.crash_before_record == Some(seq) {
            return Err(Fail::Crash); // effect happened, result lost
        }
        self.history.push(Event::ActivityDone { seq, name: name.into(), result: result.clone() });
        self.pos += 1;
        Ok(result)
    }
    /// The engine decides when a timer fires; here it fires at once and is logged.
    pub fn timer(&mut self) -> Result<(), Fail> {
        let seq = self.seq;
        self.seq += 1;
        match self.history.get(self.pos) {
            Some(Event::TimerFired { seq: s }) if *s == seq => {}
            Some(other) => return Err(Fail::NonDeterminism(format!("timer {seq}: {other:?}"))),
            None => self.history.push(Event::TimerFired { seq }),
        }
        self.pos += 1;
        Ok(())
    }
    /// Blocks until the engine has appended a matching Signal event.
    pub fn wait_signal(&mut self, name: &str) -> Result<String, Fail> {
        match self.history.get(self.pos) {
            Some(Event::Signal { name: n, payload }) if n == name => {
                self.pos += 1;
                Ok(payload.clone())
            }
            Some(other) => Err(Fail::NonDeterminism(format!("signal {name}: {other:?}"))),
            None => Err(Fail::Blocked),
        }
    }
}
/// External service that honours idempotency keys.
#[derive(Default)]
pub struct Service {
    calls: RefCell<usize>,
    applied: RefCell<HashMap<String, String>>, // key -> result; effect applied once
}
impl Service {
    pub fn call(&self, key: &str, op: &str) -> String {
        *self.calls.borrow_mut() += 1;
        self.applied.borrow_mut().entry(key.into()).or_insert_with(|| format!("{op}-ok")).clone()
    }
}
pub fn order(ctx: &mut Ctx, svc: &Service) -> Result<String, Fail> {
    let r = ctx.activity("reserve", |k| svc.call(k, "reserve"))?;
    let c = ctx.activity("charge", |k| svc.call(k, "charge"))?;
    ctx.timer()?; // e.g. a fraud-review delay
    let who = ctx.wait_signal("approve")?;
    let s = ctx.activity("ship", |k| svc.call(k, "ship"))?;
    Ok(format!("{r},{c},{who},{s}"))
}
fn main() {
    let (svc, mut h) = (Service::default(), Vec::new());
    // Worker dies after `charge` took effect but before its event was saved.
    let mut ctx = Ctx::new(&mut h, "wf-1");
    ctx.crash_before_record = Some(1);
    assert_eq!(order(&mut ctx, &svc), Err(Fail::Crash));
    assert_eq!(h.len(), 1); // only `reserve` is in the history
    // Replay skips `reserve`, re-runs `charge` with the same key, then blocks.
    assert_eq!(order(&mut Ctx::new(&mut h, "wf-1"), &svc), Err(Fail::Blocked));
    h.push(Event::Signal { name: "approve".into(), payload: "alice".into() });
    let out = order(&mut Ctx::new(&mut h, "wf-1"), &svc).unwrap();
    assert_eq!(out, "reserve-ok,charge-ok,alice,ship-ok");
    // A finished workflow replays without touching the service.
    let calls = *svc.calls.borrow();
    assert_eq!(order(&mut Ctx::new(&mut h, "wf-1"), &svc).unwrap(), out);
    assert_eq!(*svc.calls.borrow(), calls);
    // `charge` was invoked twice (the at-least-once window) but applied once.
    assert_eq!((calls, svc.applied.borrow().len()), (4, 3));
    // Code that no longer matches the history is detected.
    let bad = Ctx::new(&mut h, "wf-1").activity("charge", |k| svc.call(k, "charge"));
    assert!(matches!(bad, Err(Fail::NonDeterminism(_))));
}

The crashed charge is invoked twice but applied once (the service dedups on the key); recorded steps never re-run.

Complexity and constants

• Resume is linear in history length; n steps with a crash after every step cost O(n^2) without caching.
• Per step: several events (a regular Temporal activity adds scheduled, started and completed), one result payload kept forever in the history.
• Measured here (Apple M4 Pro, release build, in-memory): replaying 1k/10k/100k recorded activity results took about 18-21 ns per event. That is only cursor match plus one String clone; real SDKs add payload decoding and the history fetch, which dominate.
• Measured here: sync_data after a 100-byte append took about 4.3 ms; 100 appends per sync cost about 44 µs per event.

Efficiency

• Cost: one step = one durable write plus replay on the next resume. On the M4 Pro above: replay about 20 ns/event of CPU, a flushed append about 4 ms. The bound is storage latency and history fetch, not the replay loop.
• Levers:
  • Sticky execution (worker caches workflow state) — skips full replay per task (Temporal docs) — resumes hit the same worker.
  • Batch events per write/fsync — 4.3 ms to about 44 µs per event at batch 100 (measured above) — several events per workflow task.
  • Continue-as-new — bounds history and replay length (Temporal docs) — loops and long-lived entities.
  • Local activities — run in the worker, fewer history entries, no task-queue round trip (Temporal docs) — short idempotent calls only.
• Naive → standard → state of the art:
  • Re-run from scratch on every crash, no log · repeats side effects, duplicates money.
  • Full replay of the history on every wake-up · O(history) CPU and a full history fetch per task.
  • Sticky cache + batched appends + continue-as-new + local activities · replay only on cache miss or failover, bounded history.

Implementation notes

• Derive seq from call order, never from map iteration or a thread race.
• Clock, random and UUIDs come from the engine as recorded values; I/O, environment reads and threads belong in activities.
• Write all events of one workflow task in one transaction, so history and task queue move atomically.
• Heartbeat long activities to notice dead workers early; task ownership is a lease.
• Cap payload sizes: every result is re-read on every replay; store big blobs elsewhere.
• Number events densely (sequence numbers); readers resume from an offset like consumer offsets.

Pitfalls

• Non-idempotent activity without a key: a crash in the at-least-once window pays twice.
• Changing code under running executions. Gate new behaviour with a patch marker (Temporal patching) or pin old executions to old workers (worker versioning); keep the old branch until they finish.
• Unbounded loops in one history hit the event limit and fail. Call continue-as-new every N iterations, carrying the state.
• now(), random, map iteration order or globals in workflow code: works until the first replay.
• Retrying forever: unlimited default attempts hide a poisoned step. Set a maximum and surface failures like a dead-letter queue.

Variants and alternatives

In production

Temporal (forked from Uber's Cadence), Cadence, AWS Step Functions Standard (up to one year), Azure Durable Functions, Restate, DBOS, Inngest.

Implementations

Sources

• Temporal docs: Event History, Workflow Definition, limits, Sticky Execution, Continue-As-New, Local Activity, Retry Policies
• Microsoft, Durable Functions: overview, code constraints
• AWS, Step Functions quotas
• Restate key concepts · DBOS architecture · Inngest execution model
• Hector Garcia-Molina, Kenneth Salem, Sagas, SIGMOD 1987. paper