Everyone thinks a workflow engine is a topological sort with a thread pool. “Build the DAG, sort it, run tasks whose dependencies are done, repeat - it is a graph traversal, two hundred lines.” That model survives exactly until the interviewer asks the questions that turn it into a real system: your scheduler process crashes forty minutes into a three-hour pipeline that has already finished eleven of fifteen tasks - when it comes back up, does it re-run those eleven (re-charging customers, re-sending the report, double-writing the warehouse) or does it know they are done and resume from task twelve? Two scheduler replicas both decide task transform is ready at the same instant - does it get dispatched to the worker pool once or twice? Task load depends on extract_a and extract_b; extract_b fails three times and dead-letters - does load hang forever waiting, or does the DAG mark it upstream_failed and alert someone? You have ten thousand DAGs, each with hundreds of tasks, all scheduled to kick off at midnight - does the scheduler fall over trying to evaluate every dependency edge at the top of the hour?

A workflow orchestration engine is deceptive because the single-process DAG demo works perfectly and falls apart the moment you need durability (the execution state of an in-flight DAG must survive a scheduler crash, or you re-run completed work), distribution (tasks run on a pool of workers, not in the scheduler’s thread, so the scheduler only decides and tracks, never executes), correctness (a task whose side effect must not repeat has to run once even though the transport is at-least-once), and scale (tens of thousands of concurrent DAG runs, millions of task instances, dependency evaluation that cannot be a full graph walk every tick). The whole design comes down to a few decisions that are not obvious: making the durable store the source of truth for every task instance’s state so “what is done” is a fact on disk and not in the scheduler’s memory, modeling the scheduler as a stateless reconciliation loop that reads persisted state and drives the DAG forward idempotently, resolving dependencies with a per-task upstream-completion check instead of re-sorting the whole graph, and being honest that the scheduler never runs task code - it dispatches to a worker pool and the only thing it owns is state transitions.

This is the layer that sits on top of a job scheduler (the distributed job scheduler gives you the reliable timer and single-task dispatch; this gives you the graph, the dependencies, and the recovery). Let me do it properly.

Functional Requirements (FR)

In scope:

  • Define a workflow as a DAG. A workflow is a set of tasks with directed dependency edges: load runs after extract and transform, which run after ingest. The graph must be acyclic; we validate that at definition time. Each task has a handler (what code to run), parameters, and a retry policy.
  • Schedule workflow runs. Trigger a DAG run on a schedule (cron: “every day at 2am”), on a manual/API trigger, or on an external event (a file landed, an upstream DAG finished). Each trigger creates a DAG run - one concrete execution of the workflow with its own task instances.
  • Resolve dependencies and execute in order. A task becomes eligible to run only when all its upstream tasks in that DAG run have succeeded. The engine tracks each task instance’s state and schedules it the moment its dependencies are satisfied, maximizing parallelism across independent branches.
  • Execute tasks across a distributed worker pool. The scheduler does not run task code; it dispatches eligible tasks to a fleet of workers that pull and execute them, then report results back. Workers scale independently of the scheduler.
  • Retries with backoff per task. A failed task is retried a configurable number of times with backoff before being marked failed. Retry policy is per task, not per DAG.
  • Failure propagation and alerting. When a task exhausts its retries, its downstream tasks become upstream_failed (they will never run), the DAG run is marked failed, and an alert fires (page, Slack, email). Partial success is a first-class outcome: branches that completed stay completed.
  • Recovery mid-flight without re-running completed tasks. This is the core. If the scheduler crashes while a DAG run is in progress, on restart it must resume from the persisted state - already-succeeded tasks stay succeeded and are not re-executed; only not-yet-done tasks are driven forward.
  • Observability and control. Query a DAG run’s state and per-task status, view logs, retry a single failed task, re-run a whole DAG, pause a workflow, and clear/backfill a range of historical runs.

Explicitly out of scope (say it so you own the scope):

  • The business logic inside tasks. We decide when a task is eligible, dispatch it, track its state, and retry it. What the task does (run a Spark job, call an API, move a file) lives in the task handler. We own the graph and the state machine, not the work.
  • Resource-aware compute placement / bin-packing. We dispatch a task to an available worker that can run it. Packing heavy compute across a cluster by CPU/memory/GPU with affinity is a cluster scheduler’s job (Kubernetes/YARN); we assume workers pull work they can run, or we hand off to such a system as a task.
  • The low-level timer and single-task dispatch reliability. Firing “it is 2am, start DAG run X” reliably and exactly-once-ish is a job scheduler concern; we build the DAG orchestration layer on top of that primitive and reference it rather than rebuild it.
  • A general stream-processing engine. This orchestrates batch tasks with dependencies (data pipelines, ETL, ML training). Continuous record-by-record streaming with windowed state is Flink/Kafka-Streams territory, a different system.
  • Exactly-once side effects on non-cooperating external systems. We give at-least-once task execution and a stable idempotency key per task instance; making a non-idempotent downstream call happen exactly once requires that downstream to cooperate. We describe the pattern but cannot make a foreign side effect exactly-once by ourselves.

The one decision that drives everything: the execution state of every task instance lives in a durable, strongly-consistent store, and the scheduler is a stateless reconciliation loop that reads that state, computes which tasks are newly eligible, and drives transitions idempotently - it holds nothing in memory it cannot rebuild from the store. That is what makes mid-flight recovery free (restart, re-read, resume), makes multiple scheduler replicas safe (they converge on the same persisted facts with atomic transitions), and keeps the scheduler out of the execution path. Everything below is a consequence of it.

Non-Functional Requirements (NFR)

  • Scale: on the order of tens of thousands of workflow definitions, hundreds of thousands of concurrent DAG runs at peak, and DAGs ranging from a handful to thousands of tasks each. That is millions of live task instances being tracked, with a scheduling decision rate (eligibility evaluations + state transitions) in the tens of thousands per second, spiking at round times when many DAGs start together.
  • Latency (scheduling, not task runtime): when a task’s last dependency completes, the engine should make the dependent task eligible and dispatch it within a p99 of a few seconds. Task runtime is the task’s own business; what we optimize is the gap between “upstream done” and “downstream dispatched” - the scheduling overhead, which must stay small so a 15-task chain is not slowed by 15 scheduler hops.
  • Availability: 99.95%+ on accepting triggers and on making scheduling progress. No single node is a single point of failure. A scheduler replica dying must not stall DAG progress for more than the seconds it takes a peer to take over; a worker dying must not lose the task it held or corrupt the DAG state.
  • Reliability / durability: once a DAG run is started, its progress is durable. A total scheduler outage means the run pauses and resumes, never restarts from scratch and never loses completed work. Every task state transition is persisted and replicated before it is acted on. This is the property the whole design exists to protect.
  • Consistency: the task-instance store is strongly consistent for the operations that matter - transitioning a task’s state, marking a task eligible, and claiming a task for dispatch must not race. A task must never be both running on two workers and succeeded in the DB. Read-your-writes on triggering a run. Eventual consistency is acceptable only for the observability/log read path.
  • Execution semantics: at-least-once task execution by default (a task may run more than once under failure), with effectively-once available via a stable per-task-instance idempotency key. The scheduler’s view of task state is kept exactly-once via conditional transitions, even when a handler ran twice.

Back-of-the-Envelope Estimation (BoE)

Let me ground the design in numbers.

Workflow and task-instance volume:

Workflow definitions:        50,000
DAG runs per day:            50,000 defs * avg 24 runs/day (hourly-ish) = 1.2M runs/day
Tasks per DAG (avg):         50
Task instances per day:      1.2M runs * 50 = 60M task instances/day
                             = ~700 task instances/sec average created
Concurrent DAG runs (peak):  say 200,000 runs in flight at once
Live task instances tracked: 200,000 runs * 50 tasks = 10M live task instances

Scheduling decision rate (the real load):

Every task completion can unblock downstream tasks, triggering an eligibility
check on each. With 60M task instances/day and each completion triggering a
handful of downstream checks:
   60M completions/day * ~3 downstream checks = 180M checks/day
   = ~2,000 eligibility checks/sec average,
   with 10-50x spikes at round times (midnight, top of hour) when thousands
   of cron DAGs start simultaneously -> up to ~100K checks/sec at peak.
The checks MUST be event-driven (on upstream completion, check only that
task's children), NEVER a full re-scan of all 10M live task instances per tick.

The first non-obvious number: the cost is not running tasks, it is evaluating dependency edges, and a naive “re-evaluate the whole graph every second” design dies at 10M live task instances times one-second ticks. Make eligibility evaluation event-driven - a task finishing enqueues an eligibility check for its direct children only - so the work is proportional to completions (thousands/sec), not to the live task-instance count (millions).

Storage:

Task instance record: run_id, task_id, state, attempt, worker, lease, timestamps,
   params ref, upstream_done_count ~ 1 KB packed.
10M live task instances * 1 KB      = ~10 GB hot.
History: 60M task instances/day, keep 90 days = 5.4B rows if kept raw.
   At ~1 KB that is ~5 TB raw -> keep recent hot, roll older to cold/columnar,
   aggregate per-run summaries, sample verbose logs.
DAG run records:  1.2M/day * 90 days = ~108M rows, ~1 KB each = ~108 GB.
Workflow definitions (DAG structure):  50K defs, versioned, small (~tens of KB
   each with task graph) = a few GB. Cache hot in the scheduler.

Worker fleet size:

Task runtimes vary wildly (seconds to hours); the scheduler does NOT block on them.
Concurrent running tasks at peak: say 500,000 tasks actually executing at once
   (most waiting on IO / external systems - Spark, DB, API calls).
At ~200 concurrent tasks per worker (IO-bound, slot-based):
   500,000 / 200 = ~2,500 workers at peak.
Workers autoscale on queue depth / pending-eligible-task count, not on the
   scheduler's decision rate. The scheduler tier is small (tens of nodes);
   the worker tier is large and elastic.

The headline shape: millions of live task instances but only ~10 GB of hot state; the scarce resources are the event-driven eligibility-check throughput, contention on claiming a task for dispatch exactly once, and burst worker capacity when thousands of DAGs start at midnight - not raw storage. Size for the round-time spike, make dependency resolution event-driven and indexed, and keep the scheduler out of the task runtime path so a three-hour task does not tie up a scheduler slot.

High-Level Design (HLD)

The system splits into planes: an API / web tier that accepts DAG definitions, triggers, and control operations; a metadata store (sharded, strongly consistent) that holds workflow definitions, DAG runs, and every task instance’s state - the source of truth; a scheduler tier of stateless reconciler nodes that own shards of DAG runs, read persisted state, compute newly-eligible tasks, and enqueue them for execution; a task queue between scheduler and workers; a worker fleet of stateless executors that pull tasks, run the handler, and report state back; and a coordination service (Raft/ZooKeeper) for shard assignment and leader/liveness. An event bus carries task-completion events back to the scheduler to trigger event-driven eligibility checks.

  AUTHORS / CALLERS                    ┌──────────── COORDINATION (Raft quorum) ─────────────┐
 ┌──────────────┐                      │  - DAG-run shard assignment: which scheduler owns    │
 │ define DAG   │                      │    which shard of run_ids                            │
 │ trigger run  │                      │  - node liveness / failover (heartbeats, epochs)     │
 │ retry/clear  │                      └──────────────┬───────────────────────────────────────┘
 └──────┬───────┘                                     │ watch assignments
        │ 1. POST /dags, POST /dags/{id}/runs         │
        ▼                                             ▼
 ┌────────────┐  2. write DAG run +    ┌────────────────────────────────────────┐
 │  API /     │     all task instances │          METADATA STORE (sharded)        │
 │  web tier  │─────(state=pending)───►│  workflow_defs | dag_runs | task_instances│
 └────────────┘     durably            │  index: (shard, state, next_check_time)   │
                                       │  index: (run_id) ; (run_id, task_id)      │
                                       └───────────────┬────────────────────────────┘
                                                       │ 3. each scheduler reconciles ITS shards:
   ┌──────────── SCHEDULER TIER (stateless reconcilers) ┤    read runs + task states, compute
   │  node Sa owns run-shards {0,3}                     │    newly-eligible tasks (all upstream
   │  node Sb owns run-shards {1,4}  ◄── eligibility ───┘    succeeded), CLAIM + enqueue them
   │  node Sc owns run-shards {2,5}      events               (atomic state CAS pending->queued)
   └───────┬───────────────────────────────────────▲──────────────────────────────────────────┘
           │ 4. enqueue eligible task              │ 6. task-completion events
           ▼                                       │    (succeeded/failed) ->
  ┌────────────────────────┐        5. pull task,  │    event bus -> trigger eligibility
  │       TASK QUEUE        │           run handler,│    check on that task's children
  │  (durable, partitioned) │◄──────┐  heartbeat    │
  └───────────┬────────────┘        │  lease        │       ┌─────────────┐
              │ pull                 │              └────────│  EVENT BUS  │
              ▼                      │ 7. report state        └──────▲──────┘
   ┌──────────── WORKER FLEET (stateless, autoscaled on pending-eligible depth) ───────┐
   │   w0  w1  w2 ... wN  -> execute task, write result state (CAS), emit completion ───┘
   └────────────────────────────────────────────────────────────────────────────────────┘

Request flow - defining and triggering (the write path):

  1. An author POST /dags with a DAG definition: tasks, their handlers/params, and the dependency edges. The API validates it is acyclic (topological sort must succeed; reject cycles), versions it, and stores the definition.
  2. A trigger (cron fire from the scheduler primitive, an API call, or an event) creates a DAG run. The API/scheduler writes one dag_runs row and one task_instances row per task in state pending, durably and replicated, in a single shard keyed by run_id. From this instant the run’s entire structure and state is on disk - the scheduler can be restarted at any point and reconstruct exactly what is done and what is not.

Request flow - driving the DAG forward (the reconcile path):

  1. Each scheduler node owns a set of run-shards (assigned by coordination). It reconciles its runs: for each run, it finds newly-eligible tasks - tasks in state pending whose every upstream task is succeeded. Crucially this is driven by task-completion events (step 6), not a full re-scan: when a task finishes, the scheduler checks only that task’s direct children for eligibility.
  2. For each eligible task it performs an atomic claim: CAS state pending -> queued, owner, lease, conditioned on the row still being pending. The CAS makes dispatch exactly-one even if two schedulers evaluate the same task during a failover overlap. On a winning claim it enqueues the task onto the durable task queue.

Request flow - executing a task (the run path):

  1. A worker pulls a task, transitions it queued -> running (CAS), and executes the handler. While it runs, the worker heartbeats to extend its lease so the system knows it is alive and holding the task.
  2. On completion the worker writes the terminal state with a CAS (running -> succeeded or running -> failed) and emits a completion event onto the event bus. The scheduler consumes that event and runs an eligibility check on the finished task’s children (back to step 3). A succeeded event may unblock downstream tasks; a failed event (after retries exhausted) propagates upstream_failed to descendants and may fail the DAG run and alert.
  3. On transient failure the worker retries with backoff up to the task’s max_attempts; only after exhausting them is the task terminal-failed. If the worker dies mid-task, its lease expires and the task becomes visible again for redelivery - this is where at-least-once comes from, and why task handlers want idempotency.

The key architectural insight: the scheduler is a stateless function of the persisted DAG state, driven by completion events. It never holds the authoritative “what is done” in memory - that lives in the store. It never runs task code - workers do. Its only job is to read state, compute the delta (which tasks just became eligible), and apply idempotent transitions (claim + enqueue). That is what makes crash recovery a non-event (restart, re-read, continue), makes replicas safe (they converge on the same persisted facts), and lets the scheduler tier stay small while the worker tier scales out.

Component Deep Dive

Four hard parts: (1) persisting DAG execution state durably so the scheduler recovers mid-flight without re-running completed tasks - the headline problem; (2) resolving dependencies efficiently at scale without re-walking the whole graph; (3) propagating failure correctly and alerting, including partial failure; and (4) dispatching each eligible task exactly once across multiple schedulers and surviving the round-time spike. I will walk each from naive to scalable.

1. Durable DAG Execution State and Mid-Flight Recovery

The scheduler crashes forty minutes into a three-hour pipeline that has finished eleven of fifteen tasks. On restart, re-running those eleven means re-charging customers and double-writing the warehouse. This is the problem the whole system is built around.

Approach A: In-memory DAG state (the naive instinct)

Load the DAG into memory, keep a map task -> state, run a topological scheduler thread that marks tasks done as workers report back. Fast, simple, obvious.

scheduler process:
   dag = load_definition()
   state = { task: PENDING for task in dag.tasks }   # in memory
   while not done:
       for task in dag.tasks:
           if state[task]==PENDING and all(state[u]==DONE for u in upstream(task)):
               dispatch(task); state[task]=RUNNING
       on_report(task, result): state[task]=DONE or FAILED

Where it breaks: the state lives in the scheduler’s memory. When the process restarts - deploy, OOM, crash, a node reboot - the entire state map is gone. The scheduler comes back knowing the DAG structure but not that eleven tasks already ran. Its only safe options are both bad: re-run the whole DAG from scratch (re-executing completed side effects), or do nothing and leave the run wedged forever. Worse, it cannot even tell which tasks finished, because “done” was never written anywhere durable. In-memory state cannot survive the one event - a scheduler crash - that recovery exists to handle.

Approach B: Persist every task-instance state transition as the source of truth

Make the metadata store the source of truth for every task instance’s state, and treat the scheduler as holding no authoritative state at all. When a DAG run is created, write one task_instances row per task in state pending. Every transition - pending -> queued, queued -> running, running -> succeeded/failed - is a persisted, conditional (CAS) write that commits before it is acted on.

on create run:  INSERT task_instances (run_id, task_id, state='pending') for every task
on dispatch:    UPDATE ... SET state='queued'   WHERE run_id=? AND task_id=? AND state='pending'
on start:       UPDATE ... SET state='running'  WHERE ... AND state='queued'
on success:     UPDATE ... SET state='succeeded' WHERE ... AND state='running'
on failure:     UPDATE ... SET state='failed'    WHERE ... AND state='running' AND attempt>=max

Now recovery is trivial and is not a special code path. The scheduler restarts, reads its shards’ active runs and their task-instance rows, and sees exactly which tasks are succeeded (skip them - never re-run), which are pending (candidates for eligibility), and which were running. Reconciliation just continues from the persisted truth. Eleven succeeded tasks stay succeeded; the scheduler resumes at task twelve. Because the scheduler keeps nothing authoritative in memory, “crash and restart” is indistinguishable from “a slow tick” - it just re-reads the store.

The subtle case: tasks caught running at crash time. When the scheduler died, some tasks were running on workers. Two independent truths resolve this cleanly:

  • Workers are decoupled from the scheduler. A task runs on a worker, not in the scheduler. The scheduler dying does not kill the task - the worker keeps running it and will write the terminal running -> succeeded CAS and emit a completion event regardless of scheduler restarts. So an in-flight task completes normally and its result is persisted by the worker, not the scheduler.
  • Lease expiry handles a worker that also died. If the worker died too, its lease expires; the task is redelivered and its running row (with the stale lease) is reclaimed. The CAS on completion (WHERE state='running' AND lease_owner=me) plus a fencing token ensures a zombie worker’s late write is rejected. On recovery the scheduler treats a running row whose lease has expired as “re-dispatchable,” and a live-lease running row as “leave it, the worker owns it.”

Idempotent transitions make replay safe. Because every transition is a conditional CAS, replaying a reconcile is harmless: trying to move a task that is already succeeded fails the WHERE state='running' guard and is a no-op. So the scheduler can re-process the same completion event, re-evaluate the same task, or two replicas can both act - the store’s conditional writes serialize them into one real transition. The combination - persist-before-act, CAS transitions, lease + fencing on execution - is what lets the scheduler be a stateless reconciler that resumes mid-flight without ever re-running completed work.

Write the state transition before the side effect you cannot undo? The honest ordering: the scheduler persists queued before enqueuing, and the worker persists running before executing and succeeded after. Between “handler finished its side effect” and “worker wrote succeeded” there is a crash window where the side effect happened but the state says running - on redelivery the task runs again. That is the irreducible at-least-once window, handled by the idempotency key (part 4), not by pretending the window does not exist.

2. Dependency Resolution at Scale

A task is eligible when all its upstream tasks have succeeded. Computing that for millions of live task instances every tick is the thing that melts the scheduler.

Approach A: Re-topological-sort / full graph walk every tick (naive)

Each tick, for every active DAG run, walk the whole graph and check every pending task’s upstream states.

Where it breaks: with 200,000 concurrent runs averaging 50 tasks, that is 10M task instances re-evaluated every second. Most checks are pure waste - the vast majority of tasks had no upstream change since last tick, so re-checking them learns nothing. The scheduler spends all its CPU re-deriving a mostly-unchanged answer, and dependency-resolution latency balloons as the active set grows. Full graph walks make the cost scale with the live task-instance count, which is exactly the number that is huge.

Approach B: Event-driven eligibility with an upstream-completion counter

Flip it: a task is only worth re-checking when one of its upstreams just completed. When a task reaches succeeded, the scheduler (via the completion event) evaluates only that task’s direct children, not the whole graph. The cost becomes proportional to completions (thousands/sec), not to the live task count (millions).

To make each child’s check O(1) instead of “re-read all its upstreams,” maintain a remaining-upstream counter per task instance, initialized at run creation to the task’s in-degree:

on create run: for each task, task.remaining_upstreams = in_degree(task)
on a task T succeeding:
   for child in children(T):
       new = atomic_decrement(child.remaining_upstreams)   # persisted counter
       if new == 0:
           child is ELIGIBLE -> claim + enqueue
  • O(1) per edge, event-driven. Each completed task decrements each child’s counter once; a child becomes eligible exactly when its counter hits zero. Total work across a DAG run is proportional to the number of edges, spread over the run’s lifetime, not re-derived every tick. This is the scalable dependency engine.
  • The decrement must be atomic and idempotent. Two risks: a completion event processed twice would double-decrement and prematurely fire a task; concurrent completions of two upstreams racing on the same child could both read “1 remaining.” Fix both by making the decrement a conditional, idempotent operation: record per-edge “T -> child satisfied” (a row/flag) and only decrement if that edge was not already marked satisfied. Then re-processing a completion event is a no-op, and the counter reflects distinct satisfied edges. Eligibility (counter == 0) is derived from facts, so it is safe to recompute.
  • A periodic reconcile sweep as a backstop. Event-driven is the fast path, but an event can be lost (bus hiccup) and leave a task’s counter stale. Run a low-frequency full reconcile (every few minutes) over active runs that recomputes eligibility from the authoritative task states and repairs any drift. The event path is for latency; the sweep is for correctness - belt and suspenders.

Richer dependency semantics. Real engines need more than “all upstreams succeeded.” Expose a per-task trigger rule: all_success (default), all_done (run even if an upstream failed - cleanup tasks), one_success (fan-in where any one branch suffices), all_failed, etc. The eligibility check becomes “is this task’s trigger rule satisfied by its upstreams’ terminal states,” which the counter model generalizes to (count toward the rule’s threshold). This is what lets a DAG express “run the alert task if any extract failed” or “always run teardown.”

The move that makes dependency resolution scale: evaluate eligibility only on upstream completion, using a persisted per-task remaining-upstream counter with idempotent per-edge decrements, backstopped by a periodic reconcile sweep. Cost tracks edges and completions, not the live task-instance count.

3. Failure Propagation, Partial Failure, and Alerting

A task exhausts its retries. The naive engine either hangs its descendants forever or crashes the whole run opaquely. Neither is acceptable.

Approach A: Fail the whole DAG run, retry everything (naive)

On any task failure, mark the DAG run failed; to recover, re-run the entire DAG.

Where it breaks: two failures. First, descendants of the failed task are left in limbo - if you do not explicitly mark them, they sit pending with an upstream that will never succeed, and their counters never hit zero, so the run hangs forever with no clear signal. Second, re-running the entire DAG throws away every branch that succeeded - the eleven completed tasks are re-executed, re-triggering their side effects, which is the exact thing we worked to avoid in part 1. Treating failure as all-or-nothing wastes completed work and can corrupt it.

Approach B: Propagate upstream_failed, preserve partial success, alert, and support granular retry

Model failure as state that propagates through the graph, with completed branches preserved:

task T exhausts retries -> state = FAILED, emit completion(FAILED)
on failure event:
   for every descendant D reachable from T whose trigger_rule needs T to succeed:
       D.state = UPSTREAM_FAILED   (it will NEVER become eligible; stop waiting)
   independent branches not downstream of T keep running to completion
when the run has no PENDING/RUNNING tasks left:
   run.state = FAILED if any task FAILED/UPSTREAM_FAILED else SUCCEEDED
   (partial: some tasks succeeded, some upstream_failed - run is FAILED but
    completed tasks stay succeeded and are not re-run on retry)
  • Descendants stop waiting, explicitly. Marking reachable descendants upstream_failed (respecting trigger rules - an all_done cleanup task still runs) means no task hangs forever on a dead upstream, and the run reaches a terminal state deterministically. The counter model cooperates: an upstream_failed task is terminal, so it never fires and never blocks the run-completion check.
  • Partial success is preserved and is the basis of retry. Because every task’s terminal state is persisted independently (part 1), a failed run keeps its succeeded tasks succeeded. Retrying the run re-executes only the failed/upstream_failed tasks, starting from the failure point, reusing all completed work. This is “clear and retry from the failed task,” the single most important operability feature, and it is a direct payoff of persisting per-task state.
  • Alerting is driven off terminal failure, deduplicated. When a task goes terminal-failed or a run goes failed, emit an alert through a notification service (page/Slack/email, per the DAG’s alert policy). Deduplicate and throttle: a DAG that fails every hour should not page 24 times; collapse repeated failures of the same task/run into one alert with a count, and route by severity (a critical pipeline pages, a best-effort one just logs). Also alert on SLA misses - a DAG run that has not finished within its expected window - which requires tracking per-run start time and expected duration.
  • Retries are per task with backoff, before propagation. Propagation only happens after a task exhausts its own max_attempts with exponential backoff and jitter. A transient failure (worker died, target 503) is retried in place; only a persistent failure propagates. Keep the attempt counter on the task-instance row so retries survive scheduler restarts too.

Failure handling is where persisted per-task state pays off twice: descendants get an explicit upstream_failed so nothing hangs, and completed branches are preserved so retry resumes from the failure point instead of re-running the DAG - plus deduplicated, severity-routed alerting on terminal failure and SLA miss.

4. Exactly-Once Dispatch and Surviving the Round-Time Spike

Multiple schedulers for availability means a task can be dispatched twice; humans scheduling DAGs at midnight means load is spiky.

Approach A: Single scheduler, dispatch everything the instant it is eligible (naive)

One scheduler process evaluates and dispatches; at midnight, ten thousand cron DAGs start and it enqueues every root task at once.

Where it breaks: the single scheduler is a single point of failure and a throughput ceiling - when it dies, all DAG progress stops; at the midnight spike it cannot evaluate and dispatch the flood fast enough and falls minutes behind. Running a second scheduler for availability immediately reintroduces double-dispatch: both see the same eligible task and enqueue it twice.

Approach B: Partitioned run ownership + atomic claim + smear and queue-buffer the spike

  • Shard DAG runs across schedulers, one owner per shard. Partition the run_id keyspace into K shards (K far larger than node count); the coordination service assigns each shard to exactly one scheduler. Each scheduler reconciles only its runs, so eligibility evaluation and dispatch spread across all schedulers, and a given run is driven by one node. Add schedulers to scale the decision rate; lose one and its shards reassign within a heartbeat timeout. Sharding by whole run_id keeps all of a DAG run’s tasks on one owner, so dependency resolution within a run is local - no cross-node coordination to decrement a counter.
  • Atomic claim as the correctness backstop. Ownership can briefly overlap during failover (a scheduler declared dead by a GC pause is actually alive). So dispatch is a conditional claim: UPDATE task_instances SET state='queued' WHERE run_id=? AND task_id=? AND state='pending'. Only one CAS wins; a duplicate evaluation sees the row already queued and skips. Attach a fencing token (epoch) to shard ownership so a zombie scheduler’s stale write is rejected by the store. Ownership gives efficiency and usually single-dispatch; the CAS plus fencing guarantees exactly-one dispatch even during overlap. Never rely on ownership alone for correctness.
  • At-least-once execution, effectively-once via idempotency key. Dispatch is onto a durable queue with visibility leases and explicit ack (the worker leases a task, heartbeats while running, acks on done; no ack means lease expiry and redelivery). That makes execution at-least-once: a task is never lost, occasionally repeated. Each task instance carries a stable idempotency key (deterministic from run_id + task_id + attempt_generation), so a handler that writes to a cooperating store can dedup the repeat into a no-op. The scheduler’s view stays exactly-once because the terminal transition is a CAS (running -> succeeded wins once). Effectively-once = at-least-once transport + idempotent task + conditional state.
  • Smear and queue-buffer the midnight spike. Ten thousand DAGs at exactly :00:00 is a self-inflicted DDoS. Three mechanisms: jitter the DAG-run start times over a short window (most pipelines do not care about sub-minute precision), so roots do not all become eligible at the same instant; a durable, partitioned task queue between scheduler and workers buffers the residual burst, converting a dispatch spike into bounded latency instead of loss; and autoscale the stateless worker fleet on pending-eligible-task depth and oldest-pending age, the signal that directly measures falling behind. Separate priority queues/pools (a critical pipeline’s tasks vs bulk backfills) so a flood of low-priority backfill work cannot starve latency-critical DAGs.

Partitioned run ownership spreads the scheduling load and makes single-dispatch common; the atomic claim with fencing guarantees exactly-one dispatch during failover overlap; leases plus a stable idempotency key give effectively-once execution on an at-least-once transport; and jitter + a buffering queue + lag-based autoscaling tame the round-time spike.

API Design & Data Schema

Definition and control API (control plane)

POST /dags                                   # define / version a workflow
  { "dag_id": "daily_etl",
    "schedule": "0 2 * * *", "timezone": "Asia/Kolkata",
    "default_retry": { "max_attempts": 3, "backoff": {"base_ms":2000,"factor":2,"max_ms":300000} },
    "sla_ms": 3600000,                        # alert if run exceeds 1h
    "alert_policy": { "on_failure": ["page","slack:#data"], "dedup_ms": 3600000 },
    "tasks": [
      { "task_id": "extract_a", "handler": "ext.a", "deps": [] },
      { "task_id": "extract_b", "handler": "ext.b", "deps": [] },
      { "task_id": "transform", "handler": "xf",    "deps": ["extract_a","extract_b"],
        "trigger_rule": "all_success" },
      { "task_id": "load",      "handler": "load",  "deps": ["transform"] },
      { "task_id": "teardown",  "handler": "clean", "deps": ["load"], "trigger_rule": "all_done" }
    ] }
  -> 201 { "dag_id": "daily_etl", "version": 7 }      # rejected 400 if the graph has a cycle

POST   /dags/{id}/runs        -> trigger a run now (or with logical_date/params) -> { run_id }
GET    /dags/{id}/runs/{run}  -> run state + per-task states + timings
GET    /runs/{run}/tasks/{t}/logs -> task logs (from log store, paginated)
POST   /runs/{run}/tasks/{t}/retry -> clear one failed task + its downstream, re-run from there
POST   /runs/{run}/retry      -> re-run only failed/upstream_failed tasks (keep succeeded)
POST   /dags/{id}/backfill    -> create runs for a historical date range (bulk, bounded, smeared)
POST   /dags/{id}/pause       -> stop triggering new runs
DELETE /runs/{run}            -> cancel in-flight run (stop dispatch, signal workers to abort)

Internal worker API (data plane, via the queue client)

PULL   -> lease a task: { run_id, task_id, attempt, handler, params_ref,
                          idempotency_key, lease_until }
          task invisible to others until lease_until; worker CAS queued->running
HEARTBEAT(run_id, task_id) -> extend lease_until (periodic while running)
REPORT_SUCCESS(run_id, task_id) -> CAS running->succeeded; emit completion(SUCCEEDED)
REPORT_FAILURE(run_id, task_id, err) -> attempt++; if attempt<max requeue w/ backoff,
                          else CAS running->failed; emit completion(FAILED)

Data model: the metadata store

The core is a sharded, strongly-consistent store with point lookups by run_id/task_id and an indexed scan for the reconcile sweep. Three tables matter.

workflow_defs (one row per DAG version):

dag_id         STRING
version        INT
schedule       STRING          # cron; null for manual/event-triggered
graph          JSON            # tasks + edges + trigger rules + retry policy (validated acyclic)
sla_ms         INT
alert_policy   JSON
created_at     TIMESTAMP
PRIMARY KEY (dag_id, version)   # definitions are immutable + versioned

dag_runs (one row per execution of a workflow):

run_id         STRING   PRIMARY KEY
dag_id         STRING   INDEX
dag_version    INT                      # pin the definition this run uses
shard          INT                      # hash(run_id) % K; owned by one scheduler
state          ENUM     # pending | running | succeeded | failed | cancelled
logical_date   TIMESTAMP                # the "for when" date (backfills, idempotency)
started_at, finished_at TIMESTAMP
total_tasks, done_tasks INT             # for cheap run-completion checks
INDEX idx_active (shard, state, started_at)   # reconcile sweep over active runs

task_instances (one row per task per run - the hot table, the source of truth):

run_id             STRING                 # partition key (co-locate a run's tasks)
task_id            STRING
state              ENUM   # pending | queued | running | succeeded | failed |
                   #        upstream_failed | skipped
attempt            INT
max_attempts       INT
remaining_upstreams INT                   # eligibility counter (decrement per satisfied edge)
trigger_rule       ENUM   # all_success | all_done | one_success | all_failed
owner_worker       STRING
lease_until        TIMESTAMP
fencing_epoch      BIGINT                 # reject stale zombie-worker writes
idempotency_key    STRING UNIQUE          # run_id + task_id + attempt_generation
params_ref         STRING
started_at, finished_at TIMESTAMP
error              TEXT
PRIMARY KEY (run_id, task_id)
INDEX idx_lease (state, lease_until)      # reclaim expired running tasks
# satisfied-edges ledger (dedup decrements): UNIQUE (run_id, from_task, to_task)

Coordination state (in the Raft/ZooKeeper quorum, not the metadata store):

shard_assignment: shard_id -> { owner_node, epoch (fencing token), lease_until }
node_registry:    node_id  -> { host, last_heartbeat, status }

SQL vs NoSQL - the choice and why. The metadata store wants strong consistency (the claim CAS, state transitions, and the eligibility-counter decrement must not race), conditional writes (claim a task only if still pending; advance state only from the expected prior state), and horizontal sharding (millions of live task instances, tens of thousands of transitions/sec). That points to a sharded relational / NewSQL store (Postgres/MySQL sharded by run_id, or CockroachDB/Spanner) or a strongly-consistent store with conditional expressions (DynamoDB with condition expressions and a GSI for the sweep). The deciding factor is the conditional transition: you need a real UPDATE ... WHERE state=? / SELECT ... FOR UPDATE SKIP LOCKED / conditional-write. An eventually-consistent store cannot safely drive a state machine where “exactly one owner” and “a succeeded task is never re-run” are the core invariants, so it is the wrong pick for task_instances. SELECT ... FOR UPDATE SKIP LOCKED is worth a callout: it lets multiple scheduler workers claim disjoint eligible tasks concurrently without double-claiming, the simplest correct mechanism at moderate scale. Co-locating a run’s task instances under one partition key (run_id) keeps dependency resolution and recovery local to one shard - no distributed transaction to advance one DAG. Logs are append-only and bulky - put them in object storage / a log store, not the metadata DB.

Bottlenecks & Scaling

Where it breaks first, in order, and the fix for each:

1. Scheduler keeps DAG state in memory and loses it on crash. A restart re-runs completed tasks or wedges the run. Fix: persist every task-instance state transition as the source of truth; the scheduler is a stateless reconciler that re-reads the store on start and resumes from succeeded facts. Recovery is “re-read and continue,” not a special path. This is the single most important decision.

2. Dependency resolution is a full graph walk every tick. 10M live task instances re-evaluated per second melts the scheduler. Fix: event-driven eligibility - evaluate a task only when an upstream completes - with a persisted per-task remaining-upstream counter (idempotent per-edge decrement), backstopped by a low-frequency reconcile sweep for lost events. Cost tracks edges/completions, not live task count.

3. A task is dispatched twice (multiple schedulers). Availability needs multiple schedulers; naively they double-dispatch. Fix: partitioned run ownership (one scheduler per run_id shard) plus an atomic conditional claim (pending -> queued CAS) with a fencing token during failover overlap. Ownership for efficiency, CAS+fencing for correctness.

4. Single scheduler is a throughput ceiling and SPOF. One node cannot evaluate the midnight flood and stalls everything if it dies. Fix: shard DAG runs across many schedulers (K shards » nodes); decision rate scales with node count; reassign a dead node’s shards within a heartbeat timeout.

5. Midnight spike (self-inflicted DDoS). Thousands of cron DAGs start at :00:00. Fix: jitter run start times over a window, buffer the burst in a durable queue (dispatch spike becomes bounded latency), and autoscale stateless workers on pending-eligible depth / oldest-pending age. Priority pools so bulk backfill cannot starve critical DAGs.

6. Worker dies mid-task / task lost. A crashed worker holding a long task. Fix: visibility leases with heartbeats + explicit ack - no ack means lease expiry and redelivery (at-least-once); heartbeats let long tasks extend their lease so they are not double-run; a hard max stops a runaway. The scheduler keeps progressing because workers complete tasks independently of it.

7. Duplicate task execution. Redelivery and lost-ack retries run a task twice. Fix: stable idempotency key (run_id + task_id + attempt_generation) with a unique constraint / dedup ledger so the repeat is a no-op, plus conditional terminal transitions (running -> succeeded CAS) so the scheduler’s view stays exactly-once. Effectively-once = at-least-once + idempotent task.

8. Failed task hangs its descendants or fails the whole DAG opaquely. Fix: propagate upstream_failed to reachable descendants (respecting trigger rules) so nothing waits forever; preserve succeeded branches so retry resumes from the failure point instead of re-running the DAG; terminal-failure detection reaches a deterministic run state.

9. Alert storms. A DAG failing every run pages dozens of times. Fix: deduplicate and throttle alerts (collapse repeated failures into one with a count), route by severity, and add SLA-miss alerts (run exceeded expected window) off persisted run start times.

10. Hot shard / skew. One scheduler shard owns disproportionately many active runs. Fix: enough shards that any one is a small slice; hash by run_id (not by dag_id, which skews when one DAG runs far more often); split and reassign a persistently hot shard.

11. Coordination service as a single point of failure. If shard assignment dies, no failover happens. Fix: run coordination as a replicated Raft quorum (3 or 5 nodes) with tiny state (shard assignments, liveness, epochs); schedulers cache their assignment so a brief coordinator blip does not stop in-flight reconciliation.

12. Metadata and log storage explosion. Billions of historical task instances and verbose logs. Fix: keep recent runs hot, roll older task-instance history to cheap cold/columnar storage, store logs in object storage (not the metadata DB), aggregate per-run summaries, and TTL the satisfied-edges ledger and idempotency keys once a run is safely terminal.

Wrap-Up

The trade-offs that define this design:

  • The durable store is the source of truth; the scheduler is stateless. Every task-instance state transition is persisted (CAS) before it is acted on, and the scheduler holds nothing authoritative in memory. We trade the simplicity of an in-memory DAG for free mid-flight recovery, safe replicas, and a scheduler that resumes after a crash by re-reading state and never re-running completed tasks. This separation is the whole design.
  • Dependency resolution is event-driven, not a graph walk. A persisted per-task upstream counter, decremented idempotently per satisfied edge on upstream completion, makes eligibility O(edges) over a run’s life instead of O(live task instances) per tick - with a periodic reconcile sweep as the correctness backstop for lost events.
  • Ownership for efficiency, atomic claim for correctness. Partitioned run ownership spreads scheduling load and makes single-dispatch common, but the conditional claim with a fencing token is what guarantees a task is dispatched exactly once, even when ownership overlaps during failover. Never trust ownership alone.
  • At-least-once execution, effectively-once by construction. Leases with explicit acks mean a task is never lost and sometimes repeated; a stable idempotency key and conditional terminal transitions make the repeat harmless and keep the scheduler’s view exactly-once. Exactly-once across failure is impossible, so we supply the key and let the task dedup.
  • Failure preserves completed work. Persisted per-task state lets a failed run keep its succeeded branches, propagate upstream_failed so nothing hangs, and retry only from the failure point - with deduplicated, severity-routed alerting on terminal failure and SLA miss.

One-line summary: a durable, sharded metadata store that holds every task instance’s state as the source of truth, a stateless scheduler tier that partitions DAG-run ownership and drives the graph forward with event-driven eligibility (per-task upstream counters) and atomic, fencing-guarded claims, a durable queue that decouples dispatch from a stateless autoscaled worker pool executing at-least-once under heartbeat-extended leases - where mid-flight recovery falls out of persist-before-act plus CAS transitions, effectively-once falls out of a stable idempotency key, and partial-failure retry falls out of preserving per-task state.