Opensource internals

$setElementOrder: How a Strategic Merge Patch Remembers the Order of a List

15 min read Jay Hubbert

Strategic merge patch merges lists by merge key and loses the client's ordering; a parallel $setElementOrder directive carries the intended order back.

TL;DR: A strategic merge patch merges list items by merge key, so the client’s ordering is thrown away: containers: [a, b, c] and containers: [c, a, b] produce the same merged set. The fix is a second, parallel list carried in the patch under the key $setElementOrder/<field>, containing one map per item with nothing but the merge key. The server-side merge partitions the merged list into “items the patch mentions” and “items only the server has”, sorts each partition independently, and interleaves them back together, with precedence $setElementOrder > patch list order > live list order. JSON merge patch cannot do this at all, because RFC 7386 lists are atomic.

Every Kubernetes object with a list of objects has an ordering, and every Kubernetes object with a list of objects also has a merge key that says which field identifies an item across patches. The Pod spec’s containers list merges on name; env merges on name; volumeMounts merges on mountPath; topologySpreadConstraints merges on topologyKey.

The merge key is what makes strategic merge patch useful. Without it, a patch that sets one field of one container would have to restate the entire list. With it, a patch can say “the container named web now has this image” and leave the other eleven containers alone.

But a merge key is a set membership test, and a set has no order. The moment the API server merges a list by key, the ordering the user wrote down stops being a first-class property of the object. Two clients that disagree about order produce identical patches, and whichever one syncs last wins by accident.

The directive: a parallel list of merge keys

The fix is not to change how lists merge. The fix is to carry the ordering alongside the patch as a separate directive, in a separate key:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:40
const (
	directiveMarker  = "$patch"
	deleteDirective  = "delete"
	replaceDirective = "replace"
	mergeDirective   = "merge"

	retainKeysStrategy = "retainKeys"

	deleteFromPrimitiveListDirectivePrefix = "$deleteFromPrimitiveList"
	retainKeysDirective                    = "$" + retainKeysStrategy
	setElementOrderDirectivePrefix         = "$setElementOrder"
)

The naming convention is the same one used by $deleteFromPrimitiveList: a directive is a key whose name starts with $, followed by a / and the name of the field it applies to. So a patch on a Deployment carries $setElementOrder/spec/template/spec/containers.

The value of that key is a list of maps, one per item, each containing only the merge key. It is a skeleton of the list with all the payload stripped off, which is exactly what is needed to express order and nothing else:

go 
// staging/src/k8s.io/api/core/v1/types.go:4531
	Containers []Container `json:"containers" patchStrategy:"merge" patchMergeKey:"name" protobuf:"bytes,2,rep,name=containers"`

Because the directive is keyed by merge key, not by position, it survives the one thing patches always survive: the item being modified. If the patch also changes the image of container web, the directive still says web is first.

Generating the directive

Diffing a merged list produces three lists, not one: the items to add or change, the items to delete, and the order the client wanted:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:551
func diffLists(original, modified []interface{}, schema LookupPatchMeta, mergeKey string, diffOptions DiffOptions) ([]interface{}, []interface{}, []interface{}, error) {
	if len(original) == 0 {
		// Both slices are empty - do nothing
		if len(modified) == 0 || diffOptions.IgnoreChangesAndAdditions {
			return nil, nil, nil, nil
		}

		// Old slice was empty - add all elements from the new slice
		return modified, nil, nil, nil
	}

For a list of maps with a merge key, the order list is generated only when something actually changed — either the contents differ or the order differs. isOrderSame is the check, and it compares merge keys position by position:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:579
		orderSame, err := isOrderSame(original, modified, mergeKey)
		if err != nil {
			return nil, nil, nil, err
		}
		// append the deletions to the end of the patch list.
		patchList = append(patchList, deleteList...)
		deleteList = nil
		// generate the setElementOrder list when there are content changes or order changes
		if diffOptions.SetElementOrder &&
			((!diffOptions.IgnoreChangesAndAdditions && (len(patchList) > 0 || !orderSame)) ||
				(!diffOptions.IgnoreDeletions && len(patchList) > 0)) {
			// Generate a list of maps that each item contains only the merge key.
			setOrderList = make([]interface{}, len(modified))
			for i, v := range modified {
				typedV := v.(map[string]interface{})
				setOrderList[i] = map[string]interface{}{
					mergeKey: typedV[mergeKey],
				}
			}
		}

Note setOrderList has one entry per element of modified — the client’s complete list, not the subset the patch touches. That matters: the directive is the client’s opinion about the whole list, and the server will use it to place server-only items too.

Lists of primitives work the same way, except there the directive is the modified list verbatim, because a primitive is its own merge key:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:608
		// generate the setElementOrder list when there are content changes or order changes
		if diffOptions.SetElementOrder && ((!diffOptions.IgnoreDeletions && len(deleteList) > 0) ||
			(!diffOptions.IgnoreChangesAndAdditions && !reflect.DeepEqual(original, modified))) {
			setOrderList = modified
		}

The directive is attached to the patch next to the list it describes, under the composite key:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:336
		if len(setOrderList) > 0 {
			parallelSetOrderListKey := fmt.Sprintf("%s/%s", setElementOrderDirectivePrefix, key)
			patch[parallelSetOrderListKey] = setOrderList
		}

Consuming the directive

On the server, the directive and its list are processed together, before the normal merge machinery sees them. The comment at the top of the function states the whole contract:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:1102
// mergePatchIntoOriginal processes $setElementOrder list.
// When not merging the directive, it will make sure $setElementOrder list exist only in original.
// When merging the directive, it will try to find the $setElementOrder list and
// its corresponding patch list, validate it and merge it.
// Then, sort them by the relative order in setElementOrder, patch list and live list.
// The precedence is $setElementOrder > order in patch list > order in live list.
// This function will delete the item after merging it to prevent process it again in the future.
// Ref: https://git.k8s.io/design-proposals-archive/cli/preserve-order-in-strategic-merge-patch.md
func mergePatchIntoOriginal(original, patch map[string]interface{}, schema LookupPatchMeta, mergeOptions MergeOptions) error {
	for key, patchV := range patch {
		// Do nothing if there is no ordering directive
		if !strings.HasPrefix(key, setElementOrderDirectivePrefix) {
			continue
		}

Two details in the body matter. First, the directive is deleted from the patch once consumed, so the normal merge pass does not try to merge a list named $setElementOrder/containers into the object:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:1132
		delete(patch, key)

Second, the merged list is computed first (using the ordinary merge rules) and the ordering is applied afterwards, as a separate step. Ordering is not part of merging; it is a post-processing pass over the result.

Before the merge happens, the directive is validated against the patch list: every item in the patch list must appear in the directive, in the same relative order. A directive that contradicts the patch is a client bug and is rejected outright:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:1001
	patchIndex, setOrderIndex := 0, 0
	for patchIndex < len(nonDeleteList) && setOrderIndex < len(typedSetOrderList) {
		if containsDirectiveMarker(nonDeleteList[patchIndex]) {
			patchIndex++
			continue
		}
		mergeKeyEqual, err := mergeKeyValueEqual(nonDeleteList[patchIndex], typedSetOrderList[setOrderIndex], mergeKey)
		if err != nil {
			return err
		}
		if mergeKeyEqual {
			patchIndex++
		}
		setOrderIndex++
	}
	// If patchIndex is inbound but setOrderIndex if out of bound mean there are items mismatching between the patch list and setElementOrder list.
	// the second check is a sanity check, and should always be true if the first is true.
	if patchIndex < len(nonDeleteList) && setOrderIndex >= len(typedSetOrderList) {
		return fmt.Errorf("The order in patch list:\n%v\n doesn't match %s list:\n%v\n", typedPatchList, setElementOrderDirectivePrefix, setOrderList)
	}

The error surfaces in the API server as a 400 Bad Request, because the handler maps the sentinel error onto that status:

go 
// staging/src/k8s.io/apiserver/pkg/endpoints/handlers/patch.go:811
	case mergepatch.ErrBadJSONDoc, mergepatch.ErrBadPatchFormatForPrimitiveList, mergepatch.ErrBadPatchFormatForRetainKeys, mergepatch.ErrBadPatchFormatForSetElementOrderList, mergepatch.ErrUnsupportedStrategicMergePatchFormat:
		return errors.NewBadRequest(err.Error())

Partitioning into two lists

Here is the crux of the whole mechanism. The merged list contains two kinds of item: the ones the patch mentioned, and the ones the client never mentioned but that exist on the server (added by another controller, or by a previous patch that was not part of this diff). The directive only orders the first kind, because the directive is derived from the client’s list.

So the merged list is split:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:1235
// partitionPrimitivesByPresentInList partitions elements into 2 slices, the first containing items present in partitionBy, the other not.
func partitionPrimitivesByPresentInList(original, partitionBy []interface{}) ([]interface{}, []interface{}) {
	patch := make([]interface{}, 0, len(original))
	serverOnly := make([]interface{}, 0, len(original))
	inPatch := map[interface{}]bool{}
	for _, v := range partitionBy {
		inPatch[v] = true
	}
	for _, v := range original {
		if !inPatch[v] {
			serverOnly = append(serverOnly, v)
		} else {
			patch = append(patch, v)
		}
	}
	return patch, serverOnly
}

For lists of maps the same partition happens, but membership is decided by merge key rather than by value:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:1253
// partitionMapsByPresentInList partitions elements into 2 slices, the first containing items present in partitionBy, the other not.
func partitionMapsByPresentInList(original, partitionBy []interface{}, mergeKey string) ([]interface{}, []interface{}, error) {
	patch := make([]interface{}, 0, len(original))
	serverOnly := make([]interface{}, 0, len(original))
	for _, v := range original {
		typedV, ok := v.(map[string]interface{})
		if !ok {
			return nil, nil, mergepatch.ErrBadArgType(typedV, v)
		}
		mergeKeyValue, foundMergeKey := typedV[mergeKey]
		if !foundMergeKey {
			return nil, nil, mergepatch.ErrNoMergeKey(typedV, mergeKey)
		}
		_, _, found, err := findMapInSliceBasedOnKeyValue(partitionBy, mergeKey, mergeKeyValue)
		if err != nil {
			return nil, nil, err
		}
		if !found {
			serverOnly = append(serverOnly, v)
		} else {
			patch = append(patch, v)
		}
	}
	return patch, serverOnly, nil
}

The split is done on the merged list, not on the live list, so items that were modified by the patch land in the “patch” partition even if the client never named them.

Merging the two partitions back

Each partition is now sorted independently, and the two are interleaved. The sort key for the patch partition is the directive; the sort key for the server-only partition is the live list, because the server-only items have no directive entry:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:397
// normalizeElementOrder sort `patch` list by `patchOrder` and sort `serverOnly` list by `serverOrder`.
// Then it merges the 2 sorted lists.
// It guarantee the relative order in the patch list and in the serverOnly list is kept.
// `patch` is a list of items in the patch, and `serverOnly` is a list of items in the live object.
// `patchOrder` is the order we want `patch` list to have and
// `serverOrder` is the order we want `serverOnly` list to have.
// kind is the kind of each item in the lists `patch` and `serverOnly`.
func normalizeElementOrder(patch, serverOnly, patchOrder, serverOrder []interface{}, mergeKey string, kind reflect.Kind) ([]interface{}, error) {
	patch, err := normalizeSliceOrder(patch, patchOrder, mergeKey, kind)
	if err != nil {
		return nil, err
	}
	serverOnly, err = normalizeSliceOrder(serverOnly, serverOrder, mergeKey, kind)
	if err != nil {
		return nil, err
	}
	all := mergeSortedSlice(serverOnly, patch, serverOrder, mergeKey, kind)

	return all, nil
}

And the interleave itself is a best-effort merge that preserves the relative order of both partitions. It compares two items by their positions in the live list — the one common ordering both partitions share a reference to:

go 
// staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:418
// mergeSortedSlice merges the 2 sorted lists by serverOrder with best effort.
// It will insert each item in `left` list to `right` list. In most cases, the 2 lists will be interleaved.
// The relative order of left and right are guaranteed to be kept.
// They have higher precedence than the order in the live list.
// The place for a item in `left` is found by:
// scan from the place of last insertion in `right` to the end of `right`,
// the place is before the first item that is greater than the item we want to insert.
// example usage: using server-only items as left and patch items as right. We insert server-only items
// to patch list. We use the order of live object as record for comparison.
func mergeSortedSlice(left, right, serverOrder []interface{}, mergeKey string, kind reflect.Kind) []interface{} {
	// Returns if l is less than r, and if both have been found.
	// If l and r both present and l is in front of r, l is less than r.
	less := func(l, r interface{}) (bool, bool) {
		li := index(serverOrder, l, mergeKey, kind)
		ri := index(serverOrder, r, mergeKey, kind)
		if li >= 0 && ri >= 0 {
			return li < ri, true
		} else {
			return false, false
		}
	}

The less closure returns two values: “is l less than r” and “were both found”. If either item is absent from the live list — a brand-new item the client added, say — the comparison is not decidable, and the merge falls back to taking the item from the right-hand partition, which is the patch partition, first. That is the mechanism by which “directive > patch list > live list” is actually implemented: unknown items go to the front of their partition, and the patch partition goes in front of the server-only partition.

The result is a single list where:

  • the relative order of the items the client named is exactly what the client asked for;
  • the relative order of the server-only items is whatever the live object had;
  • server-only items are interleaved into the client’s list rather than appended to the end or dropped.

Why JSON merge patch cannot do this

The other patch type, JSON merge patch (RFC 7386), has a completely different implementation strategy, and it is instructive to compare. JSON merge patch cannot express “delete this list item” at all — the only way to remove something is to set it to null — so the three-way merge has to be computed as two two-way patches:

go 
// staging/src/k8s.io/apimachinery/pkg/util/jsonmergepatch/patch.go:28
// Create a 3-way merge patch based-on JSON merge patch.
// Calculate addition-and-change patch between current and modified.
// Calculate deletion patch between original and modified.
func CreateThreeWayJSONMergePatch(original, modified, current []byte, fns ...mergepatch.PreconditionFunc) ([]byte, error) {
	if len(original) == 0 {
		original = []byte(`{}`)
	}
	if len(modified) == 0 {
		modified = []byte(`{}`)
	}
	if len(current) == 0 {
		current = []byte(`{}`)
	}

	addAndChangePatch, err := jsonpatch.CreateMergePatch(current, modified)
	if err != nil {
		return nil, err
	}
	// Only keep addition and changes
	addAndChangePatch, addAndChangePatchObj, err := keepOrDeleteNullInJsonPatch(addAndChangePatch, false)
	if err != nil {
		return nil, err
	}

	deletePatch, err := jsonpatch.CreateMergePatch(original, modified)
	if err != nil {
		return nil, err
	}
	// Only keep deletion
	deletePatch, deletePatchObj, err := keepOrDeleteNullInJsonPatch(deletePatch, true)
	if err != nil {
		return nil, err
	}

Two patches, then filtered: the current -> modified patch keeps only non-null values (the additions and changes), and the original -> modified patch keeps only the nulls (the deletions). The two are then conflict-checked against each other:

go 
// staging/src/k8s.io/apimachinery/pkg/util/jsonmergepatch/patch.go:62
	hasConflicts, err := mergepatch.HasConflicts(addAndChangePatchObj, deletePatchObj)
	if err != nil {
		return nil, err
	}
	if hasConflicts {
		return nil, mergepatch.NewErrConflict(mergepatch.ToYAMLOrError(addAndChangePatchObj), mergepatch.ToYAMLOrError(deletePatchObj))
	}
	patch, err := jsonpatch.MergePatch(deletePatch, addAndChangePatch)
	if err != nil {
		return nil, err
	}

The conflict check is a plain recursive overlap test, and it treats two lists of different lengths as a conflict, because a JSON merge patch replaces lists wholesale:

go 
// staging/src/k8s.io/apimachinery/pkg/util/mergepatch/util.go:111
	case []interface{}:
		switch typedRight := right.(type) {
		case []interface{}:
			if len(typedLeft) != len(typedRight) {
				return true, nil
			}

			for i := range typedLeft {
				if conflict, err := HasConflicts(typedLeft[i], typedRight[i]); err != nil || conflict {
					return conflict, err
				}
			}

			return false, nil
		default:
			return true, nil
		}

That is the fundamental asymmetry: JSON merge patch’s lists are atomic values, so there is no place to hang an ordering directive. Strategic merge patch’s lists are collections of identified items, which is exactly what makes an ordering directive expressible — and exactly what makes the ordering problem exist.

The cost of all this

There is a real cost, and it is worth naming. Every list merge now carries a second list in the patch, and the server does a linear scan of the live list for every comparison in mergeSortedSlice — index() is O(n), so the interleave is O(n²) in the number of list items. For the list sizes the API allows (a handful of containers, a few dozen env vars) this is irrelevant. For a list of 5000 items it would not be.

There is also a semantic wart: the directive describes the client’s view of the whole list, but the server only uses it to order the items the client mentioned plus whatever it can infer about the rest. Two clients with contradictory ideas about the order of a shared list will fight, and the resolution is not “last writer wins” but “whoever’s directive covers more items”.

Wrapping up

The one thing to remember: a strategic merge patch carries list order in a separate key, $setElementOrder/<field>, whose value is a list of merge-key-only maps — one per item, in the client’s intended order. The directive is generated in diffLists (staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:551) and consumed in mergePatchIntoOriginal (staging/src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go:1110).

The part people get wrong: the directive does not replace the merge. It is applied after the merge, by partitioning the merged list into patch items and server-only items and interleaving them with mergeSortedSlice (patch.go:427). If you expect the server to place a brand-new item exactly where you wrote it in the file, understand that the placement is a best-effort merge against the live list, not a positional splice.

What to go do about it: if you are writing a controller or an operator that manages a merged list, send the ordering explicitly rather than relying on the server to guess. strategicpatch.CreateTwoWayMergePatch already sets DiffOptions.SetElementOrder: true (patch.go:141), so plain kubectl apply and kubectl patch --type strategic preserve order for you; if you build patches by hand, use strategicpatch.CreateThreeWayMergePatch (patch.go:2101) and keep the $setElementOrder key intact. And if you ever see invalid patch format of setElementOrder list or the “doesn’t match $setElementOrder list” error from validatePatchWithSetOrderList (patch.go:977), the cause is a directive that contradicts the patch list — not a malformed YAML document.

KubernetesInternalsApimachinery