Cloud Native Computing Foundation KubeCon + CloudNativeCon Europe 2020 - Virtual, 4 Sep 2020

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Better Histograms for Prometheus - Björn Rabenstein, Grafana Labs

Description

Don’t miss out! Join us at our upcoming events: EnvoyCon Virtual on October 15 and KubeCon + CloudNativeCon North America 2020 Virtual from November 17-20. Learn more at https://kubecon.io. The conferences feature presentations from developers and end users of Kubernetes, Prometheus, Envoy, and all of the other CNCF-hosted projects.

Better Histograms for Prometheus - Björn Rabenstein, Grafana Labs

Robust histogram functionality was added to Prometheus long ago, to be precise in version 0.11.0. The histogram representation as we know it from Prometheus andnow also OpenMetrics is a simple yet powerful and enables many important use cases. However, it is also infuriatingly limited, mostly because of its high per-bucket cost. Björn “Beorn” Rabenstein released the above mentioned Prometheus version in February 2015 and has been dreaming about better histograms ever since. In this talk, he will explain why it is so hard for Prometheus to adopt established techniques known from various academic publications and even practical applications in other metrics-processing systems. To add a silver lining, he will share his latest findings from reignited efforts to finally break through the barriers and bring efficient high-resolution histograms to Prometheus.

https://sched.co/ZekL

A

Hello, everyone, my name is bjorn. I work for a company called grafana labs and I've done one or two things for the prometheus project.

A

My favorite topic in the prometheus world is histograms, or at least one of my favorite topics, and it's actually such a favorite topic that I have given more talks about it than than just this one, and I decided to arrange them in a trilogy and like we know it from popular movie franchises. Those trilogies don't necessarily appear in the right order.

A

So the the logically first uh talk that you should watch first is this one which I gave earlier this year at frostem in brussels, and that's about all the ancient history of prometheus histograms, very important to know and to understand were why we? Why were sorry why we are where we are now?

A

uh The second part of the trilogy happened. First was screened first last year in munich at promcon, and this is kind of the centerpiece. It was supposed to be kind of a trilogy of its own with past present and future. But of course there wasn't enough time, so I decided to cut out the past, which gave me a reason to give this first part later.

A

So this is a very important talk. You should totally watch it if you haven't. um This is about what prometheus histograms can do well right now and what doesn't work that well and what are options to address that in the future.

A

Now this third part of the trilogy which is now this is about actual things I tried out, and I followed a certain idea, and now I want to tell you about the results.

A

This is all planned to be in a big and fat design, dog or rfc that I'll send out very soon and then the community can discuss, and we can see what of my ideas we can actually implement in prometheus and have better histograms all right. One thing has already been improved and I wanted to mention that first, because that was raised in the second part of the trilogy as a problem. That's isolation.

A

Prometheus is kind of almost acid, the tsdb part of prometheus, but I was lacking this isolation aspect and histograms were a favorite victim of that in prometheus 2.17.0. We finally got this implemented just one tiny line in the changelog, but huge step support isolation.

A

um There is a lot of detail to share about this, which I don't have time for here. So I have to refer you to this awesome blog post um by written by myself, shameless blog on the tech blog of my employer, another shameless blog, but here's the ul just look it up, and you see history in quantile. That's the infamous function that gets hit quite often by the lack of isolation.

A

We have isolation. Now, it's all good, you don't even have to think about it. It'll just magically work. So let's come to the remaining problem of histograms or, let's first recap: what are actually the things that work well. This is a slight kind of flashback to the slide of the second torque to one of the slides in the second door.

A

These are things that work well updates score. Calculation. High frequency sampling is mathematically, correct, uh which is actually you can't take for granted, unfortunately, uh and questions like those percentage questions. What percentage of requests in the last hour got a response in 100, milliseconds or less these work really well, but unfortunately they only work well under circumstances.

A

This is why all those or most of these things get a little asterisk and, as you know, this is usually where you read down here terms and conditions apply, and then you know the deal is actually not as good as it sounded first and uh with prometheus histogram, you get this if suitable pockets defined, which is actually hard to define suitable buckets.

A

um There's this other thing histogram quantile, which is what his rooms were actually added for to prometheus, to calculate quantiles like a median or 99th percentile in a correct way across distributed systems- and this is it all works? Fine. It just has a few issues again. This is just recapping from the second talk. The accuracy depends on the bucket layout, and now we come again to bucket layout. Pockets are just super expensive with the current prometheus histogram, so you only can have a few of them and then you have to pick them really wisely.

A

So you need your interesting results. You get here. They should be close to a bucket boundary. So in some areas of the observation range you can have higher resolution buckets, but not everywhere, or you can't really have higher resolution at all yeah, but then, on the other hand, the bucketing scheme must be compatible across the aggregate metrics and across the range of rate calculations, which means you should actually not change the bucket layout.

A

But since it's so hard to find the right one, you are actually tempted to change that quite often, so it's a kind of dilemma and it's really annoying back. Then in talk 2 there was lack of ingestion isolation as a problem stated on the slide. I scratched this because, as I told you, isolation no just works okay, but we still have plenty of remaining problems.

A

This illustrates the cost problem again with a different consequence. So here we have a histogram as you can configure it in go code. If you instrument go code with a prometheus histogram, so this has kind of 10-ish pockets, it's a duration, histogram for essentially http latencies, and then there is also a counter which you shouldn't need because you're already implicitly counting requests in this histogram.

A

But often you just have a counter, and you do this, because this counter is partitioned by status code or path or method or whatever you want it to be partitioned by you. Don't do this with the histogram, because the histogram is essentially as expensive as a counter per bucket. So that's an order of magnitude more expensive than the counter up here. So you're really yeah. You really don't want to partition this by too many dimensions.

A

So that's a very common topic, a counter that is partition at will and a histogram, that's not partitioned at all, which is annoying because sometimes you actually want that partitioning, and you definitely don't want to think about this in the beginning. You want to ask those questions later when you look at your metrics, so let's formulate a wish list for the rest of this talk. What we want to accomplish.

A

First of all, we are like spoiled kids here. We want everything that works well, to continue to work. Well, of course, right.

A

Second, we never want to configure buckets again because that's just annoying, but third, all histograms should always be aggregateable with each other across time and space. I never want to have this problem again and, of course, I want accurate quantile and percentage estimations across the whole range of observations. I don't want to have this area where, oh, no, sorry, you didn't put pockets there.

A

So you can't, you can't have good good, obser good values here, but of course fifth, I want all of that at a lower cost than current histograms, so that I can finally partition histograms at will. So as that greedy small kid, we want everything, let's see how far we can get here um in the second talk, I have already hinted at the solution that is most likely. The solution you go for, which is essentially a very old approach. It's just have a conventional histogram.

A

It just has infinite amount of buckets in a regular, usually exponential or logarithmic marketing schemer. But of course the question is: how can you deal with an infinite amount of buckets, and the basic idea here is that you just account for buckets that actually contain at least one observation and all the empty buckets are ignored.

A

There are different approaches. There are certainly many more than this. This is probably the top three most well known, but perhaps not hdr histogram. You have heard about it. So konos has an implementation which they have on the client part there's open source code and they have a written a paper quite recently about it. But the approach is fairly old and datadog is probably also doing this for a while, but they have recently also published a paper where they explain their histograms.

A

um I should show you the whole link here not covered with my face yeah. So here you can see. All of that. The question is: if this is all so well established and old, why haven't we done this in prometheus in the first place and um yeah? There are a few problems, because prometheus is a bit different.

A

Let's first check out how uh this histogram, uh those sparse histogram, as I call it it's usually done. You have this running on different instances. This is just one instance that is accumulating observations in a histogram. Let's say for a minute and of course every instance is doing that and then kind of at some point in time.

A

They all send these histogram data to a central data storage, where it's collected and with some magic efficiency we'll actually be able to save that store that nicely, but for the monitor target, it's quite easy to then reset everything. So you have completely empty slate and you start again to collect observations.

A

um These histograms should all look slightly different. I was just too lazy to to modify them a bit, so this means every minute you kind of start over. You start from an empty slate. You have zero entropy, all the pockets are empty, and then you only have to account for pockets that receive an observation in that minute. Then you ship it all over and you are done with it.

A

So in prometheus, that's kind of unfortunately, very different prometheus is, as you have probably heard, a pull-based monitoring system, and many people complain about that. But there are a bunch of advantages and this talk should not be about the advantages of a pool based data collection, but we are, we I mean prometheus is doing that right. This is not going to change and we have to deal with it and with small's histogram we have the problem that for prometheus was scrapes or stateless.

A

Essentially, you cannot just reset at will and then decide to send the new histogram. You essentially have to accumulate data forever, and it's also nothing about like minutely anytime. Somebody could come along and script, which is one of the advantages, but also difficult to deal with so in prometheus. This is accumulating accumulating accumulating, as I try to draw here, but uh you can probably guess uh what I mean here.

A

So you get you you, you accumulate a lot of entropy, more and more buckets are populated, and your histograms on the monitor target will take more and more storage space, which is a problem right. So this is kind of where we were where we said this is it doesn't even apply to to prometheus? We can't we just can't do that, but then also studying all the other alternatives, as laid out in the second talk and realizing they also don't work.

A

I started to think perhaps this works after all, and there is essentially a two-part thinking process here. The one is uh about the accumulating entropy, so this is essentially how many buckets you populate. If you calculate, if you accumulate data for a minute and then your chip, it would go back to zero and do more or less the same again right. But if you just do it for two minutes, it's not that you have twice as many buckets populated, because more and more often you will hit a bucket. That already has seen an observation.

A

So at some point um this is the time access here at some point in time you will reach some saturation level or most of the time you will hit the pocket that has already some counts in it. So this is the idea that this, like you will. The idea is that you will approach this saturation uh value quite quickly, so that it's not that much of a deal if you collect for one minute, two minutes three minutes an hour or a day.

A

That's the one idea right. The other idea is that um in principle, prometheus has a concept of resetting counters. It just doesn't have to happen too often it will happen if you restart your binary right. So prometheus loses uh some counts. If that happens, because as it as I said, it's pool based so a a monitor target cannot just decide before I die.

A

I will ship all the metrics, it will just die right, it will just go down and um you scrape quite often like, let's say every 15 seconds, so you might lose a few seconds of code. So if you now reset your histograms, let's say every hour, that's in relative terms, not a lot of loss. So these are the two thoughts right.

A

First, entropy will not accumulate into infinity essentially and second, if it does, I can still reset a histogram, let's say after an hour or so so perhaps it works, and we have to study that another thing that prometheus is doing in its existing histogram is this cumulative nature, which has a lot of advantages um for like an operational quality of life aspect. You can like drop buckets from it.

A

If you want to reduce the isolate the the or solution stuff like that, there are a bunch of things to say about cumulative histogram, but cumulative histograms really don't play well with the sparse nature of sparse histograms. So this is really something we need to change for, sparse, high resolution histograms. We just have to go to ordinary histograms, but that's that's probably something something we can do it's not as fundamental to prometheus as this pull-based approach all right. So this is how sparse histogram looks like very much simplified.

A

You can represent them in different ways. This is the one I chose for experiment. The idea here is that you specify the resolution of the histogram in by saying how many buckets there are for every power of 10. In this little picture I used three because I didn't want to draw hundreds of pockets in practice. This will be somewhere between 20 and 100. 100 will be super high resolution and 20 will be an okay resolution.

A

I just had three here: the buckets are all logarithmic, which you can't see here, because the x-axis is already logarithmic right. So I did it that way, because otherwise the buckets would be super tiny here and super big here. So these they look linear, but they are logarithmic, because the accesses look everything you need a zero bucket, because with logarithmic pockets you will have an infinite bucket density.

A

If you approach zero- and you might just have observations that are zero or very, very small, so you define a zero bucket, which usually has a width that is super super small and in this case I picked 0.1 just that I'm able to draw- and here we have three pockets- um then there's an empty bucket. It's a sparse histogram and then there are three other buckets and you can continue this into infinity.

A

So how does this all work in real life to test that I took observations from a real production cluster here at grafana labs from our cortex cluster? If you know cortex, you know what injester and queria means, but we don't have to worry about that. The only important information is that the queria has a very broad distribution of latencies durations.

A

So this is like a high entropy scenario. Well, the ingestor is more like it has a more a smaller distribution, most of the uh requests, the ingestor processes. It are processed in more or less the same duration.

A

So I I collected the ginormous amount of almost 2 million observations here and a bit more than half a million for the querier and put them all into one histogram, that's kind of a worst case scenario in in practice. You would probably have a histogram along certain dimensions and you would have it on every instance. uh This is really like to to to to brute force tests that put all the observations um into one histogram by the way. The two million here are happening in just two minutes, because it's a super busy cluster.

A

The query is not as busy so there was half a million was over an hour, um so resolution 20 20 buckets per power of 10. In fact, with this genomic histogram only 78 pockets were populated. With this less observations, but higher entropy distribution, 112 buckets were populated a bit more. The span here means how many continuous bands of con subsequent histograms there are right. um So this means there are two groups of pockets.

A

Sorry, there's histograms pockets spans of buckets right, so there are two groups of pockets and there is at least an empty bucket in between, and here all the 112 buckets are actually in a row right. There is no empty bucket in between.

A

You can also go to much higher resolutions, so this is the higher end resolution of 100. We have many more buckets and also more spans, like more often you have some empty pockets in the middle, but overall, like a couple of hundred buckets, I think this is something we can manage, so this gave me some confidence that I'm on the right track.

A

A

What I did next, I thought about how to encode these histograms and represent them first of all in the exposition format and how to then encode them in the tstb.

A

Of course, a lot has been thought about this. This is just um I had to come up with something to try it out in the prometheus context, so there's a zero bucket and then I number the bucket. I start with zero at the bucket. That has an upper bound of one and then I go negative to the left and positive to the right, and this pocket doesn't exist, but it still has a number and then those are organized in spans, as we have seen spans of of consecutive buckets.

A

This is a span that starts at bucket number minus two and has a length of three, and then we have one a gap of one, so the next band has an offset of one and a length of three and so on. So these are small numbers then, and you need very few- very small numbers to describe the whole bucket layout, which is great because small numbers are nicely they. They encode quite nicely with a var int encoding scheme, which is essentially built into a protobuf which simplifies things a lot.

A

The other thing are, of course, the counts in the pockets. They tend to be really high. Like we have seen there are millions of observations in my data set, so you don't want to encode the absolute numbers, but since a histogram is usually like smooth in some way, it goes up and down, but not zigzagging like crazy.

A

This is why um I encode deltas from one bucket to the next. They are usually small, can be encoded with val int quite nicely, and I skip over gaps. Just take the delta here, and this is how it works.

A

um If you put this into a protobuf and you have proto based exposition format, which was by the way what prometheus used in the beginning and only the current prometheus server uses a text-based format, we'll talk about that in a minute. So if you put this all into a protobuf with uh using var end and and specifying those spans and deltas nicely, this is what you get this 78 pocket. Histogram takes 244 bytes, the slightly larger takes a bit more, and even if you go to a really high resolution, you have more buckets.

A

But what is really nice that this is essentially five times the resolution, but the the size on the wire is significantly less than five times right, so you get gets more efficient here with more buckets. So is this a lot or not a kilobyte? um We can look at um how it looks in the current text, format that we use for histograms and it looks fairly repetitive. So this is a very simple kind of ten ish pockets histogram and this one takes 1.6 kilobyte. As you see it here, these are 1.6 kilobytes right, there's.

A

Also this older protobuf format, which is more condensed less repetitive, but even there, as you can see, 300 something bytes for like 12 pockets. Well, here we have kind of the same number of bytes for 100 buckets. So clearly we we're doing something right here right. The exposition format as uh sketched out here, works okay, uh so exposition. Let's say we can handle that right now, storage.

A

This is also interesting. How do we store this? The basic idea that should save us a lot is that we need to just save one time series per histogram, not per bucket. That's what we do right now that was decided back then, just out of simplicity to not change prometheus completely. When you introduce histograms, every pocket is its own time. Series which has huge overheads, as you can see, also because, like cardinality, is that the bottleneck currency in a matrix based monitoring system.

A

So now we, we kind of say we can have a lot of pockets, but it will still be one series per histogram, but that means assemble value is now a sequence of pockets instead of a float, and we can take the bucket deltas to have smaller numbers and those values. Why not? We can encode them in the same way we already encode timestamps, which is a double delta encoding. So I call it triple delta because we double delta encode, a bucket delta right.

A

uh It sounds fancy and then those are encoded with a what we call velvet schema. That's griller style, it's a bit different in detail, but mostly what you know probably know from the gorilla paper.

A

It's again used for timestamps already and we can use it for those triple delters. So if we do this, um we can see how much storage we need for those triple deltas. This completely ignores how to handle like pocket layout and schema changes and everything. It's really just to get the bulk storage nailed down and to find out how much space it needs. I didn't implement a whole tsub.

A

I really just simulated scrapes 80 scrapes for the ingester data set 7 240 for the courier and found out what triple delta we have here and then we see a histogram will take 50 bytes now not on the exposition format, but in the storage, where we want it to be like compressed over time in the time series.

A

uh So every histogram takes 50 bytes here, 70 bytes for the higher entropy case and in the higher resolution case it takes more but again far less than a factor of five, and if you break this down to s bytes used per bucket per sample, then you come up with a fraction of a bite here like 0.5, more or less now, as you might know, in vanilla, prometheus for normal floating point value samples we need like about 1.5 bytes per sample per floating point number, which is 3x now.

A

This is um this is already kind of the worst case scenario here, so we might be at 5x or something or even a bit better, but we also have probably 10x the amount of pockets compared to conventional histograms.

A

So, overall, the storage space will probably be a bit more demanding, but on the other hand we will save a lot with the index so that overall should. Hopefully this is what I hope for we should be more more or comparable like more or less the same efficiency or better querying.

A

That's a big deal because I haven't done concrete research about this, because then you really need to implement the tsdb, and then you have to teach from ql how it can deal with like those complex histograms instead of just individual pockets, but I have good hope that this will actually work out nicely because others have done this.

A

um It's like more than just one group of people has done this, but I have to pick one right and I really like this talk at monitor rama last year about filodb uh evan chan gave this and slide 23 is my favorite. I mean the whole talk is great because it very nicely explains all the problems with prometheus histograms and what you can do about it and slide.

A

23 is showing that a histogram, quantile calculation um is 100 times more efficient in follow db, where they, where they use, approaches quite similar to what what I'm planning here. So this is what gives me hope that it will just work. Okay, let's quickly, go through our wish list and see how this will work out. Everything that works well now should continue to work well. This is mostly true spoiler.

A

Most of the answers here are almost so the one thing that works really well, if you have like an slo which uh reads like 99 of curies to be served in 150, milliseconds or less, then you can just put a pocket boundary at 150 milliseconds, and you have a precise answer from prometheus and now with the um logarithmic histograms, it's just impossible to get a boundary at 150 milliseconds, but you have like very boundaries very close to that. So it's it's almost there right.

A

This is the only thing that works in principle a bit less. Well, uh I never want to configure markets again. I told you: there are just two parameters, the resolution and the zero threshold. This is real. Go code from my proof of concept code. Now, in practice you will never configure the zero threshold. It would just be at this very small value and you never have to change it.

A

And ideally we will find a resolution that is good enough for everyone, but not too high to not be too expensive, and you never have to touch this either it could be 42. That would be fun. It will be somewhere between 20 and 100 200. I'm pretty sure about that, and I yeah we just have to find something right, because if you change this resolution, you run into the next problem. All histograms should always be aggregated with each other across time and space yeah.

A

If you change the resolution you you will not have this, but ideally there is a resolution that will cover most of the cases and only in various special cases. You have to change that.

A

I want accurate, quantile and percentage estimation across the whole range of observations. It's also almost I mean quantile calculations are fairly accurate with a resolution of 100. You have like about one percent of worst case relative error, which is fairly good uh compared to like the industry.

A

What they're all doing a percentage has this one problem that you cannot freely pick where a pocket boundary is, so you have some tiny error there, but overall from my research results, I'm very satisfied about this one, I'm on all of that at lower cost than current histogram, so that I can finally partition histograms at will. This is orange because I really can't tell if it will really be dramatically lower in cost. I'm hopeful that it will.

A

All of this awesomeness will be same price, essentially all lower, hopefully lower, but we have to see all right. There's uh now we're at the end. You can look at all those um rough results in this github repo. It's very rough! Really, it's just my experience. Reboot the code has horrible quality. I just wanted to try things out. I'm writing a proper design, note which I will shortly announce on this mailing list, so follow this and you can pick it up when it's there to be reviewed by the world. These are my talks.

A

This is my email, but um this leads us to the end. So we have five minutes and five seconds left for q. A thanks for your attention and see you in the q. A bye, bye.