Opensource internals

Not a Random Suffix: The Deployment Hash and Its Collision Counter

13 min read Jay Hubbert

A Deployment's ReplicaSet name ends in an FNV-32a hash of the pod template, salted by a persisted collisionCount in status so the derived name stays deterministic across restarts.

TL;DR: Every ReplicaSet a Deployment creates is named <deployment-name>-<hash>, and the hash is FNV-32a over the pod template — about 4.3 billion possible values, so collisions are a matter of statistics, not of if. The interesting part is what happens on a collision: the controller does not generate a random suffix. It increments a persisted status.collisionCount on the Deployment and rehashes. Because the counter lives in the Deployment’s status, the name stays a pure function of (template, counter) and is identical across controller restarts, resyncs and multiple replicas of the controller manager.

kubectl get rs shows names like nginx-7d9f4b6c8 or coredns-5d78c9869. The suffix looks like a random string. It is not. It is a hash, and the hash is load-bearing in a way that is easy to miss: the Deployment controller uses it to decide whether the ReplicaSet it wants already exists, and the pod-template-hash label it puts on the pod template is how the ReplicaSet controller decides which pods belong to which ReplicaSet.

Get that name wrong and the controller creates duplicate ReplicaSets, which means duplicate pods, which means a rollout that never converges.

The hash

It is short, and it is FNV-32a over the whole pod template:

go 
// pkg/controller/controller_utils.go:1402
func ComputeHash(template *v1.PodTemplateSpec, collisionCount *int32) string {
	podTemplateSpecHasher := fnv.New32a()
	hashutil.DeepHashObject(podTemplateSpecHasher, *template)

	// Add collisionCount in the hash if it exists.
	if collisionCount != nil {
		collisionCountBytes := make([]byte, 8)
		binary.LittleEndian.PutUint32(collisionCountBytes, uint32(*collisionCount))
		podTemplateSpecHasher.Write(collisionCountBytes)
	}

	return rand.SafeEncodeString(fmt.Sprint(podTemplateSpecHasher.Sum32()))
}

Three details:

  1. fnv.New32a() — FNV-1a, 32 bits. The space is 2^32 ≈ 4.29 × 10^9. With a few thousand distinct pod templates in a cluster, the birthday probability is around 10^-3 per 1000 templates — small, but a Deployment that is recreated from a template farm (one template per tenant, say) can walk into it.

  2. hashutil.DeepHashObject is not json.Marshal. It writes a spew dump of the object into the hasher, with a config that is explicitly frozen:

go 
// vendor/k8s.io/utils/dump/dump.go:30
// The config MUST NOT be changed because that could change the result of a hash operation
var prettyPrintConfigForHash = &spew.ConfigState{
	Indent:                  " ",
	SortKeys:                true,
	DisableMethods:          true,
	SpewKeys:                true,
	DisablePointerAddresses: true,
	DisableCapacities:       true,
}

and the function that feeds it to the hasher:

go 
// vendor/k8s.io/utils/dump/dump.go:46
// ForHash keeps the original Spew.Sprintf format to ensure the same checksum
func ForHash(a interface{}) string {
	return prettyPrintConfigForHash.Sprintf("%#v", a)
}

SortKeys: true is what makes the hash stable across map iteration order. DisablePointerAddresses is what makes it stable across pointer identity. DisableMethods means it hashes the structure, not a String() method. And the “MUST NOT be changed” comment is a warning that this is a persistence format: change the spew config and every existing object’s pod-template-hash label becomes a lie, which means every Deployment in the cluster suddenly has a “new” template and rolls all its pods.

  1. The collision counter is mixed in after the template, as 8 little-endian bytes. It is nil for a fresh Deployment, so the hash of the very first template is a pure function of the template alone.

The encoding

The raw hash is a uint32. It is printed in decimal and then run through SafeEncodeString, which is not a base-N encoder but a per-character substitution:

go 
// staging/src/k8s.io/apimachinery/pkg/util/rand/rand.go:119
// SafeEncodeString encodes s using the same characters as rand.String. This reduces the chances of bad words and
// ensures that strings generated from hash functions appear consistent throughout the API.
func SafeEncodeString(s string) string {
	r := make([]byte, len(s))
	for i, b := range []rune(s) {
		r[i] = alphanums[(int(b) % len(alphanums))]
	}
	return string(r)
}

and the alphabet it substitutes into has vowels removed on purpose:

go 
// staging/src/k8s.io/apimachinery/pkg/util/rand/rand.go:80
const (
	// We omit vowels from the set of available characters to reduce the chances
	// of "bad words" being formed.
	alphanums = "bcdfghjklmnpqrstvwxz2456789"
	// No. of bits required to index into alphanums string.
	alphanumsIdxBits = 5
	// Mask used to extract last alphanumsIdxBits of an int.
	alphanumsIdxMask = 1<<alphanumsIdxBits - 1
	// No. of random letters we can extract from a single int63.
	maxAlphanumsPerInt = 63 / alphanumsIdxBits
)

Twenty-seven characters, no a, e, i, o, u, y, and no 0, 1 or 3. The rationale is stated plainly in the comment: the hash ends up in object names and in kubectl output, and a name that spells something unfortunate is a support ticket. It also cannot start with a digit, because the decimal digits of the hash are what get substituted, and they map as 0→b, 1→c, 2→d, 3→f, 4→4, 5→5, 6→6, 7→7, 8→8, 9→9 — so the only characters ever fed to SafeEncodeString are 0–9, and the substitution is injective on those ten characters. The encoding therefore never introduces a collision that the hash did not already have, and the resulting suffix is one to ten characters long depending on the magnitude of the hash.

The name

The hash is not the name. The name is the hash plus a prefix:

go 
// pkg/controller/deployment/sync.go:196
	// new ReplicaSet does not exist, create one.
	newRSTemplate := *d.Spec.Template.DeepCopy()
	podTemplateSpecHash := controller.ComputeHash(&newRSTemplate, d.Status.CollisionCount)
	newRSTemplate.Labels = labelsutil.CloneAndAddLabel(d.Spec.Template.Labels, apps.DefaultDeploymentUniqueLabelKey, podTemplateSpecHash)
	// Add podTemplateHash label to selector.
	newRSSelector := labelsutil.CloneSelectorAndAddLabel(d.Spec.Selector, apps.DefaultDeploymentUniqueLabelKey, podTemplateSpecHash)

	// Create new ReplicaSet
	newRS := apps.ReplicaSet{
		ObjectMeta: metav1.ObjectMeta{
			// Make the name deterministic, to ensure idempotence
			Name:            generateReplicaSetName(d.Name, podTemplateSpecHash),
			Namespace:       d.Namespace,
			OwnerReferences: []metav1.OwnerReference{*metav1.NewControllerRef(d, controllerKind)},
			Labels:          newRSTemplate.Labels,
		},

The comment is the requirement: “Make the name deterministic, to ensure idempotence.” The controller may run several times, from several replicas of kube-controller-manager, and must always converge on the same name.

The prefix is truncated to fit, because the name has to be a DNS-1123 subdomain:

go 
// pkg/controller/deployment/sync.go:559
func generateReplicaSetName(deploymentName, podTemplateSpecHash string) string {
	maxDeploymentNameLength := validation.DNS1123SubdomainMaxLength - len(replicaSetNameSeparator) - len(podTemplateSpecHash)

	if len(deploymentName) > maxDeploymentNameLength && maxDeploymentNameLength > 0 {
		return deploymentName[:maxDeploymentNameLength] + replicaSetNameSeparator + podTemplateSpecHash
	}

	return deploymentName + replicaSetNameSeparator + podTemplateSpecHash
}

DNS1123SubdomainMaxLength is 253, the separator is -, and the hash is up to ten characters. A Deployment with a 250-character name gets its prefix cut to 242 characters so the whole thing still fits.

What happens on a collision

The collision is discovered the only way it can be: the Create call comes back AlreadyExists.

go 
// pkg/controller/deployment/sync.go:231
	alreadyExists := false
	createdRS, err := dc.client.AppsV1().ReplicaSets(d.Namespace).Create(ctx, &newRS, metav1.CreateOptions{})
	switch {
	// We may end up hitting this due to a slow cache or a fast resync of the Deployment.
	case errors.IsAlreadyExists(err):
		alreadyExists = true

AlreadyExists is ambiguous. It might mean “this exact ReplicaSet is already here, because you are re-syncing” — the normal, boring case — or it might mean “there is a different ReplicaSet with this name, because your hash collided with someone else’s”. The controller distinguishes the two by comparing the pod templates, ignoring the hash label itself:

go 
// pkg/controller/deployment/util/deployment_util.go:610
// EqualIgnoreHash returns true if two given podTemplateSpec are equal, ignoring the diff in value of Labels[pod-template-hash]
// We ignore pod-template-hash because:
//  1. The hash result would be different upon podTemplateSpec API changes
//     (e.g. the addition of a new field will cause the hash code to change)
//  2. The deployment template won't have hash labels
func EqualIgnoreHash(template1, template2 *v1.PodTemplateSpec) bool {
	t1Copy := template1.DeepCopy()
	t2Copy := template2.DeepCopy()
	// Remove hash labels from template.Labels before comparing
	delete(t1Copy.Labels, apps.DefaultDeploymentUniqueLabelKey)
	delete(t2Copy.Labels, apps.DefaultDeploymentUniqueLabelKey)
	return apiequality.Semantic.DeepEqual(t1Copy, t2Copy)
}

Semantic.DeepEqual is used rather than reflect.DeepEqual so that nil and empty slices, and resource.Quantity values with different internal representations but the same magnitude, compare equal.

If the templates are equal, this is just a re-sync and the existing ReplicaSet is adopted. If they are not equal, it is a genuine hash collision — and here is the interesting part:

go 
// pkg/controller/deployment/sync.go:255
		// Matching ReplicaSet is not equal - increment the collisionCount in the DeploymentStatus
		// and requeue the Deployment.
		if d.Status.CollisionCount == nil {
			d.Status.CollisionCount = new(int32)
		}
		preCollisionCount := *d.Status.CollisionCount
		*d.Status.CollisionCount++
		// Update the collisionCount for the Deployment and let it requeue by returning the original
		// error.
		_, dErr := dc.client.AppsV1().Deployments(d.Namespace).UpdateStatus(ctx, d, metav1.UpdateOptions{})
		if dErr == nil {
			logger.V(2).Info("Found a hash collision for deployment - bumping collisionCount to resolve it", "deployment", klog.KObj(d), "oldCollisionCount", preCollisionCount, "newCollisionCount", *d.Status.CollisionCount)
		}
		return nil, err

The counter is bumped in the Deployment’s status and written with UpdateStatus. This is the crux of the design. The obvious alternative — a random suffix, or a timestamp — would break idempotence: two controllers racing on the same Deployment would generate two different names and create two ReplicaSets. A persisted counter makes the name a pure function of the inputs, so every controller computes the same next name.

The counter is part of the API, documented as such:

go 
// staging/src/k8s.io/api/apps/v1/types.go:574
	// collisionCount is the number of hash collisions for the Deployment. The Deployment controller uses this
	// field as a collision avoidance mechanism when it needs to create the name for the newest ReplicaSet.
	// +optional
	CollisionCount *int32 `json:"collisionCount,omitempty" protobuf:"varint,8,opt,name=collisionCount"`

Same field, same purpose, on StatefulSet (line 330) and DaemonSet (line 777).

The ControllerRevision variant

StatefulSet and DaemonSet do not create ReplicaSets, so they roll out via ControllerRevision objects — immutable snapshots of the pod template kept for rollback. The hash is computed differently: plain FNV-1 (not FNV-1a), and the collision counter is mixed in as a decimal string:

go 
// pkg/controller/history/controller_history.go:132
// HashControllerRevision hashes the contents of revision's Data using FNV hashing. If probe is not nil, the byte value
// of probe is added written to the hash as well. The returned hash will be a safe encoded string to avoid bad words.
func HashControllerRevision(revision *apps.ControllerRevision, probe *int32) string {
	hf := fnv.New32()
	if len(revision.Data.Raw) > 0 {
		hf.Write(revision.Data.Raw)
	}
	if revision.Data.Object != nil {
		hashutil.DeepHashObject(hf, revision.Data.Object)
	}
	if probe != nil {
		hf.Write([]byte(strconv.FormatInt(int64(*probe), 10)))
	}
	return rand.SafeEncodeString(fmt.Sprint(hf.Sum32()))
}

The difference in the collision-count encoding is not cosmetic. ComputeHash writes the counter as 8 fixed-width little-endian bytes; this writes strconv.FormatInt of the counter. With a fixed-width encoding, a counter of 1 and a counter of 256 produce different byte strings; with the decimal string, "1" followed by "256" is b"1256" and a counter of 12 followed by "56" is also b"1256" — a genuine ambiguity, but only reachable by concatenating two different fields, and in practice the revision payload is either raw bytes or an object, never both. The point of mixing the counter in at all is the same as before: it must change the hash.

Creation is a retry loop rather than a single call, and the counter is bumped in memory on AlreadyExists:

go 
// pkg/controller/history/controller_history.go:293
func (rh *realHistory) CreateControllerRevision(parent metav1.Object, revision *apps.ControllerRevision, collisionCount *int32) (*apps.ControllerRevision, error) {
	if collisionCount == nil {
		return nil, fmt.Errorf("collisionCount should not be nil")
	}

	// Clone the input
	clone := revision.DeepCopy()

	// Continue to attempt to create the revision updating the name with a new hash on each iteration
	for {
		hash := HashControllerRevision(revision, collisionCount)
		// Update the revisions name
		clone.Name = ControllerRevisionName(parent.GetName(), hash)
		ns := parent.GetNamespace()
		created, err := rh.client.AppsV1().ControllerRevisions(ns).Create(context.TODO(), clone, metav1.CreateOptions{})
		if errors.IsAlreadyExists(err) {
			exists, err := rh.client.AppsV1().ControllerRevisions(ns).Get(context.TODO(), clone.Name, metav1.GetOptions{})
			if err != nil {
				return nil, err
			}
			if bytes.Equal(exists.Data.Raw, clone.Data.Raw) {
				return exists, nil
			}
			*collisionCount++
			continue
		}
		return created, err
	}
}

Note the difference in style from the Deployment: the Deployment bumps the counter and persists it to the API and returns, letting the informer wake it up again. The history controller bumps it in memory and loops, because it holds the pointer to the parent’s status object. The DaemonSet does something in between, and it is the one with the interesting guard.

The DaemonSet’s stale-counter guard

The DaemonSet creates ControllerRevisions with the Deployment’s ComputeHash, and it hits AlreadyExists in exactly the same way:

go 
// pkg/controller/daemon/update.go:564
		// Handle name collisions between different history
		// Get the latest DaemonSet from the API server to make sure collision count is only increased when necessary
		currDS, getErr := dsc.kubeClient.AppsV1().DaemonSets(ds.Namespace).Get(ctx, ds.Name, metav1.GetOptions{})
		if getErr != nil {
			return nil, getErr
		}
		// If the collision count used to compute hash was in fact stale, there's no need to bump collision count; retry again
		if !reflect.DeepEqual(currDS.Status.CollisionCount, ds.Status.CollisionCount) {
			return nil, fmt.Errorf("found a stale collision count (%d, expected %d) of DaemonSet %q while processing; will retry until it is updated", ptr.Deref(ds.Status.CollisionCount, 0), ptr.Deref(currDS.Status.CollisionCount, 0), ds.Name)
		}

This is a guard against bumping the counter for no reason. If the counter the DaemonSet controller was working with is already stale — someone else bumped it — then the collision it detected has already been resolved by the other bump. Bumping again would skip a hash value and, worse, would race another writer on the status.

The DaemonSet therefore does a live GET of its own object before touching the counter, and refuses to bump if the value it is holding differs from the one on the server. It returns an error and lets the informer retry with a fresh copy.

The Deployment controller does not have this guard — it bumps the counter unconditionally when it detects a collision — which is a small inconsistency between the two controllers that is worth knowing about if you are debugging a DaemonSet that seems to bump its counter more than expected.

Why not a random suffix?

Because a random suffix breaks the property the controller depends on: the ReplicaSet name must be derivable. Every sync recomputes it. The Deployment controller does not look for “the ReplicaSet I created last time”; it computes the name and asks the API server. If the name were random, the controller would need to remember it somewhere, and the only somewhere is the Deployment’s status — at which point you have reinvented the collision counter, with more machinery and less determinism.

The counter approach also degrades gracefully. It is a *int32 in the status. It is zero for every object that has never collided. It is bumped at most once per genuine collision, which for a well-behaved cluster is never.

The cost is a 32-bit hash. A 64-bit hash would make collisions essentially impossible, but it would also change every existing pod-template-hash label in every cluster, which is exactly the kind of “harmless” change that rewrites the world. 32 bits it is, and the counter handles the tail.

Wrapping up

The one thing to remember: the Deployment’s ReplicaSet suffix is rand.SafeEncodeString(fmt.Sprint(fnv32a(template))) — FNV-32a over the spew dump of the pod template, printed in decimal and character-substituted into the vowel-free alphabet bcdfghjklmnpqrstvwxz2456789 (staging/src/k8s.io/apimachinery/pkg/util/rand/rand.go:83). It is a deterministic function, not a random string, and the controller relies on that (pkg/controller/deployment/sync.go:207).

The part people get wrong: the collision resolution. It is not a random suffix and not a timestamp. The controller increments status.collisionCount on the Deployment (pkg/controller/deployment/sync.go:255) and rehashes, so the name stays a pure function of (template, counter). And the bump is only triggered by a genuine collision — AlreadyExists plus a template that is not EqualIgnoreHash-equal (pkg/controller/deployment/util/deployment_util.go:610). A duplicate ReplicaSet with the same template is a re-sync, not a collision.

What to go do about it: if a Deployment seems to be creating duplicate ReplicaSets, look at kubectl get deploy <name> -o jsonpath='{.status.collisionCount}' — a non-zero value means a real hash collision happened and the controller worked around it. If the pod-template-hash label changes for every pod in the cluster after an upgrade, suspect the spew hashing config in vendor/k8s.io/utils/dump/dump.go:30 — it is explicitly frozen because changing it invalidates every stored hash. And if you write your own controller that names objects after a hash, put the salt in the object’s status, not in memory: StatefulSet and DaemonSet use the same status.collisionCount field, and the DaemonSet controller re-reads the object before bumping it precisely to avoid clobbering a concurrent bump (pkg/controller/daemon/update.go:566).

KubernetesInternalsControllers