Preemption Policies to Meet Latency SLAs Without Starvation

• When to Pull the Trigger: Preemption Triggers and Priority Rules
• Evict Without Breaking Things: Graceful Shutdowns and Checkpoint Patterns
• Break Priority Deadlocks: Avoiding Starvation and Priority Inversion
• Tune for Stability: Thresholds, Backoff, and Observability
• Operational Playbook: Runbook, Checklists, and Case Studies

The scheduler's preemption mechanism is the only fast lever that enforces strict latency SLAs when the cluster is saturated — and it is also the single biggest source of wasted work and operational pain when misused. Treat preemption as surgical: define precise triggers, choose low-impact victims, require checkpointing or graceful shutdown, and tune backoff and metrics so preemption restores SLA compliance without starving other tenants.

Clusters that rely on blunt eviction policies show the same symptoms: p95 latency spikes for front-line services during heavy batch activity, high restart churn for long-running jobs, poor SLA compliance reporting that doesn't reflect the noise from rework, and occasional priority inversion where a low-priority task holding a critical resource blocks a high-priority path. Those symptoms create operational drag: on-call pages, customer-impact incidents, and wasted CPU/GPU hours — the very things preemption is supposed to prevent.

When to Pull the Trigger: Preemption Triggers and Priority Rules

Preemption should happen for clear, measurable reasons: an imminent SLA breach for a latency-sensitive workload, a pending high-priority job that cannot be scheduled any other way, or an emergency node-degradation event where freeing resources quickly is essential. Common, defensible trigger signals are:

• A running service's predicted p95 exceeds its SLA over a short forecast window (for example, predicted p95 > 1.25 × SLA for the next 30–60s).
• A high-priority job has been pending for longer than its admission timeout and cluster headroom is below your safety threshold.
• Node-level resource pressure that cannot be relieved by bin-packing or autoscaling within the required SLA window.

Use explicit, auditable policies rather than ad hoc scripts. Model priority as a two‑dimensional policy: a coarse ordinal (e.g., PriorityClass levels) and fine-grained cost-aware ranking for victims. Kubernetes exposes PriorityClass and preemptionPolicy primitives you should integrate into your decision logic. (kubernetes.io)

Victim selection should be an optimization problem, not “kill anything that looks cheap.” Implement a minimal‑set algorithm that finds the smallest collection of victims whose reclaimed resources make the preemptor feasible. Score candidate victims with a composite cost:

• eviction_cost = checkpoint_time + restore_time + lost_work_value + pdb_penalty + statefulness_penalty - progress_bonus

Lower eviction_cost implies a better victim. Example pseudo-code (conceptual):

def select_victims(preemptor, node):
    required = preemptor.cpu_request - node.available_cpu
    candidates = [p for p in node.pods if p.priority < preemptor.priority and not p.is_protected()]
    candidates.sort(key=lambda p: p.eviction_cost)
    victims, freed = [], 0
    for p in candidates:
        victims.append(p); freed += p.cpu_request
        if freed >= required: break
    return victims

Balance fairness and priority. When multiple resources matter (CPU, memory, GPU, I/O), adopt a multi-resource fairness model such as Dominant Resource Fairness (DRF) to avoid starving workloads that dominate different resource types. DRF yields allocations that are strategy-proof and envy-free across resources. (www2.eecs.berkeley.edu)

Evict Without Breaking Things: Graceful Shutdowns and Checkpoint Patterns

Preemption is an ordered protocol, not an instantaneous kill. A safe eviction sequence has three phases: notify → drain / checkpoint → reclaim. The primitives you should standardize across your fleet:

• Signal semantics: send SIGTERM (or an equivalent control signal) and write a well-documented annotation or event so the workload knows a preemption is coming. Use a preStop hook to trigger an application-level checkpoint. Use terminationGracePeriodSeconds to give the app time to quiesce. Use SIGKILL as a last resort if the grace period expires. (kubernetes.io)
• Checkpointing modalities:
  • Application-level checkpointing: best for distributed state (Spark streaming state, ML training checkpoints to object storage). Application code decides what to persist and is usually the most robust option.
  • Process-level checkpointing: use tools like CRIU for single-process native binaries where process memory + sockets can be captured and restored; this is attractive for short-lived native workers but has limits for distributed JVM and networked services. (github.com)
  • Externalizable state: persist progress to durable storage (S3, HDFS, PVs) so restarted tasks can resume work without replaying the entire input.
• Checkpoint frequency tradeoff: compute the break-even checkpoint interval with a simple rule:

checkpoint_benefit = expected_lost_work_if_killed
checkpoint_cost = time_to_checkpoint + time_to_restore

Checkpoint when checkpoint_cost < checkpoint_benefit. For a job where the expected rework exceeds checkpoint cost (e.g., long-running scientific compute or large shuffle), checkpointing pays off.

Example Kubernetes pattern (graceful termination + app checkpoint signal):

spec:
  terminationGracePeriodSeconds: 60
  containers:
  - name: worker
    lifecycle:
      preStop:
        exec:
          command: ["/bin/sh", "-c", "/opt/app/checkpoint && sleep 1"]

Add a checkpointable: true label to pods that support fast resume and prefer them as victims in the selection algorithm.

Table: eviction modes at a glance

Mode	Description	Pros	Cons
Graceful shutdown + checkpoint	App persists state, exits cleanly	Lowest lost work	Requires app changes & storage
Suspend/serialize job	Scheduler suspends container and frees node	Fast re-start	Complex for networked state
Immediate kill	Forceful termination	Fast resource reclaim	High wasted work; risk of data loss

Break Priority Deadlocks: Avoiding Starvation and Priority Inversion

Priority inversion happens when a low-priority task holds a resource that a high-priority task needs, and medium-priority tasks keep preempting the low-priority one — the classic Mars Pathfinder incident. Real-world systems that ignore inversion create outages that are hard to diagnose. (mdpi.com)

Mitigation patterns that work in clusters:

• Protect short critical sections and prefer non-preemptive critical-region implementations in application code (e.g., time-bounded locks or try_lock with backoff).
• Apply priority inheritance or priority donation at the resource level where feasible; at the cluster level use protected annotations or PodDisruptionBudgets (PDB) for tasks performing short critical commits so they are excluded from victim selection. The OS-level priority inheritance is not a panacea for distributed locks — design the app-level protocol to avoid long-held global locks.
• Prevent infinite starvation with guaranteed minimum shares. Enforce min-share or reservation for long-running, high-value jobs so they never drop to zero allocation (YARN-style minSharePreemptionTimeout is an example of protecting a queue until a timeout elapses). (hadoop.apache.org)
• Limit administrative scope of high priorities. Keep the number of jobs that can claim top-tier priorities small via RBAC and ResourceQuota so a single tenant cannot evict the cluster.

A practical rule: short-lived, high-frequency I/O or service-level critical sections should never be co-located with long critical-region batch jobs that hold global state without either checkpointing or a protected maintenance window.

Tune for Stability: Thresholds, Backoff, and Observability

Preemption tuning is an observability problem first and a parameter problem second. Instrument aggressively and derive knobs from measured costs.

Key metrics to collect and alert on:

• p95 / p99 latency for latency-sensitive services (SLA compliance ratio).
• Preemptions/sec (global and per-node).
• Wasted compute time: sum of CPU-seconds lost due to preemptions in a window.
• Victim restart count and mean time to resume.
• Queue wait time (p95) for each priority class.
• Fairness index (Gini) across tenants for dominant resource shares.

Suggested thresholds and knobs (starting points; tune per workload):

• Emergency preemption trigger: predicted p95 > 1.25 × SLA for next 30–60s and preemptor pending > 5–10s.
• Normal preemption: pending high-priority job > 30s and cluster utilization > 85–90%.
• Backoff: apply per-job exponential backoff on re-preemption attempts, e.g., base = 30s, multiplier = 2, cap = 10m. This prevents thrash when victims repeatedly fail to release resources.
• Rate limits: cap preemptions to N per node per 5m (e.g., N=1–3 depending on cluster).

Prometheus examples (pseudocode PromQL):

• p95 latency for a service:

  histogram_quantile(0.95, sum(rate(http_request_duration_seconds_bucket{job="frontend"}[5m])) by (le))

• preemption rate:

  sum(increase(kube_pod_preemptions_total[5m]))

Make preemption decisions cost-aware: only preempt when the expected SLA improvement exceeds the sum of checkpoint+restore costs plus a safety margin. Track preemption_success_rate = number_of_preemptions_that_improved_SLA / total_preemptions and tune policies until success_rate is acceptable.

Operational Playbook: Runbook, Checklists, and Case Studies

Actionable runbook (ordered checklist for an on-call engineer or an automated policy):

1. Detection: alert fires on p95 forecast or pending high-priority queue time. Record the alert metadata (service, node, pending job id).
2. Triage: compute candidate victim set using the cost model (checkpoint readiness, restart cost, PDB, progress).
3. Signal victims with an annotated preemption event (HTTP/annotation/kubernetes event) and trigger application checkpoint via preStop or control path.
4. Wait terminationGracePeriodSeconds or the configured checkpoint timeout. If victims do not exit, escalate to forced termination according to policy.
5. Confirm the preemptor schedules and measure SLA improvement over a short window (30–120s). If SLA did not improve, run rollback diagnostics (did the preemptor lose node nomination? was a higher-priority job inserted?).
6. Post-mortem: record wasted compute, victim restart count, and whether checkpointing reduced lost work; update victim scoring weights accordingly.

Developer checklist (must-haves on any workload that can be preempted):

• Handle SIGTERM and preStop for clean shutdown or checkpoint.
• Make critical operations idempotent.
• Expose a checkpoint() endpoint and document expected duration.
• Tag pods with checkpointable=true or protected=true as appropriate.
• Set appropriate PriorityClass and backoff semantics for retries.

Concise case studies:

• Google Borg: Borg uses aggressive preemption and packing to achieve high utilization; the system accepts regular task churn and relies on fast re-scheduling and cheap task start-up to maintain service SLAs at scale. Borg shows that preemption, when combined with fast restart and tight instrumentation, is a production-hardened lever. (research.google)

• Hadoop YARN Fair Scheduler: YARN supports configurable minSharePreemptionTimeout and fairSharePreemptionTimeout so queues only preempt after a timeout, preventing aggressive immediate evictions and reducing starvation. Use those knobs to delay preemption until starvation is confirmed by the scheduler. (hadoop.apache.org)

• Graceful decommission in managed services: Google Cloud Dataproc exposes graceful decommission / drain timeouts for autoscaling to allow Spark/YARN shuffle to finish before nodes are removed, reducing re-shuffle and re-execution costs during scale-down. Use graceful decommissioning when autoscaling intersects with preemption-sensitive workloads. (cloud.google.com)

Important: priority inversion is not hypothetical — the Mars Pathfinder mission saw operational resets caused by inversion until priority inheritance was enabled. Protect critical shared resources and prefer short, timeout-bounded critical sections. (mdpi.com)

Sources

Pod Priority and Preemption | Kubernetes - Official Kubernetes documentation for PriorityClass, preemptionPolicy, graceful termination behavior, and preemption limitations; used for examples of preemptionPolicy and graceful shutdown flows. (kubernetes.io)

Dominant Resource Fairness: Fair Allocation of Multiple Resource Types (Ghodsi et al., 2011) - The DRF paper describing multi-resource fairness properties and why DRF prevents envy across heterogeneous resource demands. (www2.eecs.berkeley.edu)

Large-scale cluster management at Google with Borg (Verma et al., EuroSys 2015) - Operational description of Borg’s scheduling, packing, and preemption practices; cited for large-scale preemption design patterns and trade-offs. (research.google)

CRIU — Checkpoint/Restore In Userspace (GitHub) - Project page for a process checkpoint/restore tool used for live migration and process-level checkpointing; cited for process-level checkpoint options and limitations. (github.com)

Hadoop YARN Fair Scheduler (Apache Hadoop docs) - Fair Scheduler preemption configuration including minSharePreemptionTimeout, fairSharePreemptionTimeout, and thresholds; used to illustrate queue-level preemption controls. (hadoop.apache.org)

Fatal Software Failures in Spaceflight — Mars Pathfinder priority inversion case (MDPI) - Historical account of priority inversion on the Mars Pathfinder mission and the operational impact; cited as an authoritative real-world example of priority inversion. (mdpi.com)

Autoscale Dataproc clusters | Google Cloud - Documentation describing graceful decommissioning and autoscaling behavior to avoid job disruption during node removal; cited for autoscaler + graceful shutdown interactions. (cloud.google.com)