Cloud Native Computing Foundation PromCon North America 2021, 1 Nov 2021

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Sparse High-resolution Histograms in the Prometheus TSDB - Ganesh Vernekar & Dieter Plaetinck

Description

Don’t miss out! Join us at our next event: KubeCon + CloudNativeCon Europe 2022 in Valencia, Spain from May 17-20. Learn more at https://kubecon.io The conference features presentations from developers and end users of Kubernetes, Prometheus, Envoy, and all of the other CNCF-hosted projects.

Sparse High-resolution Histograms in the Prometheus TSDB - Ganesh Vernekar & Dieter Plaetinck, Grafana Labs

The Prometheus TSDB has gained experimental support to store and retrieve the new sparse high-resolution histograms. The talk will present exciting results fresh off the press: savings in storage and indexing space, benchmarks for storing and retrieving the new histograms, interesting tidbits encountered during implementation.

A

Hello, everyone- I am ganesh vaneker. I am one of the prometheus team member and I am also a maintainer of prometheus dsdb.

B

And I am dieter plating. I've been working on monitoring systems for about 10 years, but I've never actually contributed to prometheus before so this is kind of my first time working with tsdb and I'm really enjoying it so far and I really enjoy histograms. So when I had the chance to work on this project, I I was very excited.

B

So our colleague, jordan robinstein, already gave many presentations about histograms and how they're currently implemented in prometheus, what some of the shortcomings are and his ideas for better histograms.

B

um But first we should probably just do a quick recap. What is a histogram anyway? So basically, a histogram is a way to categorize your numeric observations into ranges, and this is very useful for looking at distributions of data, for example, for latency metrics.

B

So in this example here on the left, you can see that there were three observations that were smaller or equal to 0.25. Then there were six observations between 0.25 and and a half and so forth. So this is a really useful way to get a good understanding of your distribution of data. It lets you calculate percentiles and so forth.

B

The way this is currently implemented in prometheus is you have a separate series for every single bucket, so you can see here you have your different buckets. They all have a label declaring one of the bounds and, of course they have the number of metrics in each and then you also have some additional series, for example, a sum series with the sum of all the samples and the count which counts all the samples.

B

So there are some shortcomings here that we intend to improve on, but first of all, of course, whatever currently works should keep working, that's kind of obvious, um the second one.

B

This is kind of a one of the bigger problems I would say with the current implementation of histograms is that you have to manually, define your buckets and you basically have to make a guess around what the values will look like and then, hopefully you know your data won't go out of bounds or you'll lose precision and it's kind of a clunky method.

B

So in the new version we would rather just do away with that completely and just automatically come up with all the right bucket sizes. Third, we want to have correct aggregation both across time and also across labels, and especially when you have histograms with different bucket layouts. Those different layouts should be chosen so that they are compatible and mergable, basically, so that you don't lose uh that you can correctly aggregate them and don't lose any uh data quality.

B

And then, of course, you need to be able to have very accurate estimations. You need to have a low error rate and you so that you can compute correct quantiles and percentage estimations.

B

And finally, we believe that if we can lower the cost of the histograms, then we can make partitioning much more feasible, because I suspect that right now, many instagram users don't partition as much as they can like, for example, partitioning by an http status code label or by a route or a path label is currently not not so common. But if we, if we make histograms much cheaper, then you can partition as much as you want.

B

There is a big design dock that bjorn wrote. It goes in the design very in depth and it's a very interesting read. So if you want to understand it more, you should look at the dark, because currently in this presentation we can only really cover a small bit of the design.

A

So we recently had a hackathon at grafana labs, so beyond detail, and I thought it would be cool to get this design dock into a working prototype.

A

And before we jump into the prototype, let's see why high resolution histograms are so useful by the way the heat map that you are seeing right now is reading the data from our prototype itself. So let's see what we can figure out from this heat map. Initially the request.

A

I have some kind of short band of latencies and then, after some time the latency stabilizes and you can see there are way a lot of request for some buckets which show up as red and after some time a new canary was tested and you can see the latency dropped and but it became less practical predictable because it was spread around the big time and you can clearly see when this new canary was deployed into the prod and all the latencies just dropped and spread across a big range.

A

And after some time a part of the system started, behaving weirdly and the latency shot up. You can see two bands of slowness there. It could be some heavy operation or some cold cash, and you can see exactly the time when the issue started and the issues when the issue stopped and after the issue had stopped the latency just kept on increasing and increasing until it became stable and within a band.

A

So this is the kind of visualization that we would like to get from high resolution histograms, which not feasible right now because of expensive buckets.

A

But in this prototype like in this stock, we are going to talk about three things. One is: how do we expose this uh higher resolution histograms and how do we scrape it and then how can we encode these histograms efficiently into a tsdb and we benchmark the space taken by these new histograms in the tsd.

B

So, as far as the instrumentation goes, um this is based on. You know the the current implementation and, in fact, if you look at the orange line here, what this does is so this exposes the conventional histograms using using the current method, but it gets a little bit more interesting when we look at these three items here, so the sparse buckets factor that basically defines the precision of your histogram, and this is a growth factor and it describes whenever you go from one bucket to the next bucket.

B

It describes how much growth you see so that, as you, keep adding adding more buckets, they also keep growing and growing um and because we automatically allocate buckets. However, many are needed to accommodate your data. You probably want to set some kind of limit, because otherwise, in theory, it can just grow infinitely.

B

In this case, we set a maximum number of 150 and the way we implement that limit. It's it's in two ways. So the first way is we can reset a bucket, and this declares that we could reset up to once per hour and basically, what a reset means is.

B

You start a new chunk and you get rid of all the buckets that were at some point used by some data and you only start using the buckets that are needed for the current data and hopefully and commonly that will be enough to get you under that limit.

B

If that's not sufficient to reach your defined limit, then we have an a second solution, which is it start decreasing the precision. So that's something to keep in mind that in certain cases, when you hit your limit, you might need to or it will automatically start growing your buckets and your precision will go down a little bit.

B

So the encoding of how all the data after it gets scraped, actually gets saved into histogram chunks, there's. So by the way, this is a little bit simplified. I left out a bunch of other details, but basically there's two main things in the beginning of the chunk. You have your metadata and it describes the exact shape of your histogram and then after that are the individual histogram samples.

B

So the metadata there's two key entries here. One is the schema, and this is simply a number that describes the growth factor. So we saw a growth factor of 1.1 earlier that basically gets encoded as a simple integer, and then we declare which buckets are actually being used because in theory you could have an infinite number of buckets. The way it works is and by the way some of these buckets might be used for data. Some of those buckets might need to be skipped because they don't have any data and the way we implement.

B

This is quite simply as a list that says you know basically, for example, skip 10 buckets that are not used. Then you have 20 buckets that are used. Then you have this many that are not used, then you have that many that are used again and so forth.

B

So this basically describes the entire range of buckets that are used, and this is also why we call them sparse histograms, because in this infinite space of buckets, if you only use a subset of them, this is a very efficient way to not have the overhead of all the buckets that are not used, and I also just want to point out that using just these two items in the metadata, you can get the exact description of how the histogram looks like as far as the actual data goes.

B

um This is inspired by by the current xor encoding of simple time series there's just uh there's some more fields and then, of course, the buckets. This is a variable length field, but basically the first histogram sample that comes in um we're just going to store all the fields, raw as integers and as floats and as a sequence of integers. Then the second histogram will show we're storing deltas and the third and the fourth and so forth. Histograms we just store delta of delta everywhere.

B

The one exception here is the sum field. So the sum of all the observations because that's a floating point number. We use the xor encoding from the gorilla paper just like the standard, xor encoding of time series and all of this data gets written into a bit stream, which of course gets serialized as a chunk of bytes and so yeah. This contains the full metadata describing the histogram format and then all the histogram samples.

A

And talking about our test setup, we instrumented the cortex gateway on our graphene cloud. Dev clusters with both conventional and high resolution, histograms cortex gateway, is the component which sits in front of our cortex clusters and all the read and write traffic goes through it and we set up two prometheus one of them scraping the conventional histograms and one of them only skipping the high resolution histograms and we compared the storage at saturation, which means all the buckets that had to be filled were filled and there was less fastness.

A

And this is how the data looked like in the conventional histograms we had 14 fixed buckets, which means you have 14 time series data a time series in the dsp for each bucket, and you just saw that we have some additional series for each histogram, one of them being the infinite bucket. One of them is some uh series. One of them is count series, so add those three up. Then you have 17 tsb series per histogram and for sparse high resolution. Histograms, the number of buckets varies in our data.

A

We saw that it varied between one bucket to 128 buckets and it's dynamic, and because all of these buckets are stored in the same chunk, we only need one time series in the dsdb to represent a histogram in all its buckets. So we have two.

B

A

Two data blocks under observation here, one of them escaped data for 18 hours, which had 249 histograms, and you can see the number of series. It's multi, there's a multiple of 17 for the conventional multiple of one for this pass. Similarly, block b is spanning two hours and 144 histograms, though both of them skate the same thing. The block a has nearly the double number of histograms, because there was a rollout. So few labels changed, so you get more histograms in the next slide.

A

We will see how this dynamic buckets look like. So all of these, uh this is a snapshot of few of the series from the blocks for the sparse histogram.

A

You can see that the number of buckets vary in huge numbers, for example, if uh for querying the query can be expensive or cheap, so the latency of query can span a huge range, so you have you have to cover too many buckets and if you take example like a gateway timeout, it's mostly set at a fixed time, so you are always going to observe a fixed uh time for that particular histogram. So it's always going to fall in a single bucket, so you won't really need more than one bucket for that histogram.

A

So this shows that uh partitioning histograms into multiple histograms with different labels is not going to be expensive because the buckets are dynamic here now, let's look at our benchmark results yep this. This is pretty interesting. It also give our mind so the first column you see the reduction in index size.

A

The reduction is like 94 and 93 percent for the block, and if you look at it carefully, it is a 17 x, reduction or little more than 17 x reduction, which was the ratio between number of series required for conventional passes to come, and it's little more than 17x, because in the index store the series information, but in the sparse histogram you don't have to store the le label. So there comes the additional little more than 17x reduction in the index.

A

And if you look at the chunks, though we have more buckets in this past histogram, you still get an efficient coding, so there is like 43 and 48 reduction in the size taken by the chunks themselves, and if you combine both the sizes like the both index and chunks, overall reduction is like 48 to 60 percent it.

A

It can vary based on how long your data is, and this also means the memory that the head block would take, will be little less because it will be you it's using the same encoding as used in the block and the number of series is. It takes a lot of space in the memory usually and that's going to reduce with a single series per histogram.

A

So there comes the overall savings in memory and a space.

B

So, um let's start to recap our conclusion. So far, so there's very little configuration as we saw in the instrumentation section. You basically have to define a precision, but even that we can just default to something seen like 1.1 and you probably want to specify a limit. But hopefully you will never reach it. Just like in our experiments, as you saw, we reached up 228 buckets.

B

We never reached our 150 limit, but if you don't specify those then basically have zero config and it should just work out of the box and with that growth factor of 1.1, we also observe a significantly more uh basically precise, bucket boundaries. So we see a difference in precision of about an order of magnitude compared to the the manual bucket assignment, and then I also want to point out that, as your observations, you know if they go well beyond the range that you originally thought, your data might lie in.

B

You still get to maintain that same precision.

B

So in the conventional current implementation of histograms, I I hope you would have accounted for some of your data and configured your buckets properly, because if your data goes beyond that range, suddenly, your your relative error starts going up significantly, but but not with the new histograms and they're fully mergeable and aggregatable. We didn't really go too much in detail for that, but uh you'll you'll just have to check the design talk.

B

If you want to understand more about how how that works, but basically it's about when you have different bucket layouts how they are compatible and you can merge them.

A

And we saw that there was nearly half of a half of reduction of storage requirement and there was more than 90 percent of index reduction. So far in node test and depending on how many buckets you have chosen for your existing conventional histogram, you will see similar reduction in the index and the sparseness makes it very efficient to have partitioning in the histogram. We saw the buckets varied from 1 to 128.

A

So when you have more partitioning, it doesn't mean there is a linear cost, as we have for conventional histograms, where the buckets are fixed and and basically we have a sublinear growth, because the buckets are dynamic.

B

There are two limitations that I think are worth pointing out. The first one is obviously the limit that we already pointed out earlier.

B

You probably want to set some kind of limit to make sure you know if your data is really very.

B

If you have a lot of variability in your data that you control the amount of buckets that you use and, as I pointed out earlier, we can just try to cut a new chunk and usually that works, but in certain cases that might not be sufficient and then the precision will automatically get lowered. We currently don't have a way to really expose that, but this is something to think about in the future to maybe make that a little bit more clear in the ui and then finally, we currently don't have custom bucket boundaries.

B

So if you want to answer questions such as, what's the percentage of uh requests that were exactly 250 milliseconds or up to 250 milliseconds, and you want to set very specific human-friendly boundaries like that- that's currently not supported, but I think bjorn has some ideas on how to make that work.

A

And the work that we have done till now only contains scraping and ingesting into the tstp and retrieving histograms at a tstp layer that raw histograms and we have a lot of future work to be done, uh the main one being the promptil support, so that promgial can natively work with these past histograms and also we could create sparse histograms in recording rules using this promptu.

A

The heat map that you saw we needed to do some hacksaw to get it working, but it did not use any native, pronounced support and the next one because we want to uh uh one of our goal, was what is working right now, should keep working.

A

So we need a compatibility layer to bridge the conventional and sparse histogram so that they can work together and we want to play with more data and determine the query cost and because there is a big reduction in index, we uh we think that it will be a reduction in lookup cost for these histograms.

A

So that is just a hypothesis, but we need to play with a lot more data and return. The query cost.

B

So that's it! um If you're interested in the code, you can check the sparse histogram branches of the prometheus project and the client goaling repositories. So that's just all of our experimental codes. So far I emphasize experimental um and yeah. We would love to hear what you think so both ganesha's and my twitter handles are listed here. So please, please, let us know what you think and I hope that everyone has a great rest of the conference. Thank you very much.

A