ConfigMaps items are generated with random order

[narg95]

Description

kustomize build . produces configmap items in a random order and although it is somehow benign since it produces equivalent YAML files, it would be great if the build outputs are consistent and reproducible.

I tested it with kustomize v4.4.1

[natasha41575]

Would you mind providing a specific example with input, actual output, and expected output? This will help us write a test specifically targeted to the issue you're having.

To your point, however, we store the ConfigMap items in a Go map, which does not guarantee the order. What order are you expecting? We have two options if we want a deterministic order:

1. Alphabetical, which would be pretty simple to implement - just sort the keys before adding them to the ConfigMap data.
2. Preserve the input order. This will be a bigger change (though still small), we'd have to change the underlying data structure, and might have some extremely minor consequences on performance - but then again so would option 1.

I imagine users are expecting option 2, which we can and should do IMO.

[Shatakshi0805]

Hi, I would like to work on this.
I'm currently a beginner so could you please guide me a little so that I can get started to solve this issue

[natasha41575]

It looks like the key-value pairs are being loaded into an unordered map here:

kustomize/api/internal/generators/utils.go

Lines 37 to 56 in 25ee506

	func makeValidatedDataMap(
	ldr ifc.KvLoader, name string, sources types.KvPairSources) (map[string]string, error) {
	pairs, err := ldr.Load(sources)
	if err != nil {
	return nil, errors.WrapPrefix(err, "loading KV pairs", 0)
	}
	knownKeys := make(map[string]string)
	for _, p := range pairs {
	// legal key: alphanumeric characters, '-', '_' or '.'
	if err := ldr.Validator().ErrIfInvalidKey(p.Key); err != nil {
	return nil, err
	}
	if _, ok := knownKeys[p.Key]; ok {
	return nil, errors.Errorf(
	"configmap %s illegally repeats the key `%s`", name, p.Key)
	}
	knownKeys[p.Key] = p.Value
	}
	return knownKeys, nil
	}

We can have this function return something that keeps track of the order of key-value pairs, and preserve that order in the output.

[narg95]

Hi @natasha41575 and @natasha41575, thanks for your answers.

Option 1. with alphabetical order will work for me. I am keeping in source control the kustomize build output and the non-deterministic behavior is giving false positives of changes.

To reproduce the issue build multiple times the following kustomize file, and you will get different outputs which are equivalent but with different order.

kustomize.yaml

configMapGenerator:
  - name: test
    literals:
      - EE10D2E63AF9F498=foo
      - FDC41072BFC0BC7F=foo
      - 32E0817AE855A845=foo
      - 0C6B462C403217C4=foo
      - 024233B4DFB484FC=foo
      - 6E7E3021F1821943=foo
      - DFD86A289C3857EF=foo

Outputs of running three times kustomize build . with the same file:

output 1

apiVersion: v1
data:
  024233B4DFB484FC: foo
  0C6B462C403217C4: foo
  6E7E3021F1821943: foo
  32E0817AE855A845: foo
  DFD86A289C3857EF: foo
  EE10D2E63AF9F498: foo
  FDC41072BFC0BC7F: foo
kind: ConfigMap
metadata:
  name: test-7mt6kd57dt

output 2

apiVersion: v1
data:
 6E7E3021F1821943: foo
 024233B4DFB484FC: foo
 0C6B462C403217C4: foo
 32E0817AE855A845: foo
 DFD86A289C3857EF: foo
 EE10D2E63AF9F498: foo
 FDC41072BFC0BC7F: foo
kind: ConfigMap
metadata:
 name: test-7mt6kd57dt

output 3

apiVersion: v1
data:
  6E7E3021F1821943: foo
  32E0817AE855A845: foo
  024233B4DFB484FC: foo
  0C6B462C403217C4: foo
  DFD86A289C3857EF: foo
  EE10D2E63AF9F498: foo
  FDC41072BFC0BC7F: foo
kind: ConfigMap
metadata:
  name: test-7mt6kd57dt

As you can see each output has different order of configmap items.
I tested it with kustomize v4.4.1

[natasha41575]

@Shatakshi0805 If you would like to work on this, please assign the issue to yourself. You can do so by leaving a comment with just "/assign".

[balalnx16]

Hi @Shatakshi0805, Are you working on this ? If not can I pick this up ?

[balalnx16]

It looks like the key-value pairs are being loaded into an unordered map here:

kustomize/api/internal/generators/utils.go

Lines 37 to 56 in 25ee506

	func makeValidatedDataMap(
	ldr ifc.KvLoader, name string, sources types.KvPairSources) (map[string]string, error) {
	pairs, err := ldr.Load(sources)
	if err != nil {
	return nil, errors.WrapPrefix(err, "loading KV pairs", 0)
	}
	knownKeys := make(map[string]string)
	for _, p := range pairs {
	// legal key: alphanumeric characters, '-', '_' or '.'
	if err := ldr.Validator().ErrIfInvalidKey(p.Key); err != nil {
	return nil, err
	}
	if _, ok := knownKeys[p.Key]; ok {
	return nil, errors.Errorf(
	"configmap %s illegally repeats the key `%s`", name, p.Key)
	}
	knownKeys[p.Key] = p.Value
	}
	return knownKeys, nil
	}

We can have this function return something that keeps track of the order of key-value pairs, and preserve that order in the output.

Hi @natasha41575, go maps can't preserve the order, if we want to retain order we need to change the data-structure, but this data is consumed by a different api at multiple places and looks like it can't be changed, can you provide guidance on how to proceed ?

Please find an example below

kustomize/api/internal/generators/secret.go

Line 53 in 25ee506

if err = rn.LoadMapIntoSecretData(m); err != nil {

[natasha41575]

this data is consumed by a different api at multiple places and looks like it can't be changed

Why can't it be changed? You can also just return a string slice along with the map containing the keys in the desired order.

[balalnx16]

@natasha41575 yes you are right my bad, looks like the keys are getting sorted here, before being used further, so will the proposed solution work ?

kustomize/kyaml/yaml/datamap.go

Lines 15 to 24 in 25ee506

	func SortedMapKeys(m map[string]string) []string {
	keys := make([]string, len(m))
	i := 0
	for k := range m {
	keys[i] = k
	i++
	}
	sort.Strings(keys)
	return keys
	}

[natasha41575]

@balalnx16 That will give us the keys in alphabetical order, which would resolve @narg95's issue. However, I would prefer, if instead of having the keys in alphabetical order, if we can preserve the order of keys from the input. I was thinking we can do this by changing the signature of makeValidatedDataMap to something like

func makeValidatedDataMap( 
 	ldr ifc.KvLoader, name string, sources types.KvPairSources) (map[string]string, []string, error) 

where the returned list of strings contains the keys in the original order that they were added to the map. Do you see any reason why this might be more difficult or not possible?

[balalnx16]

@natasha41575 this is possible, but preserving keys in sorted order is already implemented and in place but is still not preserving the order when generating yaml for the same input, for multiple iterations of the test, that is the reason I'm wondering if this is the right place to do the change. Should we quickly meet to get this sorted ? I'm available on Kubernetes slack as "Balakumaran GR"

[natasha41575]

preserving keys in sorted order is already implemented and in place but is still not preserving the order when generating yaml for the same input, for multiple iterations of the test, that is the reason I'm wondering if this is the right place to do the change

I think I'm not quite following. There is code to sort the map keys but it is just getting loaded into another (unordered) go map so the order can't be preserved. My suggestion is to use an additional data structure to store the keys in order. It may even be worth defining a DataMap type to return instead of a gomap that stores the keys in a sorted order.

If it is easier to just sort the keys into alphabetical order before outputting them that's fine by me, or if there is a better place to make the change that's also fine by me. Any alternative solution that resolves the issue should be fine, if you have questions about any specific implementation feel free to submit a PR and we can review it.

[DaAlbrecht]

As suggested by @natasha41575 I would like to work on this as my first issue. If I understood the current state of this issue correctly, option 2. Preserve the input order would be preferred?

[natasha41575]

@DaAlbrecht yes, preserving input order would be preferred. But if that is too difficult, alphabetical is OK.

[DaAlbrecht]

/assign

[OsirisMedici]

/assign

[mowtschan]

Hi guys!

I tried that PR but unfortunately the issue still persists.

I created a new PR with the simple solution which will keep default order (sorted alphabetically).

please have a look!

Sascha

[narg95]

Hi all,

first PR got closed by Author without merging, seems as if the issue was not fully fixed there, can somebody have a look at the new PR #4785 from @mowtschan? it seems to fix it.

[mowtschan]

Dear @KnVerey
Dear @yuwenma

could you a have a quick look to a very small(just 3 lines!) PR #4785

[gxwilkerson33]

@natasha41575 @KnVerey

I took a run at this issue and found that the order is maintained (alphabetically currently which can be changed to original order easily) until the yaml.JSONToYAML(json) call in resource.go. Which return the yaml with some random order of the resources.

I guess a couple questions:

• Do we have something in kyaml that solves this issue?
• If not does it seem that we should add som functionality to kyaml to solve this issue when converting from JSON to YAML.
  Thanks!

[MaurGi]

this is impactful - we cannot rely on calling kustomize edit add configmap idempotently - we call the same installation twice and it fails!

[gxwilkerson33]

/assign

[stormqueen1990]

I did some investigation on this issue and it would require kubernetes-sigs/yaml#76 to be done. I narrowed this issue down to the sorting in go-yaml v2 not being entirely stable. I noticed this happens when keys that can evaluate to integer values are present. I also noticed that this behaviour happens outside of Kustomize as well.

While experimenting, I saw that bumping go-yaml to v3 solves the problem in the sense that the order is stable although not alphabetical, but I didn't do very extensive testing to check if it'd still be the case when new items are added. This sample shows the issue happening, and if sigs.k8s.io/yaml gets swapped with gopkg.in/yaml.v3, it's possible to see that the issue goes away.

[natasha41575]

Thank you for the investigation @stormqueen1990! I will ping Jordan to see if we can get kubernetes-sigs/yaml#76 merged soon.