Handling task dependencies at Scale

LeastAction never materialises the dependency graph. Each task names its parents and resolves them when its turn comes. Here is the model, the call path, the concurrency, and a 90-day backfill traced through this design and through a DAG file.

There are two places to write a dependency down. In a file, where the edge is a statement the scheduler parses, so the parser holds the whole shape and can validate it, order it and draw it. Or on the task, where each unit carries its own parents and resolves them when its turn comes, and nothing ever holds the whole shape at once.

We took the second, because the unit of scheduling here is already the task: independent rows with their own state, schedule and partition. A file-level graph would have meant a second source of truth above those rows, re-parsed and redeployed on every change.

---

PART 1 · HIGH-LEVEL DESIGN

The graph is a query result, not a stored object

No edge is ever persisted as an edge. A task holds a list of parent descriptors, and the graph rendered in the UI is the union of those declarations, computed on read.

Contract · a pre-action returning a boolean — run(action_object, parents) -> bool

LeastActionCheckIfParentsAreDone is a pre-action: a codeblock the platform runs before dispatch, whose return value determines whether dispatch continues.

returns True   -> task proceeds down the pipeline
returns False  -> dropped from this pass

The false branch writes nothing at all. The task retains whichever state it was selected in and is re-evaluated on the next tick, so being blocked is the absence of a transition rather than a transition of its own.

State · two timestamps, on every task — logical_date / prev_interval_start

logical_date is the interval a task is running for, the data epoch rather than the wall clock. prev_interval_start is the interval it last finished: on success a task copies its own logical_date into it, recording which slot completed rather than when. Both sit on every task, parent or child, and logical_date advances only inside the success path, so a task never advances past an interval it did not complete. A parent is found by the task's primary key (name, project, account and partition), which is what lets it live in another team's project on another schedule.

A blocked task and a task that isn't due yet are the same thing to this scheduler. That is exactly why blocking is free, and exactly why nothing alerts on it.

---

PART 2 · LOW-LEVEL DESIGN

From cron tick to worker

Every project runs its own scheduler: CronExecutor.run(), a Celery job supervised by heartbeat. Its work loop polls on a project_scheduler_interval cycle, five seconds by default, and queries the catalog for due tasks. That query is an allow-list on state: scheduled, success or created with next_run_date in the past, plus a retry branch. Anything already running or holding a connection slot is structurally excluded, so a slow run cannot stack up behind itself.

1. validate · dates, connection-operator pairing, referenced items; config merged workflow → task → inline.
2. pre_actions · here is where the dependency check lives. Anything that fails gets dropped from the list.
3. connection queue · survivors grouped by connection, released against available parallelism.
4. payload render · Jinja over merged config and the builtins derived from logical_date.
5. dispatch · the worker runs the operator, writes state back, and advances the schedule.

On the false path, nothing to the right of the gate is touched.

The ordering is the argument. The gate is a semantic check (is the upstream interval present?) and the connection queue is a resource check (can this connection take another concurrent task?). Semantic first means a blocked task never becomes a resource question. Shard a workflow across forty partitions and the blocked ones cost 1 + N catalog reads every five seconds and nothing else; workers track what is runnable, not how large the graph has grown.

Inside the gate: one lookup for itself, one per parent, keyed on that same primary key. A parent is rejected outright in error, fail, cancelled or cancel. Then the timing half. The parent's cron is evaluated one step back from the child's logical_date, yielding the most recent parent slot at or before it, and both that and the parent's prev_interval_start are truncated to the parent's granularity. The boundary is inclusive by construction: croniter is seeded one second past the anchor, so a child interval landing exactly on a parent slot resolves to that slot rather than the one before.

expected    = _prev_cron_time(parent_frequency, child_logical_date)
actual      = isoparse(parent["prev_interval_start"])
granularity = _get_cron_granularity(parent_frequency)
return _truncate_dt(actual, granularity) >= _truncate_dt(expected, granularity)

Granularity comes from the parent, so mixed frequencies need no special case. A weekly parent satisfies a daily child, because the question is never "did you run today" but "have you finished the interval that covers mine".

The write side closes the loop. On success the executor copies logical_date into prev_interval_start, advances it one cron step, and advances next_run_date one interval from the previous next_run_date rather than from the clock. If that is still in the past, the task is due again immediately. Catch-up is not a separate mode; it is what falls out of advancing the schedule from the schedule.

---

PART 3 · CONCURRENCY AND FAILURE

Three loops and one contended counter

One executor per project, three loops inside it, joined by asyncio.gather and stopped by a shared event: work dispatches, heartbeat writes liveness, cleanup reaps. Liveness is on its own loop deliberately. If the work loop wrote the heartbeat, a slow batch would be indistinguishable from a dead scheduler, and the supervisor would restart one that was merely busy.

Throttling happens in one place, at the contended resource rather than the worker fleet. Every connection carries a max_parallelism; each pass computes max_parallelism - current_parallelism and releases min(available, in_queue) tasks in that connection's sort order. A global pool would let one slow warehouse starve every other pipeline. Those counters are contended, with a scheduler enqueueing while workers finish and decrement, so enqueue and dequeue run under optimistic concurrency with five retries and backoff rather than a lock.

The gate sits on a transition, not in a state. A rejected task is left exactly as it was found — false means no transition at all.

Failure detection runs at two levels. Workers heartbeat while running, and the cleanup loop fails and dequeues anything past the staleness threshold (12.5 seconds by default), which is what releases the connection's counter. But an out-of-memory SIGKILL takes the process before it can record anything, so the same loop also queries Celery's result backend for the run state, which reports FAILURE or REVOKED the moment the worker is lost. At the scheduler level, the project's heartbeat is stale after three intervals. Both detectors only look at running, so a task held at the gate falls outside both.

---

PART 4 · A 90-DAY BACKFILL, TRACED

Re-running history

Three daily tasks. orders_raw writes the landing table and belongs to another team in another project; orders_enriched reads it; orders_daily_report reads that. A column was computed wrong, so 90 days have to be re-run, upstream first for each day.

In the DAG-file model the two pipelines are separate parse units, so the cross-pipeline edge is a sensor carrying an interval offset that must be right for every slot in the range, the re-run is a run-level operation, and a poking sensor holds a worker slot unless it is written to defer.

In the task-level model there is no backfill mode and no second code path, because the check never referred to the present in the first place. The 90 slots are the same three tasks with their interval set back across the range: each success advances next_run_date from the previous one, so while that stays in the past the task is selected again on the next five-second tick and advances one interval, re-running the same gate at every slot. Ninety slots are not ninety sensors; they are one task evaluated ninety times.

What the choice costs

• Reruns do not cascade. Resolution is pull-based, so re-running a parent for a day the child already consumed will not re-trigger it. You re-run the subtree.
• Names are the contract. Rename a parent and its children start reporting that it cannot be found, and stop. There is no reference to update, because there was never a reference, only a name.

---

LeastAction - source-available, self-hosted data orchestration.

github.com/LeastAction-Labs/LeastAction