Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

arxiv.org

Post reply on HN
Print view View original

11–20 of 24 posts

Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

#11

Post by homin »

heinrichhartman wrote: post #5
homin wrote: post #2

Author here. We wanted to be able to graph p99, p99.9 metrics with arbitrary ranges, and found the existing solutions were not accurate enough for our needs. Happy to answer any questions. Code here: https://github.com/DataDog/sketches-go https://github.com/DataDog/sketches-py https://github.com/DataDog/sketches-java

Nice work! Averaging percentiles is well-known to give terrible results. Glad to see more people, taking this problem serious, and providing viable alternatives! A note on Accuracy: At Circonus, we have been using a version of HDR-Histograms [1] for many years to aggregate latency distributions, and calculate accurate aggregated percentiles. Accuracy was never a problem (worst-case error If I read your evaluation res…

HDR is great for the use-case when you can bound your range beforehand and merging is not a requirement, but those were also the reasons we needed to develop DDSketch.

Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

#12

Post by homin »

ryanworl wrote: post #4
homin wrote: post #2

Author here. We wanted to be able to graph p99, p99.9 metrics with arbitrary ranges, and found the existing solutions were not accurate enough for our needs. Happy to answer any questions. Code here: https://github.com/DataDog/sketches-go https://github.com/DataDog/sketches-py https://github.com/DataDog/sketches-java

Is it fair to say that if you know the min and max values for your dataset, the DDSketch (fast) is strictly better than HDR Histogram for applications where lack of runtime memory allocations and add performance is critical?

In theory yes, but none of our implementations specifically prevent reallocations as we were not targeting this use-case. It should be easy enough to add though.

Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

#13

Post by zawerf »

homin wrote: post #2

Author here. We wanted to be able to graph p99, p99.9 metrics with arbitrary ranges, and found the existing solutions were not accurate enough for our needs. Happy to answer any questions. Code here: https://github.com/DataDog/sketches-go https://github.com/DataDog/sketches-py https://github.com/DataDog/sketches-java

No background in this, my layman interpretation is: Track a histogram with log-scaled bins. These are easy to increment and only takes up size of the number of bins in terms of memory. Two histograms from different servers can easily be merged together since they use the same bins.

But then I got completely lost in the math to show why this guarantees anything. What's actually preventing the scenario where everything falls into the same or just a few bins? (as so happens in the real world where all your data is of a relatively similar order of magnitude) For example what would happen if my data is random from 1 to 10? And on a different server random 1000 to 1010?

Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

#14

Post by heinrichhartman »

homin wrote: post #11
heinrichhartman wrote: post #5

Earlier quoted context omitted.

Nice work! Averaging percentiles is well-known to give terrible results. Glad to see more people, taking this problem serious, and providing viable alternatives! A note on Accuracy: At Circonus, we have been using a version of HDR-Histograms [1] for many years to aggregate latency distributions, and calculate accurate aggregated percentiles. Accuracy was never a problem (worst-case error If I read your evaluation res…

HDR is great for the use-case when you can bound your range beforehand and merging is not a requirement, but those were also the reasons we needed to develop DDSketch.

Sorry, but I don't follow this argument:

(1) HDR-Histogram merges are 100% accurate and very fast (few microseconds)

(2) The range of HDR-Histogram is bounded in the same way that floating point numbers are bounded. Hence the name "High Definition Range":

> For example, a Histogram could be configured to track the counts of observed integer values between 0 and 3,600,000,000,000 while maintaining a value precision of 3 significant digits across that range.

http://hdrhistogram.github.io/HdrHistogram/

Circllhist offers a default range of 10^-128 .. 10^+127, which has been more than ample for all use-cases I have seen.

https://github.com/circonus-labs/libcircllhist/blob/master/s...

Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

#15

Post by heinrichhartman »

zawerf wrote: post #13
homin wrote: post #2

Author here. We wanted to be able to graph p99, p99.9 metrics with arbitrary ranges, and found the existing solutions were not accurate enough for our needs. Happy to answer any questions. Code here: https://github.com/DataDog/sketches-go https://github.com/DataDog/sketches-py https://github.com/DataDog/sketches-java

No background in this, my layman interpretation is: Track a histogram with log-scaled bins. These are easy to increment and only takes up size of the number of bins in terms of memory. Two histograms from different servers can easily be merged together since they use the same bins. But then I got completely lost in the math to show why this guarantees anything. What's actually preventing the scenario where everything…

> number of bins in terms of memory

Less than that, with the appropriate compression scheme (sparse encoding).

> But then I got completely lost in the math to show why this guarantees anything.

You get guarantees on _relative_ error:

- 100 to 110 is a 10% error

- 1000 to 1010 is a 1% error

Depending on your logarithmic base, you can detect errors up to a certain relative %-tage.

Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

#16

Post by zawerf »

heinrichhartman wrote: post #15
zawerf wrote: post #13

Earlier quoted context omitted.

No background in this, my layman interpretation is: Track a histogram with log-scaled bins. These are easy to increment and only takes up size of the number of bins in terms of memory. Two histograms from different servers can easily be merged together since they use the same bins. But then I got completely lost in the math to show why this guarantees anything. What's actually preventing the scenario where everything…

> number of bins in terms of memory Less than that, with the appropriate compression scheme (sparse encoding). > But then I got completely lost in the math to show why this guarantees anything. You get guarantees on _relative_ error: - 100 to 110 is a 10% error - 1000 to 1010 is a 1% error Depending on your logarithmic base, you can detect errors up to a certain relative %-tage.

That makes a lot sense, thank you! I was stuck on the visualization analogy where choosing the wrong axes for the histogram makes it useless (e.g., when all the data falls into the same bin you can't see the shape of the distribution). But for answering quantile, this doesn't matter. Even if P1 and P99 are in the same bin you still know what their values are up to a multiplicative constant. Fantastic!

Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

#18

Post by germanjoey »

Hey, congratulations, this is a really cool algorithm! Thanks for sharing it.

I'm interested in this paper because I worked on a somewhat related problem some time ago, but got stuck on how to handle data that morphs into a mixed-modal distribution. Modes that are close together are no big deal, but modes that are spaced more exponentially apart are tricky to deal with. For an example of something that would be in DataDog's purview, it would be like trying to sketch the histogram of response times from an endpoint that sometimes took a "fast" path (e.g. a request for a query whose result was cached), sometimes took a "normal" path, and sometimes took a "slow" path. (e.g. a query with a flag that requested additional details to be computed) If the response times from the slow path is much bigger than the others, e.g. by an order of magnitude, their statistics might essentially drown-out the data from the other two paths since you're using them to calculate bin size.

I noticed you had some results from measuring DDSketch's performance on a mixed-modal distribution that looked pretty good (that "power" distribution on the last page). I was wondering if you had done any more investigation in this area? E.g. how messy/mixed can the data be before the sketch starts to break down?

Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

#19

Post by morei »

homin wrote: post #2

Author here. We wanted to be able to graph p99, p99.9 metrics with arbitrary ranges, and found the existing solutions were not accurate enough for our needs. Happy to answer any questions. Code here: https://github.com/DataDog/sketches-go https://github.com/DataDog/sketches-py https://github.com/DataDog/sketches-java

Minor nit from paper: The range for Moments is listed as bounded due to overflow risk using floats.

This may be true for the provided implementation, but it's not inherent to the algorithm. The calcuation of the higher order moments would normally done entirely in the log domain where there's little risk of overflow.

Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees

#20

Post by MrBuddyCasino »

MrBuddyCasino wrote: post #17

How does this compare to t-digest? https://github.com/tdunning/t-digest/blob/master/docs/t-dige...

Ah there is a short comparison in "related work":

The problems of having high relative errors on the larger quantiles has been addressed by a line of work that still uses rank error, but promises lower rank error on the quantiles further away from the median by biasing the data it keeps towards the higher (and lower) quantiles [7], [8], [17]. The latter, dubbed t-digest, is notable as it is one of the quantile sketch implementations used by Elasticsearch [18]. These sketches have much better accuracy (in rank) than uniform-rank-error sketches on percentiles like the p99.9, but they still have high relative error on heavy-tailed data sets. Like GK they are only one-way mergeable.

Post reply on HN