[
https://issues.apache.org/jira/browse/HBASE-6261?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13421031#comment-13421031
]
Andrew Wang commented on HBASE-6261:
------------------------------------
Based on feedback from Elliot and Jon, I've done some analysis of both
SampleQuantiles and MetricsHistogram.
For both, I tried item counts of 1k, 10k, 100k, 1M, 2.5M, 5M, and 10M. For each
count, I randomly shuffled longs from {{[0, count)}}, pushed them through the
estimator, and measured the runtime, # of samples, and error for various
quantiles. This was repeated ten times, giving stddev error bars for each point.
MetricsHistogram was left using default settings (1028 item reservoir).
SampleQuantiles was also left with default settings, tracking the same
quantiles as MetricsHistogram, but with bounded error. I threw away the 0.90
quantile from SampleQuantiles since MetricsHistogram didn't have a function to
compute it (though trivial).
This was all run single-threaded on my couple-years-old T410s laptop.
You can view the imgur album of just the plots here: [http://imgur.com/a/gTDYr]
h2. Runtime
Note that the y-axis is log-scale in this plot. SampleQuantiles is roughly an
order of magnitude slower at 10 million items (26.8s vs. 3.3s), but the scaling
pattern overall looks good. It's comparable for low (<=10k) items.
!http://i.imgur.com/c6SIl.png!
h2. Memory usage
Note that the y-axis is again log-scale in this plot.
MetricsHistogram uses a flat 1028 items of storage, so it has constant memory
usage. At 10 million items, SampleQuantiles uses roughly an order of magnitude
more memory (19.4k items vs. 1k). Since SampleQuantiles samples are about 40B
each and MetricsHistogram samples are 8B each, this is approximately 776KB vs.
8KB.
This matters less for small numbers of items. The crossover point on the graph
happens at between 10k and 100k items. The scaling pattern looks similar to the
runtime, overall good.
!http://i.imgur.com/3E3RQ.png!
h2. Error bounds
Note that for this series of plots, the y-axis is linear and the x-axis is log.
This makes the actual error values easier to interpret. Error was calculated by
taking the difference in the actual and the estimated rank of the percentile,
and dividing by the total count.
SampleQuantiles is by default configured to track 50th with 5% error, 75th with
2.5%, 95th with 0.5%, and 99th with 0.1%. We see less error at higher
percentiles, and with larger sized streams. For 95th and 99th, we reach
essentially 0% error at around 1 million items (0.009% for 95th, 0.004% for
99th).
MetricsHistogram doesn't really provide great error, and high percentiles seem
to get worse as the number of items increase. There's also large standard
deviation in error, which is unfortunate if these values are going to be used
for thresholding. For 95th, it looks like 0.4% to 0.6% error. For 99th, we're
looking at 0.2% to 0.3%.
An error of half a percent doesn't sound huge, but remember that this is error
in rank, or effectively on a uniform latency distribution. To translate this, I
fitted against the get latency distribution I got from running a mixed get/scan
YCSB workload against CDH3u1 HBase. At the 95th percentile, an error of 0.5%
translated to 137ms -3.4% and +4%. At the 99th, an error of 0.5% translated to
310ms -21.7% and +43.3%. These are just indicative numbers; the important point
is that half a percent on the tail of a Zipf distribution is pretty meaningful.
!http://i.imgur.com/m0ERq.png!
!http://i.imgur.com/qvfpR.png!
!http://i.imgur.com/k5y5o.png!
!http://i.imgur.com/uyqAK.png!
h2. Conclusion
For low-rate events (order 0.1s on up) like compactions or flushes, I think it
can go either way. SampleQuantiles has similar CPU/memory usage up until ~10k
items, but MetricsHistogram is perfectly accurate up until 1028 items, has
bounded memory, and can be used to compute other statistics. The 1028 mark
seems important here; just keep all the data for low-rate events.
For high-rate events (order ms) like RPCs, it depends if you care at all about
accuracy. The memory/CPU overhead of SampleQuantiles is high in relative terms
(order of magnitude), but you need to use it if you're measuring for SLAs since
MetricsHistogram basically isn't accurate. It also seems unlikely that you'll
have that many 1M+ item streams you want to track, and it's just a couple
hundred KB more memory. Use MetricsHistogram if accuracy isn't important, but I
feel like SampleQuantiles is a pretty reasonable choice.
Hopefully that was enlightening. I posted the raw data and plotting script if
anyone else wants to play with it, and I can post the test code snippets used
to make the data if anyone's interested in that too.
> Better approximate high-percentile percentile latency metrics
> -------------------------------------------------------------
>
> Key: HBASE-6261
> URL: https://issues.apache.org/jira/browse/HBASE-6261
> Project: HBase
> Issue Type: New Feature
> Reporter: Andrew Wang
> Assignee: Andrew Wang
> Labels: metrics
> Attachments: Latencyestimation.pdf, MetricsHistogram.data,
> SampleQuantiles.data, parse.py
>
>
> The existing reservoir-sampling based latency metrics in HBase are not
> well-suited for providing accurate estimates of high-percentile (e.g. 90th,
> 95th, or 99th) latency. This is a well-studied problem in the literature (see
> [1] and [2]), the question is determining which methods best suit our needs
> and then implementing it.
> Ideally, we should be able to estimate these high percentiles with minimal
> memory and CPU usage as well as minimal error (e.g. 1% error on 90th, or .1%
> on 99th). It's also desirable to provide this over different time-based
> sliding windows, e.g. last 1 min, 5 mins, 15 mins, and 1 hour.
> I'll note that this would also be useful in HDFS, or really anywhere latency
> metrics are kept.
> [1] http://www.cs.rutgers.edu/~muthu/bquant.pdf
> [2] http://infolab.stanford.edu/~manku/papers/04pods-sliding.pdf
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
