Undeterministic order in output

[lstrojny]

The output or encode() is non-deterministic when creating multiple metrics of the same type.

So basically:

pub fn repro() -> String {
    let mut registry = <prometheus_client::registry::Registry>::default();

    let gauge = Family::<MyLabels, Gauge<f64, AtomicU64>>::default();
    registry.register("test", "help", gauge.clone());

    gauge
        .get_or_create(&MyLabels {
            label: "one".into(),
        })
        .set(0.1);
    gauge
        .get_or_create(&MyLabels {
            label: "two".into(),
        })
        .set(0.2);

    let mut buffer = String::new();

    encode(&mut buffer, &registry).unwrap();

    buffer
}

This will sometimes return this:

HELP test help.
# TYPE test gauge
test{label="one"} 0.1
test{label="two"} 0.2
# EOF

And sometimes this:

HELP test help.
# TYPE test gauge
test{label="two"} 0.2
test{label="one"} 0.1
# EOF

I would expect the metrics to be somehow sorted deterministically.

[mxinden]

I expect this to be due to the use of HashMap in Family. It could be an option to use a different, ordered datastructure.

Related discussion prometheus/client_golang#483.

I would expect the metrics to be somehow sorted deterministically.

While I understand the value of sorted output for the sake of debugging, I am not sure it is worth than the (expected) performance hit.

[lstrojny]

That makes sense. My use case here is unit testing where I need to assert on a stable output, so I could even make a potential sorting flag dependent on cfg(test). How about adding optional sorting?

[mxinden]

How about adding optional sorting?

Have to give this more thought, though not opposed to it. Might as well always do it in debug mode.

Again, might be worth exploring replacing the HashMap and thus getting sorting for free.

[08d2]

The text encoding of metrics is defined by the spec, and the spec doesn't define any sort order, so callers can't assume any sort order.

[cratelyn]

I was looking into this for the same reasons as @lstrojny, and found this thread on the rust-lang board:

https://users.rust-lang.org/t/hashmap-vs-btreemap/13804

checked just now and BTreeMap is significantly faster than HashMap for many of
the benchmarks in our json-benchmark. (In the table lower is better.)

Benchmark	BTreeMap	HashMap
parse canada.json	10.9ms	11.9ms
stringify canada.json	11.3ms	11.6ms
parse citm_catalog.json	5.5ms	11.2ms
stringify citm_catalog.json	1.4ms	3.3ms
parse twitter.json	2.5ms	2.9ms
stringify twitter.json	0.6ms	0.9ms

It seems like in addition to getting sorting for free, we may be likely to actually see a performance improvement for many cases, as the serde-json maintainer notes there.

As @lstrojny notes above, stable output is often very helpful for ensuring deterministic results in unit tests. If the existing hash map behavior needed to be preserved, a similar approach that internally abstracts over the two kinds of maps could offer the benefits of both.

The issue linked above prometheus/client_golang#483 also seems to indicate that the Go client also sorts metrics, with the open question there being how to optionally disable sorting for families with an especially large exposition.

I'm sympathetic to @08d2's point above, but I see only upside, without any real downside. If we stand to (a) improve performance, (b) improve testing ergonomics, and (c) mirror the behavior of other languages' client libraries by moving to a BTreeMap, does #128 seem like a reasonable change to you all?

[cratelyn]

👋 hello! it's been a couple of months so i thought i would follow up on the message above. deterministic output seems like it would be a pleasant improvement, and would likely improve performance. do people have any input on that?

[cratelyn]

i noticed this issue again while working on unit tests for #257. it would be great if there was a way to somehow encode metrics in a deterministic order. without this, there is not a way to check if metric families work properly when populated with multiple time series.

[mxinden]

Why would a BTreeMap perform better than a HashMap on label sets? Unless we have a good benchmark proving the performance optimization, I don't think we should switch.

To the actual issue at hand, namely sorting, either sorting in debug mode, or a sorting function for unit tests only, seems like the best option.

[cratelyn]

Why would a BTreeMap perform better than a HashMap on label sets?

because for many real world workloads, ordering comparison is faster than hashing values. hash maps are asymptotically faster, but that asymptotic behavior exists behind different constants.

much like serde-json, a labeled metric family is often dealing with a relatively finite and heterogenous set of values. comparing two labels e.g. canary to production only needs to perform a single character comparison, versus the work needed to compute a hash.

Unless we have a good benchmark proving the performance optimization, I don't think we should switch.

i totally understand.

i sketched out a branch that replaces the HashMap with a BTreeMap, and found these results when running the family benchmarks:

HashMap

     Running benches/family.rs (target/release/deps/family-c4eeb6b9d7382ee4)
Gnuplot not found, using plotters backend
counter family with [(&'static str, &'static str)] label set
                        time:   [33.715 ns 33.824 ns 33.941 ns]
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild

counter family with Vec<(&'static str, &'static str)> label set
                        time:   [43.622 ns 44.128 ns 44.629 ns]

counter family with Vec<(String, String)> label set
                        time:   [63.550 ns 63.925 ns 64.296 ns]
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild

counter family with custom type label set
                        time:   [16.221 ns 16.242 ns 16.264 ns]
Found 2 outliers among 100 measurements (2.00%)
  1 (1.00%) low mild
  1 (1.00%) high severe

BTreeMap

     Running benches/family.rs (target/release/deps/family-72f8832cb4631e98)
Gnuplot not found, using plotters backend
counter family with [(&'static str, &'static str)] label set
                        time:   [10.565 ns 10.633 ns 10.710 ns]
                        change: [-68.869% -68.609% -68.311%] (p = 0.00 < 0.05)
                        Performance has improved.

counter family with Vec<(&'static str, &'static str)> label set
                        time:   [17.844 ns 17.907 ns 17.969 ns]
                        change: [-59.438% -59.064% -58.700%] (p = 0.00 < 0.05)
                        Performance has improved.

counter family with Vec<(String, String)> label set
                        time:   [43.033 ns 43.144 ns 43.252 ns]
                        change: [-33.280% -32.946% -32.593%] (p = 0.00 < 0.05)
                        Performance has improved.

counter family with custom type label set
                        time:   [5.0564 ns 5.0752 ns 5.0902 ns]
                        change: [-69.139% -68.998% -68.877%] (p = 0.00 < 0.05)
                        Performance has improved.

this looks very promising! for our existing benchmarks, metric families are nearly 3 times as fast! moreover, the mild and severe outliers also go away, meaning that BTreeMap seems to be both faster and more consistent, besides the ergonomic benefits we'd get by emitting sorted values that motivated this issue.

---

for the record, these benchmarks were run on an AMD Ryzen 9 7900X3D 12-Core Processor, with 128Gb of ram.

[mxinden]

Why would a BTreeMap perform better than a HashMap on label sets?

because for many real world workloads, ordering comparison is faster than hashing values. hash maps are asymptotically faster, but that asymptotic behavior exists behind different constants.

much like serde-json, a labeled metric family is often dealing with a relatively finite and heterogenous set of values. comparing two labels e.g. canary to production only needs to perform a single character comparison, versus the work needed to compute a hash.

Appreciate the insight. Thank you!

Benchmarks indeed look promising.

Want to update #128 with your change and the benchmark? Either pushing to the branch or creating a new pull request.

Anyone here can confirm these performance gains on a real-world deployment?