Opensource internals

The Scheduler Never Locks the Cache: Generation Stamps and Copy-on-Write NodeInfos

12 min read Jay Hubbert

kube-scheduler's cache snapshot clones only the NodeInfos that changed since the last cycle, using a monotonic Generation stamp and a recency-ordered list that stops early.

TL;DR: The scheduler cache is written by informer goroutines and read by the scheduling cycle, and the two never block each other. The cache keeps its NodeInfos in a doubly-linked list ordered by recency of update, and every NodeInfo carries a globally monotonic Generation counter. UpdateSnapshot walks that list from the head and stops at the first node whose Generation is not newer than the previous snapshot, cloning only the nodes above that line. Everything below is shared by pointer. A 5000-node cluster with two changed nodes copies two NodeInfos per cycle, not 5000.

The scheduler’s cache is the busiest data structure in the control plane. Every node add, node update, pod assignment, pod eviction and pod deletion lands there, and all of it has to be reflected in the next scheduling cycle before that cycle can make a decision. The obvious implementation is a deep copy of the whole cache at the top of every cycle: take a lock, copy every NodeInfo, release the lock, run the cycle against the copy.

That design is wrong on both ends. The copy is O(nodes x pods) per cycle, which in a large cluster is more work than the scheduling itself. And the copy is taken after the lock is released, so it is a snapshot of a moving target unless you hold the lock for the whole cycle, which would serialise the scheduler against every informer in the cluster.

Kubernetes solves it with a much older idea than copy-on-write: stamp the mutated object, keep the mutations ordered, and copy only the delta.

The cache is written by everyone and read by one

The cache is a cacheImpl with a single sync.RWMutex guarding all of its fields. Writers (the informers) take the write lock; the snapshot takes the write lock too, but only for the duration of the copy — the scheduling cycle itself runs entirely against the snapshot, lock-free:

go 
// pkg/scheduler/backend/cache/cache.go:66-77
	// This mutex guards all fields within this cache struct.
	mu sync.RWMutex
	// a set of assumed pod keys.
	// The key could further be used to get an entry in podStates.
	assumedPods sets.Set[string]
	// a map from pod key to podState.
	podStates map[string]*podState
	nodes     map[string]*nodeInfoListItem
	// headNode points to the most recently updated NodeInfo in "nodes". It is the
	// head of the linked list.
	headNode *nodeInfoListItem
	nodeTree *nodeTree

Note that nodes maps a node name to a *nodeInfoListItem, not to a *NodeInfo. The extra indirection is the list node. The map is for random access; the list is for ordered access, and it is the list that makes the delta copy possible.

A list ordered by recency, not by name

Every time a node’s NodeInfo changes, it is unlinked and pushed to the front of the list:

go 
// pkg/scheduler/backend/cache/cache.go:131-157
// moveNodeInfoToHead moves a NodeInfo to the head of "cache.nodes" doubly
// linked list. The head is the most recently updated NodeInfo.
// We assume cache lock is already acquired.
func (cache *cacheImpl) moveNodeInfoToHead(logger klog.Logger, name string) {
	ni, ok := cache.nodes[name]
	if !ok {
		utilruntime.HandleErrorWithLogger(logger, nil, "No node info with given name found in the cache", "node", klog.KRef("", name))
		return
	}
	// if the node info list item is already at the head, we are done.
	if ni == cache.headNode {
		return
	}

	if ni.prev != nil {
		ni.prev.next = ni.next
	}
	if ni.next != nil {
		ni.next.prev = ni.prev
	}
	if cache.headNode != nil {
		cache.headNode.prev = ni
	}
	ni.next = cache.headNode
	ni.prev = nil
	cache.headNode = ni
}

The list node itself is deliberately thin — info, next, prev and nothing else — so the map and the list can point at the same object without copying it. The reordering is called from addPod and removePod, immediately after the NodeInfo itself is mutated. So the list is ordered by when the node was last touched, not by node name, not by zone, not by generation. That ordering is what lets the snapshot walk terminate early.

Generation stamps: monotonic, global, never reused

Each NodeInfo carries a Generation field that is bumped on every mutation:

go 
// pkg/scheduler/framework/types.go:208-218
	// PVCRefCounts contains a mapping of PVC names to the number of pods on the node using it.
	// Keys are in the format "namespace/name".
	PVCRefCounts map[string]int

	// Whenever NodeInfo changes, generation is bumped.
	// This is used to avoid cloning it if the object didn't change.
	Generation int64

	// DeclaredFeatures is a set of features published by the node
	DeclaredFeatures ndf.FeatureSet
}

and the bump comes from a single global atomic counter, not a per-node one:

go 
// pkg/scheduler/framework/types.go:526-532
// nextGeneration: Let's make sure history never forgets the name...
// Increments the generation number monotonically ensuring that generation numbers never collide.
// Collision of the generation numbers would be particularly problematic if a node was deleted and
// added back with the same name. See issue#63262.
func nextGeneration() int64 {
	return atomic.AddInt64(&generation, 1)
}

The comment about issue #63262 is the whole point. If generations were per-node, a node named node-1 could be deleted and re-added and end up with the same generation as before, which would make the scheduler believe nothing changed when everything had. A single global counter makes generations globally unique and totally ordered, so “is this node newer than the snapshot?” is a single integer comparison. nextGeneration() is called from update (pod added or removed), SetNode and RemoveNode. Nothing else bumps it.

The snapshot walk that stops early

This is the whole mechanism:

go 
// pkg/scheduler/backend/cache/cache.go:240-271
	// Start from the head of the NodeInfo doubly linked list and update snapshot
	// of NodeInfos updated after the last snapshot.
	for node := cache.headNode; node != nil; node = node.next {
		if node.info.Generation <= snapshotGeneration {
			// all the nodes are updated before the existing snapshot. We are done.
			break
		}
		if np := node.info.Node(); np != nil {
			existing, ok := nodeSnapshot.nodeInfoMap[np.Name]
			if !ok {
				updateAllLists = true
				existing = &framework.NodeInfo{}
				nodeSnapshot.nodeInfoMap[np.Name] = existing
			}
			clone := node.info.SnapshotConcrete()
			// We track nodes that have pods with affinity, here we check if this node changed its
			// status from having pods with affinity to NOT having pods with affinity or the other
			// way around.
			if (len(existing.PodsWithAffinity) > 0) != (len(clone.PodsWithAffinity) > 0) {
				updateNodesHavePodsWithAffinity = true
			}
			if (len(existing.PodsWithRequiredAntiAffinity) > 0) != (len(clone.PodsWithRequiredAntiAffinity) > 0) {
				updateNodesHavePodsWithRequiredAntiAffinity = true
			}
			if (len(existing.PodsWithRequiredNonHostScopedAntiAffinity) > 0) != (len(clone.PodsWithRequiredNonHostScopedAntiAffinity) > 0) {
				updateNodesHavePodsWithRequiredNonHostScopedAntiAffinity = true
			}
			// We need to preserve the original pointer of the NodeInfo struct since it
			// is used in the NodeInfoList, which we may not update.
			*existing = *clone
		}
	}

Read the break condition carefully: <=. A node whose generation is exactly the snapshot generation is not copied — it was already captured. The invariant that makes the break sound is the combination of two facts:

  1. The list is ordered by last-update time, and the generation counter is monotonic in time. Therefore generations along the list are non-increasing.
  2. The snapshot generation is the generation of the head at the time of the previous snapshot, i.e. the maximum generation that existed then.

So walking from the head, every node with Generation > snapshotGeneration was updated after the last snapshot and must be copied. The first node with Generation <= snapshotGeneration was last touched at or before the previous snapshot, and so was every node behind it in the list. The break is correct.

Then the snapshot generation is bumped to the current head:

go 
// pkg/scheduler/backend/cache/cache.go:272-296
	// Update the snapshot generation with the latest NodeInfo generation.
	if cache.headNode != nil {
		nodeSnapshot.generation = cache.headNode.info.Generation
	}

	// Comparing to pods in nodeTree.
	// Deleted nodes get removed from the tree, but they might remain in the nodes map
	// if they still have non-deleted Pods.
	if len(nodeSnapshot.nodeInfoMap) > cache.nodeTree.numNodes {
		cache.removeDeletedNodesFromSnapshot(nodeSnapshot)
		updateAllLists = true
	}

	// Apply the deltas for PVC reference count to the snapshot.
	// This no-op if the snapshot is built afresh i.e. updateAllLists=true
	if !updateAllLists {
		if err := cache.applyPVCRefCountDelta(nodeSnapshot); err != nil {
			logger.Error(err, "rebuilding node snapshot due to unexpected error from refreshing PVC ref counts")
			updateAllLists = true
		}
	}

	if updateAllLists || updateNodesHavePodsWithAffinity || updateNodesHavePodsWithRequiredAntiAffinity || updateNodesHavePodsWithRequiredNonHostScopedAntiAffinity {
		cache.updateNodeInfoSnapshotList(logger, nodeSnapshot, updateAllLists)
	}

The last line is the interesting one: the lists are only rebuilt when the set of nodes changed (updateAllLists) or when a node changed whether it has pods with affinity at all. Pods moving on and off a node does not rebuild them.

What a clone actually copies

SnapshotConcrete is not free, but it is not a deep copy of the world either:

go 
// pkg/scheduler/framework/types.go:304-316
// SnapshotConcrete returns a copy of this node, Except that ImageStates is copied without the Nodes field.
func (n *NodeInfo) SnapshotConcrete() *NodeInfo {
	clone := &NodeInfo{
		node:             n.node,
		Requested:        n.Requested.Clone(),
		NonZeroRequested: n.NonZeroRequested.Clone(),
		Allocatable:      n.Allocatable.Clone(),
		UsedPorts:        make(fwk.HostPortInfo),
		ImageStates:      make(map[string]*fwk.ImageStateSummary),
		PVCRefCounts:     make(map[string]int),
		Generation:       n.Generation,
		DeclaredFeatures: n.DeclaredFeatures.Clone(),
	}

The *v1.Node object itself is shared by pointer (node: n.node), because node status updates mutate the cache’s copy of the node in place before the generation bump. The pod slices are copied by header, not by element. The resource vectors are cloned because AddPod/RemovePod mutate them in place.

The *existing = *clone line at the end of the walk is the trick that keeps pointer identity stable. nodeInfoList holds fwk.NodeInfo interfaces pointing at the snapshot’s NodeInfo structs. If the walk replaced those pointers, the list would dangle. Instead it copies the contents of the clone into the existing struct, so every list entry keeps pointing at the same object it always did.

The lists are only rebuilt when the topology changes

Three auxiliary lists hang off the snapshot, used by the inter-pod affinity plugin to avoid iterating over every node: havePodsWithAffinityNodeInfoList, havePodsWithRequiredAntiAffinityNodeInfoList and havePodsWithRequiredNonHostScopedAntiAffinityNodeInfoList. They are rebuilt from the node tree, and the expensive branch only runs when updateAll is true:

go 
// pkg/scheduler/backend/cache/cache.go:363-374
func (cache *cacheImpl) updateNodeInfoSnapshotList(logger klog.Logger, snapshot *Snapshot, updateAll bool) {
	snapshot.havePodsWithAffinityNodeInfoList = make([]fwk.NodeInfo, 0, cache.nodeTree.numNodes)
	snapshot.havePodsWithRequiredAntiAffinityNodeInfoList = make([]fwk.NodeInfo, 0, cache.nodeTree.numNodes)
	snapshot.havePodsWithRequiredNonHostScopedAntiAffinityNodeInfoList = make([]fwk.NodeInfo, 0, cache.nodeTree.numNodes)
	if updateAll {
		snapshot.usedPVCRefCounts = make(map[string]int)
		// Take a snapshot of the nodes order in the tree
		snapshot.nodeInfoList = make([]fwk.NodeInfo, 0, cache.nodeTree.numNodes)
		nodesList, err := cache.nodeTree.list()
		if err != nil {
			utilruntime.HandleErrorWithLogger(logger, err, "Error occurred while retrieving the list of names of the nodes from node tree")
		}

and the loop body walks that list, appending each node to nodeInfoList and to whichever of the three affinity lists it belongs to, while summing its PVC ref counts into snapshot.usedPVCRefCounts.

updateAllLists is set to true in exactly two places: a node that is not in the snapshot map (a node was added), and the snapshot map being larger than the node tree (a node was deleted). So the O(nodes) rebuild happens on node churn, not on pod churn. In a cluster with a steady node count and busy pod scheduling, it essentially never runs.

PVC ref counts as a delta map

The usedPVCRefCounts map is the cluster-wide count of how many pods use each PVC. It answers “is this PVC already bound elsewhere?”, and a naive implementation recomputes it by walking every node and every PVC on it on every cycle — O(nodes x PVCs). Instead, the cache keeps a delta:

go 
// pkg/scheduler/backend/cache/cache.go:92-97
	// pvcRefCountsDelta contains the delta of changes to PVCRefCounts since the last snapshot.
	// Keys are in the format "namespace/name". This data struct serves as an optimization for avoiding
	// burdensome PVC ref count aggregations during scheduler cycles. PVCRefCountsDelta holds the incoming
	// deltas from events handlers while within the scheduler cycle, we only apply and reset the delta to
	// avoid global re-calculation.
	pvcRefCountsDelta map[string]int

The delta is maintained at the point of mutation, before and after the pod is added or removed, so the change is what gets recorded:

go 
// pkg/scheduler/backend/cache/cache.go:534-539
	// new_delta = old_delta + (PVCRefCounts_after − PVCRefCounts_before)
	cache.refreshPVCRefCountsDelta(n.info, -1)
	defer cache.refreshPVCRefCountsDelta(n.info, 1)

	n.info.AddPod(pod)
	cache.moveNodeInfoToHead(logger, pod.Spec.NodeName)

and applied to the snapshot at the end of the cycle:

go 
// pkg/scheduler/backend/cache/cache.go:1112-1127
// applyPVCRefCountDelta merges cache.pvcRefCountsDelta into the snapshot's
// PVC ref counts, removes entries that reach zero, and clears the delta.
func (cache *cacheImpl) applyPVCRefCountDelta(snapshot *Snapshot) error {
	for key, delta := range cache.pvcRefCountsDelta {
		snapshot.usedPVCRefCounts[key] += delta
		if refCount := snapshot.usedPVCRefCounts[key]; refCount <= 0 {
			if refCount < 0 {
				delete(snapshot.usedPVCRefCounts, key)
				return fmt.Errorf("PVC %s had negative ref count %v", key, refCount)
			}
			delete(snapshot.usedPVCRefCounts, key)
		}
	}
	cache.pvcRefCountsDelta = map[string]int{}
	return nil
}

The negative-count branch is a genuine assertion that the delta arithmetic is correct: a negative count means the delta and the snapshot disagreed about the cluster state, and the snapshot is thrown away and rebuilt from scratch (updateAllLists = true). The fast path has a self-check.

The arithmetic: a cluster of 5000 nodes each with 20 PVC references, with 2 nodes changing, does 40 map operations per cycle instead of 100 000. The delta map is O(changed PVCs), not O(nodes x PVCs).

Wrapping up

The one thing to remember: the scheduler does not copy the cache, it copies the delta. The Generation stamp tells you whether a NodeInfo changed; the recency-ordered list tells you where the changed ones end. The snapshot walk breaks on the first unchanged node and everything behind it is shared by pointer with the live cache.

The part people get wrong: the break condition is only sound because the list is ordered by last update time and generations are globally monotonic. If you ever reorder that list — by zone, by name, by allocatable — the early break silently starts missing changes, and the scheduler will schedule against stale node state with no error anywhere. UpdateSnapshot also has a consistency check at pkg/scheduler/backend/cache/cache.go:298 that compares len(snapshot.nodeInfoList) against cache.nodeTree.numNodes; if you see snapshot state is not consistent in the scheduler log, that is this invariant breaking.

What to go do about it: measure the cycle cost before you tune anything — scheduler_framework_extension_point_duration_seconds{extension_point="Filter"} and the scheduler_pending_pods gauge tell you whether the scheduler is cycle-bound or cluster-bound. If the cache is the bottleneck, look at how often nodes churn in your cluster — node churn is what forces the O(nodes) updateNodeInfoSnapshotList rebuild — and at the pod density per node, which is what SnapshotConcrete actually copies.

KubernetesInternalsScheduler