# Design a Durable DAG Workflow for Order Refunds An order that times out may need a refund. You are given a directed acyclic graph of refund steps and must design the workflow definition and workflow engine that executes eligible steps, persists progress, handles failures, and exposes status. External APIs may be called repeatedly because clients, workers, or the engine retry. Explain the effect of repeated calls and how to reduce user-visible latency without sacrificing correctness. ### Constraints & Assumptions - A workflow instance is tied to one refund request and one immutable or versioned DAG definition. - A step may depend on multiple predecessors and may call an external service. - Workers can crash before or after the external side effect but before recording completion. - At-least-once task delivery is acceptable; duplicate refunds are not. - Some steps may be safely parallelized when their dependencies are satisfied. ### Clarifying Questions to Ask - Which step actually moves money, and does its provider support idempotency or status lookup? - Which failures are retryable, terminal, or require manual review? - Are compensation steps required after partial completion? - What response must the initiating user receive synchronously? - Can a running workflow adopt a newer DAG definition? ### Solving Hints - Separate durable state transitions from task delivery. - Treat the “request may have succeeded but the response was lost” case explicitly. - The critical path, not total work, determines the minimum workflow latency. ### What a Strong Answer Covers - Versioned DAG validation and cycle rejection. - Durable workflow, step-attempt, dependency, and output state. - Transactional scheduling or an outbox so ready work is never lost. - Stable idempotency keys, retry policy, timeouts, and reconciliation for ambiguous effects. - Parallel execution of independent nodes, bounded queues, and a fast asynchronous user response. - Compensation or manual-review semantics, observability, and replay controls. - Tests for crashes at every commit/side-effect boundary. ### Follow-up Questions 1. A payment provider accepted a refund but the worker timed out; what state should the step enter? 2. How do you prevent two schedulers from dispatching the same ready node incorrectly? 3. How would you compute and improve the workflow's critical path? 4. What happens to running instances when the DAG definition changes?