Offer a relative-error sketch alternative to ContinuousSample
- Dominant language
- C++
- Stars
- 16.7k
- Forks
- 1.6k
- Avg merge
- 1d 20h
- Merged PRs (30d)
- 126
Description
ContinuousSample current builds a population of a defined size, and then keeps a random sample of that size of all elements it has seen, such that each element has an equal chance of being included in the sample. Quantiles are calculated by sorting the array, and looking at the value stored in a specific location in the array. (ie. the 99th element gives the 99th quantile in a 100 element array.)
This seems to be the simplest version of what is referred to as a rank-error quantile sketch in literature, as they error bounds they promise are on at what rank a value will be at instead of the error bounds on the value itself. For answering quantiles near the middle of a distribution, rank-error sketches have reasonably low error. For quantiles near 0 or 1, like reporting 99th percentile tail latency, it allows a reasonably large error bound on the value.
Also from VLDB '19 is a [DDSketch](http://www.vldb.org/pvldb/vol12/p2195-masson.pdf), a paper on a relative-error quantile sketch. Relative-error sketches offer an error bound on the value rather than its rank, which makes tail latency quantiles more accurate. [HDR Histogram](http://hdrhistogram.org) is another relative-error sketch. Adopting one of these would improve the error bounds on what we report as our tail latency versus our true tail latency.
DataDog [released their code](https://github.com/DataDog/sketches-java) for DDSketch, but there isn't yet have a C or C++ implementation, though it might be not hard to translate one from the Java implementation. HDR Histogram has a [c implementation](https://github.com/HdrHistogram/HdrHistogram_c) with a compatible license.
However, discussion with @kaomakino yielded a couple wise points as always:
1. The instability of our performance tests from run-to-run will likely have more of an impact on the reported latency figures than the quantile sketch algorithm that's used
2. The end result of reporting 99.99 percentile of 10s vs 20s will probably be the same, w.r.t paging or warranting investigation.
Contributor guide
Research direction
Start by reviewing the existing ContinuousSample implementation and how its quantiles feed tail-latency reporting. Compare the DDSketch and HDR Histogram references, including the linked C implementation, and determine which relative-error approach fits FoundationDB. Done means providing a tested C++ alternative with a clear integration path and quantified error behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100