org.apache.hadoop.metrics2.util

Class MetricSampleQuantiles

java.lang.Object

org.apache.hadoop.metrics2.util.MetricSampleQuantiles

@InterfaceAudience.Private
public class MetricSampleQuantiles
extends Object

Implementation of the Cormode, Korn, Muthukrishnan, and Srivastava algorithm for streaming calculation of targeted high-percentile epsilon-approximate quantiles. This is a generalization of the earlier work by Greenwald and Khanna (GK), which essentially allows different error bounds on the targeted quantiles, which allows for far more efficient calculation of high-percentiles. See: Cormode, Korn, Muthukrishnan, and Srivastava "Effective Computation of Biased Quantiles over Data Streams" in ICDE 2005 Greenwald and Khanna, "Space-efficient online computation of quantile summaries" in SIGMOD 2001

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	MetricSampleQuantiles.SampleItem Describes a measured value passed to the estimator, tracking additional metadata required by the CKMS algorithm.

Field Summary

Fields

Modifier and Type	Field and Description
private long[]	buffer Buffers incoming items to be inserted in batch.
private int	bufferCount
private long	count Total number of items in stream
private MetricQuantile[]	quantiles Array of Quantiles that we care about, along with desired error.
private LinkedList<MetricSampleQuantiles.SampleItem>	samples Current list of sampled items, maintained in sorted order with error bounds

Constructor Summary

Constructors

Constructor and Description
MetricSampleQuantiles(MetricQuantile[] quantiles)

Method Summary

Modifier and Type	Method and Description
private double	allowableError(int rank) Specifies the allowable error for this rank, depending on which quantiles are being targeted.
void	clear() Resets the estimator, clearing out all previously inserted items
private void	compress() Try to remove extraneous items from the set of sampled items.
long	getCount() Returns the number of items that the estimator has processed
int	getSampleCount() Returns the number of samples kept by the estimator
void	insert(long v) Add a new value from the stream.
private void	insertBatch() Merges items from buffer into the samples array in one pass.
private long	query(double quantile) Get the estimated value at the specified quantile.
Map<MetricQuantile,Long>	snapshot() Get a snapshot of the current values of all the tracked quantiles.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

count

private long count

Total number of items in stream

samples

private LinkedList<MetricSampleQuantiles.SampleItem> samples

Current list of sampled items, maintained in sorted order with error bounds

buffer

private long[] buffer

Buffers incoming items to be inserted in batch. Items are inserted into the buffer linearly. When the buffer fills, it is flushed into the samples array in its entirety.

bufferCount

private int bufferCount

quantiles

private final MetricQuantile[] quantiles

Array of Quantiles that we care about, along with desired error.

Constructor Detail

MetricSampleQuantiles

public MetricSampleQuantiles(MetricQuantile[] quantiles)

Method Detail

allowableError

private double allowableError(int rank)

Specifies the allowable error for this rank, depending on which quantiles are being targeted. This is the f(r_i, n) function from the CKMS paper. It's basically how wide the range of this rank can be.

Parameters:

rank - the index in the list of samples

insert

public void insert(long v)

Add a new value from the stream.

Parameters:

v - the value to insert

insertBatch

private void insertBatch()

Merges items from buffer into the samples array in one pass. This is more efficient than doing an insert on every item.

compress

private void compress()

Try to remove extraneous items from the set of sampled items. This checks if an item is unnecessary based on the desired error bounds, and merges it with the adjacent item if it is.

query

private long query(double quantile)
            throws IOException

Get the estimated value at the specified quantile.

Parameters:

quantile - Queried quantile, e.g. 0.50 or 0.99.

Returns:

Estimated value at that quantile.

Throws:

IOException

snapshot

public Map<MetricQuantile,Long> snapshot()
                                  throws IOException

Get a snapshot of the current values of all the tracked quantiles.

Returns:

snapshot of the tracked quantiles

Throws:

IOException - if no items have been added to the estimator

getCount

public long getCount()

Returns the number of items that the estimator has processed

Returns:

count total number of items processed

getSampleCount

public int getSampleCount()

Returns the number of samples kept by the estimator

Returns:

count current number of samples

clear

public void clear()

Resets the estimator, clearing out all previously inserted items