Katkat
Back

Design a Durable DAG Workflow for Order Refunds

DoorDashSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests the ability to architect a robust, fault-tolerant workflow engine capable of managing complex state transitions and ensuring transactional integrity in distributed systems.

Problem Statement

Design a durable workflow engine that executes a Directed Acyclic Graph (DAG) for processing order refunds. A refund process involves multiple steps: ValidateOrder, CheckInventory, ProcessPayment, UpdateDatabase, and NotifyCustomer.

Requirements

  1. Durable State: The system must persist the execution state so that if a worker node crashes, the workflow can resume from the last successful step.
  2. Dependency Management: Steps must only execute when all parent nodes in the DAG have completed successfully.
  3. Idempotency: Every task must be idempotent to ensure that retrying a step after a partial failure does not result in duplicate side effects (e.g., double-refunding a customer).
  4. Failure Handling: Define a mechanism for handling terminal failures, including automated compensation (rollback) or transitioning to a 'Manual Review' state.
  5. Interface Design: Define the necessary data structures for representing a WorkflowDefinition (nodes/edges) and a WorkflowExecution (current state/logs).

Considerations

  • How do you ensure exactly-once semantics for side effects that are not naturally idempotent?
  • How would you implement a 'heartbeat' or timeout mechanism for long-running steps?
  • How does the system handle versioning of a workflow definition if an order is currently mid-process when a new schema is deployed?

Hints

Hint 1

Consider using an 'Outbox Pattern' or a state machine database table to atomically transition between task states.

Hint 2

Think about how to use a content-based idempotency key, derived from the order ID and task type, to prevent double-execution.

Hint 3

Decide whether to use a centralized orchestrator or a distributed worker-queue pattern based on your requirements for throughput and latency.

Follow-up questions

  • How would you implement a visibility layer that allows support teams to debug stuck workflows?
  • If a service in the DAG has a strict rate limit, how would you incorporate backpressure or scheduling delays into your engine?
  • How would you handle a scenario where an upstream service (e.g., Payment Gateway) returns a 'Pending' status indefinitely?