Pushgateway and quadratic complexity of pushing metrics

[Rafał Dowgird]

Dear and Esteemed Prometheus developers,

I'd like to discuss with you a performance problem with Pushgateway, namely that the complexity of adding n metrics might get quadratic (O(n^2)). Details follow.

We have a mixed push/scrape system where Pushgateway handles some of the metrics which come from batch jobs. While migrating some jobs to Pushgateway we hit a performance bottleneck. We worked around this by sharding Pushgateway. Still the sharded setup is more complex and the amount of data wasn't that big, so we investigated the Pushgateway side of things.

It seems that the root of the problem is that every push operation causes recalculation of hashes for all metrics already existing in the database. This is how the consistency check logic works at present.

I have created a simple benchmark to isolate/demonstrate the problem: https://github.com/dowgird/pushgateway/commit/e0629ecb999c2f22cf098c87c78fc71cd0414733

The output demonstrates that subsequent pushes of metrics get linearly slower:

I: 100 elapsed:220.379138ms diff:220.379138ms
I: 200 elapsed:505.576881ms diff:285.197743ms
I: 300 elapsed:841.153205ms diff:335.576324ms
.
.
.
I: 2700 elapsed:21.806380441s diff:1.391117119s
I: 2800 elapsed:23.229272852s diff:1.422892411s
I: 2900 elapsed:24.674250223s diff:1.444977371s

Possible fix doesn't look very complicated algorithmically (memorizing the hashes should work). Code-wise it's a bit more complex, which is a part of why I'm writing this message. I can contribute the fix but this would require some discussion of client API.

The other part is that I understand from documentation and communications on github issues that Pushgateway is not meant to be high performance. That said, I still think it would be beneficial to remove this particular performance bottleneck - there seem to be other people hitting it (https://github.com/prometheus/pushgateway/issues/643 might be caused by this).

Would you be open to accepting a fix for this issue?

--
Rafał

[Giedrius Statkevičius]

Hello,

I'm not "a Prometheus dev" but this is something that I am interested in. Could you open up a PR with the benchmark and the fix? I'll help out with reviewing.

Thanks,
Giedrius

[Rafał Dowgird]

Hi Giedrius, thanks for looking at this!

Before I submit the fix PRs (plural, see below) I need some feedback on the intended implementation. I don't see a simple fix which could be contained in Pushgateway only. It seems that some changes to Prometheus code (prometheus/client_golang to be specific) are required in addition to modifying Pushgateway.

The current logic for the duplicates check is in client_golang in the Gather() method: https://github.com/prometheus/client_golang/blob/aea1a5996a9d8119592baea7310810c65dc598f5/prometheus/registry.go#L424 Unfortunately this API can only take a whole set of metrics and answer if it's consistent. It does so by calculating hashes for the whole set, which in case of Pushgateway leads to quadratic complexity. Pushgateway keeps a dynamic set of metrics and needs to keep track of its consistency and you cannot do it efficiently using the current Gather() API.

So my plan is to:

  * factor out the consistency logic from client_golang's Gather() so that it also works for a dynamically changing set of metrics
    * basically expose a data structure which keeps the set of metrics with their hashes
  * use this logic in Pushgateway

The alternative is to do a Pushgateway-only fix but this would require duplicating the logic for consistency checks, so it's probably worse than the fix above.

Does that sound sensible?

--
Rafał

--
You received this message because you are subscribed to the Google Groups "Prometheus Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to prometheus-devel...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/prometheus-developers/b53b5c14-a4ea-4c21-8a53-aeb1cb0a6036n%40googlegroups.com.

[Bjoern Rabenstein]

Hi Rafał, hi Giedrius,

Thanks for your interest.

Any provable performance improvement that doesn't come with a huge
increase in code complexity will certainly be welcome.

However, I have a few comments below, with the possible conclusion
that the effort isn't really worth it in this case (or that the effort
would be way more involved than you currently anticipate).

On 06.01.25 22:03, Rafał Dowgird wrote:
>
> The current logic for the duplicates check is in client_golang in the
> Gather() method:
> https://github.com/prometheus/client_golang/blob/aea1a5996a9d8119592baea7310810c65dc598f5/prometheus/registry.go#L424
> Unfortunately this API can only take a whole set of metrics and answer if
> it's consistent. It does so by calculating hashes for the whole set, which
> in case of Pushgateway leads to quadratic complexity. Pushgateway keeps a
> dynamic set of metrics and needs to keep track of its consistency and you
> cannot do it efficiently using the current Gather() API.

I wrote this code (both the PGW side and the client_golang side) long
ago. My memory might be patchy, but I'll try to recall the rationale
from back then.

Whenever the PGW (or in fact any program instrumented with
prometheus/client_golang) is scraped, the logic implemented in the
Gather() method takes place, i.e. in that moment the current state of
metrics to be exposed is checked for self-consistency. In the way it
is implemented, this is linear with the number of metrics (O(n)), so
it is generally an accepted burden and hasn't really been perceived as a
problem except in very specialized edge cases (kube-state-metrics is
an (in-)famous example). Part of the reason is that a scrape happens
relatively rarely (a few times per minute) so that the resource need
to serve metrics is usually negligible compared to the resource need
of the actual primary task the instrumented program is doing.

So what happens during pushing? What we do in the current code is to
essentially simulate what would happen if the PGW gets scraped with
the newly pushed metrics added to the already existing metrics. This
appears quite costly, but the rationale here is that the same cost
will be paid again when the PGW is scraped for real. While I said
above that scrapes are relatively rare (a few times per minute),
pushes happen even less often.

This means in turn that all the effort to make the consistency check
less expensive will be small compared to the effort required during
scraping.

While you are technically right that the consistency check is O(n*m)
with n being the total number of metrics in the PGW and m being the
number of pushes, I doubt that this is the relevant metric to look
at. In the same way, you could say that the scrape is quadratic with n
being the total number of metrics and m being the number of
scrapes. As long as you scrape more often than you push, you have to
also change the whole way scraping works to actually make a
dent. (This is what kube-state-metric did. They removed all layers of
abstractions and are now rendering the metrics output directly. In the
PGW case, you could probably follow a less radical approach, but you
would still break contracts like Gather() being responsible for the
final self-consistency check.)

Unless of course you are using the PGW for a use case it is not
designed for. You quoted me saying "Pushgateway is not meant to be
high performance", but that's not what I said. Pushgateway performs
just fine for the use case it was designed for. If you really use it
in a situation where you push more often than you scrape, I would be
concerned about more things than just performance. You are now
funneling a whole lot of metrics through a SPOF. The PGW has no HA
story whatsoever, following the idea that it is for metrics that only
update a few times a day or so, so that nothing bad will happen if it
has some downtime. If a huge number of your frequently updating
metrics are lost while the PGW is down, you have a bigger problem than
performance.

--
Björn Rabenstein
[PGP-ID] 0x851C3DA17D748D03
[email] bjo...@rabenste.in