Envoy: Replace std::unordered_map with absl::node_hash_map?

[wrowe]

In a number of places throughout the test code, and likely also in user's anticipated behavior of Envoy, it seems that the unordered nature of an unordered map has been ignored. The results are compared to constant strings where the resulting iteration is predicted, and this does not conform to stdc++ unordered map's definition.

For examples, two secrets are documented in an expected list of secrets, and compared to the string dump of an unordered map by SecretManagerImplTest.ConfigDumpHandlerStaticSecrets. In the second case (already fixed) we elected to simplify a configuration to a single element, to avoid this predictable, but inverted ordering that occurs in the libc++/libstdc++ vs msvc cpp runtime library implementations of std::unordered_map.

The later example was discussed at some length https://github.com/envoyproxy/envoy/pull/11335#pullrequestreview-421444954 - however the suggestion to use absl::flat_hash_map turned out to be a non-starter because it is non-deterministic by design. A request to add determinism for purposes such as Envoy seeks turn out to be roundly rejected by the absl authors, see the feedback of the feature request https://github.com/abseil/abseil-cpp/issues/339 for their philosophy.

As a general solution to this and similar observations of small sets for testing that are implemented in Envoy by an unordered_map today, it still seems sensible to migrate to absl::flat_hash_map for the very reason given by the abesil authors. This will obviously break tests which will need to be modified, and possibly could break some user expectations based on expected sequencing. Do we have any thoughts on the Envoy project's approach to this set of issues?

Tagging @mattklein123 and @sunjayBhatia for feedback.

[antoniovicente]

Utilities like ::testing::UnorderedElementsAre may help with test ordering issues. If the problem is non-determinism in string representations created for the benefit of humans, it may make sense to sort those containers while generating the string representation. There is some precedent for sorting while generating string representation in the admin interface.

https://github.com/envoyproxy/envoy/blob/91905443ca743a22a347006e3e447a3d84e4b6e1/source/server/admin/admin.cc#L396

[mattklein123]

One option here would be to bulk migrate from unordered_map to absl::node_hash_map. This should be compatible in all cases, and we can then block unordered_map via format check. This will force the issue and the solutions that @antoniovicente outlines.

[sunjayBhatia]

Utilities like ::testing::UnorderedElementsAre may help with test ordering issues

Yep, we're experimenting with that and also the protobuf MessageDifferencer to compare proto messages with repeated fields. The MessageDifferencer::TreatAsSet is useful for comparing repeated fields have the same unordered contents.

[sunjayBhatia]

On the switch to absl::node_hash_map, per https://abseil.io/docs/cpp/guides/container#recommendation-1 we could prefer new code that doesn't rely on pointer stability to use absl::flat_hash_map, but yeah as per the docs it is safest to switch to absl::node_hash_map immediately, though there may be existing places we can assert we don't need pointer stability and can prefer absl::flat_hash_map

[sunjayBhatia]

There is some precedent for sorting while generating string representation in the admin interface.

Yeah, anything like this that doesn't have tests ensuring ordering seems like it should. Mainly, we're so far seeing cases where stats/proto message repeated fields/etc. are not in a guaranteed order which we can use testing changes to fix as stated above.

[sunjayBhatia]

See: https://github.com/envoyproxy/envoy/pull/11879