Switch Deployments to new hashing algo w/ collision avoidance mechanism #44774

0xmichalis · 2017-04-21T17:59:20Z

@kubernetes/sig-apps-api-reviews @kubernetes/sig-apps-pr-reviews

Deployments are updated to use (1) a more stable hashing algorithm (fnv) than the previous one (adler) and (2) a hashing collision avoidance mechanism that will ensure new rollouts will not block on hashing collisions anymore.

k8s-reviewable · 2017-04-21T18:00:28Z

This change is

janetkuo · 2017-04-21T22:33:46Z

pkg/apis/apps/v1beta1/types.go

+
+	// Monotonically increasing counter that tracks hash collisions for
+	// the Deployment. Used as a collision avoidance mechanism by the
+	// Deployment controller.


I think we need +optional here
Ref #34860, cc @mehdy

Do we also need this tag in the internal types?

janetkuo · 2017-04-24T21:56:11Z

pkg/controller/deployment/util/pod_util.go

+	// Add uniquifier in the hash if it exists.
+	if uniquifier != nil {
+		uniquifierBytes := make([]byte, 8)
+		binary.PutVarint(uniquifierBytes, *uniquifier)


It'll panic with a larger uniquifier. Use binary.LittleEndian.PutUint64 instead.

Can an int64 integer be larger than 8 bytes?

On a side note, I still need to unit test this function.

I did some experiment https://play.golang.org/p/3DKSA8wYup

Interesting. Updated and also added a simple unit test.

janetkuo · 2017-04-24T23:02:47Z

We sync status by calling calculateStatus first, which basically wipes out whatever is set in Deployment status.uniquifier

0xmichalis · 2017-04-25T06:37:42Z

We sync status by calling calculateStatus first, which basically wipes out whatever is set in Deployment status.uniquifier

Yeah, on my list to fix.

0xmichalis · 2017-04-29T09:54:26Z

@janetkuo @kubernetes/sig-apps-pr-reviews this is ready for reviews. I will follow up with unit tests for getNewReplicaSet in a different PR because I want to break down that function into pieces before unit-testing it and I don't want to make reviews harder here.

0xmichalis · 2017-05-04T09:07:28Z

@lukaszo can you also have a look?

lukaszo · 2017-05-05T21:33:50Z

pkg/apis/apps/v1beta1/types.go

+	// the Deployment. Used as a collision avoidance mechanism by the
+	// Deployment controller.
+	// +optional
+	Uniquifier *int64 `json:"uniquifier,omitempty" protobuf:"varint,8,opt,name=uniquifier"`


Why do we keep this in status? It seems little strange.
Also, who can update status? Only controller?

Putting it in status was discussed in the proposal for hash collision. We don't want users to set it or even think about it.

API server can update status as well (if we implement it).

lukaszo · 2017-05-05T21:38:43Z

pkg/apis/extensions/validation/validation.go

@@ -346,6 +346,9 @@ func ValidateDeploymentStatus(status *extensions.DeploymentStatus, fldPath *fiel
 	allErrs = append(allErrs, apivalidation.ValidateNonnegativeField(int64(status.ReadyReplicas), fldPath.Child("readyReplicas"))...)
 	allErrs = append(allErrs, apivalidation.ValidateNonnegativeField(int64(status.AvailableReplicas), fldPath.Child("availableReplicas"))...)
 	allErrs = append(allErrs, apivalidation.ValidateNonnegativeField(int64(status.UnavailableReplicas), fldPath.Child("unavailableReplicas"))...)
+	if status.Uniquifier != nil {


can you add a test for this case?

janetkuo · 2017-05-09T17:24:39Z

Sorry, didn't have time to review this further. Taking a look now.

janetkuo · 2017-05-09T20:00:49Z

test/e2e/deployment.go

+			framework.Logf("cannot get deployment %q: %v", deploymentName, err)
+			return false, nil
+		}
+		framework.Logf("deployment status: %v", d.Status)


uniquifier is a pointer and this won't print its int64 value for debugging. It's easier to debug if field names are printed too.

Use framework.Logf(spew.Sprintf("deployment status: %#v", d.Status)) to address both. You'll need to import "github.com/davecgh/go-spew/spew"

janetkuo · 2017-05-09T20:35:10Z

pkg/apis/extensions/validation/validation.go

@@ -346,6 +346,9 @@ func ValidateDeploymentStatus(status *extensions.DeploymentStatus, fldPath *fiel
 	allErrs = append(allErrs, apivalidation.ValidateNonnegativeField(int64(status.ReadyReplicas), fldPath.Child("readyReplicas"))...)
 	allErrs = append(allErrs, apivalidation.ValidateNonnegativeField(int64(status.AvailableReplicas), fldPath.Child("availableReplicas"))...)
 	allErrs = append(allErrs, apivalidation.ValidateNonnegativeField(int64(status.UnavailableReplicas), fldPath.Child("unavailableReplicas"))...)
+	if status.Uniquifier != nil {
+		allErrs = append(allErrs, apivalidation.ValidateNonnegativeField(*status.Uniquifier, fldPath.Child("uniquifier"))...)
+	}


Maybe we want something like validating that uniquifier won't decrease and will only be increased by 1 at a time in ValidateDeploymentStatusUpdate.

I don't feel strong for tightening this to check that the field increases by 1 - either way if we stabilize to a value, we won't care. Added validation that it won't decrease.

My worry is that some stale Deployment status in cache may cause uniquifier to decrease or increase too much. We need the value to be stable for idempotent RS names. This can be a follow-up.

janetkuo · 2017-05-09T21:21:58Z

test/e2e/framework/util.go

@@ -3646,7 +3648,7 @@ type updateRsFunc func(d *extensions.ReplicaSet)
 func UpdateReplicaSetWithRetries(c clientset.Interface, namespace, name string, applyUpdate updateRsFunc) (*extensions.ReplicaSet, error) {
 	var rs *extensions.ReplicaSet
 	var updateErr error
-	pollErr := wait.PollImmediate(10*time.Millisecond, 1*time.Minute, func() (bool, error) {
+	pollErr := wait.PollImmediate(1*time.Second, 1*time.Minute, func() (bool, error) {


(optional) create const for poll interval and timeout so that we have consistent value in all func UpdateXxxWithRetries

I prefer to leave this change for a follow-up

0xmichalis · 2017-05-23T15:33:51Z

I will add the appropriate labels at 12:00 CET tomorrow if there are no comments until then.

0xmichalis · 2017-05-23T16:27:37Z

@k8s-bot pull-kubernetes-e2e-gce-etcd3 test this

mikedanese · 2017-05-24T03:04:41Z

I've seen "uniquifier" referred to as "fingerprint" in other apis. Is there significance to the monotonically incrementing or is that an implementation detail? Is it guaranteed dense?

0xmichalis · 2017-05-24T08:15:10Z

I've seen "uniquifier" referred to as "fingerprint" in other apis. Is there significance to the monotonically incrementing or is that an implementation detail? Is it guaranteed dense?

There is significance in that it's incrementing so in case of a collision we are essenitally changing the algo used to compute a hash and it should be a new one. It is used as a counter of the actual collisions.

wanghaoran1988 · 2017-05-24T16:30:57Z

@k8s-bot pull-kubernetes-federation-e2e-gce test this

lavalamp · 2017-05-24T16:55:46Z

I vote for collisionCounter and against uniquifier which is super unintuitive.

revision, generation, historyIndex all are better. fingerprint and etag both seem like the wrong concept.

janetkuo · 2017-05-25T00:29:49Z

collisionCounter is fine. revision, generation, historyIndex aren't appropriate because this is not a field for version-like information but just a way to avoid name collisions when hash collision happens.

bgrant0607 · 2017-05-25T00:29:53Z

@Kargakis

PSA: I don't receive ANY github notifications now. If something needs my attention, please resort to other means, such as slack or email.

Clayton asked for my opinion via slack. I said I was ok with collisionCount(er).

The fact that it is sequential is not really material, nor strongly guaranteed, since there are scenarios where it could double count or reset, but "count" makes it easy to understand what it's doing. I oppose any name containing "index", "revision", or "generation", that might imply stronger semantics, be confused with other fields of the same names, or otherwise lead to an expectation that the value would appear in labels, annotations, or resource names.

bgrant0607 · 2017-05-25T00:31:40Z

Please remove the word "monotonically" from the API field descriptions.

bgrant0607 · 2017-05-25T00:36:26Z

Also: @ncdc suggested hashCollisions, which isn't bad, though I'm not 100% committed to the idea of keeping a hash forever. Just collisions is a bit too obscure. resourceCollisions could potentially work, but collisionCount is good enough to call it done and move on.

thockin · 2017-05-25T03:24:40Z

I'm concerned that this is kept in Status, but doesn't really pass the litmus test of "could be rebuilt by observation",

0xmichalis · 2017-05-25T08:51:14Z

I'm concerned that this is kept in Status, but doesn't really pass the litmus test of "could be rebuilt by observation",

I see your point and we could potentially annotate ReplicaSets with the collisionCounter they were created and reflect the highest adopted value back to the Deployment status but eventually this specific field doesn't need to be rebuilt, mostly due to our defaults (new Deployments in the apps group are defaulted to retaining 3 old ReplicaSets, coupled with fnv it's unlike that we will ever have a collision again).

Signed-off-by: Michail Kargakis <[email protected]>

0xmichalis · 2017-05-25T10:24:16Z

Updated to use collisionCount and fixed the API comment.

0xmichalis · 2017-05-25T11:50:01Z

Approving assuming consensus on the name. Adding lgtm based on prior lgtm.

k8s-github-robot · 2017-05-25T13:09:57Z

Automatic merge from submit-queue

@erictune

Automatic merge from submit-queue Implement Daemonset history ~Depends on #45867 (the 1st commit, ignore it when reviewing)~ (already merged) Ref kubernetes/community#527 and kubernetes/community#594 @kubernetes/sig-apps-api-reviews @kubernetes/sig-apps-pr-reviews @erictune @kow3ns @lukaszo @Kargakis --- TODOs: - [x] API changes - [x] (maybe) Remove rollback subresource if we decide to do client-side rollback - [x] deployment controller - [x] controller revision - [x] owner ref (claim & adoption) - [x] history reconstruct (put revision number, hash collision avoidance) - [x] de-dup history and relabel pods - [x] compare ds template with history - [x] hash labels (put it in controller revision, pods, and maybe deployment) - [x] clean up old history - [x] Rename status.uniquifier when we reach consensus in #44774 - [x] e2e tests - [x] unit tests - [x] daemoncontroller_test.go - [x] update_test.go - [x] ~(maybe) storage_test.go // if we do server side rollback~ kubectl part is in #46144 --- **Release note**: ```release-note ```

0xmichalis assigned janetkuo Apr 21, 2017

k8s-ci-robot added the cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. label Apr 21, 2017

k8s-github-robot added kind/api-change Categorizes issue or PR as related to adding, removing, or otherwise changing an API size/XXL Denotes a PR that changes 1000+ lines, ignoring generated files. release-note-label-needed labels Apr 21, 2017

k8s-github-robot added release-note Denotes a PR that will be considered when it comes time to generate release notes. and removed release-note-label-needed labels Apr 21, 2017

janetkuo reviewed Apr 21, 2017

View reviewed changes

0xmichalis added this to the v1.7 milestone Apr 22, 2017

0xmichalis mentioned this pull request Apr 24, 2017

Refine the Deployment proposal and switch hashing algorithm kubernetes/community#477

Merged

janetkuo reviewed Apr 24, 2017

View reviewed changes

0xmichalis mentioned this pull request Apr 25, 2017

[WIP] Change hashing algorithm in Deployments #38714

Closed

k8s-github-robot added the needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. label Apr 26, 2017

0xmichalis mentioned this pull request Apr 28, 2017

Deployments to GA kubernetes/enhancements#194

Closed

k8s-github-robot added needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. and removed needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. labels Apr 28, 2017

k8s-ci-robot added the sig/apps Categorizes an issue or PR as relevant to SIG Apps. label Apr 29, 2017

k8s-github-robot added needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. and removed needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. labels Apr 29, 2017

lukaszo reviewed May 5, 2017

View reviewed changes

janetkuo reviewed May 9, 2017

View reviewed changes

k8s-github-robot added the needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. label May 24, 2017

k8s-github-robot removed the needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. label May 24, 2017

janetkuo mentioned this pull request May 25, 2017

Implement Daemonset history #45924

Merged

16 tasks

0xmichalis added 5 commits May 25, 2017 11:17

Add collisionCount api field in DeploymentStatus

4aa8b1a

Signed-off-by: Michail Kargakis <[email protected]>

Remove obsolete deployment helpers

fcf68ba

Signed-off-by: Michail Kargakis <[email protected]>

Deep equality helper should not mutate state

aeb2d9b

Signed-off-by: Michail Kargakis <[email protected]>

Implement hash collision avoidance mechanism

4a2c5ea

Signed-off-by: Michail Kargakis <[email protected]>

Generated changes for collision count

9190a47

Signed-off-by: Michail Kargakis <[email protected]>

0xmichalis added lgtm "Looks good to me", indicates that a PR is ready to be merged. approved Indicates a PR has been approved by an approver from all required OWNERS files. labels May 25, 2017

0xmichalis mentioned this pull request May 25, 2017

Rename uniquifier field to collisionCount kubernetes/community#664

Merged

k8s-github-robot merged commit 26d7ee0 into kubernetes:master May 25, 2017

0xmichalis deleted the uniquifier branch May 25, 2017 13:41

Dyanngg mentioned this pull request Aug 30, 2022

Label Identity replication for MCS antrea-io/antrea#3664

Merged

Switch Deployments to new hashing algo w/ collision avoidance mechanism #44774

Switch Deployments to new hashing algo w/ collision avoidance mechanism #44774

Conversation

0xmichalis commented Apr 21, 2017 • edited Loading

k8s-reviewable commented Apr 21, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

0xmichalis Apr 25, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

janetkuo commented Apr 24, 2017

0xmichalis commented Apr 25, 2017

0xmichalis commented Apr 29, 2017

0xmichalis commented May 4, 2017

Choose a reason for hiding this comment

janetkuo May 9, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

janetkuo commented May 9, 2017

janetkuo May 9, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

0xmichalis May 10, 2017 • edited Loading

Choose a reason for hiding this comment

0xmichalis commented May 23, 2017

0xmichalis commented May 23, 2017

mikedanese commented May 24, 2017

0xmichalis commented May 24, 2017

wanghaoran1988 commented May 24, 2017

lavalamp commented May 24, 2017

janetkuo commented May 25, 2017

bgrant0607 commented May 25, 2017

bgrant0607 commented May 25, 2017

bgrant0607 commented May 25, 2017

thockin commented May 25, 2017

0xmichalis commented May 25, 2017

0xmichalis commented May 25, 2017

0xmichalis commented May 25, 2017

k8s-github-robot commented May 25, 2017

0xmichalis commented Apr 21, 2017 •

edited

Loading

0xmichalis Apr 25, 2017 •

edited

Loading

janetkuo May 9, 2017 •

edited

Loading

janetkuo May 9, 2017 •

edited

Loading

0xmichalis May 10, 2017 •

edited

Loading