11 - Durable Execution

distributedsystem/books/think-distributed-systems

1. Abstraction & The Pitfalls of Partial Executions

Durable executions are to distributed systems what transactions are to databases: a powerful abstraction that completely conceals the possibility of underlying physical failures.

• The Composition Problem: While individual operations might be atomic, the sequential composition of two atomic actions is not itself atomic.
• Partial Execution Vulnerability: If a crash occurs mid-sequence, the system is left in a partially executed, corrupted state. Formally, a crash reduces an execution trace $t$ to its prefix:
  $t\mid \text{crash}\equiv \text{prefix }t$
• Failure-Transparent Goal: Ideally, an execution should run to completion as if no failure ever occurred, or leave no trace if it cannot:
  $t\mid \text{crash}\equiv t\vee \text{nothing}$

The Two Flavors of Atomicity

• Concurrency-Atomicity (Isolation): A process executes as if uninterrupted. Intermediate states are completely hidden from other concurrent processes.
• Failure-Atomicity (All-or-Nothing): A process executes completely or not at all, though intermediate states may be observable by external systems while running.

2. System Model: Definition vs. Execution

To reason clearly about failure handling, we must distinguish between the static representation of a process and its dynamic execution.

                    ┌──────────────────────────────┐
                    │      Static Definition       │ (Failure-Aware / Agnostic)
                    └──────────────┬───────────────┘
                                   │ Interpreted / Run
                                   ▼
                    ┌──────────────────────────────┐
                    │      Dynamic Execution       │ (Failure-Tolerant / Transparent)
                    └──────────────────────────────┘

• Process Definition ($P$): Defined as a sequence of steps, where each step is a failure-atomic action:
  $P=A\cdot P^{\prime }\mid \epsilon$
  • $A\cdot P^{\prime }$ represents executing atomic action $A$ and transitioning to successor process $P^{\prime }$.
  • $\epsilon$ represents successful termination.
• Process Execution ($t$): The actual trace of observable events under a Crash-Stop failure model where execution can halt at any instant:
  • $✓$ represents a successful execution.
  • $\times$ represents a crash failure.
  • For a definition $P=A\cdot B\cdot \epsilon$, the possible execution traces are:
    $t=\times \vee a\cdot \times \vee a\cdot b\cdot ✓$

Short-Running vs. Long-Running Executions

• Short-running (short-lived): An execution consisting of a single step.
• Long-running (long-lived): An execution consisting of multiple sequential or parallel steps.
• Logical Time vs. Physical Time: “Long-running” is a statement about logical steps, not physical duration. Because failure atomicity does not compose, long-running processes are inherently vulnerable to partial execution failures.

3. Failure-Transparent Recovery

Recovery is failure-transparent if a failed, recovered, and continued execution produces a sequence of events equivalent to a perfectly failure-free execution. Equivalence is application-specific and determined by an equivalence function.

Let a failure-free execution trace be:
$t_{\text{free}}=a\cdot b\cdot c\cdot d\cdot e\cdot f\cdot ✓$

Common Equivalence Functions

1. Identity Equivalence (Exactly-Once Processing):
   The sequence of events is identical, completely hiding the crash ($\text{crash}$):
   $t_{\text{failed}}=a\cdot b\cdot c\cdot \text{crash}\cdot d\cdot e\cdot f\cdot ✓\equiv t_{\text{free}}$
   (Note: This is the ideal scenario but is not always physically achievable.)
2. Valid to Duplicate Last Event:
   Safe if the immediately preceding action is idempotent and can be safely re-run upon recovery:
   $t_{\text{failed}}=a\cdot b\cdot c\cdot \text{crash}\cdot c\cdot d\cdot e\cdot f\cdot ✓$
3. Valid to Duplicate Last $n$ Events:
   Allows a wider rollback window during recovery, replaying several past steps:
   $t_{\text{failed}}=a\cdot b\cdot c\cdot \text{crash}\cdot b\cdot c\cdot d\cdot e\cdot f\cdot ✓$
4. Restart Equivalence:
   The execution is rolled back completely and started from the beginning:
   $t_{\text{failed}}=a\cdot b\cdot c\cdot \text{crash}\cdot a\cdot b\cdot c\cdot d\cdot e\cdot f\cdot ✓$

4. Recovery Strategies: Restart vs. Resume

When an execution is interrupted, the recovery subsystem has two primary operational options to reach a failure-transparent state.

Strategy A: Restart

The runtime throws away active execution memory and restarts the entire process from the beginning.

• Prerequisite: Every step must be strictly idempotent ($f(f(x))=f(x)$).
• Drawbacks:
  • Temporal Disruptions: Restarts reset physical delays or timers (e.g., restarting a signup workflow with a one-week payment delay resets the one-week clock).
  • Non-Determinism: If any step involves non-deterministic outputs (e.g., fetching current system time, generating random numbers), a complete restart can divert the execution path away from the original trace.

Strategy B: Resume

The runtime captures state metadata (“save points”) between steps. Upon recovery, it reloads the last save point and resumes execution.

• Benefits: Safely handles non-determinism and avoids repeating resource-intensive or time-sensitive steps.

5. Implementations: Application-Level vs. Platform-Level

The placement of the recovery subsystem radically changes the design and clean readability of application code.

Application-Level Recovery: Sagas

Sagas require failure-aware process definitions. The developer is explicitly responsible for coding failure handling, tracking state transitions, and managing compensations.

• Pattern: Often implemented as a persistent state machine using explicit conditional logic:

async function signupSaga(state) {
  switch (state.label) {
    case 'createAccount':
      const account = await AccountCreate();
      return { label: 'createPayment', account };
    case 'createPayment':
      const payment = await PaymentCreate();
      return { label: 'done', payment };
    default:
      throw new Error('Unknown state');
  }
}

• Con: The core business logic is heavily obfuscated by boilerplates of error catching, compensation, and state tracking, making maintenance difficult.

Platform-Level Recovery: Durable Executions

Durable executions enable failure-agnostic (or failure-oblivious) process definitions. The application code is written linearly as if failures do not exist, and the platform transparently manages state retention and recovery.

                           Sagas (Application-Level)
           ┌────────────────────────────────────────────────────────┐
           │   Core Logic + State Machine + Compensations (Mixed)   │
           └────────────────────────────────────────────────────────┘
                    
                     Durable Executions (Platform-Level)
           ┌────────────────────────────────────────────────────────┐
           │                      Core Logic                        │
           ├────────────────────────────────────────────────────────┤
           │           Platform Orchestration & Persistence         │
           └────────────────────────────────────────────────────────┘

6. Durable Execution Mechanics

Platforms leverage one of two core strategies to preserve state across failures: Log-based (Replay) or State-based (Continuation).

1. Log-Based Implementation (Replay)

The platform records the output of every completed execution step in a durable log.

• Recovery Mechanism: Upon crash, the runtime restarts the execution from step 1. When it encounters a step that has an entry in the durable log, it bypasses execution, intercepts the call, and returns the logged result.
• Runtime Loop Pattern:

async function runtime(coroutine, args, durableLog) {
  const execution = coroutine(args);
  let stepResult = execution.next();
  let i = 0;
  while (!stepResult.done) {
    if (durableLog[i] !== undefined) {
      // Replay: fast-forward using logged value
      stepResult = execution.next(durableLog[i]);
    } else {
      // Execute and persist result
      durableLog[i] = await stepResult.value();
      stepResult = execution.next(durableLog[i]);
    }
    i++;
  }
}

• Drawbacks:
  1. Strict Determinism: Replay requires the execution flow to be completely deterministic; any code change or non-deterministic side-effect will cause a mismatch with the log.
  2. Log Bloat: The log size grows indefinitely with the number of steps.

2. State-Based Implementation (Continuation)

The platform serializes the entire runtime state of the program (its execution context or continuation) after each step and saves it to a durable store.

• Recovery Mechanism: Upon crash, the runtime deserializes the saved continuation and resumes execution directly from the exact line of failure without any history replay.
• Runtime Loop Pattern:

async function runtime(coroutine, args, durableState) {
  let execution = durableState ? load(durableState) : coroutine(args);
  let stepResult = execution.next();
  while (!stepResult.done) {
    durableState = save(execution); // Serialize and save current continuation
    const value = await stepResult.value();
    stepResult = execution.next(value);
  }
}

• Pros: No deterministic execution constraint, and no replaying of growing event logs.
• Cons: Requires specialized compiler or language runtime support for serializable continuations (emerging in modern languages like Grain or Unison).