Index: src/test/java/org/apache/hadoop/hbase/metrics/TestExponentiallyDecayingSample.java =================================================================== --- src/test/java/org/apache/hadoop/hbase/metrics/TestExponentiallyDecayingSample.java (revision 1343837) +++ src/test/java/org/apache/hadoop/hbase/metrics/TestExponentiallyDecayingSample.java (working copy) @@ -20,8 +20,8 @@ import junit.framework.Assert; -import org.apache.hadoop.hbase.metrics.histogram.ExponentiallyDecayingSample; -import org.apache.hadoop.hbase.metrics.histogram.Snapshot; +import com.yammer.metrics.stats.ExponentiallyDecayingSample; +import com.yammer.metrics.stats.Snapshot; import org.junit.Test; public class TestExponentiallyDecayingSample { Index: src/test/java/org/apache/hadoop/hbase/metrics/TestMetricsHistogram.java =================================================================== --- src/test/java/org/apache/hadoop/hbase/metrics/TestMetricsHistogram.java (revision 1343837) +++ src/test/java/org/apache/hadoop/hbase/metrics/TestMetricsHistogram.java (working copy) @@ -22,7 +22,7 @@ import java.util.Random; import org.apache.hadoop.hbase.metrics.histogram.MetricsHistogram; -import org.apache.hadoop.hbase.metrics.histogram.Snapshot; +import com.yammer.metrics.stats.Snapshot; import org.junit.Assert; import org.junit.Test; Index: src/main/java/org/apache/hadoop/hbase/metrics/histogram/Snapshot.java =================================================================== --- src/main/java/org/apache/hadoop/hbase/metrics/histogram/Snapshot.java (revision 1343837) +++ src/main/java/org/apache/hadoop/hbase/metrics/histogram/Snapshot.java (working copy) @@ -1,166 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.hadoop.hbase.metrics.histogram; - -import java.io.File; -import java.io.IOException; -import java.io.PrintWriter; -import java.util.Arrays; -import java.util.Collection; - -/** - * A snapshot of all the information seen in a Sample. - */ -public class Snapshot { - - private static final double MEDIAN_Q = 0.5; - private static final double P75_Q = 0.75; - private static final double P95_Q = 0.95; - private static final double P98_Q = 0.98; - private static final double P99_Q = 0.99; - private static final double P999_Q = 0.999; - - private final double[] values; - - /** - * Create a new {@link Snapshot} with the given values. - * - * @param values an unordered set of values in the sample - */ - public Snapshot(Collection values) { - final Object[] copy = values.toArray(); - this.values = new double[copy.length]; - for (int i = 0; i < copy.length; i++) { - this.values[i] = (Long) copy[i]; - } - Arrays.sort(this.values); - } - - /** - * Create a new {@link Snapshot} with the given values. - * - * @param values an unordered set of values in the sample - */ - public Snapshot(double[] values) { - this.values = new double[values.length]; - System.arraycopy(values, 0, this.values, 0, values.length); - Arrays.sort(this.values); - } - - /** - * Returns the value at the given quantile. - * - * @param quantile a given quantile, in [0..1] - * @return the value in the distribution at quantile - */ - public double getValue(double quantile) { - if (quantile < 0.0 || quantile > 1.0) { - throw new IllegalArgumentException(quantile + " is not in [0..1]"); - } - - if (values.length == 0) { - return 0.0; - } - - final double pos = quantile * (values.length + 1); - - if (pos < 1) { - return values[0]; - } - - if (pos >= values.length) { - return values[values.length - 1]; - } - - final double lower = values[(int) pos - 1]; - final double upper = values[(int) pos]; - return lower + (pos - Math.floor(pos)) * (upper - lower); - } - - /** - * Returns the number of values in the snapshot. - * - * @return the number of values in the snapshot - */ - public int size() { - return values.length; - } - - /** - * Returns the median value in the distribution. - * - * @return the median value in the distribution - */ - public double getMedian() { - return getValue(MEDIAN_Q); - } - - /** - * Returns the value at the 75th percentile in the distribution. - * - * @return the value at the 75th percentile in the distribution - */ - public double get75thPercentile() { - return getValue(P75_Q); - } - - /** - * Returns the value at the 95th percentile in the distribution. - * - * @return the value at the 95th percentile in the distribution - */ - public double get95thPercentile() { - return getValue(P95_Q); - } - - /** - * Returns the value at the 98th percentile in the distribution. - * - * @return the value at the 98th percentile in the distribution - */ - public double get98thPercentile() { - return getValue(P98_Q); - } - - /** - * Returns the value at the 99th percentile in the distribution. - * - * @return the value at the 99th percentile in the distribution - */ - public double get99thPercentile() { - return getValue(P99_Q); - } - - /** - * Returns the value at the 99.9th percentile in the distribution. - * - * @return the value at the 99.9th percentile in the distribution - */ - public double get999thPercentile() { - return getValue(P999_Q); - } - - /** - * Returns the entire set of values in the snapshot. - * - * @return the entire set of values in the snapshot - */ - public double[] getValues() { - return Arrays.copyOf(values, values.length); - } -} Index: src/main/java/org/apache/hadoop/hbase/metrics/histogram/ExponentiallyDecayingSample.java =================================================================== --- src/main/java/org/apache/hadoop/hbase/metrics/histogram/ExponentiallyDecayingSample.java (revision 1343837) +++ src/main/java/org/apache/hadoop/hbase/metrics/histogram/ExponentiallyDecayingSample.java (working copy) @@ -1,226 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.hadoop.hbase.metrics.histogram; - -import java.util.ArrayList; -import java.util.Random; -import java.util.concurrent.ConcurrentSkipListMap; -import java.util.concurrent.Executors; -import java.util.concurrent.ScheduledExecutorService; -import java.util.concurrent.ThreadFactory; -import java.util.concurrent.TimeUnit; -import java.util.concurrent.atomic.AtomicInteger; -import java.util.concurrent.atomic.AtomicLong; -import java.util.concurrent.locks.ReentrantReadWriteLock; - -/** - * An exponentially-decaying random sample of {@code long}s. - * Uses Cormode et al's forward-decaying priority reservoir sampling method - * to produce a statistically representative sample, exponentially biased - * towards newer entries. - * - * see Cormode et al. - * Forward Decay: A Practical Time Decay Model for Streaming Systems. ICDE '09 - */ -public class ExponentiallyDecayingSample implements Sample { - - private static final Random RANDOM = new Random(); - private static final long RESCALE_THRESHOLD = TimeUnit.HOURS.toNanos(1); - - private static final ScheduledExecutorService TICK_SERVICE = - Executors.newScheduledThreadPool(1, - getNamedDaemonThreadFactory(Thread.currentThread().getName() + ".decayingSampleTick.")); - - private static volatile long CURRENT_TICK = - TimeUnit.MILLISECONDS.toSeconds(System.currentTimeMillis()); - - static { - // sample at twice our signal's frequency (1Hz) per the Nyquist theorem - TICK_SERVICE.scheduleAtFixedRate(new Runnable() { - @Override - public void run() { - CURRENT_TICK = - TimeUnit.MILLISECONDS.toSeconds(System.currentTimeMillis()); - } - }, 0, 500, TimeUnit.MILLISECONDS); - } - - private final ConcurrentSkipListMap values = - new ConcurrentSkipListMap(); - private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(); - private final AtomicLong count = new AtomicLong(0); - private final AtomicLong nextScaleTime = new AtomicLong(0); - - private final double alpha; - private final int reservoirSize; - private volatile long startTime; - - /** - * Constructor for an ExponentiallyDecayingSample. - * - * @param reservoirSize the number of samples to keep in the reservoir - * @param alpha the exponential decay factor; the higher this is, - * the more biased the sample will be towards newer - * values - */ - public ExponentiallyDecayingSample(int reservoirSize, double alpha) { - this.alpha = alpha; - this.reservoirSize = reservoirSize; - clear(); - } - - @Override - public void clear() { - lockForRescale(); - try { - values.clear(); - count.set(0); - this.startTime = CURRENT_TICK; - nextScaleTime.set(System.nanoTime() + RESCALE_THRESHOLD); - } finally { - unlockForRescale(); - } - } - - @Override - public int size() { - return (int) Math.min(reservoirSize, count.get()); - } - - @Override - public void update(long value) { - update(value, CURRENT_TICK); - } - - /** - * Adds an old value with a fixed timestamp to the sample. - * - * @param value the value to be added - * @param timestamp the epoch timestamp of {@code value} in seconds - */ - public void update(long value, long timestamp) { - lockForRegularUsage(); - try { - final double priority = weight(timestamp - startTime) - / RANDOM.nextDouble(); - final long newCount = count.incrementAndGet(); - if (newCount <= reservoirSize) { - values.put(priority, value); - } else { - Double first = values.firstKey(); - if (first < priority) { - if (values.putIfAbsent(priority, value) == null) { - // ensure we always remove an item - while (values.remove(first) == null) { - first = values.firstKey(); - } - } - } - } - } finally { - unlockForRegularUsage(); - } - - final long now = System.nanoTime(); - final long next = nextScaleTime.get(); - if (now >= next) { - rescale(now, next); - } - } - - @Override - public Snapshot getSnapshot() { - lockForRegularUsage(); - try { - return new Snapshot(values.values()); - } finally { - unlockForRegularUsage(); - } - } - - private double weight(long t) { - return Math.exp(alpha * t); - } - - /* "A common feature of the above techniques—indeed, the key technique that - * allows us to track the decayed weights efficiently—is that they maintain - * counts and other quantities based on g(ti − L), and only scale by g(t − L) - * at query time. But while g(ti −L)/g(t−L) is guaranteed to lie between zero - * and one, the intermediate values of g(ti − L) could become very large. For - * polynomial functions, these values should not grow too large, and should - * be effectively represented in practice by floating point values without - * loss of precision. For exponential functions, these values could grow - * quite large as new values of (ti − L) become large, and potentially - * exceed the capacity of common floating point types. However, since the - * values stored by the algorithms are linear combinations of g values - * (scaled sums), they can be rescaled relative to a new landmark. That is, - * by the analysis of exponential decay in Section III-A, the choice of L - * does not affect the final result. We can therefore multiply each value - * based on L by a factor of exp(−α(L′ − L)), and obtain the correct value - * as if we had instead computed relative to a new landmark L′ (and then use - * this new L′ at query time). This can be done with a linear pass over - * whatever data structure is being used." - */ - private void rescale(long now, long next) { - if (nextScaleTime.compareAndSet(next, now + RESCALE_THRESHOLD)) { - lockForRescale(); - try { - final long oldStartTime = startTime; - this.startTime = CURRENT_TICK; - final ArrayList keys = new ArrayList(values.keySet()); - for (Double key : keys) { - final Long value = values.remove(key); - values.put(key * Math.exp(-alpha * (startTime - oldStartTime)), - value); - } - } finally { - unlockForRescale(); - } - } - } - - private void unlockForRescale() { - lock.writeLock().unlock(); - } - - private void lockForRescale() { - lock.writeLock().lock(); - } - - private void lockForRegularUsage() { - lock.readLock().lock(); - } - - private void unlockForRegularUsage() { - lock.readLock().unlock(); - } - - private static ThreadFactory getNamedDaemonThreadFactory(final String prefix) { - return new ThreadFactory() { - - private final AtomicInteger threadNumber = new AtomicInteger(1); - - @Override - public Thread newThread(Runnable r) { - Thread t= new Thread(r, prefix + threadNumber.getAndIncrement()); - t.setDaemon(true); - return t; - } - }; - } -} Index: src/main/java/org/apache/hadoop/hbase/metrics/histogram/Sample.java =================================================================== --- src/main/java/org/apache/hadoop/hbase/metrics/histogram/Sample.java (revision 1343837) +++ src/main/java/org/apache/hadoop/hbase/metrics/histogram/Sample.java (working copy) @@ -1,49 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.hadoop.hbase.metrics.histogram; - -/** - * A statistically representative sample of items from a stream. - */ -public interface Sample { - /** - * Clears all recorded values. - */ - void clear(); - - /** - * Returns the number of values recorded. - * - * @return the number of values recorded - */ - int size(); - - /** - * Adds a new recorded value to the sample. - * - * @param value a new recorded value - */ - void update(long value); - - /** - * Returns a snapshot of the sample's values. - * - * @return a snapshot of the sample's values - */ - Snapshot getSnapshot(); -} Index: src/main/java/org/apache/hadoop/hbase/metrics/histogram/UniformSample.java =================================================================== --- src/main/java/org/apache/hadoop/hbase/metrics/histogram/UniformSample.java (revision 1343837) +++ src/main/java/org/apache/hadoop/hbase/metrics/histogram/UniformSample.java (working copy) @@ -1,105 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.hadoop.hbase.metrics.histogram; - -import java.util.ArrayList; -import java.util.List; -import java.util.Random; -import java.util.concurrent.atomic.AtomicLong; -import java.util.concurrent.atomic.AtomicLongArray; - -/** - * A random sample of a stream of longs. Uses Vitter's Algorithm R to produce a - * statistically representative sample. - * - * see: http://www.cs.umd.edu/~samir/498/vitter.pdf - */ -public class UniformSample implements Sample { - - private static final Random RANDOM = new Random(); - private static final int BITS_PER_LONG = 63; - - private final AtomicLong count = new AtomicLong(); - private final AtomicLongArray values; - - /** - * Creates a new UniformSample - * - * @param reservoirSize the number of samples to keep - */ - public UniformSample(int reservoirSize) { - this.values = new AtomicLongArray(reservoirSize); - clear(); - } - - @Override - public void clear() { - for (int i = 0; i < values.length(); i++) { - values.set(i, 0); - } - count.set(0); - } - - @Override - public int size() { - final long c = count.get(); - if (c > values.length()) { - return values.length(); - } - return (int) c; - } - - @Override - public void update(long value) { - final long c = count.incrementAndGet(); - if (c <= values.length()) { - values.set((int) c - 1, value); - } else { - final long r = nextLong(c); - if (r < values.length()) { - values.set((int) r, value); - } - } - } - - /** - * Get a pseudo-random long uniformly between 0 and n-1. Stolen from - * {@link java.util.Random#nextInt()}. - * - * @param n the bound - * @return a value select randomly from the range {@code [0..n)}. - */ - private static long nextLong(long n) { - long bits, val; - do { - bits = RANDOM.nextLong() & (~(1L << BITS_PER_LONG)); - val = bits % n; - } while (bits - val + (n - 1) < 0L); - return val; - } - - @Override - public Snapshot getSnapshot() { - final int s = size(); - final List copy = new ArrayList(s); - for (int i = 0; i < s; i++) { - copy.add(values.get(i)); - } - return new Snapshot(copy); - } -} Index: src/main/java/org/apache/hadoop/hbase/metrics/histogram/MetricsHistogram.java =================================================================== --- src/main/java/org/apache/hadoop/hbase/metrics/histogram/MetricsHistogram.java (revision 1343837) +++ src/main/java/org/apache/hadoop/hbase/metrics/histogram/MetricsHistogram.java (working copy) @@ -25,6 +25,11 @@ import org.apache.hadoop.metrics.util.MetricsBase; import org.apache.hadoop.metrics.util.MetricsRegistry; +import com.yammer.metrics.stats.Sample; +import com.yammer.metrics.stats.Snapshot; +import com.yammer.metrics.stats.UniformSample; +import com.yammer.metrics.stats.ExponentiallyDecayingSample; + public class MetricsHistogram extends MetricsBase { // 1028 items implies 99.9% CI w/ 5% margin of error Index: src/main/java/org/apache/hadoop/hbase/regionserver/metrics/RegionServerMetrics.java =================================================================== --- src/main/java/org/apache/hadoop/hbase/regionserver/metrics/RegionServerMetrics.java (revision 1343837) +++ src/main/java/org/apache/hadoop/hbase/regionserver/metrics/RegionServerMetrics.java (working copy) @@ -31,7 +31,7 @@ import org.apache.hadoop.hbase.metrics.MetricsRate; import org.apache.hadoop.hbase.metrics.PersistentMetricsTimeVaryingRate; import org.apache.hadoop.hbase.metrics.histogram.MetricsHistogram; -import org.apache.hadoop.hbase.metrics.histogram.Snapshot; +import com.yammer.metrics.stats.Snapshot; import org.apache.hadoop.hbase.regionserver.wal.HLog; import org.apache.hadoop.hbase.util.Pair; import org.apache.hadoop.hbase.util.Strings; Index: pom.xml =================================================================== --- pom.xml (revision 1343837) +++ pom.xml (working copy) @@ -976,6 +976,7 @@ 1.1.1 2.1 1.6 + 2.1.2 r09 1.8.8 5.5.23 @@ -1037,6 +1038,11 @@ + com.yammer.metrics + metrics-core + ${metrics-core.version} + + com.google.guava guava ${guava.version}