voldemort.store.stats
Class Histogram

java.lang.Object
  extended by voldemort.store.stats.Histogram

public class Histogram
extends java.lang.Object

A class for computing percentiles based on a simple histogram. The histogram starts at 0 and then has uniformly sized buckets. The number of buckets and width of each bucket is specified upon construction. Each bucket in the histogram "counts" the number of values inserted into the histogram that fall into the bucket's range. All interfaces for adding data to the histogram or querying the histogram for quantiles are synchronized to make this object threadsafe.


Constructor Summary
Histogram(int nBuckets, int step)
          Initialize an empty histogram
Histogram(int nBuckets, int step, long resetIntervalMs)
          Initialize an empty histogram
 
Method Summary
 double getAverage()
          Obtain the average of the data in the histogram Note: Caller is responsible for making sure 'sum' does not overflow within the reset interval
 long getQuantile(double quantile)
          Find the a value n such that the percentile falls within [ n, n + step).
 void insert(long data)
          Insert a value into the right bucket of the histogram.
 void reset()
          Reset the histogram back to empty (set all values to 0)
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Histogram

public Histogram(int nBuckets,
                 int step,
                 long resetIntervalMs)
Initialize an empty histogram

Parameters:
nBuckets - The number of buckets to use
step - The size of each bucket

Histogram

public Histogram(int nBuckets,
                 int step)
Initialize an empty histogram

Parameters:
nBuckets - The number of buckets to use
step - The size (width) of each bucket
Method Detail

reset

public void reset()
Reset the histogram back to empty (set all values to 0)


insert

public void insert(long data)
Insert a value into the right bucket of the histogram. If the value is larger than any bound, insert into the last bucket. If the value is less than zero, then ignore it.

Parameters:
data - The value to insert into the histogram

getQuantile

public long getQuantile(double quantile)
Find the a value n such that the percentile falls within [ n, n + step). This method does a LINEAR probe of the histogram. I.e., this method is O(nBuckets).

Parameters:
quantile - The percentile to find
Returns:
Lower bound associated with the percentile

getAverage

public double getAverage()
Obtain the average of the data in the histogram Note: Caller is responsible for making sure 'sum' does not overflow within the reset interval

Returns:
the average over the current samples


Jay Kreps, Roshan Sumbaly, Alex Feinberg, Bhupesh Bansal, Lei Gao, Chinmay Soman, Vinoth Chandar, Zhongjie Wu