Feature request: `+kubebuilder:validation:UniqueItems` for uniqueness of field among structs

[mattwelke]

Feature request: `+kubebuilder:validation:UniqueItems` for uniqueness of field among structs

[camilamacedo86]

Hi @mattwelke

@camilamacedo86

Can you clarify? Since the suggested workaround involves using markers defined in https://github.com/kubernetes-sigs/controller-tools, we should move this issue there?

If this remained open as a feature request, would it remain here? I'm guessing it would depend on which repo would be where new markers were added.

Yes, that should remain there. We (Kubebuilder Maintainers cannot help you out with this one)
The kubebuilder maintainers are not the same as controller-tools

The RFE that you are asking is in controller-tools and not kubebuilder
Kubebuilder use/consume controller tools
So, the discussion to see if it is or is not acceptable must be in the project where the implementations will be made

Also, see that, indeed, our documentation is generated automatically from the comments/documentation of the source code in controller-tools

So, I am closing this one in favor of: kubernetes-sigs/controller-tools#868
And re-open that there.

[JoelSpeed]

The problem with this approach is the time complexity of the algorithm. It's greater than linear, and this makes it expensive.

The operation of supporting the UniqueItems is equally expensive, it's just that it's hidden from the user in this case.

The workaround we've used so far is to use a validation rule with CEL.

This is actually probably the correct path forward rather then directly supporting this in kubebuilder. Supporting it in kubebuilder would allow users to blindly add very complex validations without any thought for the complexity of the rules in question.

When using this validation rule alone, we get errors when applying the CRDs warning us that the validation is too expensive:

• spec.validation.openAPIV3Schema.properties[spec].properties[foos].x-kubernetes-validations[0].rule: Forbidden: estimated rule cost exceeds budget by factor of more than 100x (try simplifying the rule, or adding maxItems, maxProperties, and maxLength where arrays, maps, and strings are declared)

We find that for this CEL expression, we can only get the expensiveness down to an acceptable level by severely limiting the size of the list via MaxItems.

This is the expectation, where you have complex validations you must limit the length of your inputs, this is, in general good practice anyway.

Bear in mind that the cost calculation not only takes into account the length of the list, but also what the size of the elements within them are. So, if you have an unbounded length string within your struct, that will not be helping you here. Make sure to add maximum sizes to all structs!

---

Given everything I have said above, I don't think CEL or UniqueItems is what you want for your particular use case.

If I have understood correctly, your desire is to have a list of items, where there is one field in the list that is unique. This is a standard thing in kube, for example, the list of containers in a pod must all have unique names.

The following validation will achieve what you want, set the list to a map type and add the id field as the map key

// +listType=map
// +listMapKey=id

The validations will ensure every list has a unique id entry. This also sets you up for server side apply where different actors will be able to update their own entries in the list without affecting the whole list.

[camilamacedo86]

Hi @JoelSpeed

Thank you for the hand here.
However, since those markers are controller-tools implementation, could we move this issue there?

[mattwelke]

@JoelSpeed Thanks for the suggestions.

Bear in mind that the cost calculation not only takes into account the length of the list, but also what the size of the elements within them are. So, if you have an unbounded length string within your struct, that will not be helping you here. Make sure to add maximum sizes to all structs!

This is a great suggestion. We completely forgot about this and I think it'll make a big improvement. It should allow us to squeeze in a lot more items via MaxItems.

// +listType=map and // +listMapKey=id

We actually prefer using structs over maps because it means things are more strongly typed and we can add documentation for each field.

But, we found kubernetes-sigs/controller-tools#435 (comment) which talks about how you can use those markers on structs too.

type BarSpec struct {
	// +listType=map
	// +listMapKey=id
	Foos []Foo `json:"foos,omitempty"`
}

type Foo struct {
	ID    string `json:"id"`
	Other string `json:"other"`
}

I tested this and it worked too!

But unfortunately, it was determined by k8s to be just as expensive as the CEL approach. I actually find this surprising because as far as I know, one could determine uniqueness in an inexpensive way by doing something like this:

package main

import "fmt"

func duplicate(items []string) *string {
	seen := map[string]bool{}

	for _, str := range items {
		if _, ok := seen[str]; ok {
			// Duplicate found!
			return &str
		}
		seen[str] = true
	}

	// No duplicates found.
	return nil
}

func main() {
	if dupStr := duplicate([]string{"a", "b", "b", "c"}); dupStr != nil {
		fmt.Printf("Duplicate found: %s\n", *dupStr)
	} else {
		fmt.Printf("No duplicates found.\n")
	}
}

Duplicate found: b

[mattwelke]

@camilamacedo86

Can you clarify? Since the suggested workaround involves using markers defined in https://github.com/kubernetes-sigs/controller-tools, we should move this issue there?

If this remained open as a feature request, would it remain here? I'm guessing it would depend on which repo would be where new markers were added.

[JoelSpeed]

We actually prefer using structs over maps because it means things are more strongly typed and we can add documentation for each field.

Maps are discouraged (forbidden even) in Kube API types. The markers I'm suggesting do not mean you have to use maps. They are designed for lists, hence, listType.

I tested this and it worked too!

Yep, what you have in that example looks like what I was expecting.

But unfortunately, it was deemed by k8s to be just as expensive as the CEL approach.

Can you provide the error message that came out? To my knowledge the listType and listMapKey do not have cost counting, only CEL validations have cost counting so I don't think your error will have been from this

[mattwelke]

Maps are discouraged (forbidden even) in Kube API types. The markers I'm suggesting do not mean you have to use maps. They are designed for lists, hence, listType.

Sorry. To clarify, what I meant was that we needed to use a list regardless, and it was just a matter of what type to use with the list. So []OurStruct vs. []map[K]V. We prefer []OurStruct for the reasons I mentioned.

Can you provide the error message that came out? To my knowledge the listType and listMapKey do not have cost counting, only CEL validations have cost counting so I don't think your error will have been from this

Confirmed through more troubleshooting that I was incorrect earlier. It wasn't listType and listMapKey that were contributing to the cost counting in that case. It was the fact that I was working from a different example (our actual code base), tweaking it, and then making code snippets to post here. So the cost counting was coming from other validation that did involve cost counting nested more deeply in our struct.