Scheduling Systems: How Kubernetes, Airflow, and Distributed Schedulers Place and Run Workloads

Scheduling systems decide what runs where, when, and with what resources. Get scheduling right and your nodes are evenly utilised, your jobs survive failures, and your noisy neighbours stay quiet. Get it wrong and you end up with thrashing pods, starved background workers, and a Kubernetes cluster that runs at 30% utilisation while telling you it has no room.

This guide is the practitioner's walk through the scheduling algorithms and systems that matter in production: the Kubernetes scheduler internals, distributed cron, queue-based job orchestration with Airflow and Nomad, the bin-packing and fairness algorithms underneath, and the failure modes that determine whether your workloads survive node failure. Examples are grounded in real Kubernetes scheduler code paths, Airflow DAG semantics, and the operational lessons that come from running these systems at scale.

The Scheduling Problem

Every scheduler is solving the same shape of problem: given a set of pending tasks and a set of available resources, decide which task runs on which resource, in what order, with what priority. The variations are in what counts as a "task" (a Kubernetes pod, an Airflow operator, a Spark stage), what counts as a "resource" (a node, a worker pool, an executor slot), and what counts as "optimal" (lowest latency, highest packing, fairest distribution).

Scheduling is hard because the problem is inherently combinatorial — bin packing is NP-hard — and because the inputs change continuously. New work arrives, nodes fail, priorities shift, resource limits get hit. Real schedulers make local greedy decisions that approximate the global optimum and re-evaluate continuously.

The Kubernetes Scheduler in Depth

The Kubernetes scheduler (kube-scheduler) is the most studied production scheduler in modern infrastructure. Every pod creation triggers a scheduling cycle that follows a strict two-phase shape: filter the nodes that can run the pod, then score the surviving nodes to pick the best.

Filter Plugins (Predicates)

Filter plugins reject nodes that cannot run the pod. The defaults include:

• NodeResourcesFit: does the node have enough CPU, memory, ephemeral storage, and pod count?
• NodeUnschedulable: is the node cordoned?
• NodeAffinity: does the pod's nodeSelector and nodeAffinity match the node's labels?
• TaintToleration: does the pod tolerate any NoSchedule taints on the node?
• VolumeBinding: are the requested PVCs bindable to volumes on this node?
• PodTopologySpread: would scheduling here violate spread constraints (e.g. across AZs)?
• InterPodAffinity: does the node satisfy the pod's required pod (anti-)affinity?

Score Plugins (Priorities)

For nodes that pass all filters, score plugins rank them. Each plugin returns a score 0–100; the plugin's weight determines how much its score contributes to the total. Defaults include:

• NodeResourcesFit (score): prefers nodes with the right balance of utilization. Two strategies: LeastAllocated (spread) and MostAllocated (pack). The default is a balanced score that prefers nodes where CPU and memory utilisation are similar.
• InterPodAffinity: prefers nodes that satisfy preferred pod affinity (vs required, which is a filter).
• NodeAffinity: prefers nodes matching preferredDuringScheduling node affinity.
• ImageLocality: prefers nodes that already have the container image cached — saves pull time.
• PodTopologySpread: prefers nodes that spread pods across topology domains (zones, hosts).
• TaintToleration (score): prefers nodes with fewer PreferNoSchedule taints that the pod tolerates.

The winning node is the one with the highest weighted score. Ties are broken randomly.

Preemption

If no node fits the pod after filtering, the scheduler may preempt lower-priority pods to make room. Each pod can have a priorityClassName referencing a PriorityClass with an integer priority. When scheduling fails, the scheduler considers evicting lower-priority pods on candidate nodes such that the new pod fits.

Preemption is gated by PodDisruptionBudgets (the scheduler tries to respect them but may violate them as a last resort), graceful termination periods, and explicit non-preempting policies. Critical system pods (kube-system) typically use the system-cluster-critical and system-node-critical PriorityClasses with very high priorities — they almost never get preempted.

Pod Topology Spread

One of the most consequential scheduler features for production reliability. Topology spread constraints tell the scheduler to distribute pods evenly across topology domains (typically AZs). Without it, the scheduler might pack three replicas of a critical service onto one zone — an AZ outage takes them all down.

spec:
  topologySpreadConstraints:
  - maxSkew: 1
    topologyKey: topology.kubernetes.io/zone
    whenUnsatisfiable: ScheduleAnyway
    labelSelector:
      matchLabels: { app: payments-api }

maxSkew: 1 means the difference between the most-loaded and least-loaded zone for this label cannot exceed 1. whenUnsatisfiable: ScheduleAnyway is a soft constraint (preferred but not required); use DoNotSchedule for hard. Most production deployments use spread on both zone (HA) and node (anti-affinity).

Custom Schedulers and Scheduling Frameworks

The Kubernetes Scheduling Framework (KEP-624, GA in 1.19) lets you write plugins that hook into specific extension points (PreFilter, Filter, PostFilter, PreScore, Score, PreBind, Bind) without forking the scheduler. Used for: GPU-aware scheduling, gang scheduling for ML workloads, custom anti-affinity logic, cost-aware scheduling.

Real custom schedulers in production: Volcano (gang scheduling for batch ML), Yunikorn (Apache, multi-tenant resource fairness), Karmada (cross-cluster scheduling), and the GCP / Azure cost-optimised schedulers. Most teams stick with the default scheduler and tune via priorities, affinities, and taints — custom schedulers carry significant operational cost.

Bin Packing and Resource Allocation

The fundamental scheduling sub-problem is bin packing: given items of various sizes, pack them into bins (nodes) of fixed capacity. NP-hard in general; real schedulers use heuristics that approximate the optimum:

• First-fit: place each item in the first bin it fits. Fast, decent packing.
• Best-fit: place each item in the bin with the least remaining capacity that still fits. Better packing, more compute.
• First-fit decreasing: sort items by size descending, then first-fit. Within ~22% of optimal in the worst case — the standard production heuristic.
• Worst-fit: place each item in the bin with the most remaining capacity. Spreads load; useful when you want utilisation balance over packing density.

Kubernetes' default NodeResourcesFit score is balanced — it prefers nodes where CPU and memory utilisation are similar (balanced allocation) but does not aggressively pack. The opt-in MostAllocated strategy approximates first-fit-decreasing, packing pods onto nodes to leave others empty for autoscaler scale-down.

Real production lesson: pure bin packing fights against resilience. Tightly packed nodes have no headroom for the next pod or for memory spikes. Spread-out nodes are robust but waste money. The right answer depends on whether your cluster autoscaler is aggressive enough to recover the "waste" nodes — if it is, packing wins; if it is not, spreading wins.

Distributed Cron and Periodic Jobs

Scheduling jobs that should run periodically (every minute, hourly, nightly) is harder than it looks at scale. Single-node cron is reliable on one machine but does not survive that machine going down. Running cron on every node duplicates work. Running it on a designated leader node creates a single point of failure.

The robust pattern: distributed coordination via lease. The job framework runs on multiple nodes; each iteration starts with a lease acquisition (etcd, Zookeeper, Redis with proper fencing) for the (job, scheduled-time) tuple. Whoever wins the lease runs that iteration; everyone else does nothing. The lease has a TTL so a crashed leader does not starve the schedule.

Kubernetes implements this as CronJob resources. The CronJob controller (running with leader election in kube-controller-manager) creates a Job for each scheduled iteration. The Job controller in turn ensures one Pod completes successfully. Failed Pods are retried (subject to backoffLimit); the next scheduled iteration creates a new Job.

apiVersion: batch/v1
kind: CronJob
metadata:
  name: nightly-billing-rollup
spec:
  schedule: "0 2 * * *"
  concurrencyPolicy: Forbid
  successfulJobsHistoryLimit: 3
  failedJobsHistoryLimit: 3
  startingDeadlineSeconds: 600
  jobTemplate:
    spec:
      backoffLimit: 4
      activeDeadlineSeconds: 7200
      template:
        spec:
          restartPolicy: OnFailure
          containers:
          - name: rollup
            image: registry/billing-rollup:1.42

The non-obvious settings:

• concurrencyPolicy: Forbid ensures only one iteration runs at a time. The alternative Allow can stack iterations if jobs run longer than the schedule interval.
• startingDeadlineSeconds bounds how late a missed iteration can be started. Without it, if the controller is down for an hour, all missed iterations fire when it returns.
• activeDeadlineSeconds bounds total runtime per iteration. Critical for jobs that can hang.

Queue-Based Job Orchestration

For jobs with dependencies, fan-out, or DAG structure, plain CronJobs are not enough. The orchestration layer needs to model task graphs, retry semantics, partial failures, and observability. The dominant tools:

Apache Airflow

Airflow models workflows as Directed Acyclic Graphs (DAGs) of tasks. The scheduler parses DAGs, schedules tasks on workers, and tracks state in a database (Postgres or MySQL). Workers can be local processes (LocalExecutor), distributed Celery workers (CeleryExecutor), or Kubernetes pods (KubernetesExecutor).

from airflow import DAG
from airflow.operators.python import PythonOperator
from datetime import datetime, timedelta

with DAG(
    dag_id="daily_etl",
    start_date=datetime(2026, 1, 1),
    schedule="0 3 * * *",
    catchup=False,
    max_active_runs=1,
    default_args={
        "retries": 3,
        "retry_delay": timedelta(minutes=5),
    },
) as dag:
    extract  = PythonOperator(task_id="extract",  python_callable=extract_data)
    validate = PythonOperator(task_id="validate", python_callable=validate_extract)
    load     = PythonOperator(task_id="load",     python_callable=load_to_warehouse)
    notify   = PythonOperator(task_id="notify",   python_callable=send_summary)

    extract >> validate >> load >> notify

Airflow excels at: complex dependencies (fan-out, fan-in, dynamic tasks), backfills (retry past dates), and observability (the UI is one of the best in the space). It struggles with: low-latency triggering (Airflow is designed for batch, not sub-second scheduling), and operational complexity at large DAG counts (the metadata database and scheduler can become bottlenecks at thousands of DAGs).

HashiCorp Nomad

Nomad is a generalist scheduler — it schedules anything, not just containers. Batch jobs, system services, periodic tasks, parameterized jobs, and dispatched jobs (one-off invocations of a job template). The scheduler uses bin-packing with anti-affinity and constraint solving.

Nomad's differentiator from Kubernetes: simpler operational model, a single binary, multi-region native (federated clusters out of the box), and it can run in environments where Kubernetes is overkill (edge, IoT, simple batch farms).

Apache Mesos and the Two-Level Scheduling Model

Mesos was the dominant cluster scheduler before Kubernetes — Twitter, Apple, eBay, Airbnb, and Uber ran Mesos at huge scale. It is in decline operationally (the project was archived by the ASF in 2021 and most users have migrated to Kubernetes), but the design ideas it pioneered remain influential and worth understanding.

Mesos' defining innovation was the two-level scheduler. A central Mesos master tracked cluster resources and offered them — literally, as resource offers — to frameworks (Marathon for long-running services, Chronos for cron, Aurora for batch + services, and frameworks for Spark, Hadoop, Cassandra, Kafka, Jenkins). Each framework received offers and decided whether to accept any of them and what to schedule. The master never made placement decisions itself; it just brokered offers.

The advantages were real: a single cluster could run dozens of workload types each with its own scheduling logic; framework authors could implement domain-specific algorithms (Spark could co-locate stages, Hadoop could place near HDFS replicas) without modifying the master; and resource offers were a clean separation between "what is available" and "who decides what to do with it".

The disadvantages were also real and ultimately decisive. Operating Mesos meant operating the master, the agents, ZooKeeper for HA, and at least one framework per workload type — typically Marathon for services, Chronos for cron, sometimes Aurora as a Marathon alternative. Each framework had its own configuration model, its own UI, its own operational gotchas. Kubernetes' integrated "one scheduler, one API, one operational model" was easier to onboard, easier to staff for, and ultimately won the platform-engineering battle. The K8s scheduling framework (with its plugin extension points) is a more disciplined re-thinking of the Mesos two-level idea inside a single integrated control plane.

If you operate Mesos today, you are likely already on a migration path to Kubernetes or Nomad. The Mesos design ideas show up in modern systems — the Kubernetes scheduler framework, the Yunikorn multi-tenant resource fairness model, the Yarn capacity scheduler — in cleaner forms.

Custom Job Queues (Sidekiq, Celery, RQ, BullMQ)

For application-level background jobs (send an email, regenerate a thumbnail, run an import), full orchestration is overkill. Per-language job queue libraries provide: priority queues, retries with exponential backoff, dead-letter queues, scheduled jobs, and worker pools. Built on Redis (Sidekiq, RQ, BullMQ) or a dedicated broker (Celery + RabbitMQ).

Fairness, Priority, and Quotas

Multi-tenant schedulers need to prevent one tenant from starving others. The core algorithms:

Dominant Resource Fairness (DRF)

The standard fairness algorithm for schedulers that allocate multiple resource types (CPU, memory, GPU). DRF (Ghodsi et al., 2011) computes each tenant's "dominant share" — the largest share they hold across all resources — and equalizes those dominant shares.

Concretely: if tenant A is using 50% of CPU and 20% of memory, A's dominant share is 50%. If tenant B is using 30% of CPU and 60% of memory, B's dominant share is 60%. DRF would prefer to allocate the next slot to A. Used by Mesos, Yunikorn, and Yarn capacity scheduler.

Priority Classes

Kubernetes supports priority via PriorityClass resources. Higher-priority pods preempt lower-priority pods when needed. A common production setup has three or four classes:

• system-critical: kube-system pods, never preempted.
• production: latency-sensitive user-facing services.
• best-effort-batch: background processing, low priority.
• opportunistic: spot-instance batch, preemptible at any time.

Resource Quotas and LimitRanges

ResourceQuota caps the aggregate resource consumption per namespace (e.g. payments-team can use at most 100 CPU and 200Gi memory). LimitRange sets per-pod defaults and bounds within a namespace. These are not technically scheduling features — they are admission-time validations — but they shape the inputs to scheduling.

Failure Recovery and Retries

Every scheduler needs to handle: jobs that fail, workers that crash, jobs that get stuck, and the bookkeeping problem of "was this job already done?" The standard tools:

Exponential Backoff with Jitter

The default retry pattern. Wait 1s, then 2s, then 4s, then 8s — with random jitter to avoid synchronizing retries from many workers. Kubernetes job backoffLimit, Sidekiq retries, AWS SDK's default retry policy all use this. Without jitter, a downstream brownout can be amplified by retry storms.

Idempotency Keys

If a job retries, it should not double-charge the customer or send two emails. Idempotency keys (a unique string per logical job invocation) let the receiver detect and reject duplicate executions. The job framework typically generates the key (often a hash of the job's inputs) and the receiving service stores it for the deduplication window.

Dead Letter Queues

After N retries, the job moves to a dead letter queue (DLQ) where humans (or another job) can inspect it. The DLQ exists because the alternative — infinite retries — is worse. Production runbooks should monitor DLQ depth as a first-class metric; a growing DLQ is a real incident signal.

Visibility Timeouts

When a worker pulls a job, the job is invisible to other workers for the visibility timeout (typically 30s–5min). If the worker completes and acknowledges, the job is deleted. If the timeout elapses without ack, the job becomes visible again and another worker picks it up. This is how SQS, Kafka with rebalances, and most queue systems handle worker failure.

Stuck Job Detection

A job that runs for hours instead of minutes is probably stuck (deadlock, network partition, infinite loop). Set activeDeadlineSeconds on Jobs and CronJobs; alert on jobs that exceed their typical p99 runtime; require all workers to emit periodic heartbeats so a hung worker is detectable.

Resource-Aware and GPU Scheduling

GPU workloads break naive scheduling. A GPU is a discrete, indivisible resource — you cannot split a GPU between two pods (until recently; nvidia's MIG support changes this). The scheduler needs to know about GPU types (H100 vs A100 vs T4), GPU counts per node, and topology (NVLink groups for multi-GPU jobs).

Kubernetes models this through device plugins: nvidia's plugin advertises nvidia.com/gpu as a schedulable resource, and pods request it via resources.limits. For more sophisticated patterns (gang scheduling N pods together for distributed training, topology-aware placement, fractional GPU), custom schedulers like Volcano, KAI Scheduler, or Run:AI take over.

Specifically for AI inference workloads, the cost-control pattern is critical: schedule inference replicas on GPU nodes with low utilisation, use the remaining capacity for preemptible batch training. This dual-tenancy is hard to do well without a custom scheduler that understands both workload classes.

Workload Placement Across Clusters and Clouds

Single-cluster scheduling is solved. Multi-cluster scheduling — deciding which cluster a workload runs on across many regions or cloud providers — is open territory. Approaches:

• Karmada: open-source Kubernetes-native multi-cluster scheduler. Workloads are submitted to a host cluster; Karmada propagates them to member clusters based on policy.
• Cluster API + custom controllers: each business workload has a controller that watches across clusters and reconciles placement.
• External orchestrator (Spinnaker, Argo CD with multi-cluster, Crossplane): orchestrate deployments across clusters from a central control plane.
• Cell-based architecture: pre-partition tenants across clusters; each tenant lives in a single cell. No cross-cluster scheduling needed at runtime — the placement is decided at tenant-onboarding time.

The cross-cluster identity layer matters for security: a workload that can move between clusters needs an identity that travels with it. SPIFFE workload identity solves this — the same SPIFFE ID is valid across federated clusters, so cross-cluster scheduling does not require credential re-issuance. See the SPIFFE/SPIRE Deep Dive module in the Cloud Native Security Engineering course for the full pattern.

Common Pitfalls

1. Setting Resource Requests Too High

If pods request more resources than they actually use, the scheduler reserves that capacity even though it sits idle. Cluster utilisation drops; the autoscaler adds nodes that are mostly empty. The fix: profile your workloads, set requests at the p95 of actual usage, and set limits at p99. Tools like Robusta KRR and the Vertical Pod Autoscaler analyser can recommend per-workload values.

2. Forgetting PodDisruptionBudgets

The scheduler will happily evict and reschedule pods during node maintenance, autoscaler scale-down, or preemption. Without PDBs, the entire replica set can be terminated simultaneously — causing a brief outage. Always declare a PDB with minAvailable or maxUnavailable for production deployments.

3. Topology Spread Without Resilience Goals

A common misuse: setting topologySpreadConstraints with maxSkew: 1 on a 3-replica deployment in a 3-zone cluster. The scheduler now refuses to schedule a 4th replica because that would violate the constraint — even though there is plenty of capacity. Use ScheduleAnyway for soft constraints and reason about what spread you actually need.

4. Cron Schedule Drift

Long-running jobs that take longer than the schedule interval will overlap (with concurrencyPolicy: Allow) or skip iterations (with Forbid). Always measure job runtime, set activeDeadlineSeconds as a safety net, and set the schedule generously.

5. Trusting Visibility Timeout for Long Jobs

If a worker takes longer than the visibility timeout to process a message, the message becomes visible again and another worker picks it up — double processing. Workers for long jobs should periodically extend the visibility timeout (heartbeat) or split the job into smaller chunks.

Observability

Production schedulers need:

• Pending-pod time histogram: how long pods wait between creation and scheduling. p99 should be sub-second; multi-minute waits indicate scheduler bottleneck or capacity issues.
• Scheduler errors per reason: insufficient CPU, insufficient memory, node selector mismatch, taint, etc. Tells you whether to grow the cluster, fix node labels, or tune affinities.
• Node utilisation distribution: per-node CPU/memory utilisation as a histogram. Wide variance suggests packing problems or hot spots.
• Job latency p50/p99 for batch jobs, broken down by job type and tenant. Drift in p99 is an early signal of scheduler or worker degradation.
• DLQ depth and time-in-DLQ: zero is the only acceptable steady state.
• Preemption events: which pods got evicted by which higher-priority pods. Helps diagnose "my pod keeps getting killed" reports.

Security Considerations

Schedulers operate with cluster-wide privilege and decide where workloads run. Three security failure modes specific to scheduling:

1. Hostile pod placement: an attacker who can schedule a pod (via a compromised SA, an exploited admission gap) can target specific nodes via node affinity. The mitigation is admission policy: PodSecurity restricted, image-signing enforcement, NetworkPolicy default-deny per namespace. Walk the Kubernetes Security Simulator for hands-on practice on these defences.
2. Cross-tenant noisy neighbours: a CPU- or I/O-hungry pod on a shared node degrades co-tenant performance. CPU and memory limits, plus dedicated node pools for sensitive workloads, are the common defenses.
3. Privileged scheduler plugins: a custom scheduler plugin runs in the cluster with cluster-scope read access. Vet plugins like you vet admission webhooks — signed images, audited code, monitored behaviour.

Frequently Asked Questions

How does the Kubernetes scheduler scale to thousands of nodes?

The default scheduler can comfortably handle ~5,000 nodes and ~150,000 pods. Beyond that you tune: enable percentage-of-nodes-to-score (don't score every node, just a representative sample), shard the scheduler into multiple instances by workload class, or run custom schedulers per namespace. The CNCF KEP-3094 (multiple schedulers running concurrently) is the upstream pattern.

When should I use a custom scheduler vs tuning the default scheduler?

The default scheduler with affinities, taints, priorities, and topology spread covers ~95% of use cases. Reach for a custom scheduler when you need: gang scheduling (N pods together or none), GPU topology awareness, budget-aware placement (cost optimisation across cloud regions), or cross-cluster scheduling. The operational cost is significant; exhaust the defaults first.

Should batch jobs run in the same cluster as production services?

Two patterns. Shared cluster: separate node pools, priority classes, and resource quotas isolate batch from prod. Cheaper, more flexible. Dedicated batch cluster: lower blast radius (a batch outage cannot affect prod), simpler operational model. Most teams start shared and graduate to dedicated when batch scale or sensitivity demands it.

How do I know if my cluster is under-utilised or over-utilised?

The right metric is request utilisation (CPU/memory requested / available), not actual usage (CPU/memory used / available). The scheduler cares about requests; nodes appear "full" at request utilisation even if actual usage is 30%. If request utilisation is high but actual usage is low, your requests are oversized — tune them down.

Should I use Airflow, Argo Workflows, Dagster, or Prefect?

Airflow is the incumbent — mature, huge ecosystem, hard to operate at scale. Argo Workflows is Kubernetes-native — great if you already run Kubernetes and want simple infra. Dagster has the best modern developer experience and asset-based modelling. Prefect is the cleanest Pythonic API. For new projects, evaluate Argo + Dagster first; pick Airflow only if you need its specific operators or community.

What is "gang scheduling" and when do I need it?

Gang scheduling guarantees that a set of related pods all start together, or none of them start. Required for distributed ML training (rank 0 cannot do useful work without rank 1...N), Spark jobs (the driver needs all executors), and MPI workloads. The default Kubernetes scheduler does not support it; Volcano, Yunikorn, and KubeFlow's training-operator add it.

Conclusion

Scheduling decides what runs where. Get it right and your nodes are evenly utilised, your jobs survive failures, and your priorities are respected without manual intervention. Get it wrong and you end up with thrashing pods, starved background work, and a cluster running at 30% utilisation while telling you it has no room.

The high-leverage takeaways for production engineers: topology spread across zones is the difference between "single-AZ outage" and "customer-impacting outage"; resource requests should be set at p95 of actual usage, not p99-of-peak-day, otherwise the scheduler refuses to pack; PriorityClasses + PodDisruptionBudgets together let you reason about both preemption and drain safety; distributed cron needs leader election, not "cron on every node" or "cron on the master"; queue-based orchestration needs idempotency keys, exponential backoff with jitter, dead-letter queues, and visibility timeouts — not all four is incomplete; fairness is not free — pick a tenancy model (DRF, dedicated namespaces, dedicated clusters) that matches your actual isolation requirements. The scheduler that quietly does the right thing is the one that has been instrumented and tuned over real production traffic.

Where to Go Next

• Read the Distributed Systems Algorithms guide for the consensus and leader-election primitives that underpin every distributed scheduler.
• Walk through the Rate Limiting Algorithms guide to see how rate limiting and scheduling interact when load exceeds capacity.
• Read the Caching Strategies guide to round out the performance-engineering picture.
• Try the Kubernetes Security Simulator and the Secure Architecture Builder for hands-on practice on the architectural decisions that surround scheduling.
• Take the free Kubernetes Foundations & Security module for the broader picture of how scheduling fits with the rest of the cluster control plane.