Field Ownership as a Sorted Slice: The Data Structure Behind Server-Side Apply

TL;DR: The core data structure of server-side apply is fieldpath.Set, which records which fields a manager owns. It is not a Go map: Members is a sorted slice and every lookup is a binary search. The reason is determinism — the same field set must always produce byte-identical JSON in metadata.managedFields or etcd writes churn on every write. Union, intersection and difference are merge-joins over two sorted slices.

Server-side apply has a problem that ordinary JSON merging does not: it has to remember who owns which field, and it has to write that memory back to the object every single time. The record of ownership lives in metadata.managedFields, and it is read by every client, compared by tests, and diffed by humans reading kubectl get -o yaml.

If the ownership set were a Go map, its iteration order would be random. The same object, applied twice with the same manifest, would produce a managedFields block in a different order each time — different bytes, different etcd revision, a watch event for a change that did not happen. So the ownership set is a sorted slice, and every operation on it is either a binary search or a linear merge of two sorted slices.

The Set is a tree, not a set

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/set.go:31
// Set identifies a set of fields.
type Set struct {
	// Members lists fields that are part of the set.
	// TODO: will be serialized as a list of path elements.
	Members PathElementSet

	// Children lists child fields which themselves have children that are
	// members of the set. Appearance in this list does not imply membership.
	// Note: this is a tree, not an arbitrary graph.
	Children SetNodeMap
}

Two levels. Members is the set of leaf path elements owned at this level. Children maps a path element to the Set of things owned under it. And note the comment on Children: “Appearance in this list does not imply membership.” A Set can contain a.b.c without containing a or a.b — ownership is per-leaf, and the intermediate nodes are just routing.

That is a meaningful semantic. If I own spec.replicas, I do not own spec. If you own spec.template.spec.containers, you do not own spec.template.spec.containers[0], and I do not own it either. The structure encodes “I own exactly this leaf, and nothing else at any level”.

PathElementSet is the sorted slice:

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/element.go:226
// PathElementSet is a set of path elements.
// TODO: serialize as a list.
type PathElementSet struct {
	members sortedPathElements
}

The backing type is a plain slice that satisfies sort.Interface, so a bulk sort.Sort is possible as well as one-at-a-time insertion:

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/element.go:242
func (spe sortedPathElements) Len() int           { return len(spe) }
func (spe sortedPathElements) Less(i, j int) bool { return spe[i].Less(spe[j]) }
func (spe sortedPathElements) Swap(i, j int)      { spe[i], spe[j] = spe[j], spe[i] }

Members is unexported. You cannot reach into it. The only way to add anything is Insert, which maintains the sorted invariant.

Insert is a binary search

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/element.go:256
// Insert adds pe to the set.
func (s *PathElementSet) Insert(pe PathElement) {
	loc, found := slices.BinarySearchFunc(s.members, pe, func(a, b PathElement) int {
		return a.Compare(b)
	})
	if found {
		return
	}
	s.members = slices.Insert(s.members, loc, pe)
}

slices.BinarySearchFunc returns the insertion point and whether the element is already present. If it is present, Insert is a no-op — the set semantics come from the sortedness, not from a separate membership map. If it is not present, slices.Insert splices it into the right place, shifting the tail.

The cost is O(log n) to find, O(n) to splice. For the field counts involved in a real managedFields entry — tens, maybe a couple of hundreds of fields — that is the right trade. A map would be O(1) but would break determinism, and it would make the serialization O(n log n) anyway because you would still have to sort before writing.

Note the asymmetry with SetNodeMap: SetNodeMap.Union is a pure merge-join, no binary search, because the inputs are already sorted.

The total order

Everything above depends on PathElement having a total order — a comparison that is antisymmetric, transitive, and total. Here it is:

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/element.go:87
func (e PathElement) Compare(rhs PathElement) int {
	if e.FieldName != nil {
		if rhs.FieldName == nil {
			return -1
		}
		return strings.Compare(*e.FieldName, *rhs.FieldName)
	} else if rhs.FieldName != nil {
		return 1
	}

	if e.Key != nil {
		if rhs.Key == nil {
			return -1
		}
		return e.Key.Compare(*rhs.Key)
	} else if rhs.Key != nil {
		return 1
	}

The rest of the function continues the same way for Value (compared with value.Compare) and Index (compared numerically), and the final return 0 closes the case where both elements are empty.

The structure is: field names sort before keys, keys before values, values before indices. Within a kind, the natural comparison applies — lexicographic for field names, the value comparison for set elements, numeric for indices.

So the sort order of a mixed path element list is deterministic and total. a (field name) always sorts before [x=1] (key) always sorts before [=literal] (value) always sorts before [0] (index). It does not matter what the actual names are.

That total order is what makes slices.BinarySearchFunc legal, and it is what makes two independently-built sets comparable element-by-element, which is what makes the merge-joins below work.

Union is a merge-join

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/set.go:547
// Union returns a SetNodeMap with members that appear in either s or s2.
func (s *SetNodeMap) Union(s2 *SetNodeMap) *SetNodeMap {
	out := &SetNodeMap{}

	i, j := 0, 0
	for i < len(s.members) && j < len(s2.members) {
		if s.members[i].pathElement.Less(s2.members[j].pathElement) {
			out.members = append(out.members, s.members[i])
			i++
		} else {
			if !s2.members[j].pathElement.Less(s.members[i].pathElement) {
				out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: s.members[i].set.Union(s2.members[j].set)})
				i++
			} else {
				out.members = append(out.members, s2.members[j])
			}
			j++
		}
	}

	if i < len(s.members) {
		out.members = append(out.members, s.members[i:]...)
	}
	if j < len(s2.members) {
		out.members = append(out.members, s2.members[j:]...)
	}
	return out
}

This is a textbook merge of two sorted lists. i and j are the two cursors. At each step, if s[i] sorts before s2[j], take s[i]. If s2[j] sorts before s[i], take s2[j]. If they are equal — detected by the double negative !s2.members[j].pathElement.Less(s.members[i]) combined with the earlier check — take one of them but union their subtrees recursively.

That last part is the whole point: two managers can both own things under the same path element, and the union has to keep both. a.b owned by manager X and a.c owned by manager Y produces a union where a has children {b, c}.

The same shape appears in PathElementSet.Union, one level down, where the members are leaves and there are no subtrees to merge. The whole Set union is then just the two halves:

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/set.go:79
// Union returns a Set containing elements which appear in either s or s2.
func (s *Set) Union(s2 *Set) *Set {
	return &Set{
		Members:  *s.Members.Union(&s2.Members),
		Children: *s.Children.Union(&s2.Children),
	}
}

Difference is asymmetric, on purpose.

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/set.go:97
// Difference returns a Set containing elements which:
// * appear in s
// * do not appear in s2
//
// In other words, for leaf fields, this acts like a regular set difference
// operation. When non leaf fields are compared with leaf fields ("parents"
// which contain "children"), the effect is:
// * parent - child = parent
// * child - parent = {empty set}
func (s *Set) Difference(s2 *Set) *Set {
	return &Set{
		Members:  *s.Members.Difference(&s2.Members),
		Children: *s.Children.Difference(s2),
	}
}

Read those two bullets carefully, because they are not what “set difference” normally means.

• parent - child = parent. If s owns a.b (a leaf) and s2 owns a (which has children), the difference is a.b — the child survives the subtraction of its parent.
• child - parent = {empty set}. If s owns a and s2 owns a.b, the difference is empty. Subtracting a descendant from an ancestor removes the ancestor entirely.

This is not an accident; it falls out of the tree structure. a is a node in the tree with children. a.b is a leaf in Members. The Children.Difference walk compares a node’s children against the other set; if the other set contains a.b as a member of a’s subtree, then a as a whole is removed — because the whole of a is being subtracted, including its own membership.

And there is a second, recursive variant that behaves the way you might expect:

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/set.go:113
// RecursiveDifference returns a Set containing elements which:
// * appear in s
// * do not appear in s2
//
// Compared to a regular difference,
// this removes every field **and its children** from s that is contained in s2.
//
// For example, with s containing `a.b.c` and s2 containing `a.b`,
// a RecursiveDifference will result in `a`, as the entire node `a.b` gets removed.

a.b.c minus a.b gives a — the whole a.b node, children included, is removed.

Both semantics are needed, and they are used for different things: Difference for computing what a manager no longer owns after another manager claimed a field, RecursiveDifference for “I am taking over this whole subtree”.

The associative-list trick

Kubernetes has list types that are really maps with a key: containers in a PodSpec is a list, but two entries with the same name are the same entry. Server-side apply has to know that, so an item’s identity is defined by its key fields — and here is the elegant part: the key fields are sorted, so {name: x, port: 80} and {port: 80, name: x} are the same element.

// vendor/sigs.k8s.io/structured-merge-diff/v7/typed/helpers.go:212
	for _, fieldName := range list.Keys {
		if val, ok := m.Get(fieldName); ok {
			keyMap = append(keyMap, value.Field{Name: fieldName, Value: val})
		} else if def, err := getAssociativeKeyDefault(s, list, fieldName); err != nil {
			return pe, fmt.Errorf("couldn't find default value for %v: %v", fieldName, err)
		} else if def != nil {
			keyMap = append(keyMap, value.Field{Name: fieldName, Value: value.NewValueInterface(def)})
		} else {
			// Don't add the key to the key field list.
			// A key field list where it is set then represents a different entry
			// in the associate list.
		}
	}

	if len(list.Keys) > 0 && len(keyMap) == 0 {
		return pe, fmt.Errorf("associative list with keys has an element that omits all key fields %q (and doesn't have default values for any key fields)", list.Keys)
	}

	keyMap.Sort()
	pe.Key = &keyMap
	return pe, nil
}

keyMap.Sort() at the end is the whole trick. The sort is by field name:

// vendor/sigs.k8s.io/structured-merge-diff/v7/value/fields.go:165
	sort.SliceStable(f, func(i, j int) bool {
		return f[i].Name < f[j].Name
	})

So the key ["name"="x", "port"=80] and the key ["port"=80, "name"="x"] become the same FieldList, and therefore the same PathElement, and therefore the same element of the sorted set. Two managers applying {name: x, port: 80} and {port: 80, name: x} are talking about the same field, and the apply machinery will not see a conflict.

The other subtlety in that function: a key field that is omitted and has no default is simply left out of the key list. The comment explains why: “A key field list where it is set then represents a different entry in the associate list.” So {name: x} and {name: x, port: 80} are different elements, which is correct — they are different containers.

And if all the key fields are missing with no defaults, that is an error: “associative list with keys has an element that omits all key fields”.

The serializers

Writing the set out is where the determinism actually matters, because the output goes into metadata.managedFields.

The bulk deserializer is optimistic: it assumes the input is already in sorted order (which it is, because it was written by the same code), and appends rather than inserting:

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/serialize.go:227
			m := &children.Members.members
			// Since we expect that most of the time these will have been
			// serialized in the right order, we just verify that and append.
			appendOK := len(*m) == 0 || (*m)[len(*m)-1].Less(pe)
			if appendOK {
				*m = append(*m, pe)
			} else {
				children.Members.Insert(pe)
			}

The Children half of the deserializer does the same thing with setNode{pe, grandchildren} instead of a bare pe. The check is a single comparison against the last element: if the new element sorts after the last one, append (O(1)). Otherwise, fall back to the full Insert (O(n)). The comment says the expectation out loud: “Since we expect that most of the time these will have been serialized in the right order, we just verify that and append.” The fallback exists because the input might have been hand-written or produced by an older version.

And the per-element serializer is pooled, with a cap on how much buffer it keeps:

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/serialize.go:35
const maxRetainedBuffer = 1024

var pool = sync.Pool{
	New: func() any {
		return &pathElementSerializer{}
	},
}

writePathKey pulls a pathElementSerializer out of the pool, serializes the path element into its bytes.Buffer, writes the buffer as a JSON string token, and puts the serializer back.

The reset is where the cap lives:

// vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/serialize-pe.go:140
func (pes *pathElementSerializer) reset() {
	if pes.builder.Cap() > maxRetainedBuffer {
		pes.builder = bytes.Buffer{}
	} else {
		pes.builder.Reset()
	}
	pes.fastValue.Value = nil
}

If the buffer grew beyond 1024 bytes, throw the whole thing away and let the GC have it; otherwise reuse it with a Reset. Without this, one pathological element with a huge key would permanently pin a large buffer in the sync.Pool for the life of the process. The same reasoning as the workqueue’s (*q)[0] = *new(T): a pooled object that grows without bound is a leak.

The trade-off

What the sorted slice buys: deterministic output. The same logical field set always serialises to the same bytes, in the same order, on every machine and every version. That is what stops managedFields from churning on every write, and what makes the ownership record diffable and testable.

What it costs:

• Insertion is O(n), not O(1). slices.Insert shifts the tail. For the field counts in a real object that is irrelevant; for a synthetic object with thousands of owned fields it is not.
• Every set operation is O(n) or O(n log n). Union and difference are linear merge-joins, which is optimal for sorted inputs but means you cannot get sub-linear set algebra. For a server applying thousands of objects per second, that is real work.
• The Set is a tree, and trees are awkward to compare. Equality between two Sets is a recursive walk, not a pointer or a hash.
• Key fields must be sorted to be comparable. The associative-list trick means the identity of a list element is order-independent, but it also means the code that constructs the key has to remember to sort it, and a missing Sort() produces a set where two identical logical elements look different.
• The optimistic deserializer has a slow path. If the input is not sorted, every element falls back to Insert, making deserialisation O(n^2).

Wrapping up

The one thing to remember: fieldpath.Set.Members is a sortedPathElements slice and every lookup is a slices.BinarySearchFunc at vendor/sigs.k8s.io/structured-merge-diff/v7/fieldpath/element.go:258. It is a sorted slice because the output must be byte-identical every time — a Go map would randomise the order of metadata.managedFields and cause a write to every applied object on every apply.

The part people get wrong: assuming set difference is symmetric. It is not: parent - child = parent but child - parent = {empty set} (fieldpath/set.go:104). If you are reasoning about ownership transfer by hand, use RecursiveDifference when you mean “remove this whole subtree”, and plain Difference when you mean “remove exactly these leaves”.

What to go do about it: when you write a controller that manages lists with x-kubernetes-list-type: map, remember that the identity of an element is its sorted key fields, so {name: x, port: 80} and {port: 80, name: x} are the same element — always include every key field in your apply configuration, because an omitted key field with no default produces a different element. When debugging apply conflicts, read metadata.managedFields with kubectl get pod -o yaml --show-managed-fields and compare the fieldsV1 entries as sorted lists; the ordering you see there is this total order, not an accident of serialisation.