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;

    public void addRequest(long timeNS) {

        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>

Welcome your comments,
Thanks,
John Cohen