It's unclear from reading the docs what value means. Given that a bucket is always a range of values, what is this single value? Upper bound? Lower bound? Midpoint?

@ramaraochavali do you know? I think I tried to suss this out with a test but couldn't determine it, nor could I found precise doc for it other than the sparse comments in the circlhist header file.

@ramaraochavali do you know? I think I tried to suss this out with a test but couldn't determine it, nor could I found precise doc for it other than the sparse comments in the circlhist header file.

I think you need to either use hist_bucket_to_string() or hist_bucket_to_double() and some other fields to figure out the bounds of the bucket and express that in the output.

Oh I didn't see hist_bucket_t APIs and I think I can use those to get a bucket-min and bucket-max and ultimately use those to control the width of the histogram bar when rendering.

I'll go off and do that.

Depending on the distribution of the histogram, this may not be a good algorithm for reducing bucket count. It is often preferable to keep more buckets near the upper/lower limits, and fewer buckets in the middle.

Can we get away with not limiting the buckets at all, and just using whatever the histogram library gives us? I believe it is a finite number of buckets, and not excessively large.

I'm not sure what the maximum is from the histogram library, but I couldn't get it to give that many buckets, and felt that based on my experiments if I set 64 buckets that would generally not require any interpolation. The interpolation is just defensive to protect against a future version of circlhist, or a certain data pattern that I have not tried, resulting in a lot more buckets.

I agree with you putting the remainder at the beginning is not necessarily best but I'm not sure why another distribution would be better, and so I opted for what would be easiest :)

I'm not sure what the maximum is from the histogram library, but I couldn't get it to give that many buckets, and felt that based on my experiments if I set 64 buckets that would generally not require any interpolation. The interpolation is just defensive to protect against a future version of circlhist, or a certain data pattern that I have not tried, resulting in a lot more buckets.

I agree with you putting the remainder at the beginning is not necessarily best but I'm not sure why another distribution would be better, and so I opted for what would be easiest :)

I'd say for now, just add an ENVOY_BUG(buckets <= 100) or something and remove the interpolation code entirely.

That's probably OK. We could also decide on that at call-sites by calling getDetail(MAX_BUCKETS + 1) and then asserting at call-site we got <= MAX_BUCKETS.

Hmm, 190 buckets is a lot; but it's probably not so many that it would be difficult to render, right? But let me express this a different way: why try to keep the native resolution of the underlying histogram, if we then change that resolution immediately by combining buckets? I believe the underlying design of this histogram has dynamic bucket widths. What if you are combining buckets are drastically different widths? I think that could result in strange distortions of the histogram. I'm wary of doing this type of math on histograms without fully understanding how it changes the data.

If we just want to render geometry it's probably OK, but I wanted to annotate with actual values as text. I think 30-40 is about that max we'd want to interpolate to.

My thinking is that circlhist is reasonably good at picking buckets logarithmically needed for a dynamic range, and that incrementally changing them by combining neighbors until you get the number of buckets you want should avoid being misleading. I think changing from just a bucket 'value' to a range (min,width) makes me feel like we are not distorting the data with this transform.

But in any case this isn't changing the existing behavior; this would (at least for now) only be used for graphical rendering. We could then iterate on how we combine them.

Another option is to have the C++ always yield all the buckets and sort out interpolation in JS.

I ran a few more experiments and found that the number of buckets appears to go up with the log of the number of distinct values I record. With 10M entries I get to 550 buckets. So from a memory and bandwidth perspective it might be OK to just stream out all the buckets as there will not be so many that it will OOM the binary.

But from a UI perspective we are going to want to combine buckets. We could do that in JS instead if that makes you feel better about this C++ interface. That would also make it possible for the UI to show detailed sub bucket info when hovering over an interpolated histogram bar.

Oh, that's interesting.

This is way outside the scope of this PR, but here's a thought: do we get any value from the current histogram implementation with dynamic buckets? For prometheus, we always coerce to a fixed set of buckets. For this new use case, you need to significantly coerce the buckets (although at least you're just moving them, not changing any of the bounds). Would it make more sense to just use a really simple histogram implementation with fixed buckets?

Assuming that's a topic for another day, I think in this PR I'd prefer having the JS do the bucket-merging for now so that we're not committing to a specific bucket merging behavior in Envoy; any client can merge in any way they see fit (linear, logarithmic, fancy-math, etc).

I think we don't get much value from the dynamic impl right now in terms of detailed buckets, but I suspect it currently helps us provide accurate p95, p99, p99.5 etc across a wide range of data values. And with this series of PRs we'd get detailed bucketing for a single proxy via its admin endpoint. I think this coercion I proposed would rarely be activated in practice; it'd only come into play with a very wide dynamic range of actual data.

We could implement the coercion in C++ but let the endpoint query-params determine whether to coerce at all or what the max bucket-count should be. I think in practice we'll get less than 30 buckets; but I don't have actual data for this yet.

However I'm warming up to moving the coercion to JS as that way a UI could easily be added to show the detail within a merged bucket. So I'll remove the coercion from this PR. I'll move status to 'draft' for now and and re-open soon. Thanks for working through this.