Repository: kubernetes-csi/external-provisioner
Pull request #1310 (2024-12-11 19:14:46)

Optimize for topology term
<!--  Thanks for sending a pull request!  Here are some tips for you:

1. If this is your first time, please read our contributor guidelines: https://git.k8s.io/community/contributors/guide#your-first-contribution and developer guide https://git.k8s.io/community/contributors/devel/development.md#development-guide
2. Follow the instructions for writing a release note: https://git.k8s.io/community/contributors/guide/release-notes.md
3. If the PR is unfinished, see how to mark it: https://git.k8s.io/community/contributors/guide/pull-requests.md#marking-unfinished-pull-requests
-->

**What type of PR is this?**

/kind cleanup


**What this PR does / why we need it**:

Greatly reduce the CPU and memory usage, especially for drivers assign different topology to each host. Benchmark shows 30x CPU reduction and 21x memory allocation size reduction.

We were performing a stress test recently, and found the bottleneck to be the CPU usage of external-provisioner. From profiling, `topologyTerm.hash` takes almost all the CPU time (apart from logGRPC).
![image](https://github.com/user-attachments/assets/919c01f6-2cb4-4dfa-b3bc-db7dfd4dfabf)
Our setup is a 3k node cluster, each node has a distinct topology. It took about 50s for provisioning 3k immediate binding volumes, despite that we have raised the CPU limit to 10. external-provisioner also took ~3GiB memory, which is far higher than expected.

[This](https://github.com/huww98/external-provisioner/commit/4998f1d35d2f7091fa044508a6fb7abe9dd32f9a) is my initial attempt (not included in this PR) to optimize this. I re-implemented the compare function for sort to avoid hash() and added some benchmarks. The benchmark result is:
```
goos: darwin
goarch: arm64
pkg: github.com/kubernetes-csi/external-provisioner/v5/pkg/controller
cpu: Apple M2 Pro
BenchmarkDedupAndSortZone/baseline-12               1641            643224 ns/op          697858 B/op      15032 allocs/op
BenchmarkDedupAndSortZone/compare-12                1812            642864 ns/op          697004 B/op      15012 allocs/op
BenchmarkDedupAndSortZone/slices.Sort-12            1795            644037 ns/op          696948 B/op      15010 allocs/op
BenchmarkDedupAndSortZone/slices.Compact-12          906           1309465 ns/op          540267 B/op       8060 allocs/op
BenchmarkDedupAndSortHost/baseline-12                 50          22663181 ns/op        27017105 B/op     530151 allocs/op
BenchmarkDedupAndSortHost/compare-12                 156           7625107 ns/op         5039063 B/op      60242 allocs/op
BenchmarkDedupAndSortHost/slices.Sort-12             156           7646612 ns/op         5040749 B/op      60260 allocs/op
BenchmarkDedupAndSortHost/slices.Compact-12          193           6147562 ns/op         3457850 B/op      37009 allocs/op
```
By comparing `compare` and `baseline` for `BenchmarkDedupAndSortHost`, re-implementing compare already gives 3x speedup and 5x memory allocation size reduction. But when I try to replace the hash() func completely by `slices.Compact`, the host case is faster, but the zone case becomes slower.

While I'm trying to find more opportunity to optimize, I do another profile for `Host/slices.Sort` case:
![image](https://github.com/user-attachments/assets/c44cffd1-b403-414b-8daa-98eae263b102)
Making slice, accessing map, and sorting keys can all be avoid if we define topologyTerm as a sorted slice instead of map (the first commit of this PR). The benchmark result from the first commit is:
```
BenchmarkDedupAndSortZone/slices.Sort-12                    1975            527407 ns/op          747079 B/op      15014 allocs/op
BenchmarkDedupAndSortZone/slices.Compact-12                10000            114418 ns/op           74904 B/op         11 allocs/op
BenchmarkDedupAndSortHost/slices.Sort-12                     652           1847723 ns/op         2948386 B/op      30078 allocs/op
BenchmarkDedupAndSortHost/slices.Compact-12                 1597            739441 ns/op         1250314 B/op       9002 allocs/op
```
`Host/slices.Sort` case is speedup several times again, the `Zone/slices.Sort` case is also improved because of the more efficient hash(). With the very cheap compare(), using `slices.Compact` to deduplicate becomes beneficial for both case!
So, with the second commit, the hash() is removed completely.

Note that for fair comparation, the benchmark also includes `toCSITopology` invocation, because if topologyTerm is a slice, we need to convert it back to map for GRPC. Actually, after this refactor, most of the time is spent on `toCSITopology()`. If I remove it, the result is:
```
BenchmarkDedupAndSortZone-12               10725            111114 ns/op           73753 B/op          1 allocs/op
BenchmarkDedupAndSortHost-12                4029            287086 ns/op           73830 B/op          3 allocs/op
```
This is ~78x speedup compared to the baseline, with zero allocation in deduplication and sort step!


**Which issue(s) this PR fixes**:
<!--
*Automatically closes linked issue when PR is merged.
Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`.
_If PR is about `failing-tests or flakes`, please post the related issues/tests in a comment and do not use `Fixes`_*
-->
Fixes #

**Special notes for your reviewer**:

**Does this PR introduce a user-facing change?**:
<!--
If no, just write "NONE" in the release-note block below.
If yes, a release note is required:
Enter your extended release note in the block below. If the PR requires additional action from users switching to the new release, include the string "action required".
-->
```release-note
NONE
```


jsafrane: /ok-to-test

Patch:
diff --git a/pkg/controller/topology.go b/pkg/controller/topology.go
index 93aaf7a9b..02d8fe4ec 100644
--- a/pkg/controller/topology.go
+++ b/pkg/controller/topology.go
@@ -20,7 +20,7 @@ import (
 	"fmt"
 	"hash/fnv"
 	"math/rand"
-	"sort"
+	"slices"
 	"strconv"
 	"strings"
 
@@ -39,8 +39,14 @@ import (
 	"k8s.io/klog/v2"
 )
 
+type topologySegment struct {
+	Key, Value string
+}
+
 // topologyTerm represents a single term where its topology key value pairs are AND'd together.
-type topologyTerm map[string]string
+//
+// Be sure to sort after construction for compare() and subset() to work properly.
+type topologyTerm []topologySegment
 
 func GenerateVolumeNodeAffinity(accessibleTopology []*csi.Topology) *v1.VolumeNodeAffinity {
 	if len(accessibleTopology) == 0 {
@@ -229,7 +235,8 @@ func GenerateAccessibilityRequirements(
 		return nil, nil
 	}
 
-	requisiteTerms = deduplicate(requisiteTerms)
+	slices.SortFunc(requisiteTerms, topologyTerm.compare)
+	requisiteTerms = slices.CompactFunc(requisiteTerms, slices.Equal)
 	// TODO (verult) reduce subset duplicate terms (advanced reduction)
 
 	requirement.Requisite = toCSITopology(requisiteTerms)
@@ -243,14 +250,19 @@ func GenerateAccessibilityRequirements(
 		// requisiteTerms and shifting the sorted terms based on hash of pvcName and replica index suffix
 		hash, index := getPVCNameHashAndIndexOffset(pvcName)
 		i := (hash + index) % uint32(len(requisiteTerms))
-		preferredTerms = sortAndShift(requisiteTerms, nil, i)
+		preferredTerms = append(requisiteTerms[i:], requisiteTerms[:i]...)
 	} else {
 		// Delayed binding, use topology from that node to populate preferredTerms
 		if strictTopology {
 			// In case of strict topology, preferred = requisite
 			preferredTerms = requisiteTerms
 		} else {
-			preferredTerms = sortAndShift(requisiteTerms, selectedTopology, 0)
+			for i, t := range requisiteTerms {
+				if t.subset(selectedTopology) {
+					preferredTerms = append(requisiteTerms[i:], requisiteTerms[:i]...)
+					break
+				}
+			}
 			if preferredTerms == nil {
 				// Topology from selected node is not in requisite. This case should never be hit:
 				// - If AllowedTopologies is specified, the scheduler should choose a node satisfying the
@@ -417,12 +429,12 @@ func flatten(allowedTopologies []v1.TopologySelectorTerm) []topologyTerm {
 
 				if len(oldTerms) == 0 {
 					// No previous terms to distribute over. Simply append the new term.
-					newTerms = append(newTerms, topologyTerm{selectorExpression.Key: v})
+					newTerms = append(newTerms, topologyTerm{{selectorExpression.Key, v}})
 				} else {
 					for _, oldTerm := range oldTerms {
 						// "Distribute" by adding an entry to the term
-						newTerm := oldTerm.clone()
-						newTerm[selectorExpression.Key] = v
+						newTerm := slices.Clone(oldTerm)
+						newTerm = append(newTerm, topologySegment{selectorExpression.Key, v})
 						newTerms = append(newTerms, newTerm)
 					}
 				}
@@ -435,41 +447,10 @@ func flatten(allowedTopologies []v1.TopologySelectorTerm) []topologyTerm {
 		finalTerms = append(finalTerms, oldTerms...)
 	}
 
-	return finalTerms
-}
-
-func deduplicate(terms []topologyTerm) []topologyTerm {
-	termMap := make(map[string]topologyTerm)
-	for _, term := range terms {
-		termMap[term.hash()] = term
-	}
-
-	var dedupedTerms []topologyTerm
-	for _, term := range termMap {
-		dedupedTerms = append(dedupedTerms, term)
-	}
-	return dedupedTerms
-}
-
-// Sort the given terms in place,
-// then return a new list of terms equivalent to the sorted terms, but shifted so that
-// either the primary term (if specified) or term at shiftIndex is the first in the list.
-func sortAndShift(terms []topologyTerm, primary topologyTerm, shiftIndex uint32) []topologyTerm {
-	var preferredTerms []topologyTerm
-	sort.Slice(terms, func(i, j int) bool {
-		return terms[i].less(terms[j])
-	})
-	if primary == nil {
-		preferredTerms = append(terms[shiftIndex:], terms[:shiftIndex]...)
-	} else {
-		for i, t := range terms {
-			if t.subset(primary) {
-				preferredTerms = append(terms[i:], terms[:i]...)
-				break
-			}
-		}
+	for _, term := range finalTerms {
+		term.sort()
 	}
-	return preferredTerms
+	return finalTerms
 }
 
 func getTopologyKeys(csiNode *storagev1.CSINode, driverName string) []string {
@@ -482,14 +463,15 @@ func getTopologyKeys(csiNode *storagev1.CSINode, driverName string) []string {
 }
 
 func getTopologyFromNode(node *v1.Node, topologyKeys []string) (term topologyTerm, isMissingKey bool) {
-	term = make(topologyTerm)
+	term = make(topologyTerm, 0, len(topologyKeys))
 	for _, key := range topologyKeys {
 		v, ok := node.Labels[key]
 		if !ok {
 			return nil, true
 		}
-		term[key] = v
+		term = append(term, topologySegment{key, v})
 	}
+	term.sort()
 	return term, false
 }
 
@@ -514,56 +496,65 @@ func buildTopologyKeySelector(topologyKeys []string) (labels.Selector, error) {
 	return selector, nil
 }
 
-func (t topologyTerm) clone() topologyTerm {
-	ret := make(topologyTerm)
-	for k, v := range t {
-		ret[k] = v
-	}
-	return ret
+func (t topologyTerm) sort() {
+	slices.SortFunc(t, func(a, b topologySegment) int {
+		r := strings.Compare(a.Key, b.Key)
+		if r != 0 {
+			return r
+		}
+		// Should not happen currently. We may support multi-value in the future?
+		return strings.Compare(a.Value, b.Value)
+	})
 }
 
-// "<k1>#<v1>,<k2>#<v2>,..."
-// Hash properties:
-// - Two equivalent topologyTerms have the same hash
-// - Ordering of hashes correspond to a natural ordering of their topologyTerms. For example:
-//   - com.example.csi/zone#zone1 < com.example.csi/zone#zone2
-//   - com.example.csi/rack#zz    < com.example.csi/zone#zone1
-//   - com.example.csi/z#z1       < com.example.csi/zone#zone1
-//   - com.example.csi/rack#rackA,com.example.csi/zone#zone2  <  com.example.csi/rackB,com.example.csi/zone#zone1
-//     Note that both '#' and ',' are less than '/', '-', '_', '.', [A-Z0-9a-z]
-func (t topologyTerm) hash() string {
-	var segments []string
-	for k, v := range t {
-		segments = append(segments, k+"#"+v)
+func (t topologyTerm) compare(other topologyTerm) int {
+	if len(t) != len(other) {
+		return len(t) - len(other)
 	}
-
-	sort.Strings(segments)
-	return strings.Join(segments, ",")
-}
-
-func (t topologyTerm) less(other topologyTerm) bool {
-	return t.hash() < other.hash()
+	for i, k1 := range t {
+		k2 := other[i]
+		r := strings.Compare(k1.Key, k2.Key)
+		if r != 0 {
+			return r
+		}
+		r = strings.Compare(k1.Value, k2.Value)
+		if r != 0 {
+			return r
+		}
+	}
+	return 0
 }
 
 func (t topologyTerm) subset(other topologyTerm) bool {
-	for key, tv := range t {
-		v, ok := other[key]
-		if !ok || v != tv {
+	if len(t) == 0 {
+		return true
+	}
+	j := 0
+	for _, k2 := range other {
+		k1 := t[j]
+		if k1.Key != k2.Key {
+			continue
+		}
+		if k1.Value != k2.Value {
 			return false
 		}
+		j++
+		if j == len(t) {
+			// All segments in t have been checked and is present in other.
+			return true
+		}
 	}
-
-	return true
-}
-
-func (t topologyTerm) equal(other topologyTerm) bool {
-	return t.hash() == other.hash()
+	return false
 }
 
 func toCSITopology(terms []topologyTerm) []*csi.Topology {
-	var out []*csi.Topology
+	out := make([]*csi.Topology, 0, len(terms))
 	for _, term := range terms {
-		out = append(out, &csi.Topology{Segments: term})
+		segs := make(map[string]string, len(term))
+		for _, k := range term {
+			segs[k.Key] = k.Value
+		}
+		out = append(out, &csi.Topology{Segments: segs})
 	}
 	return out
 }
diff --git a/release-tools/build.make b/release-tools/build.make
index 39a34777d..5d3079308 100644
--- a/release-tools/build.make
+++ b/release-tools/build.make
@@ -45,10 +45,9 @@ REV=$(shell git describe --long --tags --match='v*' --dirty 2>/dev/null || git r
 # Determined dynamically.
 IMAGE_TAGS=
 
-# A "canary" image gets built if the current commit is the head of the remote "master" or "main" branch.
+# A "canary" image gets built if the current commit is the head of the remote "master" branch.
 # That branch does not exist when building some other branch in TravisCI.
 IMAGE_TAGS+=$(shell if [ "$$(git rev-list -n1 HEAD)" = "$$(git rev-list -n1 origin/master 2>/dev/null)" ]; then echo "canary"; fi)
-IMAGE_TAGS+=$(shell if [ "$$(git rev-list -n1 HEAD)" = "$$(git rev-list -n1 origin/main 2>/dev/null)" ]; then echo "canary"; fi)
 
 # A "X.Y.Z-canary" image gets built if the current commit is the head of a "origin/release-X.Y.Z" branch.
 # The actual suffix does not matter, only the "release-" prefix is checked.
@@ -144,7 +143,7 @@ DOCKER_BUILDX_CREATE_ARGS ?=
 # Windows binaries can be built before adding a Dockerfile for it.
 #
 # BUILD_PLATFORMS determines which individual images are included in the multiarch image.
-# PULL_BASE_REF must be set to 'master', 'main', 'release-x.y', or a tag name, and determines
+# PULL_BASE_REF must be set to 'master', 'release-x.y', or a tag name, and determines
 # the tag for the resulting multiarch image.
 $(CMDS:%=push-multiarch-%): push-multiarch-%: check-pull-base-ref build-%
 	set -ex; \
@@ -192,7 +191,7 @@ $(CMDS:%=push-multiarch-%): push-multiarch-%: check-pull-base-ref build-%
 		done; \
 		docker manifest push -p $(IMAGE_NAME):$$tag; \
 	}; \
-	if [ $(PULL_BASE_REF) = "master" ] || [ $(PULL_BASE_REF) = "main" ]; then \
+	if [ $(PULL_BASE_REF) = "master" ]; then \
 			: "creating or overwriting canary image"; \
 			pushMultiArch canary; \
 	elif echo $(PULL_BASE_REF) | grep -q -e 'release-*' ; then \
@@ -210,7 +209,7 @@ $(CMDS:%=push-multiarch-%): push-multiarch-%: check-pull-base-ref build-%
 .PHONY: check-pull-base-ref
 check-pull-base-ref:
 	if ! [ "$(PULL_BASE_REF)" ]; then \
-		echo >&2 "ERROR: PULL_BASE_REF must be set to 'master', 'main', 'release-x.y', or a tag name."; \
+		echo >&2 "ERROR: PULL_BASE_REF must be set to 'master', 'release-x.y', or a tag name."; \
 		exit 1; \
 	fi
 
diff --git a/release-tools/prow.sh b/release-tools/prow.sh
index 67d8dfb2a..df8c61502 100755
--- a/release-tools/prow.sh
+++ b/release-tools/prow.sh
@@ -86,7 +86,7 @@ configvar CSI_PROW_BUILD_PLATFORMS "linux amd64 amd64; linux ppc64le ppc64le -pp
 # which is disabled with GOFLAGS=-mod=vendor).
 configvar GOFLAGS_VENDOR "$( [ -d vendor ] && echo '-mod=vendor' )" "Go flags for using the vendor directory"
 
-configvar CSI_PROW_GO_VERSION_BUILD "1.23.1" "Go version for building the component" # depends on component's source code
+configvar CSI_PROW_GO_VERSION_BUILD "1.22.5" "Go version for building the component" # depends on component's source code
 configvar CSI_PROW_GO_VERSION_E2E "" "override Go version for building the Kubernetes E2E test suite" # normally doesn't need to be set, see install_e2e
 configvar CSI_PROW_GO_VERSION_SANITY "${CSI_PROW_GO_VERSION_BUILD}" "Go version for building the csi-sanity test suite" # depends on CSI_PROW_SANITY settings below
 configvar CSI_PROW_GO_VERSION_KIND "${CSI_PROW_GO_VERSION_BUILD}" "Go version for building 'kind'" # depends on CSI_PROW_KIND_VERSION below
@@ -199,7 +199,7 @@ kindest/node:v1.18.20@sha256:738cdc23ed4be6cc0b7ea277a2ebcc454c8373d7d8fb991a7fc
 # If the deployment script is called with CSI_PROW_TEST_DRIVER=<file name> as
 # environment variable, then it must write a suitable test driver configuration
 # into that file in addition to installing the driver.
-configvar CSI_PROW_DRIVER_VERSION "v1.15.0" "CSI driver version"
+configvar CSI_PROW_DRIVER_VERSION "v1.12.0" "CSI driver version"
 configvar CSI_PROW_DRIVER_REPO https://github.com/kubernetes-csi/csi-driver-host-path "CSI driver repo"
 configvar CSI_PROW_DEPLOYMENT "" "deployment"
 configvar CSI_PROW_DEPLOYMENT_SUFFIX "" "additional suffix in kubernetes-x.yy[suffix].yaml files"
@@ -425,7 +425,7 @@ die () {
     exit 1
 }
 
-# Ensure we use the desired version of the Go tools, then run command given as argument.
+# Ensure that PATH has the desired version of the Go tools, then run command given as argument.
 # Empty parameter uses the already installed Go. In Prow, that version is kept up-to-date by
 # bumping the container image regularly.
 run_with_go () {
@@ -433,16 +433,15 @@ run_with_go () {
     version="$1"
     shift
 
-    if [ "$version" ]; then
-        version=go$version
-        if [ "$(GOTOOLCHAIN=$version go version | cut -d' ' -f3)" != "$version" ]; then
-            die "Please install Go 1.21+"
-        fi
+    if ! [ "$version" ] || go version 2>/dev/null | grep -q "go$version"; then
+        run "$@"
     else
-        version=local
+        if ! [ -d "${CSI_PROW_WORK}/go-$version" ];  then
+            run curl --fail --location "https://dl.google.com/go/go$version.linux-amd64.tar.gz" | tar -C "${CSI_PROW_WORK}" -zxf - || die "installation of Go $version failed"
+            mv "${CSI_PROW_WORK}/go" "${CSI_PROW_WORK}/go-$version"
+        fi
+        PATH="${CSI_PROW_WORK}/go-$version/bin:$PATH" run "$@"
     fi
-    # Set GOMODCACHE to make sure Kubernetes does not need to download again.
-    GOTOOLCHAIN=$version GOMODCACHE="$(go env GOMODCACHE)" run "$@"
 }
 
 # Ensure that we have the desired version of kind.
@@ -625,7 +624,7 @@ start_cluster () {
             go_version="$(go_version_for_kubernetes "${CSI_PROW_WORK}/src/kubernetes" "$version")" || die "cannot proceed without knowing Go version for Kubernetes"
             # Changing into the Kubernetes source code directory is a workaround for https://github.com/kubernetes-sigs/kind/issues/1910
             # shellcheck disable=SC2046
-            (cd "${CSI_PROW_WORK}/src/kubernetes" && run_with_go "$go_version" kind build node-image "${CSI_PROW_WORK}/src/kubernetes" --image csiprow/node:latest) || die "'kind build node-image' failed"
+            (cd "${CSI_PROW_WORK}/src/kubernetes" && run_with_go "$go_version" kind build node-image --image csiprow/node:latest --kube-root "${CSI_PROW_WORK}/src/kubernetes") || die "'kind build node-image' failed"
             csi_prow_kind_have_kubernetes=true
         fi
         image="csiprow/node:latest"


Test patch:
diff --git a/pkg/controller/topology_test.go b/pkg/controller/topology_test.go
index d4bbc2d64..46c4d32a6 100644
--- a/pkg/controller/topology_test.go
+++ b/pkg/controller/topology_test.go
@@ -18,10 +18,12 @@ package controller
 
 import (
 	"fmt"
+	"slices"
 	"testing"
 
 	"github.com/container-storage-interface/spec/lib/go/csi"
 	"github.com/google/go-cmp/cmp"
+	"github.com/stretchr/testify/assert"
 	"google.golang.org/protobuf/testing/protocmp"
 	v1 "k8s.io/api/core/v1"
 	storagev1 "k8s.io/api/storage/v1"
@@ -1454,6 +1456,42 @@ func TestPreferredTopologies(t *testing.T) {
 	}
 }
 
+func BenchmarkDedupAndSortZone(b *testing.B) {
+	terms := make([]topologyTerm, 0, 3000)
+	for range 1000 {
+		for _, zone := range [...]string{"zone1", "zone2", "zone3"} {
+			terms = append(terms, topologyTerm{
+				{"topology.kubernetes.io/region", "some-region"},
+				{"topology.kubernetes.io/zone", zone},
+			})
+		}
+	}
+	benchmarkDedupAndSort(b, terms)
+}
+
+func BenchmarkDedupAndSortHost(b *testing.B) {
+	terms := make([]topologyTerm, 0, 3000)
+	for i := range 1000 {
+		for j, zone := range [...]string{"zone1", "zone2", "zone3"} {
+			terms = append(terms, topologyTerm{
+				{"example.com/instance-id", fmt.Sprintf("i-%05d", i+j*10000)},
+				{"topology.kubernetes.io/region", "some-region"},
+				{"topology.kubernetes.io/zone", zone},
+			})
+		}
+	}
+	benchmarkDedupAndSort(b, terms)
+}
+
+func benchmarkDedupAndSort(b *testing.B, terms []topologyTerm) {
+	for range b.N {
+		terms := slices.Clone(terms)
+		slices.SortFunc(terms, topologyTerm.compare)
+		terms = slices.CompactFunc(terms, slices.Equal)
+		toCSITopology(terms)
+	}
+}
+
 func buildNodes(nodeLabels []map[string]string) *v1.NodeList {
 	list := &v1.NodeList{}
 	i := 0
@@ -1636,3 +1674,160 @@ func listers(kubeClient *fakeclientset.Clientset) (
 	factory.WaitForCacheSync(stopChan)
 	return scLister, csiNodeLister, nodeLister, claimLister, vaLister, stopChan
 }
+
+func TestTopologyTermSort(t *testing.T) {
+	testCases := []struct {
+		name            string
+		terms, expected topologyTerm
+	}{
+		{
+			name: "empty",
+		},
+		{
+			name: "single-key",
+			terms: topologyTerm{
+				{"zone", "us-east-1a"},
+			},
+			expected: topologyTerm{
+				{"zone", "us-east-1a"},
+			},
+		},
+		{
+			name: "multiple-keys",
+			terms: topologyTerm{
+				{"zone", "us-east-1a"},
+				{"instance", "i-123"},
+			},
+			expected: topologyTerm{
+				{"instance", "i-123"},
+				{"zone", "us-east-1a"},
+			},
+		},
+		{
+			name: "multiple-values", // should not happen currently
+			terms: topologyTerm{
+				{"zone", "us-east-1b"},
+				{"zone", "us-east-1a"},
+			},
+			expected: topologyTerm{
+				{"zone", "us-east-1a"},
+				{"zone", "us-east-1b"},
+			},
+		},
+	}
+	for _, tc := range testCases {
+		t.Run(tc.name, func(t *testing.T) {
+			tc.terms.sort()
+			assert.Equal(t, tc.expected, tc.terms)
+		})
+	}
+}
+
+func TestTopologyTermCompare(t *testing.T) {
+	testCases := []struct {
+		name          string
+		first, second topologyTerm
+	}{
+		{
+			name:  "shorter",
+			first: topologyTerm{},
+			second: topologyTerm{
+				{"zone", "us-east-1a"},
+			},
+		},
+		{
+			name: "key-smaller",
+			first: topologyTerm{
+				{"instance", "i-123"},
+			},
+			second: topologyTerm{
+				{"zone", "us-east-1a"},
+			},
+		},
+		{
+			name: "value-smaller",
+			first: topologyTerm{
+				{"instance", "i-123"},
+				{"zone", "us-east-1a"},
+			},
+			second: topologyTerm{
+				{"instance", "i-123"},
+				{"zone", "us-east-1b"},
+			},
+		},
+	}
+	for _, tc := range testCases {
+		t.Run(tc.name, func(t *testing.T) {
+			assert.Less(t, tc.first.compare(tc.second), 0)
+			assert.Greater(t, tc.second.compare(tc.first), 0)
+			assert.Equal(t, 0, tc.first.compare(tc.first))
+			assert.Equal(t, 0, tc.second.compare(tc.second))
+		})
+	}
+}
+
+func TestTopologyTermSubset(t *testing.T) {
+	testCases := []struct {
+		name         string
+		terms, other topologyTerm
+		subset       bool
+	}{
+		{
+			name:   "empty",
+			subset: true,
+		},
+		{
+			name:   "shorter",
+			terms:  topologyTerm{},
+			other:  topologyTerm{{"zone", "us-east-1a"}},
+			subset: true,
+		},
+		{
+			name:   "longer",
+			terms:  topologyTerm{{"zone", "us-east-1a"}},
+			other:  topologyTerm{},
+			subset: false,
+		},
+		{
+			name:   "same",
+			terms:  topologyTerm{{"zone", "us-east-1a"}},
+			other:  topologyTerm{{"zone", "us-east-1a"}},
+			subset: true,
+		},
+		{
+			name:   "shorter-2",
+			terms:  topologyTerm{{"instance", "i-123"}},
+			other:  topologyTerm{{"instance", "i-123"}, {"zone", "us-east-1a"}},
+			subset: true,
+		},
+		{
+			name:   "longer-2",
+			terms:  topologyTerm{{"instance", "i-123"}, {"zone", "us-east-1a"}},
+			other:  topologyTerm{{"instance", "i-123"}},
+			subset: false,
+		},
+		{
+			name:   "shorter-3",
+			terms:  topologyTerm{{"zone", "us-east-1a"}},
+			other:  topologyTerm{{"instance", "i-123"}, {"zone", "us-east-1a"}},
+			subset: true,
+		},
+		{
+			name:   "longer-3",
+			terms:  topologyTerm{{"instance", "i-123"}, {"zone", "us-east-1a"}},
+			other:  topologyTerm{{"zone", "us-east-1a"}},
+			subset: false,
+		},
+		{
+			name:   "unrelated",
+			terms:  topologyTerm{{"instance", "i-123"}},
+			other:  topologyTerm{{"zone", "us-east-1a"}},
+			subset: false,
+		},
+	}
+	for _, tc := range testCases {
+		t.Run(tc.name, func(t *testing.T) {
+			assert.Equal(t, tc.subset, tc.terms.subset(tc.other))
+		})
+	}
+}
diff --git a/release-tools/pull-test.sh b/release-tools/pull-test.sh
index 80317720d..5ea051eca 100755
--- a/release-tools/pull-test.sh
+++ b/release-tools/pull-test.sh
@@ -20,11 +20,6 @@
 
 set -ex
 
-# Prow checks out repos with --filter=blob:none. This breaks
-# "git subtree pull" unless we enable fetching missing file content.
-GIT_NO_LAZY_FETCH=0
-export GIT_NO_LAZY_FETCH
-
 # It must be called inside the updated csi-release-tools repo.
 CSI_RELEASE_TOOLS_DIR="$(pwd)"