Opensource internals

Solid, Dangling, Waiting: How the Garbage Collector Decides to Delete

15 min read Jay Hubbert

The garbage collector classifies every owner reference into solid, dangling or waiting-for-dependents-deletion, using a metadata-only client so only PartialObjectMetadata crosses the wire.

TL;DR: The garbage collector never deletes an object just because it has owner references. It asks the API server — through a metadata-only client, so only PartialObjectMetadata crosses the wire — whether each owner still exists, and sorts the references into three buckets: solid (the owner exists), dangling (it does not) and waiting (it exists, is being deleted, and carries the foregroundDeletion finalizer). Solid owners mean “hands off”; dangling owners mean “delete, or strip the reference”; waiting owners mean “not yet”. There is also a cycle breaker: two objects that are each waiting on the other are unblocked by patching the owner references to non-blocking and deleting with DeletePropagationForeground.

Ownership in Kubernetes is a promise, not a lock. A Deployment sets an owner reference on its ReplicaSets, a ReplicaSet sets one on its Pods, and a Job sets one on the pods it creates. When the owner goes away, the dependents should go away with it — but “should” is doing a lot of work in that sentence, because a dependent can have several owners, one owner can be deleted and recreated with the same name but a different UID, and the API server will happily accept a reference to an object that never existed.

The garbage collector is the component that has to reconcile all of that without ever holding the whole object graph in memory at once, and without racing the API server’s own cascading delete.

Three buckets, not one

The classification happens in one place, and it is short enough to read in full:

go 
// pkg/controller/garbagecollector/garbagecollector.go:455
// classify the latestReferences to three categories:
// solid: the owner exists, and is not "waitingForDependentsDeletion"
// dangling: the owner does not exist
// waitingForDependentsDeletion: the owner exists, its deletionTimestamp is non-nil, and it has
// FinalizerDeletingDependents
// This function communicates with the server.
func (gc *GarbageCollector) classifyReferences(ctx context.Context, item *node, latestReferences []metav1.OwnerReference) (
	solid, dangling, waitingForDependentsDeletion []metav1.OwnerReference, err error) {
	for _, reference := range latestReferences {
		isDangling, owner, err := gc.isDangling(ctx, reference, item)
		if err != nil {
			return nil, nil, nil, err
		}
		if isDangling {
			dangling = append(dangling, reference)
			continue
		}

		ownerAccessor, err := meta.Accessor(owner)
		if err != nil {
			return nil, nil, nil, err
		}
		if ownerAccessor.GetDeletionTimestamp() != nil && hasDeleteDependentsFinalizer(ownerAccessor) {
			waitingForDependentsDeletion = append(waitingForDependentsDeletion, reference)
		} else {
			solid = append(solid, reference)
		}
	}
	return solid, dangling, waitingForDependentsDeletion, nil
}

Two things are decided here. “Does the owner exist?” — that is isDangling. And “if it exists, is it in the middle of being torn down?” — that is the DeletionTimestamp != nil && hasDeleteDependentsFinalizer test, which is what separates waiting from solid.

The finalizer in question is metav1.FinalizerDeleteDependents, which the API server adds when a delete is requested with DeletePropagationForeground. Its presence is the API server’s way of saying “I am waiting for my dependents to go away before I disappear”.

Asking the server, cheaply

The liveness question is answered by the API server, not by the GC’s own cache. That matters: the GC’s graph is built from informers and can lag, and a lagging cache would turn into a false “the owner is gone” and a mass deletion.

go 
// pkg/controller/garbagecollector/garbagecollector.go:428
	// TODO: It's only necessary to talk to the API server if the owner node
	// is a "virtual" node. The local graph could lag behind the real
	// status, but in practice, the difference is small.
	owner, err = gc.metadataClient.Resource(resource).Namespace(resourceDefaultNamespace(namespaced, item.identity.Namespace)).Get(ctx, reference.Name, metav1.GetOptions{})
	switch {
	case errors.IsNotFound(err):
		gc.absentOwnerCache.Add(absentOwnerCacheKey)
		logger.V(5).Info("item's owner is not found",
			"item", item.identity,
			"owner", reference,
		)
		return true, nil, nil
	case err != nil:
		return false, nil, err
	}

	if owner.GetUID() != reference.UID {
		logger.V(5).Info("item's owner is not found, UID mismatch",
			"item", item.identity,
			"owner", reference,
		)
		gc.absentOwnerCache.Add(absentOwnerCacheKey)
		return true, nil, nil
	}
	return false, owner, nil

Two details are load-bearing.

First, gc.metadataClient is a metadata.Interface — the metadata-only client from k8s.io/client-go/metadata. The returned object is a *metav1.PartialObjectMetadata, which contains only TypeMeta and ObjectMeta. The GC never needs the owner’s spec or status, only its existence, its UID, its deletion timestamp and its finalizers — and fetching a full Pod object to learn four facts about it is exactly the kind of waste that makes a control plane fall over.

Second, the UID check. A name alone is not identity. If a Deployment is deleted and recreated with the same name, its old ReplicaSet still carries an owner reference with the old UID. The name resolves; the UID does not match; the reference is dangling. Without that check, every recreated owner would orphan a generation of dependents.

The absent owner cache

The GET above is a live API call, and the GC makes a lot of them. The absentOwnerCache is the escape hatch — a small LRU of owner references known to be gone:

go 
// pkg/controller/garbagecollector/uid_cache.go:24
type ReferenceCache struct {
	cache *lru.Cache
}

// NewReferenceCache returns a ReferenceCache.
func NewReferenceCache(maxCacheEntries int) *ReferenceCache {
	return &ReferenceCache{
		cache: lru.New(maxCacheEntries),
	}
}

It is created with a hard-coded size:

go 
// pkg/controller/garbagecollector/graph_builder.go:165
	absentOwnerCache := NewReferenceCache(500)

500 entries, no flag, no config API. A reference that is known-absent is remembered so the GC does not have to ask again. The cache is checked before the API call, twice, because a cluster-scoped owner and a namespaced owner with the same name are different objects:

go 
// pkg/controller/garbagecollector/garbagecollector.go:384
	// check for recorded absent cluster-scoped parent
	absentOwnerCacheKey := objectReference{OwnerReference: ownerReferenceCoordinates(reference)}
	if gc.absentOwnerCache.Has(absentOwnerCacheKey) {
		logger.V(5).Info("according to the absentOwnerCache, item's owner does not exist",
			"item", item.identity,
			"owner", reference,
		)
		return true, nil, nil
	}

	// check for recorded absent namespaced parent
	absentOwnerCacheKey.Namespace = item.identity.Namespace
	if gc.absentOwnerCache.Has(absentOwnerCacheKey) {
		logger.V(5).Info("according to the absentOwnerCache, item's owner does not exist in namespace",
			"item", item.identity,
			"owner", reference,
		)
		return true, nil, nil
	}

The cache is a correctness optimisation, not just a performance one: a dangling reference that is also in the cache short-circuits before the API call, which means the GC does not have to distinguish “owner gone” from “owner gone but a new one exists with the same name” for the cached entries.

The three-way switch

Now the decision. attemptToDeleteItem reads the live object, classifies its owner references, and branches three ways:

go 
// pkg/controller/garbagecollector/garbagecollector.go:567
	switch {
	case len(solid) != 0:
		logger.V(2).Info("item has at least one existing owner, will not garbage collect",
			"item", item.identity,
			"owner", solid,
		)
		if len(dangling) == 0 && len(waitingForDependentsDeletion) == 0 {
			return nil
		}
		logger.V(2).Info("remove dangling references and waiting references for item",
			"item", item.identity,
			"dangling", dangling,
			"waitingForDependentsDeletion", waitingForDependentsDeletion,
		)
		// waitingForDependentsDeletion needs to be deleted from the
		// ownerReferences, otherwise the referenced objects will be stuck with
		// the FinalizerDeletingDependents and never get deleted.
		ownerUIDs := append(ownerRefsToUIDs(dangling), ownerRefsToUIDs(waitingForDependentsDeletion)...)
		p, err := c.GenerateDeleteOwnerRefStrategicMergeBytes(item.identity.UID, ownerUIDs)
		if err != nil {
			return err
		}
		_, err = gc.patch(item, p, func(n *node) ([]byte, error) {
			return gc.deleteOwnerRefJSONMergePatch(n, ownerUIDs...)
		})
		return err
	case len(waitingForDependentsDeletion) != 0 && item.dependentsLength() != 0:

Read the first branch carefully. A single solid owner is enough to prevent deletion — the object stays, no matter what else is wrong. But the GC does not simply leave it alone: if some of the other references are dangling, it patches them off. An object with one live owner and three references to long-dead owners keeps its live owner and loses the ghosts, because a dangling reference to a UID that never existed is a permanent trip hazard for anything that walks the graph.

The second branch is the interesting one, and it is the cycle breaker:

go 
// pkg/controller/garbagecollector/garbagecollector.go:593
	case len(waitingForDependentsDeletion) != 0 && item.dependentsLength() != 0:
		deps := item.getDependents()
		for _, dep := range deps {
			if dep.isDeletingDependents() {
				// this circle detection has false positives, we need to
				// apply a more rigorous detection if this turns out to be a
				// problem.
				// there are multiple workers run attemptToDeleteItem in
				// parallel, the circle detection can fail in a race condition.
				logger.V(2).Info("processing item, some of its owners and its dependent have FinalizerDeletingDependents, to prevent potential cycle, its ownerReferences are going to be modified to be non-blocking, then the item is going to be deleted with Foreground",
					"item", item.identity,
					"dependent", dep.identity,
				)
				patch, err := item.unblockOwnerReferencesStrategicMergePatch()
				if err != nil {
					return err
				}
				if _, err := gc.patch(item, patch, gc.unblockOwnerReferencesJSONMergePatch); err != nil {
					return err
				}
				break
			}
		}
		logger.V(2).Info("at least one owner of item has FinalizerDeletingDependents, and the item itself has dependents, so it is going to be deleted in Foreground",
			"item", item.identity,
		)
		// the deletion event will be observed by the graphBuilder, so the item
		// will be processed again in processDeletingDependentsItem. If it
		// doesn't have dependents, the function will remove the
		// FinalizerDeletingDependents from the item, resulting in the final
		// deletion of the item.
		policy := metav1.DeletePropagationForeground
		err := gc.deleteObject(item.identity, latest.ResourceVersion, latest.OwnerReferences, &policy)

Here is the deadlock this prevents. Object A owns object B. Both are being deleted with foreground propagation. A is waiting for B to disappear; B is waiting for A to disappear. Neither will ever go away, because each one’s deletion is gated on a dependent that is itself gated.

The fix is to break the blocking nature of the owner references rather than the deletion. unblockOwnerReferencesStrategicMergePatch rewrites the owner references so they no longer carry the blocking flag, and then the item is deleted with DeletePropagationForeground anyway. The foreground deletion still waits for the dependents — it is the owner→dependent direction that gets unblocked.

And when the owner is merely waiting — no cycle, just an owner in the middle of being deleted — the GC does not touch the object at all. It stays put until its owner goes away.

The third branch is the actual delete:

go 
// pkg/controller/garbagecollector/garbagecollector.go:631
	default:
		// item doesn't have any solid owner, so it needs to be garbage
		// collected. Also, none of item's owners is waiting for the deletion of
		// the dependents, so set propagationPolicy based on existing finalizers.
		var policy metav1.DeletionPropagation
		switch {
		case hasOrphanFinalizer(latest):
			// if an existing orphan finalizer is already on the object, honor it.
			policy = metav1.DeletePropagationOrphan
		case hasDeleteDependentsFinalizer(latest):
			// if an existing foreground finalizer is already on the object, honor it.
			policy = metav1.DeletePropagationForeground
		default:
			// otherwise, default to background.
			policy = metav1.DeletePropagationBackground
		}

Every owner reference is dangling, so the object is garbage. The propagation policy is not chosen freely: an object that already carries the orphan finalizer gets DeletePropagationOrphan, one that already carries the foreground finalizer gets DeletePropagationForeground, and everything else gets background — which is the cheap one, because background deletion lets the API server cascade without waiting for the dependents to be confirmed gone.

Finishing the foreground deletion

The foreground path needs a second pass. When the GC sees an object that is already deleting its dependents, it checks whether any dependent is still blocking:

go 
// pkg/controller/garbagecollector/garbagecollector.go:660
// process item that's waiting for its dependents to be deleted
func (gc *GarbageCollector) processDeletingDependentsItem(logger klog.Logger, item *node) error {
	blockingDependents := item.blockingDependents()
	if len(blockingDependents) == 0 {
		logger.V(2).Info("remove DeleteDependents finalizer for item", "item", item.identity)
		return gc.removeFinalizer(logger, item, metav1.FinalizerDeleteDependents)
	}
	for _, dep := range blockingDependents {
		if !dep.isDeletingDependents() {
			logger.V(2).Info("adding dependent to attemptToDelete, because its owner is deletingDependents",
				"item", item.identity,
				"dependent", dep.identity,
			)
			gc.attemptToDelete.Add(dep)
		}
	}
	return nil
}

If nothing is blocking any more, the foregroundDeletion finalizer is removed, and the API server — which is what actually enforces the finalizer — completes the deletion. If something is still blocking, the dependent is pushed back onto the delete queue and the loop continues.

Orphaning is the mirror image, and it is the one place the GC fans out:

go 
// pkg/controller/garbagecollector/garbagecollector.go:679
// dependents are copies of pointers to the owner's dependents, they don't need to be locked.
func (gc *GarbageCollector) orphanDependents(logger klog.Logger, owner objectReference, dependents []*node) error {
	errCh := make(chan error, len(dependents))
	wg := sync.WaitGroup{}
	wg.Add(len(dependents))
	for i := range dependents {
		go func(dependent *node) {
			defer wg.Done()
			// the dependent.identity.UID is used as precondition
			p, err := c.GenerateDeleteOwnerRefStrategicMergeBytes(dependent.identity.UID, []types.UID{owner.UID})
			if err != nil {
				errCh <- fmt.Errorf("orphaning %s failed, %v", dependent.identity, err)
				return
			}
			_, err = gc.patch(dependent, p, func(n *node) ([]byte, error) {
				return gc.deleteOwnerRefJSONMergePatch(n, owner.UID)
			})
			// note that if the target ownerReference doesn't exist in the
			// dependent, strategic merge patch will NOT return an error.
			if err != nil && !errors.IsNotFound(err) {
				errCh <- fmt.Errorf("orphaning %s failed, %v", dependent.identity, err)
			}
		}(dependents[i])
	}
	wg.Wait()
	close(errCh)

One goroutine per dependent, because orphaning a Deployment with 200 ReplicaSets means 200 patches, and they are independent. The comment about strategic merge patch not erroring on a missing owner reference is the important part: it makes the orphan operation idempotent, so a retry after a partial failure does not fail.

The graph behind it

All of this runs against a dependency graph that the GC maintains from informers. The graph is a map[UID]*node where each node has a set of dependents, and the concurrency model is spelled out in the type itself:

go 
// pkg/controller/garbagecollector/graph.go:58
// The single-threaded GraphBuilder.processGraphChanges() is the sole writer of the
// nodes. The multi-threaded GarbageCollector.attemptToDeleteItem() reads the nodes.
// WARNING: node has different locks on different fields. setters and getters
// use the respective locks, so the return values of the getters can be
// inconsistent.
type node struct {
	identity objectReference
	// dependents will be read by the orphan() routine, we need to protect it with a lock.
	dependentsLock sync.RWMutex
	// dependents are the nodes that have node.identity as a
	// metadata.ownerReference.
	dependents map[*node]struct{}
	// this is set by processGraphChanges() if the object has non-nil DeletionTimestamp
	// and has the FinalizerDeleteDependents.
	deletingDependents     bool
	deletingDependentsLock sync.RWMutex
	// this records if the object's deletionTimestamp is non-nil.
	beingDeleted     bool
	beingDeletedLock sync.RWMutex
	// this records if the object was constructed virtually and never observed via informer event
	virtual     bool
	virtualLock sync.RWMutex
	// when processing an Update event, we need to compare the updated
	// ownerReferences with the owners recorded in the graph.
	owners     []metav1.OwnerReference
	ownersLock sync.RWMutex
}

One writer, many readers, and per-field locks rather than one lock for the whole node. That is why the comment warns that two getters can be inconsistent with each other: the GC deliberately does not want the cost of a consistent snapshot of the whole node, because the fields it reads are independent facts.

The graph also contains nodes that do not correspond to real objects. When an informer event names an owner the GC has never seen, it creates a virtual node for it:

go 
// pkg/controller/garbagecollector/graph_builder.go:446
// addDependentToOwners adds n to owners' dependents list. If the owner does not
// exist in the gb.uidToNode yet, a "virtual" node will be created to represent
// the owner. The "virtual" node will be enqueued to the attemptToDelete, so that
// attemptToDeleteItem() will verify if the owner exists according to the API server.
func (gb *GraphBuilder) addDependentToOwners(logger klog.Logger, n *node, owners []metav1.OwnerReference) {
	// track if some of the referenced owners already exist in the graph and have been observed,
	// and the dependent's ownerRef does not match their observed coordinates
	hasPotentiallyInvalidOwnerReference := false

	for _, owner := range owners {
		ownerNode, ok := gb.uidToNode.Read(owner.UID)
		if !ok {
			// Create a "virtual" node in the graph for the owner if it doesn't
			// exist in the graph yet.
			ownerNode = &node{
				identity: objectReference{
					OwnerReference: ownerReferenceCoordinates(owner),
					Namespace:      n.identity.Namespace,
				},
				dependents: make(map[*node]struct{}),
				virtual:    true,
			}
			logger.V(5).Info("add virtual item", "identity", ownerNode.identity)
			gb.uidToNode.Write(ownerNode)
		}
		ownerNode.addDependent(n)
		if !ok {
			// Enqueue the virtual node into attemptToDelete.
			// The garbage processor will enqueue a virtual delete
			// event to delete it from the graph if API server confirms this
			// owner doesn't exist.
			gb.attemptToDelete.Add(ownerNode)
		} else if !hasPotentiallyInvalidOwnerReference {

The virtual node is the GC’s way of saying “I do not know this owner yet”. It is put on the delete queue, and when the GC processes it, the API server is asked whether it exists. If it does not, the virtual node is removed from the graph with a synthetic delete event:

go 
// pkg/controller/garbagecollector/graph_builder.go:431
// enqueueVirtualDeleteEvent is used to add a virtual delete event to be processed for virtual nodes
// once it is determined they do not have backing objects in storage
func (gb *GraphBuilder) enqueueVirtualDeleteEvent(ref objectReference) {
	gv, _ := schema.ParseGroupVersion(ref.APIVersion)
	gb.graphChanges.Add(&event{
		virtual:   true,
		eventType: deleteEvent,
		gvk:       gv.WithKind(ref.Kind),
		obj: &metaonly.MetadataOnlyObject{
			TypeMeta:   metav1.TypeMeta{APIVersion: ref.APIVersion, Kind: ref.Kind},
			ObjectMeta: metav1.ObjectMeta{Namespace: ref.Namespace, UID: ref.UID, Name: ref.Name},
		},
	})
}

Note the object in that synthetic event is a metaonly.MetadataOnlyObject — the same metadata-only type used by the API client. The GC’s graph builder never needs the owner’s spec either.

The knobs

There are surprisingly few. The worker count is the main one:

go 
// pkg/controller/garbagecollector/config/v1alpha1/defaults.go:37
	if obj.ConcurrentGCSyncs == 0 {
		obj.ConcurrentGCSyncs = 20
	}

which is the --concurrent-gc-syncs flag on kube-controller-manager (“The number of garbage collector workers that are allowed to sync concurrently”, cmd/kube-controller-manager/app/options/garbagecollectorcontroller.go:36).

The GC’s client QPS is doubled, because a deletion is two API calls:

go 
// cmd/kube-controller-manager/app/core.go:664
	// Increase garbage collector controller's throughput: each object deletion takes two API calls,
	// so to get |config.QPS| deletion rate we need to allow 2x more requests for this controller.
	config.QPS *= 2
	metadataClient, err := metadata.NewForConfig(config)

Those two calls are the metadata GET that establishes liveness and the DELETE that removes the object. Both go through the same config, so doubling the QPS doubles both.

The absence of a knob for the absentOwnerCache size (500) is worth noting: it is a fixed constant in graph_builder.go:165, not a config API field.

Wrapping up

The one thing to remember: the GC deletes only when every owner reference is dangling. The classification lives in classifyReferences (pkg/controller/garbagecollector/garbagecollector.go:461), and it is built on a live metadata.Interface GET plus a UID comparison — never on the informer’s cache alone.

The part people get wrong: that a “solid” owner protects the object. It does not protect it cleanly. A solid owner plus some dangling references means the GC still patches the dangling references off the object (garbagecollector.go:589), and an owner that is waiting (being deleted with foreground propagation) can end with the GC unblocking its owner references to break a mutual-delete deadlock (garbagecollector.go:606).

What to go do about it: if an object is not being cleaned up, look at its metadata.ownerReferences and check each owner by UID with kubectl get <owner> -o jsonpath='{.metadata.uid}' — a name that resolves is not enough. If an object is stuck with a foregroundDeletion finalizer, the blocker is a dependent, not the owner; find it with kubectl get <owner> -o jsonpath='{.metadata.finalizers}' and inspect the dependents’ own owner references. And if you are running a large cluster and see GC API traffic dominating the control plane, the QPS budget is --kube-api-qps doubled (cmd/kube-controller-manager/app/core.go:666) and the parallelism is --concurrent-gc-syncs (default 20).

KubernetesInternalsControllers