The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Percentile calculation

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Jan 27 2010, 6:21 pm
From: John Cohen <john.java.w...@gmail.com>
Date: Wed, 27 Jan 2010 15:21:31 -0800 (PST)
Local: Wed, Jan 27 2010 6:21 pm
Subject: Re: Percentile calculation
I have looked this in different directions, I have considered
performance and  simplicity.  I would like a second opinion.

This is the easiest approach:

<pre>
public class StatTrackingStore<K, V> extends DelegatingStore<K, V> {
...
...
@JmxGetter(name = "writeLatencyInMs", description = "Write
Latencies for: 50, 90, 99, 99.5 and 99.9 percentile")
public String getWriteLatencyInMs() {
return stats.getLatencyStats(Tracked.PUT);
}

}

public class RequestCounter {

/**
* Used to divide the TimeNS that a transaction took. The result
will be
* used as index into an array that keeps track of the total
number of tx.
* For example a value of:
* 34000 ns represents index=3 (int)(34000/10^4)
* 38000 ns represents index=3 (int)(38000/10^4)
* 375000 ns represents index=37 (int)(375000/10^4)
*
* Basically this will knock down 5 digits from time NS.
* I doubt anyone cares to be more accurate than 1ms, so that
would be a
* reasonable default.
*
*/
private final static int DISTRIBUTION_FACTOR = 100000;

/**
* Normalize the index back to millis.
*/
private final static float NORMILIZE_TO_MILLIS =
DISTRIBUTION_FACTOR / 1000000.0F;

int index = (int) (timeNS / Accumulator.MAX_ARRAY);

for(int i = 0; i < 3; i++) {
Accumulator oldv = getValidAccumulator();

long startTimeMS = oldv.startTimeMS;
long count = oldv.count + 1;
long totalTimeNS = oldv.totalTimeNS + timeNS;
long total = oldv.total + 1;
int[] latencies = oldv.latencies;

// Updates the counter that keeps track of the number of
// transactions that took the same amount of time.
//
//
// If the index is bigger than Accumulator.MAX_ARRAY it
means that the
// transaction took such a big time that can be considered
a rare case,
// For example, let's consider:
//
// timeNS = 10.000.000.000 (10 seconds)
// index = timeNS / Accumulator.MAX_ARRAY
// index = 10.000.000.000 / 100.000
// index = 100.000
if(index < Accumulator.MAX_ARRAY) {
latencies[index] = getSafeNextCounter(latencies
[index]);
}else{
// Put this value in the last bucket.
latencies[Accumulator.MAX_ARRAY] = getSafeNextCounter
(latencies[Accumulator.MAX_ARRAY]);
}
//System.out.println("timeNS:" + timeNS + ", latencies["
+index + "]:" + latencies[index]);

if(values.compareAndSet(oldv, new Accumulator(startTimeMS,
count, totalTimeNS, total, latencies))) {
return;
}
}
}

private int getSafeNextCounter(int value) {
// reset the counter if maximum value is reached, unlikely to
// happen...
int nextValue = value+1;
if(nextValue < 2147483640)
return nextValue;
else
return 0;
}

private int findIndexByPercentage(final float percentage, final
long totalTx, int[] latencies) {
float countTx = (totalTx * percentage);
long found = 0;
for(int index = 0; index < Accumulator.MAX_ARRAY; index++) {
found = latencies[index] + found;
if(found > countTx) {
return index;
}
}

return 0;
}

public String getLatency() {
int[] latencies = getValidAccumulator().latencies;
long totalTx = 0;
for(int val: latencies) {
totalTx = val + totalTx;
}

int index50 = findIndexByPercentage(0.50F, totalTx,
latencies);
int index90 = findIndexByPercentage(0.90F, totalTx,
latencies);
int index99 = findIndexByPercentage(0.99F, totalTx,
latencies);
int index995 = findIndexByPercentage(0.995F, totalTx,
latencies);
int index999 = findIndexByPercentage(0.999F, totalTx,
latencies);

// Calculate the percentiles in Millis.
float p50Ms = index50 * NORMILIZE_TO_MILLIS;
float p90MS = index90 * NORMILIZE_TO_MILLIS;
float p99MS = index99 * NORMILIZE_TO_MILLIS;
float p995MS = index995 * NORMILIZE_TO_MILLIS;
float p999MS = index999 * NORMILIZE_TO_MILLIS;

return "Latency: 50=" + String.format("%.2f", p50Ms) +
", 90=" + String.format("%.2f", p90MS) +
", 99=" + String.format("%.2f", p99MS) +
", 99.5=" + String.format("%.2f", p995MS) +
", 99.9=" + String.format("%.2f", p999MS);

}
...
...
...

}

private static class Accumulator {
public final static int MAX_ARRAY = 100000;
private final static int MAX_ARRAY_PLUS_ONE = MAX_ARRAY + 1;
final int[] latencies;

public Accumulator() {
this(System.currentTimeMillis(), 0, 0, 0, new int
[MAX_ARRAY_PLUS_ONE]);
}

...
...

</pre>