Add a fast path for adding new node in node_authorizer #87688

mborsz · 2020-01-30T13:34:43Z

What type of PR is this?
/kind feature

What this PR does / why we need it:
This is a performance improvement for scheduling new pod with secrets, configmaps and other resources.
Without this patch, each pod using secret X will trigger index recomputation of size O(pods using that secret), so in clusters with highly replicated secrets this can be a huge cost.
With this patch, each such pod will be handled in O(1) time.

We saw that this was impacting scalability tests when we created pods with secrets with high rate (100 pods/s), creating a O(minute) delay between the time when pod was scheduled on some node and time when node was able to fetch associated secret.

Similar improvement can be implemented for removing secrets, but this will require introducing reference counting, so maybe in future.

This seems to improve WriteIndexMaintenance benchmark:

Before:
BenchmarkWriteIndexMaintenance-12    	    1034	   1157922 ns/op	    1906 B/op	      41 allocs/op
After:
BenchmarkWriteIndexMaintenance-12    	    4891	    239821 ns/op	    1572 B/op	      37 allocs/op

This also changes the way the index is used in node_authorizer: before this patch, even if destinationEdgeIndex is present for given node, but there is no path between two nodes, DFS will be triggered. This can be simplified, as if destinationEdgeIndex is present, it must be complete so we can easily fail if destinationEdgeIndex is present, but destination node is not there.

Which issue(s) this PR fixes:

Fixes #

Special notes for your reviewer:

Does this PR introduce a user-facing change?:

NONE

Additional documentation e.g., KEPs (Kubernetes Enhancement Proposals), usage docs, etc.:

/assign @wojtek-t
/assign @liggitt

liggitt · 2020-01-30T15:07:25Z

While reviewing this, I found an existing bug in the index maintenance code. Opened #87693 to resolve that first (required since this PR makes the index authoritative)

plugin/pkg/auth/authorizer/node/node_authorizer.go

liggitt · 2020-01-30T15:30:18Z

go ahead and squash, then lgtm pending #87693

mborsz · 2020-01-30T15:34:33Z

Squashed, thanks!

liggitt · 2020-01-30T16:50:40Z

opened WIP #87696 that builds on this and switches to refcount and adds a fastpath for edge removal.

benchmark                             old ns/op     new ns/op     delta
BenchmarkWriteIndexMaintenance-12     1935450       8629          -99.55%

benchmark                             old allocs     new allocs     delta
BenchmarkWriteIndexMaintenance-12     44             37             -15.91%

benchmark                             old bytes     new bytes     delta
BenchmarkWriteIndexMaintenance-12     2141          1521          -28.96%

liggitt · 2020-01-31T06:33:45Z

/retest
/test pull-kubernetes-bazel-test

liggitt · 2020-01-31T06:50:06Z

plugin/pkg/auth/authorizer/node/node_authorizer.go

@@ -302,8 +302,11 @@ func (r *NodeAuthorizer) hasPathFrom(nodeName string, startingType vertexType, s
 	}

 	// Fast check to see if we know of a destination edge
-	if r.graph.destinationEdgeIndex[startingVertex.ID()].has(nodeVertex.ID()) {
-		return true, nil
+	if index := r.graph.destinationEdgeIndex[startingVertex.ID()]; index != nil {


This will only hold items that had a destination edge and were added to the index. AddVolumeAttachment, SetNodeConfigMap, and AddPod all have places where they add destination edges and do not update the index.

AddPV explicitly doesn't have the ability to add a destination edge:

// since we don't know the other end of the pvc -> pod -> node chain (or it may not even exist yet), we can't decorate these edges with kubernetes node info

Unless all added edges are indexed, we can't make the presence of this index short-circuit a DFS fallback

The fact that unit tests are passing with this change as well means that not all relationships are well-exercised in the presence of an index. For example, create enough node{1,2,3,...}<-pod->configmap1 relationships that configmap1 has an index, then create a nodeN<->configmap1 relationship with SetNodeConfigMap and verify authorizer.hasPathFrom finds a path from the node to the configmap:

diff --git a/plugin/pkg/auth/authorizer/node/graph_test.go b/plugin/pkg/auth/authorizer/node/graph_test.go index a87d6c0a7b8..a3a16064196 100644 --- a/plugin/pkg/auth/authorizer/node/graph_test.go +++ b/plugin/pkg/auth/authorizer/node/graph_test.go @@ -348,20 +348,28 @@ func TestIndex(t *testing.T) { g.SetNodeConfigMap("node1", "cm1", "ns") g.SetNodeConfigMap("node2", "cm1", "ns") g.SetNodeConfigMap("node3", "cm1", "ns") + g.SetNodeConfigMap("node4", "cm1", "ns") + if ok, err := a.hasPathFrom("node1", configMapVertexType, "ns", "cm1"); err != nil || !ok { + t.Errorf("expected path from %s to cm1, got %v, %v", "node1", ok, err) + } + if ok, err := a.hasPathFrom("node4", configMapVertexType, "ns", "cm1"); err != nil || !ok { + t.Errorf("expected path from %s to cm1, got %v, %v", "node4", ok, err) + } expectGraph(map[string][]string{ "node:node1": {}, "node:node2": {}, "node:node3": {}, + "node:node4": {}, "pod:ns/pod2": {"node:node2"}, "pod:ns/pod3": {"node:node3"}, "pod:ns/pod4": {"node:node1"}, - "configmap:ns/cm1": {"node:node1", "node:node2", "node:node3", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, + "configmap:ns/cm1": {"node:node1", "node:node2", "node:node3", "node:node4", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, "configmap:ns/cm2": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, "configmap:ns/cm3": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, "serviceAccount:ns/sa1": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, }) expectIndex(map[string][]string{ - "configmap:ns/cm1": {"node:node1", "node:node2", "node:node3"}, + "configmap:ns/cm1": {"node:node1", "node:node2", "node:node3", "node:node4"}, "configmap:ns/cm2": {"node:node1", "node:node2", "node:node3"}, "configmap:ns/cm3": {"node:node1", "node:node2", "node:node3"}, "serviceAccount:ns/sa1": {"node:node1", "node:node2", "node:node3"}, @@ -373,16 +381,17 @@ func TestIndex(t *testing.T) { "node:node1": {}, "node:node2": {}, "node:node3": {}, + "node:node4": {}, "pod:ns/pod2": {"node:node2"}, "pod:ns/pod3": {"node:node3"}, "pod:ns/pod4": {"node:node1"}, - "configmap:ns/cm1": {"node:node2", "node:node3", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, + "configmap:ns/cm1": {"node:node2", "node:node3", "node:node4", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, "configmap:ns/cm2": {"node:node1", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, "configmap:ns/cm3": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, "serviceAccount:ns/sa1": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, }) expectIndex(map[string][]string{ - "configmap:ns/cm1": {"node:node1", "node:node2", "node:node3"}, + "configmap:ns/cm1": {"node:node1", "node:node2", "node:node3", "node:node4"}, "configmap:ns/cm2": {"node:node1", "node:node2", "node:node3"}, "configmap:ns/cm3": {"node:node1", "node:node2", "node:node3"}, "serviceAccount:ns/sa1": {"node:node1", "node:node2", "node:node3"}, @@ -394,16 +403,17 @@ func TestIndex(t *testing.T) { "node:node1": {}, "node:node2": {}, "node:node3": {}, + "node:node4": {}, "pod:ns/pod2": {"node:node2"}, "pod:ns/pod3": {"node:node3"}, "pod:ns/pod4": {"node:node1"}, - "configmap:ns/cm1": {"node:node2", "node:node3", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, + "configmap:ns/cm1": {"node:node2", "node:node3", "node:node4", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, "configmap:ns/cm2": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, "configmap:ns/cm3": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, "serviceAccount:ns/sa1": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"}, }) expectIndex(map[string][]string{ - "configmap:ns/cm1": {"node:node1", "node:node2", "node:node3"}, + "configmap:ns/cm1": {"node:node1", "node:node2", "node:node3", "node:node4"}, "configmap:ns/cm2": {"node:node1", "node:node2", "node:node3"}, "configmap:ns/cm3": {"node:node1", "node:node2", "node:node3"}, "serviceAccount:ns/sa1": {"node:node1", "node:node2", "node:node3"},

that test fails on this PR with:

--- FAIL: TestIndex (0.00s) graph_test.go:356: expected path from node4 to cm1, got false, node "node4" cannot get configmap ns/cm1, no relationship to this object was found in the node authorizer graph index

Wow, thanks for catching this!

Could you include this test case in your PR?

liggitt · 2020-01-31T07:07:56Z

/hold

the destination index is not authoritative, since not all edges know their destination node. see #87688 (comment)

liggitt · 2020-01-31T07:08:34Z

the fastpath index add is useful and should be kept (and the corresponding refcount and fastpath remove in #87696)

mborsz · 2020-01-31T09:04:05Z

Thanks for finding the issue with destination index. I reverted this part.

plugin/pkg/auth/authorizer/node/graph.go

mborsz · 2020-02-04T08:46:09Z

PTAL

This seems to improve WriteIndexMaintenance benchmark: Before: BenchmarkWriteIndexMaintenance-12 1034 1157922 ns/op 1906 B/op 41 allocs/op After: BenchmarkWriteIndexMaintenance-12 4891 239821 ns/op 1572 B/op 37 allocs/op

mborsz · 2020-02-04T12:53:19Z

/retest

liggitt · 2020-02-04T13:23:05Z

/hold cancel
/lgtm
/approve

k8s-ci-robot · 2020-02-04T13:23:49Z

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: liggitt, mborsz

The full list of commands accepted by this bot can be found here.

The pull request process is described here

Needs approval from an approver in each of these files:

~~plugin/pkg/auth/authorizer/node/OWNERS~~ [liggitt]

Approvers can indicate their approval by writing /approve in a comment
Approvers can cancel approval by writing /approve cancel in a comment

wojtek-t · 2020-02-04T13:36:51Z

/retest

liggitt · 2020-02-04T15:31:10Z

/priority important-longterm
/retest

wojtek-t · 2020-02-04T19:08:55Z

/retest

fejta-bot · 2020-02-04T23:34:14Z

/retest
This bot automatically retries jobs that failed/flaked on approved PRs (send feedback to fejta).

Review the full test history for this PR.

Silence the bot with an /lgtm cancel or /hold comment for consistent failures.

fejta-bot · 2020-02-05T05:10:15Z

/retest
This bot automatically retries jobs that failed/flaked on approved PRs (send feedback to fejta).

Review the full test history for this PR.

Silence the bot with an /lgtm cancel or /hold comment for consistent failures.

wojtek-t · 2020-02-05T07:12:18Z

/retest

mborsz · 2020-02-05T08:25:47Z

/retest

mborsz · 2020-02-05T09:23:10Z

/retest

mborsz · 2020-02-05T10:25:56Z

/retest

mborsz · 2020-02-05T11:45:16Z

/retest

fejta-bot · 2020-02-06T17:33:20Z

/retest
This bot automatically retries jobs that failed/flaked on approved PRs (send feedback to fejta).

Review the full test history for this PR.

Silence the bot with an /lgtm cancel or /hold comment for consistent failures.

fejta-bot · 2020-02-07T01:36:01Z

/retest
This bot automatically retries jobs that failed/flaked on approved PRs (send feedback to fejta).

Review the full test history for this PR.

Silence the bot with an /lgtm cancel or /hold comment for consistent failures.

wojtek-t · 2020-02-07T07:12:27Z

/retest

k8s-ci-robot assigned liggitt Jan 30, 2020

k8s-ci-robot added the release-note-none Denotes a PR that doesn't merit a release note. label Jan 30, 2020

k8s-ci-robot assigned wojtek-t Jan 30, 2020

k8s-ci-robot requested review from liggitt and tallclair January 30, 2020 13:38

wojtek-t requested a review from mikedanese January 30, 2020 14:03

liggitt reviewed Jan 30, 2020

View reviewed changes

plugin/pkg/auth/authorizer/node/node_authorizer.go Outdated Show resolved Hide resolved

mborsz force-pushed the node2 branch from ea1da3c to f10ee99 Compare January 30, 2020 15:34

liggitt mentioned this pull request Jan 30, 2020

Switch node authorizer indexes to reference counts, add fastpath edge removal #87696

Merged

liggitt mentioned this pull request Jan 30, 2020

Fix node authorizer index recomputation #87693

Merged

liggitt reviewed Jan 31, 2020

View reviewed changes

k8s-ci-robot added the do-not-merge/hold Indicates that a PR should not merge because someone has issued a /hold command. label Jan 31, 2020

mborsz force-pushed the node2 branch from f10ee99 to 823c02c Compare January 31, 2020 09:03

liggitt reviewed Feb 3, 2020

View reviewed changes

plugin/pkg/auth/authorizer/node/graph.go Outdated Show resolved Hide resolved

mborsz force-pushed the node2 branch from 823c02c to 4d4124a Compare February 4, 2020 08:45

Add a fast path for adding new node in node_autorizer.

69df8a8

This seems to improve WriteIndexMaintenance benchmark: Before: BenchmarkWriteIndexMaintenance-12 1034 1157922 ns/op 1906 B/op 41 allocs/op After: BenchmarkWriteIndexMaintenance-12 4891 239821 ns/op 1572 B/op 37 allocs/op

mborsz force-pushed the node2 branch from 4d4124a to 69df8a8 Compare February 4, 2020 10:32

k8s-ci-robot added lgtm "Looks good to me", indicates that a PR is ready to be merged. and removed do-not-merge/hold Indicates that a PR should not merge because someone has issued a /hold command. labels Feb 4, 2020

k8s-ci-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Feb 4, 2020

k8s-ci-robot added priority/important-longterm Important over the long term, but may not be staffed and/or may need multiple releases to complete. and removed needs-priority Indicates a PR lacks a `priority/foo` label and requires one. labels Feb 4, 2020

k8s-ci-robot merged commit 91738cb into kubernetes:master Feb 7, 2020

k8s-ci-robot added this to the v1.18 milestone Feb 7, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add a fast path for adding new node in node_authorizer #87688

Add a fast path for adding new node in node_authorizer #87688

mborsz commented Jan 30, 2020

liggitt commented Jan 30, 2020 •

edited

liggitt commented Jan 30, 2020

mborsz commented Jan 30, 2020

liggitt commented Jan 30, 2020

liggitt commented Jan 31, 2020

liggitt Jan 31, 2020

liggitt Jan 31, 2020 •

edited

mborsz Jan 31, 2020

liggitt commented Jan 31, 2020

liggitt commented Jan 31, 2020

mborsz commented Jan 31, 2020

mborsz commented Feb 4, 2020

mborsz commented Feb 4, 2020

liggitt commented Feb 4, 2020

k8s-ci-robot commented Feb 4, 2020

wojtek-t commented Feb 4, 2020

liggitt commented Feb 4, 2020

wojtek-t commented Feb 4, 2020

fejta-bot commented Feb 4, 2020

fejta-bot commented Feb 5, 2020

wojtek-t commented Feb 5, 2020

mborsz commented Feb 5, 2020

mborsz commented Feb 5, 2020

mborsz commented Feb 5, 2020

mborsz commented Feb 5, 2020

fejta-bot commented Feb 6, 2020

fejta-bot commented Feb 7, 2020

wojtek-t commented Feb 7, 2020

Add a fast path for adding new node in node_authorizer #87688

Add a fast path for adding new node in node_authorizer #87688

Conversation

mborsz commented Jan 30, 2020

liggitt commented Jan 30, 2020 • edited

liggitt commented Jan 30, 2020

mborsz commented Jan 30, 2020

liggitt commented Jan 30, 2020

liggitt commented Jan 31, 2020

liggitt Jan 31, 2020

Choose a reason for hiding this comment

liggitt Jan 31, 2020 • edited

Choose a reason for hiding this comment

mborsz Jan 31, 2020

Choose a reason for hiding this comment

liggitt commented Jan 31, 2020

liggitt commented Jan 31, 2020

mborsz commented Jan 31, 2020

mborsz commented Feb 4, 2020

mborsz commented Feb 4, 2020

liggitt commented Feb 4, 2020

k8s-ci-robot commented Feb 4, 2020

wojtek-t commented Feb 4, 2020

liggitt commented Feb 4, 2020

wojtek-t commented Feb 4, 2020

fejta-bot commented Feb 4, 2020

fejta-bot commented Feb 5, 2020

wojtek-t commented Feb 5, 2020

mborsz commented Feb 5, 2020

mborsz commented Feb 5, 2020

mborsz commented Feb 5, 2020

mborsz commented Feb 5, 2020

fejta-bot commented Feb 6, 2020

fejta-bot commented Feb 7, 2020

wojtek-t commented Feb 7, 2020

liggitt commented Jan 30, 2020 •

edited

liggitt Jan 31, 2020 •

edited