DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees • Hacker News Board

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

#21

Post by camel_gopher » Fri, Aug 30, 2019, 6:30 AM UTC

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

I've relied on HDR histograms for that. It looks like your sketches are a bit more performant in the paper, but what was the issue with accuracy that histograms couldn't fulfill?

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

#22

Post by oertl » Fri, Aug 30, 2019, 10:33 AM UTC

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

FYI, already in 2015, I have proposed exactly the same idea as improvement to HdrHistogram. See https://github.com/HdrHistogram/HdrHistogram/issues/54 and corresponding code https://github.com/oertl/HdrHistogram/blob/memory_efficiency.... Unfortuantely, the author of HdrHistogram did not pick up my proposal as that would have lead to major changes and problems regarding compatibility. The mapping to histogram bins is the same as in your code https://github.com/DataDog/sketches-java/blob/master/src/mai.... I am curious, have you been inspired by that?

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

#23

Post by CharlesMasson » Tue, Sep 03, 2019, 3:58 PM UTC

oertl wrote: post #22

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

FYI, already in 2015, I have proposed exactly the same idea as improvement to HdrHistogram. See https://github.com/HdrHistogram/HdrHistogram/issues/54 and corresponding code https://github.com/oertl/HdrHistogram/blob/memory_efficiency... . Unfortuantely, the author of HdrHistogram did not pick up my proposal as that would have lead to major changes and problems regarding compatibility. The mapping to histogram bins i…

I did see that thread and that's what inspired the mapping with the quadratic interpolation.

To clarify though, DDSketch as defined in the paper uses the logarithmic mapping, as our main goal was to make the memory footprint as small as possible. See: https://github.com/DataDog/sketches-java/blob/1650d939f1485f...

The Java implementation abstracts out the index mapping. This let us add alternative ways to map values to indices and we added the method with the quadratic interpolation as it seems to be a good tradeoff between index computation speed and memory footprint.

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

#24

Post by jamesblonde » Sat, Sep 07, 2019, 5:40 AM UTC

oertl wrote: post #22

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

FYI, already in 2015, I have proposed exactly the same idea as improvement to HdrHistogram. See https://github.com/HdrHistogram/HdrHistogram/issues/54 and corresponding code https://github.com/oertl/HdrHistogram/blob/memory_efficiency... . Unfortuantely, the author of HdrHistogram did not pick up my proposal as that would have lead to major changes and problems regarding compatibility. The mapping to histogram bins i…

This sucks, but a problem we have in academia is that you can't reference a closed PR request at a top-tier conference like VLDB. If you wrote up your proposal as a referable document, you should rightly claim that you deserve scholarly recognition. Morally, you deserve recognition (which you are getting here, at least). It's decent of the author to admit he was inspired by you - there are others who would think it is easier to deny it. But there is no recourse, if it's only a PR.