Graph Scheduler — prior-art research

State: open/active · Genre: research

Prior art behind PR-DZTZ-graph-scheduler and D-BPD8-graph-scheduler-api. Surveys systems that answer some form of “which nodes are runnable now?” and extracts the API shapes, naming, and pitfalls worth borrowing.

Recommendation in one paragraph

Model the core on Python’s graphlib.TopologicalSorter — an incremental frontier (get_ready / done) — but generalize its binary “done” into a small status enum so Airflow-style trigger rules are expressible, and add the two layers those stdlib/library analogs lack: eligibility filters and priority ordering, both borrowed from the Kubernetes filter → score scheduling framework. Keep capacity out of the core (the caller asks for N); keep weighted resource budgets (Buck2) and pull/goal-direction (Buck2 DICE) as opt-in layers.

1. Closest analog — graphlib.TopologicalSorter (Python stdlib)

The nearest thing to graph-scheduler’s core. Incremental frontier API:

ts = TopologicalSorter(graph)
ts.prepare()
while ts.is_active():
    ready = ts.get_ready()   # ALL nodes whose deps are done, right now
    # run some/all of them ...
    ts.done(*finished)       # completing nodes re-opens the frontier

• get_ready() returns the whole ready frontier, not “next N” — the caller loops/slices. Graph-scheduler’s getReady({ limit }) makes “next N” first-class.
• State is stateful/incremental: the sorter tracks done. Graph-scheduler instead takes caller-supplied state (a pure function of graph + state), with an optional stateful wrapper — see D-BPD8-graph-scheduler-api.
• No rules, categories, ordering, or reasons. This is the gap the product fills.

Source: https://docs.python.org/3/library/graphlib.html

2. DAG workflow orchestrators

System	Runnable decision	Concurrency cap	Per-node condition	Ordering
Airflow	upstream states satisfy the task’s trigger_rule	pools + slots	trigger_rule (12 presets)	priority_weight (+ weight_rule)
Dagster	upstream materialized / asset freshness	run/backfill concurrency	asset checks, sensors	run-queue priority
Prefect	upstream futures resolved	work-pool concurrency limits	task-run states, wait_for	(queue)

Airflow is the design source for two features:

• trigger_rules generalize “all deps done”: all_success (default), all_failed, all_done, one_success, one_failed, one_done, none_failed, none_failed_min_one_success, none_skipped, always. These require knowing how a parent finished — the reason graph-scheduler’s state is an enum, not a boolean. https://airflow.apache.org/docs/apache-airflow/stable/core-concepts/dags.html#trigger-rules
• priority_weight + weight_rule rank the ready set when slots are scarce; weight_rule: downstream makes a task inherit the weight of everything it unblocks (critical-path bubbling). https://airflow.apache.org/docs/apache-airflow/stable/administration-and-deployment/priority-weight.html

3. Kubernetes scheduling framework — filter → score

The canonical two-phase pattern and the model for graph-scheduler’s rule API. A scheduling cycle runs PreFilter → Filter → PostFilter → PreScore → Score → NormalizeScore → Reserve → Permit.

• Filter eliminates ineligible candidates (hard predicate); Score ranks the survivors (soft). Maps directly onto graph-scheduler’s eligibility filters and sorters.
• Predicate signature returns a reasoned status, not a bool: Filter(ctx, state, pod, nodeInfo) *Status, built with NewStatus(code, reasons...). The two-tier reject code — Unschedulable (retry might help) vs UnschedulableAndUnresolvable (never) — is the single most transferable idea: a rule says not just no but no, and don’t re-test me until X changes. Powers explain().
• Registry = map[string]PluginFactory (name → constructor); available vs active plugins are decoupled via config, with per-plugin typed args.
• Pitfall: percentageOfNodesToScore stops scoring early for latency, so the globally-best candidate may never be scored — a completeness/optimality trade-off to document, not hide.

Sources: https://kubernetes.io/docs/concepts/scheduling-eviction/scheduling-framework/, interface.go https://github.com/kubernetes/kubernetes/blob/master/staging/src/k8s.io/kube-scheduler/framework/interface.go, registry.go https://github.com/kubernetes/kubernetes/blob/master/pkg/scheduler/framework/runtime/registry.go

4. Build systems

System	Ready frontier	Job limit	Resource pools
Ninja	leaf-up dependency graph	-j (semaphore of permits)	pool with depth
Bazel	action graph, RE fan-out	--jobs	--local_resources, action resource_set
Buck2	pull/demand-driven (DICE)	-j / [build] threads	per-action weight + HostSharingRequirements
Make	recursive prerequisite check	-j	(none native)

Buck2 contributes two ideas beyond the push frontier:

• Pull / demand-driven (DICE). Instead of enumerating the global frontier, you request a target (ctx.compute(Key)) and it pulls transitive deps on demand; “ready” falls out of the graph. (ctx.compute(Key) demands a computation’s result by its input Key — running that node and transitively pulling its deps if not already memoized; graph-scheduler’s pull layer mirrors this “request a target, resolve toward it” shape.) This is the model for graph-scheduler’s goal-directed / pull wrapper — “next N toward goal G” restricts the frontier to ancestors(G). https://github.com/facebook/buck2/blob/main/dice/dice/docs/index.md
• Weighted resource budget. Each action declares a WeightClass (Permits / Percentage) and a HostSharingRequirements (Exclusive / OnePerToken / OnePerTokens / Shared); the scheduler packs a batch under a permit budget, and a LowPassFilter drops low-priority work to zero permits when oversubscribed (anti-thrash). This generalizes per-category caps and is the reference for the deferred weighted-budget feature (a non-goal for v1). https://github.com/facebook/buck2/blob/main/host_sharing/src/host_sharing.rs

A deliberate non-feature worth copying: Buck2 exposes no critical-path priority scheduler as a user knob — critical path is observability-only. Argues for keeping graph-scheduler’s ordering simple (insertion order or a plain weight) and treating critical-path as something to report, not schedule by.

5. Job / queue schedulers

• Nomad — same two-phase shape as K8s, assembled as a literal Stack (“ranking objects stacked over feasibility objects”) so feasibility can’t be skipped. FeasibilityChecker.Feasible(node) bool returns a bare bool and reports the reason via a metrics side-channel — the pattern to avoid (keep the reason with the verdict). Keeps the top ~5 via a heap, not a full sort — the efficiency trick for “next N”. https://github.com/hashicorp/nomad/blob/main/scheduler/feasible/feasible.go
• Slurm — sorts the pending queue by one scalar Multifactor Priority (age, fairshare, job-size, QOS, …), then backfills. age_factor is its anti-starvation mechanism; a documented surprise is that the highest-priority job is not always evaluated first (priority inversion via reservations). https://slurm.schedmd.com/priority_multifactor.html
• Quartz — the veto pattern: a TriggerListener.vetoJobExecution(...) boolean gates execution, registered on a ListenerManager with a Matcher that scopes which triggers a rule applies to. The Matcher (separating “does this rule apply here” from “is this eligible”) is worth borrowing. https://www.quartz-scheduler.org/api/2.2.3/org/quartz/TriggerListener.html

6. Graph substrate libraries

Library	Language	Gives us	Note
graphology	JS	rich graph model, traversal, serialization	heaviest; event model may be overkill
graphlib / dagre	JS	directed graph + topological sort	dagre is layout-oriented
petgraph	Rust	DAG algorithms, toposort	if a Rust core is ever wanted
NetworkX	Python	everything, incl. topological_generations	reference semantics

topological_generations (NetworkX) is notable: it yields the frontier generation by generation — exactly the “layers of parallel-safe work” shape. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.topological_generations.html

Wrap vs. hand-roll: the frontier algorithm (Kahn’s) is small and the zero-dep-core tenet (PR-0002-intersect) argues for hand-rolling the L0 graph, with a library adapter only if serialization/visualization/other algorithms are later needed. Settled in D-BPD8-graph-scheduler-api.

7. Naming precedent

Concept	Precedent term(s)	Chosen
Runnable set	ready set / frontier / generation	getReady, “frontier”
Mark complete	done() (graphlib)	status transition
Eligibility gate	filter (K8s), feasibility (Nomad), veto (Quartz)	filter
Ranking	score (K8s), priority (Slurm/Airflow)	sorter / priority_weight
Per-node condition	trigger_rule (Airflow)	triggerRule
Reasoned reject	Status + code (K8s)	verdict + explain()
Rule scoping	Matcher (Quartz)	appliesTo

8. Pitfalls to design against

• Boolean “done” is insufficient once trigger rules exist — success / failed / skipped must be distinguishable (D-BPD8-graph-scheduler-api).
• Double-dispatch — a dispatched-but-unfinished node reappears in the next frontier unless a running state excludes it.
• Starvation under caps — a low-priority category can be perpetually outranked; Slurm’s age_factor and round-robin fairness are the mitigations.
• Reason side-channels (Nomad) — keep the ineligibility reason attached to the verdict, not in metrics.
• Early-stop optimality (K8s percentageOfNodesToScore, Nomad top-N heap) — if we bound work for latency, log/surface it rather than silently returning a non-optimal set.
• Cycles — a dependency cycle has no frontier; reject at construction or report explicitly.
• Dynamic mutation — adding nodes/edges mid-run (Airflow dynamic tasks); the immutable core rebuilds rather than mutating in place.

---

← Back to Notes