3 ms·

Shameless plug. Just wrote a paper about this: https://arxiv.org/abs/2001.06561 https://arxiv.org/abs/2001.06561 Containing a survey of the most popular Laten

Shameless plug. Just wrote a paper about this: https://arxiv.org/abs/2001.06561 https://arxiv.org/abs/2001.06561 Containing a survey of the most popular Latency Aggregation methods used in the industry (Prometheus Histograms, t-digest, HDR-Histogram, DD-sketch/histogram).

jmacd333 7y ago
The Circllhist algorithm is interesting, but I get an uneasy feeling from the use of a _relative error_ measure to evaluate the performance of quantile estimation. Note that other authors don't use this measure. Dunning uses Mean Absolute Error in his latest T-digest paper: https://arxiv.org/pdf/1902.04023.pdf https://arxiv.org/pdf/1902.04023.pdf Cohen uses Normalized Root-Mean-Squared Error to evaluate sampling schemes, which are equally capable of estimating latency quantiles: https://dl.acm.org/doi/abs/10.1145/3234338 https://dl.acm.org/doi/abs/10.1145/3234338 The problem with Relative Error as a measure of accuracy is that it depends on the location of the distribution. The same size absolute error becomes a large relative error near zero and becomes a small relative error farther up the number line. Another thing about this study is that only one value for the T-digest quality is tested. Of course, the T-digest quality parameter equates directly with compressed size, so it's unsurprising that T-digest's size is fixed throughout the experiment. I also suspect that the choice of data set matters quite a lot in this study. If your latency values were clustered around a small range, then the algorithms like DDSketch and Circllhist will indeed have relative error less than 5% (as they prove) but T-digest will be significantly more accurate.
- heinrichhartman 7y ago
  Thanks for your comment! Relative error is a practical choice, since it allows to cover an extremely large value range (essentially all floating point numbers) with small size ( O(log(range)) ) and zero-configuration. You can't have that with bounding the absolute error. Also the relative error is what you are interested in most of the time as a practitioner. (200ms+/-10ms; 1year+/-15days) DDSketch uses relative error for estimation as well. > If your latency values were clustered around a small range, [...] T-digest will be significantly more accurate. That is correct! One point of this example was to demonstrate that merged t-digest can have unbounded errors. In the t-digest paper it was speculated that merged digest have bounded error, but the proof was just more difficult. As it turns out, if you have heavy merges and an extremely large value range, you can get unbounded errors.

jmacd333 7y ago

The Circllhist algorithm is interesting, but I get an uneasy feeling from the use of a _relative error_ measure to evaluate the performance of quantile estimation. Note that other authors don't use this measure. Dunning uses Mean Absolute Error in his latest T-digest paper: https://arxiv.org/pdf/1902.04023.pdf https://arxiv.org/pdf/1902.04023.pdf Cohen uses Normalized Root-Mean-Squared Error to evaluate sampling schemes, which are equally capable of estimating latency quantiles: https://dl.acm.org/doi/abs/10.1145/3234338 https://dl.acm.org/doi/abs/10.1145/3234338 The problem with Relative Error as a measure of accuracy is that it depends on the location of the distribution. The same size absolute error becomes a large relative error near zero and becomes a small relative error farther up the number line. Another thing about this study is that only one value for the T-digest quality is tested. Of course, the T-digest quality parameter equates directly with compressed size, so it's unsurprising that T-digest's size is fixed throughout the experiment. I also suspect that the choice of data set matters quite a lot in this study. If your latency values were clustered around a small range, then the algorithms like DDSketch and Circllhist will indeed have relative error less than 5% (as they prove) but T-digest will be significantly more accurate.

heinrichhartman 7y ago
Thanks for your comment! Relative error is a practical choice, since it allows to cover an extremely large value range (essentially all floating point numbers) with small size ( O(log(range)) ) and zero-configuration. You can't have that with bounding the absolute error. Also the relative error is what you are interested in most of the time as a practitioner. (200ms+/-10ms; 1year+/-15days) DDSketch uses relative error for estimation as well. > If your latency values were clustered around a small range, [...] T-digest will be significantly more accurate. That is correct! One point of this example was to demonstrate that merged t-digest can have unbounded errors. In the t-digest paper it was speculated that merged digest have bounded error, but the proof was just more difficult. As it turns out, if you have heavy merges and an extremely large value range, you can get unbounded errors.