tree b8dd2c96cab9a83ddb553e27e9c590111ed348cb
parent 06f2b6f50ca2c6c1ccc630aa9d9fd761abf1becc
author Nicolas Michael <git@nmichael.de> 1554860692 -0700
committer Sijie Guo <guosijie@gmail.com> 1554860692 +0800

ISSUE #2053: Bugfix for Percentile Calculation in FastCodahale Timer Implementation

This bugfix for the FastCodahale timer implementation ensures that percentiles provided by a FastSnapshot are calculated correctly even if the total count of events (provided by FastTimer) is out of sync with the recorded events in the percentile buckets.

### Motivation

FastCodahale Timer implementation may miscalculate percentiles if snapshots of values are slightly out of sync, and if only few events have been recorded.

FastCodahale Timers use fine-grained locking and are meant to tolerate that (some) values change while being recorded or while snapshots are created. Currently, the total count of requests is not synchronized with the number of requests recorded in percentile buckets. If a snapshot is created while the total count of the timer has been incremented beyond the sum of values in the percentile buckets, the percentile calculation may produce wrong values.

For example, if 3 percentile values have been recorded, but the overall count is 4, then the percentile calculation would be based on 4 values. This becomes most obvious if a percentile > .75 (e.g. p95) is being calculated. For this, the implementation will try to find 0.95 * 4 values, which is more than the 3 values recorded in the buckets. Since no bucket fulfills the criteria, the bound of the last (overflow) bucket will be returned, i.e. Long.MAX_VALUE.

### Changes

FastSnapshots now bases the percentile calculation on the sum of values in the percentile buckets rather than a count provided by the caller (i.e. FastTimer). This ensures that percentiles are calculated correctly without the need of having all counters fully synchronized.

Master Issue: #2053 


Reviewers: Jia Zhai <zhaijia@apache.org>, Sijie Guo <sijie@apache.org>

This closes #2054 from nicmichael/fast-codahale-bugfix, closes #2053