Distributed systems · 2026 · completed

Scheherazade

A crash-safe saga orchestrator with a write-ahead log and a chaos harness.

A saga orchestrator that survives the night. Scheherazade survived by suspending a story mid-telling and resuming exactly where she left off. This saga orchestrator does the same for multi-system operations — a durable, fsync’d log, crash recovery, and a chaos harness that kills the process at every possible boundary to prove one guarantee: any saga converges to fully committed or fully compensated, never halfway.

I first implemented the saga pattern in production; this is a from-scratch Haskell rebuild in neutral domains — the pattern itself is public knowledge (Garcia-Molina & Salem, Sagas, 1987).

The instrument

Write-ahead, actually fsync'd

Intent entries hit disk via a real `fsync(2)` before their effect runs; outcomes are written after. A torn log line is either an intent with no effect (drop it) or an effect with no confirmation (redo it).

Recovery is not a mode

Startup and post-crash restart run the same code path — replay the log into a pure fold, decide the next action, continue. No separate recovery branch to drift out of sync.

An out-of-process chaos harness

Tests run the compiled binaries as child processes and send a real `SIGKILL`, then judge only external artifacts — never the program's own claims. Fault matrix, crash-at-every-boundary loop, and 500 seeded chaos runs, all converging.

Compensation restores consistency, not history

Every undo must be idempotent and safe against nothing having run — laws no type system checks. Honest residue by design: a cancelled booking still carries its fee.

The movement

The engineering underneath

The write discipline carries the whole crash-safety argument — and states its own limits.

The write discipline carries everything

Intents fsync before their effect; outcomes are written after. Every crash-safety property falls out of that one ordering, by a case split on what a torn line was.

Log.hs

appendEntry :: LogHandle -> LogEntry -> IO ()
appendEntry (LogHandle fd) e = do
    _ <- fdWrite fd (renderEntry e ++ "\n")
    fileSynchronise fd

fsync vs. hFlush — the harness's blind spot

`hFlush` only empties Haskell's buffer, not the OS page cache; `kill -9` never touches it. Delete the `fsync` call and the suite stays green — the durability claim rests on the write-ahead argument, not the tests. Stated on purpose in the design doc.

Backward recovery over-compensates on purpose

An unknown outcome during unwind gets compensated anyway — a timeout can leave effects even when reported clean. Only legal because compensations are contractually idempotent and safe against no-ops.

No third terminal state

A compensation that keeps failing retries forever rather than escalating. A third terminal would quietly weaken the two-state guarantee every caller relies on.

Specification

Language: Haskell
Paper: Garcia-Molina & Salem, "Sagas" (1987)
Recovery: Same code path as startup — replay the log into a pure fold, no separate branch
Guarantee: Committed or compensated — never partial
Log: Append-only, line-oriented, fsync'd at every intent
Testing: Fault matrix + crash-loop + 500 seeded chaos runs