Remove Everything, Then Reprieve: How Preemption Finds the Smallest Victim Set

TL;DR: Preemption does not search for a minimal victim set combinatorially. On each candidate node it (1) removes every eligible victim, (2) re-runs the Filter plugins to see whether the preemptor now fits, and (3) if it does, sorts the victims by importance and re-adds them one at a time until the preemptor stops fitting. Whatever could not be re-added is the victim set. Pods whose eviction would break a PodDisruptionBudget are reprieved first, so the scheduler prefers to free a node without breaking any PDB.

Preemption is the scheduler’s most expensive and least understood code path. It runs only when a pod cannot be placed, it can evict other people’s pods, and it has to respect disruption budgets while minimising the blast radius. The naive reading — “find the smallest set of pods to evict” — is a set-cover problem and would be intractable.

The actual algorithm sidesteps the search entirely with a move that is geniusly cheap: remove everything, then put back as much as you can.

The candidate set is already narrowed

Preemption is a PostFilter plugin, so it runs only after the Filter pass has already rejected every node. The nodes it even considers are the ones that failed with Unschedulable — the ones where a plugin said “no” rather than “error”:

// pkg/scheduler/framework/preemption/preemption.go:200-208
	// Get a list of nodes with failed predicates (Unschedulable) that may be satisfied by removing pods from the node.
	potentialNodes, err := m.NodesForStatusCode(ev.Handler.MutableSnapshotSharedLister().NodeInfos(), fwk.Unschedulable)
	if err != nil {
		return nil, nil, err
	}
	if len(potentialNodes) == 0 {
		logger.V(3).Info("Preemption will not help schedule pod on any node", "pod", klog.KObj(pod))
		return nil, framework.NewDefaultNodeToStatus(), nil
	}

This list is all the unschedulable nodes, not a sample. The PDBs are then loaded, a random offset and a candidate budget are computed, and the dry run begins (pkg/scheduler/framework/preemption/preemption.go:210-216).

Remove everything first

Here is the core of SelectVictimsOnNode. First, the eligible victims are collected, then all of them are removed from the node:

// pkg/scheduler/framework/plugins/defaultpreemption/default_preemption.go:317-352
	var potentialVictims []*preemption.DomainVictim
	for _, victim := range allPossibleVictims {
		if pl.isPreemptionAllowedAcrossAllVictimNodes(victim, preemptor) {
			potentialVictims = append(potentialVictims, victim)
		}
	}

	// No preemption victims found for incoming preemptor, and so we don't need to evaluate the node again since its state didn't change.
	if len(potentialVictims) == 0 {
		return nil, 0, fwk.NewStatus(fwk.UnschedulableAndUnresolvable, "No preemption victims found for incoming pod")
	}

	// As the first step, remove all victims eligible for preemption from the node.
	for _, victim := range potentialVictims {
		// If a Victim is a PodGroup spanning multiple nodes, some affected nodes
		// might not be in the nameToNode map yet. We add them to ensure
		// they are considered during preemption.
		for name, nodeInfo := range victim.AffectedNodes() {
			if _, ok := nameToNode[name]; !ok {
				nameToNode[name] = nodeInfo
			}
		}
		if err := removeVictim(victim); err != nil {
			return nil, 0, fwk.AsStatus(err)
		}
	}

	// If the preemptor does not fit after removing all the eligible victims,
	// we are almost done and this node is not suitable for preemption. The only
	// condition that we could check is if the preemptor is failing to schedule due to
	// inter-pod affinity to one or more victims, but we have decided not to
	// support this case for performance reasons. Having affinity to lower
	// importance (priority) pods is not a recommended configuration anyway.
	if status := pl.fh.RunFilterPluginsWithNominatedPods(ctx, cycleState, preemptor, nodeInfo); !status.IsSuccess() {
		return nil, 0, status
	}

Removing all eligible victims is an upper bound on what preemption can achieve on this node. If the preemptor still does not fit with every possible victim gone, no subset will help — the node is rejected outright. For a pod that simply does not fit anywhere (too big, wrong node selectors), the dry run costs one Filter pass per candidate node and stops.

Two side effects of “remove everything” are worth understanding. First, removeVictim mutates the node’s NodeInfo in place (for the main node only) and calls the PreFilterExtension hooks so plugins can update their CycleState — topology spread counters, affinity counters. Second, the preemptor’s own Filter run sees a node with nothing on it, so the filters evaluate “would this pod fit on an empty node?” rather than “would it fit after removing these specific pods?”

Then reprieve, one at a time

If the preemptor fits on the emptied node, the victims are sorted and re-added:

// pkg/scheduler/framework/plugins/defaultpreemption/default_preemption.go:354-396
	// Sort potentialVictims by descending importance, which ensures reprieve of
	// higher importance victims first.
	sort.Slice(potentialVictims, func(i, j int) bool {
		return pl.MoreImportantVictim(potentialVictims[i], potentialVictims[j])
	})

	// Try to reprieve as many pods as possible. We first try to reprieve the PDB
	// violating victims and then other non-violating ones. In both cases, we start
	// from the highest importance victims.
	violatingVictims, nonViolatingVictims := preemption.FilterVictimsWithPDBViolation(potentialVictims, pdbs)
	var victims []*preemption.DomainVictim
	reprieveVictim := func(v *preemption.DomainVictim) (bool, error) {
		if err := addVictim(v); err != nil {
			return false, err
		}

		status := pl.fh.RunFilterPluginsWithNominatedPods(ctx, cycleState, preemptor, nodeInfo)
		fits := status.IsSuccess()
		if !fits {
			if err := removeVictim(v); err != nil {
				return false, err
			}
			victims = append(victims, v)
			if loggerV := logger.V(5); loggerV.Enabled() {
				var pods []klog.ObjectRef
				for _, p := range v.Pods() {
					pods = append(pods, klog.KObj(p.GetPod()))
				}
				loggerV.Info("Pods are potential preemption victims on node", "pods", pods, "node", mainNodeName)
			}
		}

		return fits, nil
	}

	numViolatingVictim := 0
	for _, violatingVictim := range violatingVictims {
		if fits, err := reprieveVictim(violatingVictim.Victim); err != nil {
			return nil, 0, fwk.AsStatus(err)
		} else if !fits {
			numViolatingVictim += violatingVictim.ViolateCount
		}
	}

and then the non-violating ones:

// pkg/scheduler/framework/plugins/defaultpreemption/default_preemption.go:398-403
	// Now we try to reprieve non-violating victims.
	for _, v := range nonViolatingVictims {
		if _, err := reprieveVictim(v); err != nil {
			return nil, 0, fwk.AsStatus(err)
		}
	}

The loop reads backwards from what you might expect: “reprieve” means keep. The function adds a victim back to the node and re-runs Filter. If the preemptor still fits, the victim stays and the next one is tried. If it no longer fits, the victim is removed again and appended to the victim set — that pod is going to be evicted.

So the algorithm is: put everything back that you can afford to keep, in descending order of importance, and evict the rest.

Two properties fall out of this:

• The victim set is not guaranteed to be cardinality-minimal. Reprieve is greedy in importance order. If a high-importance pod is added back and happens to consume the exact resource the preemptor needs, the preemptor stops fitting and every remaining pod becomes a victim — even if a different combination would have evicted only one. The result is “importance-maximal subject to fitting”, not “smallest possible”.
• The cost is O(victims) Filter runs per candidate node. Each reprieve attempt re-runs the full Filter plugin set against the node. This is the dominant cost of preemption, and it is why the number of candidate nodes is capped.

The importance cascade

The ordering comes from a single function, and its doc comment is the clearest statement of the policy in the tree:

// pkg/scheduler/framework/preemption/util.go:42-85
// MoreImportantVictim decides which of two preemption units is considered more critical.
// It applies the following rules in order:
//
//  1. Priority:
//     Higher priority units are more important.
//
//  2. Workload Type:
//     CompositePodGroups are considered more important than PodGroups, and
//     PodGroups are more important than individual Pods to preserve group integrity.
//
//  3. Runtime / Start Time (for individual Pods):
//     For two individual Pods, the one that started earlier (longer runtime)
//     is more important. This honors "first-come, first-served".
//
//  4. Group Size (for PodGroups and CompositePodGroups):
//     If both units are of the same type, the one with more members (larger size) is considered
//     more important. This avoids the high cost of rescheduling massive jobs.
//
//  5. Start Time (Tie-breaker for group types):
//     If group types and sizes are equal, the group that started earlier (has the oldest pod)
//     is more important.
func MoreImportantVictim(vi1, vi2 Victim) bool {
	if vi1.Priority() != vi2.Priority() {
		return vi1.Priority() > vi2.Priority()
	}

	rank1 := victimRank(vi1)
	rank2 := victimRank(vi2)

	if rank1 != rank2 {
		return rank1 > rank2
	}

	if len(vi1.Pods()) != len(vi2.Pods()) {
		return len(vi1.Pods()) > len(vi2.Pods())
	}

	t1, t2 := vi1.EarliestStartTime(), vi2.EarliestStartTime()
	if t1 != nil && t2 != nil && !t1.Equal(t2) {
		return t1.Before(t2)
	}

	return podIdentityLess(vi1, vi2)
}

Priority dominates everything. Two pods with the same priority are then ranked by workload type:

// pkg/scheduler/framework/preemption/util.go:94-103
func victimRank(vi Victim) int {
	switch vi.Type() {
	case fwk.CompositePodGroupKeyType:
		return 3
	case fwk.PodGroupKeyType:
		return 2
	default:
		return 1
	}
}

A composite pod group outranks a pod group, which outranks a bare pod. The reason is stated in the comment: gang members are not independently reschedulable, so evicting one member of a gang usually means evicting the whole gang. The scheduler would rather bump a standalone pod than shatter a gang. Then group size, then earliest start time, and finally the pod UID as a deterministic tiebreak so the ordering is stable across cycles.

The whole function is replaceable — the plugin exposes it as a MoreImportantVictimFunc hook on the DefaultPreemption struct, and its doc comment describes the algorithm in one paragraph: “the search for nodes eligible for preemption is done by omitting all eligible victims from a node then checking whether the preemptor fits on the node without them, before adding back victims (starting from the most important) that still fit with the preemptor” (pkg/scheduler/framework/plugins/defaultpreemption/default_preemption.go:55-63). Someone should update that comment when the code changes.

PDB atomicity

The PDB handling is where the “remove everything, reprieve” structure pays off. The victims are split into two buckets, and the PDB-violating bucket is reprieved first:

// pkg/scheduler/framework/preemption/util.go:141-165
	for i, pdb := range pdbs {
		pdbsAllowed[i] = pdb.Status.DisruptionsAllowed
	}

	// A Victim is atomic: if any single pod inside it would violate a PDB on
	// eviction, the entire Victim is classified as violating. This is required
	// for PodGroup victims, where partial preemption is not allowed — we cannot
	// "reprieve" only the pods that violate a PDB and keep the rest evicted.
	for _, victim := range victims {
		violatingPods := 0

		for _, pi := range victim.Pods() {
			if podIsViolating(pi.GetPod()) {
				violatingPods++
			}
		}
		if violatingPods > 0 {
			violatingVictims = append(violatingVictims, ViolatingVictim[T]{
				Victim:       victim,
				ViolateCount: violatingPods,
			})
		} else {
			nonViolatingVictims = append(nonViolatingVictims, victim)
		}
	}

The atomicity rule is the subtle part. If a gang of 10 pods is protected by a PDB that allows 1 disruption, and 3 of those 10 pods are candidates for preemption, then evicting any of them violates the budget — but the gang cannot be evicted partially, because the remaining 7 members would be orphaned. So the entire gang is classified as violating, and the count of violating pods (ViolateCount) is the number of pods that individually break the budget.

That count is what gets reported back to the caller as numViolatingVictim, and it flows into the candidate:

// pkg/scheduler/framework/preemption/preemption.go:488-498
		if status.IsSuccess() && (len(pods) != 0 || ev.hasInterestedPreemptExtender(pod)) {
			victims := extenderv1.Victims{
				Pods:             pods,
				NumPDBViolations: int64(numPDBViolations),
			}
			c := newCandidate(&victims, nodeInfo.Node().Name, 0, nodeInfo.Node().Name)
			if numPDBViolations == 0 {
				nonViolatingCandidates.add(c)
			} else {
				violatingCandidates.add(c)
			}

Candidates that break no PDB are kept in a separate list, and the two lists are drained in order — non-violating first — so a node that can be freed without breaking any budget always wins over one that cannot.

The podIsViolating closure inside FilterVictimsWithPDBViolation is careful about one thing: it decrements a per-PDB budget counter as it walks the victims, so the third pod to break a PDB with disruptionsAllowed: 1 is flagged, and the pods already recorded in pdb.Status.DisruptedPods are skipped so the budget is not over-decremented.

Which nodes get dry-run at all

Preemption cannot afford to evaluate every unschedulable node, so the plugin picks a random offset and a bounded number of candidates:

// pkg/scheduler/framework/plugins/defaultpreemption/default_preemption.go:220-243
// calculateNumCandidates returns the number of candidates the FindCandidates
// method must produce from dry running based on the constraints given by
// <minCandidateNodesPercentage> and <minCandidateNodesAbsolute>. The number of
// candidates returned will never be greater than <numNodes>.
func (pl *DefaultPreemption) calculateNumCandidates(numNodes int32) int32 {
	n := (numNodes * pl.args.MinCandidateNodesPercentage) / 100
	if n < pl.args.MinCandidateNodesAbsolute {
		n = pl.args.MinCandidateNodesAbsolute
	}
	if n > numNodes {
		n = numNodes
	}
	return n
}

// getOffsetRand is a dedicated random source for GetOffsetAndNumCandidates calls.
// It defaults to rand.Int31n, but is a package variable so it can be overridden to make unit tests deterministic.
var getOffsetRand = rand.Int31n

// GetOffsetAndNumCandidates chooses a random offset and calculates the number
// of candidates that should be shortlisted for dry running preemption.
func (pl *DefaultPreemption) GetOffsetAndNumCandidates(numNodes int32) (int32, int32) {
	return getOffsetRand(numNodes), pl.calculateNumCandidates(numNodes)
}

The defaults for the two arguments are 10% and 100 absolute (pkg/scheduler/apis/config/v1/defaults.go:186-190). So in a cluster with 500 unschedulable nodes, preemption dry-runs 100 of them, starting at a random offset. The random offset matters: it prevents the same nodes from being preemption candidates on every attempt, which would otherwise create a hot spot where the same well-connected node gets preempted over and over.

Wrapping up

The one thing to remember: preemption is “remove everything, then reprieve as much as you can afford”. The victim set is whatever could not be put back without the preemptor stopping fitting — it is importance-maximal, not necessarily cardinality-minimal. The whole thing is one loop of Filter runs per candidate node, so the cost scales with the number of victims times the number of candidates.

The part people get wrong: preemption does not respect PodDisruptionBudgets as a hard constraint. It prefers not to violate them — PDB-violating victims are reprieved first and non-violating candidates are selected first — but if the only way to schedule the pod is to break a budget, the scheduler will break it and report NumPDBViolations. If your workload depends on budgets being respected, put the preemptor’s priority below the protected pods; preemption only ever evicts pods with strictly lower priority.

What to go do about it: the knobs are in KubeSchedulerConfiguration.plugins.defaultPreemption — minCandidateNodesPercentage (default 10) and minCandidateNodesAbsolute (default 100) — and raising them buys you more candidate nodes at a proportional cost in Filter runs. Watch scheduler_preemption_attempts_total, scheduler_preemption_goroutines_duration_seconds and scheduler_preemption_pdb_violations_total. If preemption is thrashing a node, check the priority relationship first: a preemptor that is only one priority class above a protected Deployment will evict it the moment the Deployment’s pods land on the same node.