Methods for dynamically determining bin sizes for histograms

[thomas....@googlemail.com]

Hello Prometheus Developers,

I just got back from an awesome Promcon2017 conference -
thanks to everyone who made that happen!

A brief discussion with Richard Hartmann encouraged me (thanks) to
write my first post on the Prometheus developer list.

At the conference it was mentioned that Prometheus currently doesn't
have a way to dynamically size the bins of histograms.
Besides being mathematically challenging and difficult to do in a
distributed setting, I wanted to bring some food for thought to the table.

The astropy [1] python library, which is used for astronomical computations,
contains several methods for dynamically compute the bins
of a histogram based on some statistical properties of the data.

The contained methods include:

[2.0] [2.1] ‘blocks’ : use bayesian blocks for dynamic bin widths
[3] ‘knuth’ : use Knuth’s rule to determine bins
[4.0] [4.1]‘scott’ : use Scott’s rule to determine bins
[5] ‘freedman’ : use the Freedman-Diaconis rule to determine bins

It was mentioned that some of the Prometheus team already looked into
this but perhaps they can still find something new.

Unfortunately my stats-fu is not strong enough to tell
whether / how those methods could be applied/adapted to streaming
timeseries data but perhaps some of those methods could be
useful for Prometheus.

Cheers,
Thomas

[1] http://docs.astropy.org/en/stable/api/astropy.stats.histogram.html
[2.0] http://adsabs.harvard.edu/abs/2012arXiv1207.5578S
[2.1] https://jakevdp.github.io/blog/2012/09/12/dynamic-programming-in-python/
[3] Optimal Data-Based Binning for Histograms https://arxiv.org/abs/physics/0605197
[4.0] Scott's rule http://onlinelibrary.wiley.com/doi/10.1002/wics.103/abstract
[4.1] https://www.researchgate.net/publication/250594515_Scott's_rule
[5.0] Freedman–Diaconis rule https://en.wikipedia.org/wiki/Freedman%E2%80%93Diaconis_rule

[Ben Kochie]

The difficulty with dynamic buckets is that we need identical buckets across all instances of a job in order for the histogram functions to work correctly.  Dynamic bucketing doesn't work well with time-series data.  We need all samples from history so a restart will trigger a new bucketing, which will be incompatible with the old bucketing.  Plus this doesn't account for dynamic changes in the future.

Basically, we have to use static buckets in Prometheus.  Our idea for a "workaround" for this problem is to improve the way we expose and store buckets.  If we can make the storage efficient enough for a "large" amount of buckets, in the range of 100s, we can basically cover "practically all possible buckets"

--
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-developers+unsub...@googlegroups.com.
To post to this group, send email to prometheus-developers@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/prometheus-developers/b24ef822-0602-42f8-a582-55ed5ae133a7%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Richard Hartmann]

On Mon, Aug 21, 2017 at 10:42 AM, Ben Kochie <sup...@gmail.com> wrote:
> The difficulty with dynamic buckets is that we need identical buckets across
> all instances of a job in order for the histogram functions to work
> correctly. Dynamic bucketing doesn't work well with time-series data. We
> need all samples from history so a restart will trigger a new bucketing,
> which will be incompatible with the old bucketing. Plus this doesn't
> account for dynamic changes in the future.

This covers my concerns; plus that you would need to sync bucket sizes
across any possible set of Prometheus servers scraping them, i.e.
globally.

Still, the approach of "look at the data to determine your buckets"
makes sense. Maybe it would make sense to reach out to data scientists
and ask "if you had X fixed buckets and unknown data, what buckets
would you choose?"

Information about what the underlying data distribution looks like
would also need to be exposed or deducted to make this useful. This
might be a valid use case for ENUMs.


Richard

[Brian Brazil]

I don't see how enums help here at all. For the underlying data, you need event logging.

Brian

 

Richard

--
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-developers+unsub...@googlegroups.com.
To post to this group, send email to prometheus-developers@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/prometheus-developers/CAD77%2BgT3wA7e2zZOo9RmUBr6k5ROhLXiivQj4BgPdzmhvP1e9A%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

Brian Brazil

www.robustperception.io

[Richard Hartmann]

On Mon, Aug 21, 2017 at 12:51 PM, Brian Brazil
<brian....@robustperception.io> wrote:
> I don't see how enums help here at all. For the underlying data, you need
> event logging.

The exporter could know what the underlying data looks like (and yes,
this would blow it up compared to just storing the buckets) and expose
"this bucketing would fit best".


Richard

[Brian Brazil]

I could imagine that as a separate debug endpoint using a t-digest or something, you still want to know how it changes under various conditions so event logging would give the best answer.

--

Brian Brazil

www.robustperception.io

[Ben Kochie]

+1

Typically I inform bucketing decisions based on SLOs.

Using event logs to inform bucketing decisions is also a technique I've used when SLOs are less obvious, or not the only goal.

[Brian Brazil]

And thinking on this a bit, doing this in the binary would lose us the performance benefits of histograms as against summaries so probably not the best of ideas.

Brian

 

--

Brian Brazil

www.robustperception.io

--

Brian Brazil

www.robustperception.io

[Jack Neely]

You can use a log-linear / significant figures method similar to HDRhistogramp[1].  This always produces known bucket intervals, so your histograms are compatible and aggregatable with a set level of accuracy.

However, its storing this data efficiently on disk, as Ben mentioned, where this gets challenging.  100s of buckets per histogram and its handy when they can be represented without having to include buckets with 0 observations.  Dealing with resets and working with the data structure atomically are also concerns, but touch on a lot of previous conversations.

Jack

[1]: http://hdrhistogram.org/

On Mon, Aug 21, 2017 at 4:42 AM, Ben Kochie <sup...@gmail.com> wrote:

The difficulty with dynamic buckets is that we need identical buckets across all instances of a job in order for the histogram functions to work correctly.  Dynamic bucketing doesn't work well with time-series data.  We need all samples from history so a restart will trigger a new bucketing, which will be incompatible with the old bucketing.  Plus this doesn't account for dynamic changes in the future.

Basically, we have to use static buckets in Prometheus.  Our idea for a "workaround" for this problem is to improve the way we expose and store buckets.  If we can make the storage efficient enough for a "large" amount of buckets, in the range of 100s, we can basically cover "practically all possible buckets"

To unsubscribe from this group and stop receiving emails from it, send an email to prometheus-developers+unsubscri...@googlegroups.com.

To post to this group, send email to prometheus-developers@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/prometheus-developers/b24ef822-0602-42f8-a582-55ed5ae133a7%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
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-developers+unsub...@googlegroups.com.
To post to this group, send email to prometheus-developers@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/prometheus-developers/CABbyFmq3Qy3_vEKyK%3D0_QrUehexD%2BuKXQv4YHZj3fNvCC5D0Og%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

Jack Neely
Operations Engineer
42 Lines, Inc.

[Björn Rabenstein]

This is one of my favorite research topics. I come back to it whenever
I have a bit of time (which is "almost never" right now as there are
too many more mundane things keeping me busy).

Obviously, making buckets cheaper in general, and in particular those
that aren't currently receiving any increments, would help a lot.
(That's Jack's suggestion, essentially.) I have championed that for a
while, but it needs more support throughout the ecosystem (and in
particular the support of those that are more active in development
than I currently can be).

A more involved approach would be to not represent histograms as naive
buckets but in some other way. There is a lot of research about it
(q-digest and t-digest are examples), but to my current knowledge,
they all lack certain attributes needed for the Prometheus data and
execution model, mainly concerned with the ability to express “give me
the φ-quantile over the timespan t” with arbitrary values for φ and t,
selected only after collection.

Once life and work is in a bit calmer state I hope to solidify some of
my ideas of how this can be pulled off for Prometheus and write
something up.

--
Björn Rabenstein, Engineer
http://soundcloud.com/brabenstein

SoundCloud Ltd. | Rheinsberger Str. 76/77, 10115 Berlin, Germany
Managing Director: Alexander Ljung | Incorporated in England & Wales
with Company No. 6343600 | Local Branch Office | AG Charlottenburg |
HRB 110657B

[mbon...@gmail.com]

​Hi,

We are building an application for track the metrics of all services in our company (we work in a cloud infra team). Since all services communicate each other through a load balancer, we parse the access log and expose to prometheus metrics like RPM, status codes, response times, etc. For response times, we expose metrics with the Histogram Object. The problem is that the response times of each service (more than 1000) are very different from each other. So pick a right bucket size is hard.

We are thinking to build our own exporter and change buckets sizes dynamically based on some criteria (it doesn't matters now). The idea is recalculate the buckets sizes once a day or something like that. We know that we wont be able to get quantiles in periods between the buckets sizes changes, but we hope improve accurency for some metrics.

What do you think about this?

[Brian Brazil]

That sort of approach could work, though I'd expect much rarer updates to be sufficient. Beware that you won't be able to aggregate up across services with different buckets.

However with that many services, I'd question if histograms should be used at all. Even with just 10 buckets we're talking over 12k time series for this single metric and that's per balancer.

--

Brian Brazil

www.robustperception.io