DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
1–10 of 24 posts
Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
#2Author 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
Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
#3great!
so main difference is more accuracy on average or more the fact the maximum
error possible is bounded?
Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
#4Author 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?
Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
#5Author 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 results correctly, you also found HRD-Histograms to be as-accurate or more-accurate, than DDSketches, correct?
The differentiator to HDR Histograms seems to be merging speed and size, where DDSketches seem to have an edge.
One thing that is not immediately clear to me from reading the paper is, how much of the distribution function can be reconstructed from the sketch? E.g. for SLO calculations one is often interested in latency bands: "How many requests were faster than 100ms?" [2].
Is it possible to approximate CDF values ("lower counts") from the sketch with low/bounded error?
[1] https://github.com/circonus-labs/libcircllhist
[2] http://heinrichhartmann.com/pdf/Heinrich%20Hartmann%20-%20La...
Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
#6Author 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
Thanks for publishing this. I admit I have only skimmed the paper and plan to look closer later today. My first critical thought was "I wonder why section 4 doesn't make comparisons to t-digest?" I think of t-digest as the most common mergeable streaming modern quantile algorithm in practice. Why didn't you include it in your comparisons?
Either way - looks very promising, I am excited to take a closer look and possibly use this. Thanks!
Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
#7Author 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
Looks really cool. Thanks for releasing the source.
How would you compare this to somewhat similar algorithm like t-digest [1]? I've only just skimmed your paper so I see some key differences, but thought it would be good to have your insight.
Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
#8great! so main difference is more accuracy on average or more the fact the maximum error possible is bounded?
Most previous sketches used what they called "rank accuracy". So if your inputs were [2^1, 2^2, ...., 2^1000]. The actual p95 is 2^950, and a 0.01 rank-accurate sketch would be allowed to give you any value between 2^940 to 2^960 (which can be up to a factor of 1024 away).
A 0.01 relative-accurate sketch has to give you a value within a factor of 100.
The above example is contrived, but with real web request data, there is often a very long tail, and rank accurate sketches quickly start giving values far from the actual percentiles.
So to more directly answer you question, it's that the maximum error possible is bounded.
Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
#9Author 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
Thanks for publishing this. I admit I have only skimmed the paper and plan to look closer later today. My first critical thought was "I wonder why section 4 doesn't make comparisons to t-digest?" I think of t-digest as the most common mergeable streaming modern quantile algorithm in practice. Why didn't you include it in your comparisons? Either way - looks very promising, I am excited to take a closer look and possi…
T-digest is definitely the best rank-accuracy sketch for higher percentiles in terms of size. However, it was much slower than GK, and we found that by increasing the rank-accuracy of GK (taking the penalty of a larger sketch-size), the results were not too different. Both of course had the issues inherent in all rank-accurate sketches in the higher percentiles over long-tailed data.
Re: DDSketch: A fast, fully-mergeable quantile sketch with relative-error guarantees
#10Author 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…
Yes, the sketch can quickly answer questions like "How many requests were faster than 100ms?" 100ms maps to a bucket index, and we would just sum up all the buckets with indices at most that.