DUE TO SPAM, SIGN-UP IS DISABLED. Goto Selfserve wiki signup and request an account.
Status
Motivation
The critical section in Airflow's scheduler uses an optimistic strategy: it fetches a batch of scheduled task instances from the database (up to max_tis_per_query), then filters them in Python against all concurrency limits:
- pool slots
max_active_tasks_per_dagmax_active_tis_per_dag,max_active_tis_per_dagrun- executor slots (exception as it's local to scheduler).
This works well enough for standard workloads. However, in large-scale deployments with thousands of tasks—often driven by dynamic task mapping—it causes starvation, where the scheduler fixates on tasks from one constrained group, discards most after checks, and queues far fewer than possible per cycle. The issue appears identically across every one of these limits. It was first noted with prioritized pools nearly full, starving lower-priority ones despite free slots (Issue 45636). Unknown User (xbis) highlighted the same with huge DAGs hitting max_active_tasks. (Mail discussion). The pattern repeats for symmetrically for other concurrency limits: instead of skipping to viable tasks, the scheduler loops over the same ineligible set.
Narrow fixes like PR 54103 tackle one limit but ignore the rest, and production environments differ widely—from DAG run floods to mapped task surges or complex priorities. Building all limits into the initial query has been tough, often infeasible in the current design. PR 53492 tried window functions and lateral joins for a full solution, but orthogonal limits (pools independent of DAG caps) led to poor SQL performance and unresolved edges. PR 55537 utilized pessimistic DB procedures, which looks promising as it solves the problem, but still needs thorough examination and community discussion. Rethinking the priorities in airflow seems to be the simplest method, not yet examined practically (no POC created), where dag-level priorities are introduced, while the current task-level priorities will become internal to each dagrun, this methodology relies on changing the task-creation method, creating only tasks we can run with all concurrency limits considered per dagrun, and simplifying the main scheduler loop, fetching only max_tis tasks once, and moving them to the executor, in a single iteration, as any task in the scheduled state, is guaranteed to be able to run without further checks (other than executor_slots ).
Large-scale reliability is the goal here. Dynamic mapping enables massive DAGs for per-item batching (one task per file or data pointer), so Airflow has to handle it without breaking. Community benchmarks on real heavy loads would help confirm solutions, and we need queuing that's truly resistant to starvation under any concurrency limit. This proposal aims to serve the updated summary of our research in improving the scheduler's throughput and eliminating starvation. As there's still uncertainty regarding the desired outcome, we present all the strategies we tried or thought of, and expect a fruitful discussion.
Terminology
Optimistic scheduling refers to planning based on the best-case scenario assumptions.
Pessimistic scheduling is based on the worst-case scenario assumptions.
Hybrid scheduling is a general term for an adaptive strategy that can behave like optimistic or pessimistic algorithm, depending on the actual workflow.
Task scheduling in this AIP refers to the process of enqueueing tasks (sending tasks to executor, making them run)
Considerations
What change do you propose to make?
Change the methodology in which the scheduler currently decides which tasks to run, allowing for an increased throughput of the scheduler and running more tasks with a wider variety of workflows without causing noisy neighbours during scheduling.
Why is it needed?
Large-scale Airflow deployments with dynamic task mapping—generating thousands of tasks per DAG—suffer severe scheduler starvation. The optimistic strategy fetches batches of tasks but discards most due to concurrency limits, queuing almost nothing per cycle while workers idle and tasks pile up in scheduled state indefinitely. This change ensures scalable, equitable queuing across all limits, avoiding partial fixes and enabling reliable performance at extreme volumes.
Are there any downsides to this change?
There are strategy-specific downsides documented below. The overall effect should be positive for all users.
Which users are affected by the change?
- Large-scale deployments
- Deployments shared by several teams
- Power users - clients that heavily utilize concurrency limits and priority weights
How are users affected by the change? (e.g. DB upgrade required?)
A DB upgrade might be required, depending on the solution of choice.
- Single-limit pre-filtering:
- No db migration is needed.
- Window functions:
- 2 integer fields need to be added to the task_instance field, nullable and slowly inserted as tasks are created.
- SQL Procedures:
- Same as window functions.
- Priority Semantic Changes:
- Possibly adding a priority field to the dag and or dagrun table.
Alternatives considered
| Strategy | Current optimistic | Single-limit pre-filtering | Window functions | SQL procedures / exhaustive linear scan | Priority Semantics Change |
| Description | Fetch up to | Use a single limit, like max_active_tasks and eliminate starvation on that limit using lateral join / window function. | Nested window functions/lateral joins incorporate multiple limits in a single query. | DB-stored procedures (PostgreSQL/MySQL) or Python (SQlite) scan sorted TIs exhaustively until enough queueable ones found. | Increase the scheduler's variety of choice by giving up the concept of task-level priorities. |
| Motivation | Simple, fast for small/medium workloads; no complex SQL. | Improves performance by considering just one most common concurrency limit which works for many users. | Theoretically, could allow checking multiple concurrency limits in a single SQL query. | Universal solution for all orthogonal limits; eliminates post-fetch drops entirely. Runs on DB side and prevents RTT latencies / slow Python processing. | Priorities make it very hard to come up with a viable in-code solution as every single task should be considered in each iteration. Allowing for a change in the priorities defenition (which as of now is not clearly defined) will allow us to consider tasks in a simple manner without causing a maintnance overhead while solving starvation |
| Advantages | Minimal query overhead; works across DBs including SQLite; easy to maintain/debug, as most logic is in Python. | Boosts throughput for large DAGs (hundreds of tasks); avoids wasting cycles re-querying saturated DAGs. | Theoretically comprehensive, single query for all DB vendors. | Throughput gain even with multiple limits, fewest scheduler iterations, blazingly-fast linear scanning. Solves all starvation cases by using a simple and algorithmically efficient scan on DB side where the data resides. | Per-task priorities are incomprehensible and significantly complicate scheduling. Directly removing any scheduling strategy relying on obsolescence, meaning round-robin style scheduling is not possible. Using an obsolescence based priority algorithm allows for a clearly defined priority behaviour, while keeping scheduling descisions effiecient and fair. |
| Drawbacks | Throughput degradation that leads to starvation in case the average number of schedulable tasks per query is low across iterations. | Considers just one limit and solves just part of the problem, while some limits continue to starve. For example, while max_active_tasks is handled in the query, pool limits may cause tasks to be dropped. | Window functions' behavior is not suitable for Airflow task concurrency model, and they don't solve all cases while imposing a large performance overhead. | Requires several implementations for different DB vendors, may be considered a technical debt. The logic is difficult to test. SQLite doesn't support procedures at all. | Requires a complete refactor of priority logic which is a breaking change. Breakage in the current expected behaviour, may have an effect on existing workflows. Defining a good obsolescence scheduling heuristic can be hard and tedious, as it requires trial and error. |
| Drawback mitigations | Deploy multiple Airflow clusters for large workloads. | It solves the common case of DAG run level limit. Don't define complex concurrency constraints in workloads. | Cases where tasks are dropped with this approach are rare. | DB vendors are not added too often, as critical section algorithm isn't frequently updated, if at all. If it is, adding the logic in several places isn't a big overhead. Keep the logic as simple as possible so no testing is needed. Mimic the algorithm in Python for SQLite. | The change is beneficial to the project as it both contributes to solving starvation and provides a more useful priority feature, while allowing to control which workflows are more important than the others, without starving other workflows. |
| Summary | Serves typical workloads well but fundamentally incapable of handling large-scale starvation without repeated post-fetch drops. | Helpful short-term throughput boost for one common limit, but can't be a long-term solution since other concurrency limits like pools and max_active_tis_per_dag/dagrun remain frequently used and broken. | Theoretically elegant but ruled out—unsuitable for Airflow's multi-dimensional concurrency model and imposes a slight performance overhead (up to 10x slower on large tables). | A viable path forward; benchmarks show 1.7-2x throughput gains across single/dual/triple limit workloads. Remaining technical issues (metrics, SQLite, DB fields) are resolvable, drawback mitigation is possible. | Promising alternative if community reaches consensus on desired priority semantics; enables simpler in-code round-robin scheduling by reducing per-task priority complexity. |
| POC | Runs in production | PR 54103 | PR 53492 | PR 55537 | Still to come, may be several POCs depending on the number of implementations |
Implementation Considerations
Priority Semantics Refactor
A consensus within the community suggests that rethinking priorities is a viable option among the presented alternatives.
Priority use cases
Real use cases must be considered before introducing a mechanism. While prioritizing individual tasks appears to bring a nice-to-have granularity, it should be asked whether this granularity has real use cases. Is there a reason we want to define a total order on all the tasks running in a cluster? Do we think about comparing priority of an email-sending task in one DAG to a data pipeline triggered in another one?
Some may think that priorities, if at all, should be defined on the DAG level. It follows from the notion of DAG being a single, irreducible workflow from the user's point of view.
Current task priorities are used opportunistically - they have impact just on the tasks that are eligible to run in one iteration. There's nothing that prevents a less-prioritized task to "sneak" into an executor slot just one cycle before the more prioritized one comes in. There are even some edge cases where a low-prioritized task "steals" slot of a more prioritized one.
A crucial fact to remember is:
Priorities in Airflow have an impact when a cluster has insufficient resources.
This is true, because otherwise we would expect things to "run on time". Priorities are helpful when we don't have enough pool slots, or the scheduler is choking on too many tasks.
Difficulties with task-level priorities
Pessimistic scheduling
Current task-level priorities make it challenging to implement a AIP-100 Eliminate Scheduler Starvation On Concurrency Limits scheduling algorithm in Python code. If we assume:
(0) A large amount of tasks, i.e. too large to be fetched entirely into code in one iteration.
(0') We want to schedule exactly max_tis task instances in every scheduler cycle if available. If not, schedule every task whose concurrency limits allow them to run.
The problem is described in points:
(1) The goal is to get N of the most prioritized tasks whose concurrency limits are met.
(2) Due to high workflow variety, it's hard to maintain a consistent view of tasks that are eligible to be scheduled.
(3) From (0'), (1) and (2) it follows that in every iteration we have to build a view of all the tasks sorted by their priority, and validate for every task if it's eligible to run until max_tis tasks are found that can run.
(4) Doing (3) in code considering (0) means possibly multiple fetches from the DB and in-code iteration. RTT and memory-buffer allocations are factors that make it extremely slow (from benchmarks).
If these points are correct (subject to discussion), then we must change the behavior of task priorities or remove them altogether in order to achieve a pessimistic in-code scheduling.
Non-pessimistic scheduling
As purely optimistic scheduling with constant priorities leads to starvation and decreased throughput mostly because of priority weights and a lack of variety between scheduler iterations, to continue with non-pessimistic scheduling, we still must change the way priorities work.
Theoretical summary
| Strategy Type | Optimistic | Pessimistic | Hybrid |
|---|---|---|---|
| Problem | Constant priority weights lead to starvation due to dropped tasks and low variety between cycles. | Can't be done in Python code due to technical difficulty in processing large amounts of tasks stored in SQL. | |
| Known solutions | SQL stored procedures. | Change priorities mid-run, use task obsolescence or other heuristics that allow more variety for the scheduler choosing tasks to run. |
Alternatives considered
| Strategy | Keeping task-level priorities but making them weaker | Introducing DAG-level priorities, changing task-level priorities | Completely removing all priorities at all levels |
|---|---|---|---|
| Description | Retain task-level priority weights, but make them flexible to avoid starvation. Use Mitigate starvation by using round-robin style scheduling where the priority of the tasks determine the order in which dagruns will be looked at. An example is taking the highest priority task (awaiting scheduling) of each dag, and multiplying the priority by the delta since the dagrun was considered. | Introduce DAG-level priorities, where each DAG run created inherits the priority of the DAG it belongs to. DAG-level priority acts as a global priority deciding which DAGs will be looked at first. To retain optimistic scheduling and prevent starvation at the same time, as in the strategy on the left, a notion of obsolescence is needed. Use heuristics to punish DAG runs whose tasks couldn't be scheduled for too long. Task priority is now inter-dagrun, meaning that we can control which task from a dagrun will be run first. | Remove all priorities, use plain round-robin scheduling by Check only the concurrency limits, and create tasks without looking or caring about ordering. |
| Motivation | Classic solution against starving less-prioritized tasks - punish tasks that couldn't be scheduled for too long. | Stems from a use case of prioritizing entire workflows. Classic solution against starving less-prioritized DAGs - punish DAGs that couldn't be scheduled for too long. | Plain and simple algorithm that makes scheduling easy. |
| Advantages | The slightest API breakage, starvation is mitigated by deprioritizing tasks that waited for too long. | Accurately matches the workflow model of Airflow, starvation is mitigated by deprioritizing DAG runs that waited for too long. Meets well the prioritization use case. | Simplest and easiest to implement and maintain, no starvation due to priorities as they simply do not exist. |
| Drawbacks | Harder to implement, requires SQL queries to update the priorities mid-run. Adds even more to opportunistic nature of priorities and draws us away from the original use-case - DAGs with long but important tasks can be deprioritized at critical moments. Starvation is mitigated, but the algorithm still remains optimistic - meaning some time may be needed to adjust for starved, highly-prioritized tasks and move forward. Although the feature remains, logic still changes which can lead to possible breakages. Requires a careful mathematical treatment in choosing the heuristic to match the desired behavior. | Behavioral API breakage (long-existing feature changed). Unexpected reliance on task-level priorities may change the execution of users' workflows. Adds even more to opportunistic nature of priorities and draws us away from the original use-case - DAGs with long but important tasks can be deprioritized at critical moments (depending on the algorithm of choice). Starvation is mitigated, but the algorithm still remains optimistic - meaning some time may be needed to adjust for starved, highly-prioritized tasks and move forward. | API breakage (long-existing feature removed). Unexpected reliance on task-level priorities may change or break users' workflows. The use case of prioritizing on low resources is not met which requires users to carefully adjust workflow to existing CPU power, risking important tasks stalling. |
| Drawback mitigation | Starvation is solved in general case. To avoid deprioritizing important tasks, the user will be able to define a policy that controls how quickly we're going to allow such deprioritization. The logic change matches the opportunistic nature of task priorities that become even more opportunistic. You apparently can't rely much on priority weights anymore, but you couldn't rely on them before either. | Old DAGs will still compile. To avoid deprioritizing important DAGs, the user will be able to define a policy that controls how quickly we're going to allow such deprioritization. Starvation is solved in general case. | Old DAGs will still compile. A decision can be made that running Airflow on insufficient resources is an inherent problem not addressed by the project. |
| Summary | API breakage is minimal, though logic still changes considerably. Imposes higher maintenance burden and more implementation complexity, yet mitigates starvation in a classic way of punishing long-awaiting tasks. | Approach that matches the use case of prioritizing important workflows in conditions of resource deficit, makes priorities more comprehensive and easier to control for the end user despite giving up some granularity. Imposes some Behavioral API breakage, as task-level priorities won't work the same way anymore. | Simplest implementation and maintenance, yet removes a widely used feature. Makes scheduling the simplest job possible. The use case of prioritizing on low resources is not met. API breakage in the long run, the |
Migration
A breaking change such as refactoring priority weights requires a careful consideration for possible breakages and user migrations. As it's hard to know how people use priority weights, there is a need for a community brainstorm regarding possible breakages and how we can mitigate them.
A hybrid approach where task-level priority weights are retained is the easiest one to handle, as a toggle for enabling the hybrid approach may be added. For example, the obsolescence algorithm may be turned on/off or tuned with user-specified policy, see Separation of mechanism and policy.
Theoretically, every approach taken may be enabled or disabled with a toggle for several releases, allowing users to tests their workflows with the new strategy (in case task-level priority weights are removed).
Implementation details
Obsolescence Algorithm WORK IN PROGRESS
Implementing any change in the priority semantics still leaves place for starvation, where same prioritized dagruns are considered over and over, without considering other lower-priority dagrun's tasks, even if we can run the given tasks, and so in this case, an obsolescence algorithm comes into play.
Having an obsolescence algorithm means that even if there are more prioritized dagruns, their relative priority changes, as we take into a count the time since last scheduling descision on the current dagruns, meaning that the older the dagrun, the higher priority it will be, while a higher priority dagrun which is old, will still be looked at before a lesser prioritized dagrun waiting for the same amount of time.
This introduces the complication of choosing the obsolescence algorithm, such that it remains simple, easy to implement and understand while still allowing for round-robin style prioritizd scheduling.
As part of the algorithm, we might also look into dag defined sla's, and prioritize dags with a closer sla, in addition to all the aging part, where we also consider last_scheduling_decision minus the current time.
A few algorithms emerge, that allow the scheduler to make smarter decisions, and ensuring that tasks do not starve, in order, from simplest to most complex.
| Algorithm | Simple Weighted Aging | Improved Weighted Aging | Weighted Aging and SLA Urgency |
|---|---|---|---|
| Motivation and Explanation | The simplest algorithm, which will work for most cases. To get the runtime priority of a workflow, take the defined priority of the workflow, apply a simple arithmetic operation (such as multiply the values), and order by the result. This allows for higher priority tasks to be looked at more often, though can cause issues when a priority is to high. The choice of the arithmetic operation can vary the behaviour drasticly, from giving the priority more effect on the scheduling decisions or less. | An approach similar to the simple weighted aging aproach, yet the choice of the aging algorithm is a smarter algorithm allowing for complex scheduling behavior with simple logic, where no workflow types are left to starve. This is a promising choice, as it is both simple and effective at solving the issue, yet it will most likely lack tunability, as there will most likely be only 1 or 2 variables to tune, which will change either the weight of the priority or the weight of the waiting time. | A weighted aging algorithm with urgency of tasks, which is needed to solve the "starvation of highly prioritized tasks in critical moments", where we consider the sla urgency of a given dag along with the priority, this allows for a complete optimistic solution for task scheduling while significantly mitigating starvation across the workflows. This is the more complex solution, yet this solution is the one which solves all of our issues, and can be extended to various directions, with countless improvements which can be built uppon the given solution. All while allowing for inter-dagrun priorities with the current A proposed aging algorithm is shown below. score(J,t)=wp⋅Pbase(J)+wa⋅waiting_time(J,t)+wd⋅urgency(J,t) wa - arrival weight; wd - deadline/sla weight; t - current time. Pbase(J) - base priority of J(ob) urgency - how close the sla is (sla end time - current time ([possibly] - average Job/workflow runtime)) waiting time - time since last examined score - runtime priority |
Advantages |
|
|
|
Drawbacks |
|
|
|
| Summary | The simplest of the bunch, yet might not fully solve all issues for all possible scenarios. | An improved alternative to the simple weighted aging, fitting a wider spectrum of workflows, while not hindering implementation complexity. | The most complex behavior-wise yet solves the widest variety of use cases, allowing for tunability and behavioral control. Not more complex than any of the other proposals, while solving starvation of tasks in a relatively optimistic manner. |
The proposed solutions are simplest to implement at the task creation stage: concurrency limits can be assessed once per scheduler loop, ensuring only eligible tasks are created. This approach streamlines the current scheduler loop by executing a single database query and dispatching tasks directly to their respective executors, bypassing redundant checks. Furthermore, this design enables more flexible, round-robin-inspired scheduling and reduces the risk of task starvation. Re-evaluating priority logic also allows for future innovation; the concepts considered to date are as follows:
What defines this AIP as "done"?
The Airflow scheduler's performance improves in terms of queued tasks over a time frame. Any unnecessary starvation is eliminated after improving the algorithmics of the task queueing logic.
Appendix
Considerations will be moved here after a decision is made on the strategy.