sort identities by id/name to avoid random results #23329

nickolaev · 2023-01-25T08:16:44Z

Signed-off-by: Nikolay Nikolaev nikolay.nikolaev@isovalent.com

maintainer-s-little-helper · 2023-01-25T08:41:08Z

Commit 2151c8a68e152f7c3dd155f856f3a78a946ea56a does not contain "Signed-off-by".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

squeed · 2023-01-25T09:15:19Z

pkg/k8s/identitybackend/identity.go

+			return false
+		}
+
+		return left.Name < right.Name


TIL: identities aren't namespaced :-)

squeed

Please rebase on latest master and remove your merge commit.

sayboras · 2023-01-25T11:18:18Z

/test

Job 'Cilium-PR-K8s-1.16-kernel-4.9' hit: #22578 (98.61% similarity)

sayboras

Thanks and LGTM 💯

aditighag

Thanks for the fix! :)
While the fix looks pretty straight forward, I'm not sure if sorting is strictly required. It's not clear if the test that this PR is fixing was added with a wrong assumption. We probably don't expect a list of identities mapped to the same set of labels to be a large number, so it might be okay to sort the list. Please update the function description, it doesn't return the "first" identity found anymore.

// get returns the first identity found for the given set of labels as we might
// have duplicated entries identities for the same set of labels.

Also, please add fixes: https://github.com/cilium/cilium/pull/23064 to the commit/PR description, so we have context as to why we decided to sort the identities.

Edit: Looking closely, the identities, err := c.Store.ByIndex(byKeyIndex, key.GetKey()) is now returning a list which is supposed to be ordered, so why do we need to sort again? 😕

aditighag · 2023-01-25T18:08:15Z

/cc @alan-kut as the author of the original PR.

nickolaev · 2023-01-25T19:33:51Z

Thanks for the review. I will update accordingly.

Edit: Looking closely, the identities, err := c.Store.ByIndex(byKeyIndex, key.GetKey()) is now returning a list which is supposed to be ordered, so why do we need to sort again? 😕

From what I can track, the implementation ends up here:
https://github.com/kubernetes/client-go/blob/v0.26.0/tools/cache/thread_safe_store.go#L298

where set, err := c.index.getKeysByIndex(indexName, indexedValue) is returning a map type for set, namely https://github.com/kubernetes/apimachinery/blob/v0.26.0/pkg/util/sets/string.go#L25

And then this gets converted to the list with:

	for key := range set {
		list = append(list, c.items[key])
	}

And this is where the unpredictable order of the result comes from.
In fact, I was checking the failing unit test by printing the members of the test array where I added the slice sort, and they were typically ordered "10, 11", while when the test was failing we were getting "11,10".

IMHO this ordering is needed and provides a more stable API.

christarazi

Requesting changes just to hold this PR on potentially introducing unintended behavior. I think something that we missed during the review of #23064 is how should we handle the duplicated identity case. I don't think we've previously given it much thought, but now that we are changing the behavior, it's unclear if something depends on it.

I'd like to pull in folks who may have more context here, @cilium/sig-policy might be our best bet.

joestringer · 2023-01-25T20:38:16Z

@sayboras the original PR was not marked for backport to 1.13, so I don't think we need to backport this to 1.13 #23064

alan-kut

I agree that sorting is not required.
Sorry about the test, the test was intended to check only that the code still works when there are duplicated identities, it's not required to be deterministic which one should be returned.

However I like the sorting here. In huge majority of cases there will one or just a few returned identities here so sorting will be cheap and deterministic results are in general much better IMO

alan-kut · 2023-01-26T07:42:51Z

pkg/k8s/identitybackend/identity.go

@@ -228,6 +230,20 @@ func (c *crdBackend) get(ctx context.Context, key allocator.AllocatorKey) *v2.Ci
 		return nil
 	}



I'd suggest adding comment to tell why it is sorted here.

I have updated the function comment, is that not enough? I mean "duplicates, therefore we are selecting the 'lexicographically smalles' name" implies to certain extent we will 'sort' the results before deciding which one to return.

Cilium identity name is just a numeric. I would suggest something along these lines "In the case of duplicate entries, return an identity entry from a sorted list."

sayboras · 2023-01-30T00:42:49Z

/test

Job 'Cilium-PR-K8s-1.26-kernel-net-next' failed:

Click to show.

Test Name

K8sAgentPolicyTest Multi-node policy test with L7 policy using connectivity-check to check datapath

Failure Output

FAIL: cannot install connectivity-check

If it is a flake and a GitHub issue doesn't already exist to track it, comment /mlh new-flake Cilium-PR-K8s-1.26-kernel-net-next so I can create one.

aditighag

LGTM! I don't need to review the change again if it's just the function description that was updated.

aditighag · 2023-01-31T16:57:52Z

pkg/k8s/identitybackend/identity.go

@@ -228,6 +230,20 @@ func (c *crdBackend) get(ctx context.Context, key allocator.AllocatorKey) *v2.Ci
 		return nil
 	}



Cilium identity name is just a numeric. I would suggest something along these lines "In the case of duplicate entries, return an identity entry from a sorted list."

christarazi

Upon further review, I think the gist of the PR is fine regarding changing the semantics of handling duplicated identities. Read below.

The only callers of Get() on the backend is

pkg/allocator/allocator.go|704 col 19| GetNoCache
pkg/allocator/allocator.go|739 col 26| GetIncludeRemoteCaches
pkg/k8s/identitybackend/identity.go|262 col 11| GetIfLocked

What I see is it's ultimately checking if an identity already exists and acquire a reference on it if it does. It doesn't really matter what the actual identity value is that's assigned to the endpoint, as long as the labels association is correct. Policy selectors use labels and not the identity value, so that's why the identity value doesn't matter.

We can ultimately rely on the identity GC to remove any duplicated identities which are no longer in use (based on refcount). By sorting the list of identities to get a stable output on Get(), then this ensure we always get the same one. So in theory, the "unselected", duplicated identity will have 0 refcount and be a candidate for GC anyway.

With that said, I would +1 for changing the sort logic to handle either the timestamp or whichever identity value is less. Ideally, we don't need to do string to int conversions as we already have the creation timestamp as a time.Time.

christarazi

Holding for

With that said, I would +1 for changing the sort logic to handle either the timestamp or whichever identity value is less. Ideally, we don't need to do string to int conversions as we already have the creation timestamp as a time.Time.

nickolaev · 2023-02-01T21:42:35Z

Holding for

With that said, I would +1 for changing the sort logic to handle either the timestamp or whichever identity value is less. Ideally, we don't need to do string to int conversions as we already have the creation timestamp as a time.Time.

OK but - using the timestamps make the test indeterministic again, as there are no guaranties of the order of creation of the test entries.
I ma not sure what "indentity value" is.

I am updating the PR with the latest comment suggested and will leave it as it is. If someone has a better idea of how this sorting should work, please take over.

christarazi · 2023-02-01T22:55:33Z

Holding for

With that said, I would +1 for changing the sort logic to handle either the timestamp or whichever identity value is less. Ideally, we don't need to do string to int conversions as we already have the creation timestamp as a time.Time.

OK but - using the timestamps make the test indeterministic again, as there are no guaranties of the order of creation of the test entries. I ma not sure what "indentity value" is.

Why would they become nondeterministic? If they are initialized like

identities: []v2.CiliumIdentity{
	createCiliumIdentity(10, duplicateMap1),
	createCiliumIdentity(11, duplicateMap1),
},

then we are instantiating a Go slice which is ordered. We just need to ensure that createCiliumIdentity() sets the creationTimestamp to time.Now() and it should work.

aditighag · 2023-02-02T17:09:30Z

@nickolaev Please check the go linter warning. Travis failure is related.

Why would they become nondeterministic? If they are initialized like
identities: []v2.CiliumIdentity{
	createCiliumIdentity(10, duplicateMap1),
	createCiliumIdentity(11, duplicateMap1),
},
then we are instantiating a Go slice which is ordered. We just need to ensure that createCiliumIdentity() sets the creationTimestamp to time.Now() and it should work.

@christarazi I'm not sure I follow your proposal. In general, we don't seem to set the creationTimestamp in the code, so how could the sorting logic use the field for comparison? Based on your suggestion above, it seems like you are suggesting that we only set it for tests? But that's not ideal.

pkg/k8s/identitybackend/identity.go

pkg/k8s/identitybackend/identity_test.go

christarazi · 2023-02-02T18:06:16Z

@christarazi I'm not sure I follow your proposal. In general, we don't seem to set the creationTimestamp in the code, so how could the sorting logic use the field for comparison? Based on your suggestion above, it seems like you are suggesting that we only set it for tests? But that's not ideal.

Well, we only need to set the timestamp in the tests because we can't rely on K8s doing that for us. In non-test code, K8s will definitely set the creationTimestamp so we can rely on it.

aditighag · 2023-02-02T18:43:31Z

@christarazi I'm not sure I follow your proposal. In general, we don't seem to set the creationTimestamp in the code, so how could the sorting logic use the field for comparison? Based on your suggestion above, it seems like you are suggesting that we only set it for tests? But that's not ideal.

Well, we only need to set the timestamp in the tests because we can't rely on K8s doing that for us. In non-test code, K8s will definitely set the creationTimestamp so we can rely on it.

Thanks for the context. If it's guaranteed to be always set by the system, then yes, it makes sense to use the timestamp to sort the identities.

christarazi · 2023-02-04T00:04:02Z

/test

Edit: oops, accidentally closed.

christarazi · 2023-02-04T00:04:34Z

/test

Job 'Cilium-PR-K8s-1.24-kernel-5.4' failed:

Click to show.

Test Name

K8sDatapathConfig Host firewall With VXLAN

Failure Output

FAIL: Failed to reach 10.0.0.50:80 from testclient-host-5xdvm

If it is a flake and a GitHub issue doesn't already exist to track it, comment /mlh new-flake Cilium-PR-K8s-1.24-kernel-5.4 so I can create one.

Fixes cilium#23314 Signed-off-by: Nikolay Nikolaev <nikolay.nikolaev@isovalent.com>

sayboras · 2023-02-05T07:31:18Z

/test

nickolaev requested a review from a team as a code owner January 25, 2023 08:16

nickolaev requested a review from squeed January 25, 2023 08:16

maintainer-s-little-helper bot added the dont-merge/needs-release-note-label The author needs to describe the release impact of these changes. label Jan 25, 2023

github-actions bot added the kind/community-contribution This was a contribution made by a community member. label Jan 25, 2023

maintainer-s-little-helper bot added the dont-merge/needs-sign-off The author needs to add signoff to their commits before merge. label Jan 25, 2023

squeed reviewed Jan 25, 2023

View reviewed changes

pkg/k8s/identitybackend/identity.go Outdated

return false

}

return left.Name < right.Name

Copy link

Contributor

squeed Jan 25, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

TIL: identities aren't namespaced :-)

squeed approved these changes Jan 25, 2023

View reviewed changes

squeed removed the kind/community-contribution This was a contribution made by a community member. label Jan 25, 2023

squeed requested changes Jan 25, 2023

View reviewed changes

nickolaev force-pushed the fix_23314 branch from 2151c8a to 3012f99 Compare January 25, 2023 09:23

maintainer-s-little-helper bot removed the dont-merge/needs-sign-off The author needs to add signoff to their commits before merge. label Jan 25, 2023

tklauser added the release-note/misc This PR makes changes that have no direct user impact. label Jan 25, 2023

maintainer-s-little-helper bot removed the dont-merge/needs-release-note-label The author needs to describe the release impact of these changes. label Jan 25, 2023

sayboras approved these changes Jan 25, 2023

View reviewed changes

squeed approved these changes Jan 25, 2023

View reviewed changes

sayboras added the needs-backport/1.13 This PR / issue needs backporting to the v1.13 branch label Jan 25, 2023

maintainer-s-little-helper bot mentioned this pull request Jan 25, 2023

CI: K8sDatapathConfig Host firewall With VXLAN #22578

Closed

sayboras mentioned this pull request Jan 25, 2023

contrib: Add devcontainer configuration #22856

Merged

aditighag reviewed Jan 25, 2023

View reviewed changes

nickolaev force-pushed the fix_23314 branch from 3012f99 to 4ef23d3 Compare January 25, 2023 19:44

christarazi requested changes Jan 25, 2023

View reviewed changes

joestringer removed the needs-backport/1.13 This PR / issue needs backporting to the v1.13 branch label Jan 25, 2023

alan-kut approved these changes Jan 26, 2023

View reviewed changes

joestringer mentioned this pull request Jan 26, 2023

CI: TestGetIdentity/Duplicated_identity failure #23314

Closed

aditighag requested a review from christarazi January 31, 2023 16:49

aditighag approved these changes Jan 31, 2023

View reviewed changes

christarazi approved these changes Jan 31, 2023

View reviewed changes

christarazi requested changes Jan 31, 2023

View reviewed changes

nickolaev force-pushed the fix_23314 branch from 4ef23d3 to cf71283 Compare February 1, 2023 21:44

nickolaev force-pushed the fix_23314 branch from cf71283 to 036eee6 Compare February 2, 2023 05:07

christarazi reviewed Feb 2, 2023

View reviewed changes

pkg/k8s/identitybackend/identity.go Outdated Show resolved Hide resolved

christarazi reviewed Feb 2, 2023

View reviewed changes

pkg/k8s/identitybackend/identity_test.go Outdated Show resolved Hide resolved

nickolaev force-pushed the fix_23314 branch from 036eee6 to c27097c Compare February 3, 2023 13:44

nickolaev requested a review from christarazi February 3, 2023 21:23

christarazi closed this Feb 4, 2023

christarazi reopened this Feb 4, 2023

christarazi approved these changes Feb 4, 2023

View reviewed changes

github-actions bot added the kind/community-contribution This was a contribution made by a community member. label Feb 4, 2023

sort identities by id/name to avoid random results

a009615

Fixes cilium#23314 Signed-off-by: Nikolay Nikolaev <nikolay.nikolaev@isovalent.com>

nickolaev force-pushed the fix_23314 branch from c27097c to a009615 Compare February 5, 2023 07:09

aanm approved these changes Feb 6, 2023

View reviewed changes

aanm merged commit 84e9641 into cilium:master Feb 6, 2023

nickolaev deleted the fix_23314 branch February 7, 2023 15:42

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

sort identities by id/name to avoid random results #23329

sort identities by id/name to avoid random results #23329

nickolaev commented Jan 25, 2023 •

edited

maintainer-s-little-helper bot commented Jan 25, 2023

squeed Jan 25, 2023

squeed left a comment

sayboras commented Jan 25, 2023 •

edited by maintainer-s-little-helper bot

sayboras left a comment

aditighag left a comment •

edited

aditighag commented Jan 25, 2023

nickolaev commented Jan 25, 2023

christarazi left a comment •

edited

joestringer commented Jan 25, 2023

alan-kut left a comment

alan-kut Jan 26, 2023

nickolaev Jan 27, 2023

aditighag Jan 31, 2023

sayboras commented Jan 30, 2023 •

edited by maintainer-s-little-helper bot

Test Name

Failure Output

aditighag left a comment

aditighag Jan 31, 2023

christarazi left a comment

christarazi left a comment

nickolaev commented Feb 1, 2023

christarazi commented Feb 1, 2023

aditighag commented Feb 2, 2023

christarazi commented Feb 2, 2023

aditighag commented Feb 2, 2023

christarazi commented Feb 4, 2023 •

edited

christarazi commented Feb 4, 2023 •

edited by maintainer-s-little-helper bot

Test Name

Failure Output

sayboras commented Feb 5, 2023

		@@ -228,6 +230,20 @@ func (c crdBackend) get(ctx context.Context, key allocator.AllocatorKey) v2.Ci
		return nil
		}

sort identities by id/name to avoid random results #23329

sort identities by id/name to avoid random results #23329

Conversation

nickolaev commented Jan 25, 2023 • edited

maintainer-s-little-helper bot commented Jan 25, 2023

squeed Jan 25, 2023

Choose a reason for hiding this comment

squeed left a comment

Choose a reason for hiding this comment

sayboras commented Jan 25, 2023 • edited by maintainer-s-little-helper bot

sayboras left a comment

Choose a reason for hiding this comment

aditighag left a comment • edited

Choose a reason for hiding this comment

aditighag commented Jan 25, 2023

nickolaev commented Jan 25, 2023

christarazi left a comment • edited

Choose a reason for hiding this comment

joestringer commented Jan 25, 2023

alan-kut left a comment

Choose a reason for hiding this comment

alan-kut Jan 26, 2023

Choose a reason for hiding this comment

nickolaev Jan 27, 2023

Choose a reason for hiding this comment

aditighag Jan 31, 2023

Choose a reason for hiding this comment

sayboras commented Jan 30, 2023 • edited by maintainer-s-little-helper bot

Test Name

Failure Output

aditighag left a comment

Choose a reason for hiding this comment

aditighag Jan 31, 2023

Choose a reason for hiding this comment

christarazi left a comment

Choose a reason for hiding this comment

christarazi left a comment

Choose a reason for hiding this comment

nickolaev commented Feb 1, 2023

christarazi commented Feb 1, 2023

aditighag commented Feb 2, 2023

christarazi commented Feb 2, 2023

aditighag commented Feb 2, 2023

christarazi commented Feb 4, 2023 • edited

christarazi commented Feb 4, 2023 • edited by maintainer-s-little-helper bot

Test Name

Failure Output

sayboras commented Feb 5, 2023

nickolaev commented Jan 25, 2023 •

edited

sayboras commented Jan 25, 2023 •

edited by maintainer-s-little-helper bot

aditighag left a comment •

edited

christarazi left a comment •

edited

sayboras commented Jan 30, 2023 •

edited by maintainer-s-little-helper bot

christarazi commented Feb 4, 2023 •

edited

christarazi commented Feb 4, 2023 •

edited by maintainer-s-little-helper bot