001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, software 013 * distributed under the License is distributed on an "AS IS" BASIS, 014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 015 * See the License for the specific language governing permissions and 016 * limitations under the License. 017 */ 018package org.apache.hadoop.hbase.metrics.impl; 019 020import java.util.Arrays; 021import java.util.concurrent.atomic.AtomicLong; 022import java.util.concurrent.atomic.LongAdder; 023import java.util.stream.Stream; 024import org.apache.hadoop.hbase.metrics.Snapshot; 025import org.apache.hadoop.hbase.util.AtomicUtils; 026import org.apache.yetus.audience.InterfaceAudience; 027import org.apache.yetus.audience.InterfaceStability; 028 029/** 030 * FastLongHistogram is a thread-safe class that estimate distribution of data and computes the 031 * quantiles. 032 */ 033@InterfaceAudience.Private 034@InterfaceStability.Evolving 035public class FastLongHistogram { 036 037 /** 038 * Default number of bins. 039 */ 040 public static final int DEFAULT_NBINS = 255; 041 042 public static final double[] DEFAULT_QUANTILES = 043 new double[] { 0.25, 0.5, 0.75, 0.90, 0.95, 0.98, 0.99, 0.999 }; 044 045 /** 046 * Bins is a class containing a list of buckets(or bins) for estimation histogram of some data. 047 */ 048 private static class Bins { 049 050 private final LongAdder[] counts; 051 // inclusive 052 private final long binsMin; 053 // exclusive 054 private final long binsMax; 055 private final long bins10XMax; 056 private final AtomicLong min = new AtomicLong(Long.MAX_VALUE); 057 private final AtomicLong max = new AtomicLong(0L); 058 059 private final LongAdder count = new LongAdder(); 060 private final LongAdder total = new LongAdder(); 061 062 // set to true when any of data has been inserted to the Bins. It is set after the counts are 063 // updated. 064 private volatile boolean hasData = false; 065 066 /** 067 * The constructor for creating a Bins without any prior data. 068 */ 069 public Bins(int numBins) { 070 counts = createCounters(numBins); 071 this.binsMin = 1L; 072 073 // These two numbers are total guesses 074 // and should be treated as highly suspect. 075 this.binsMax = 1000; 076 this.bins10XMax = binsMax * 10; 077 } 078 079 /** 080 * The constructor for creating a Bins with last Bins. 081 */ 082 public Bins(Bins last, int numBins, double minQ, double maxQ) { 083 long[] values = last.getQuantiles(new double[] { minQ, maxQ }); 084 long wd = values[1] - values[0] + 1; 085 // expand minQ and maxQ in two ends back assuming uniform distribution 086 this.binsMin = Math.max(0L, (long) (values[0] - wd * minQ)); 087 long binsMax = (long) (values[1] + wd * (1 - maxQ)) + 1; 088 // make sure each of bins is at least of width 1 089 this.binsMax = Math.max(binsMax, this.binsMin + numBins); 090 this.bins10XMax = Math.max((long) (values[1] + (binsMax - 1) * 9), this.binsMax + 1); 091 092 this.counts = createCounters(numBins); 093 } 094 095 private LongAdder[] createCounters(int numBins) { 096 return Stream.generate(LongAdder::new).limit(numBins + 3).toArray(LongAdder[]::new); 097 } 098 099 private int getIndex(long value) { 100 if (value < this.binsMin) { 101 return 0; 102 } else if (value > this.bins10XMax) { 103 return this.counts.length - 1; 104 } else if (value >= this.binsMax) { 105 return this.counts.length - 2; 106 } 107 // compute the position 108 return 1 109 + (int) ((value - this.binsMin) * (this.counts.length - 3) / (this.binsMax - this.binsMin)); 110 111 } 112 113 /** 114 * Adds a value to the histogram. 115 */ 116 public void add(long value, long count) { 117 if (value < 0) { 118 // The whole computation is completely thrown off if there are negative numbers 119 // 120 // Normally we would throw an IllegalArgumentException however this is the metrics 121 // system and it should be completely safe at all times. 122 // So silently throw it away. 123 return; 124 } 125 AtomicUtils.updateMin(min, value); 126 AtomicUtils.updateMax(max, value); 127 128 this.count.add(count); 129 this.total.add(value * count); 130 131 int pos = getIndex(value); 132 this.counts[pos].add(count); 133 134 // hasData needs to be updated as last 135 this.hasData = true; 136 } 137 138 /** 139 * Computes the quantiles give the ratios. 140 */ 141 public long[] getQuantiles(double[] quantiles) { 142 if (!hasData) { 143 // No data yet. 144 return new long[quantiles.length]; 145 } 146 147 // Make a snapshot of lowerCounter, higherCounter and bins.counts to counts. 148 // This is not synchronized, but since the counter are accumulating, the result is a good 149 // estimation of a snapshot. 150 long[] counts = new long[this.counts.length]; 151 long total = 0L; 152 for (int i = 0; i < this.counts.length; i++) { 153 counts[i] = this.counts[i].sum(); 154 total += counts[i]; 155 } 156 157 int rIndex = 0; 158 double qCount = total * quantiles[0]; 159 long cum = 0L; 160 161 long[] res = new long[quantiles.length]; 162 countsLoop: for (int i = 0; i < counts.length; i++) { 163 // mn and mx define a value range 164 long mn, mx; 165 if (i == 0) { 166 mn = this.min.get(); 167 mx = this.binsMin; 168 } else if (i == counts.length - 1) { 169 mn = this.bins10XMax; 170 mx = this.max.get(); 171 } else if (i == counts.length - 2) { 172 mn = this.binsMax; 173 mx = this.bins10XMax; 174 } else { 175 mn = this.binsMin + (i - 1) * (this.binsMax - this.binsMin) / (this.counts.length - 3); 176 mx = this.binsMin + i * (this.binsMax - this.binsMin) / (this.counts.length - 3); 177 } 178 179 if (mx < this.min.get()) { 180 continue; 181 } 182 if (mn > this.max.get()) { 183 break; 184 } 185 mn = Math.max(mn, this.min.get()); 186 mx = Math.min(mx, this.max.get()); 187 188 // lastCum/cum are the corresponding counts to mn/mx 189 double lastCum = cum; 190 cum += counts[i]; 191 192 // fill the results for qCount is within current range. 193 while (qCount <= cum) { 194 if (cum == lastCum) { 195 res[rIndex] = mn; 196 } else { 197 res[rIndex] = (long) ((qCount - lastCum) * (mx - mn) / (cum - lastCum) + mn); 198 } 199 200 // move to next quantile 201 rIndex++; 202 if (rIndex >= quantiles.length) { 203 break countsLoop; 204 } 205 qCount = total * quantiles[rIndex]; 206 } 207 } 208 // In case quantiles contains values >= 100% 209 for (; rIndex < quantiles.length; rIndex++) { 210 res[rIndex] = this.max.get(); 211 } 212 213 return res; 214 } 215 216 long getNumAtOrBelow(long val) { 217 return Arrays.stream(counts).mapToLong(c -> c.sum()).limit(getIndex(val) + 1).sum(); 218 } 219 220 public long getMin() { 221 long min = this.min.get(); 222 return min == Long.MAX_VALUE ? 0 : min; // in case it is not initialized 223 } 224 225 public long getMean() { 226 long count = this.count.sum(); 227 long total = this.total.sum(); 228 if (count == 0) { 229 return 0; 230 } 231 return total / count; 232 } 233 } 234 235 // The bins counting values. It is replaced with a new one in calling of reset(). 236 private volatile Bins bins; 237 238 /** 239 * Constructor. 240 */ 241 public FastLongHistogram() { 242 this(DEFAULT_NBINS); 243 } 244 245 /** 246 * Constructor. 247 * @param numOfBins the number of bins for the histogram. A larger value results in more precise 248 * results but with lower efficiency, and vice versus. 249 */ 250 public FastLongHistogram(int numOfBins) { 251 this.bins = new Bins(numOfBins); 252 } 253 254 /** 255 * Constructor setting the bins assuming a uniform distribution within a range. 256 * @param numOfBins the number of bins for the histogram. A larger value results in more precise 257 * results but with lower efficiency, and vice versus. 258 * @param min lower bound of the region, inclusive. 259 * @param max higher bound of the region, inclusive. 260 */ 261 public FastLongHistogram(int numOfBins, long min, long max) { 262 this(numOfBins); 263 Bins bins = new Bins(numOfBins); 264 bins.add(min, 1); 265 bins.add(max, 1); 266 this.bins = new Bins(bins, numOfBins, 0.01, 0.999); 267 } 268 269 private FastLongHistogram(Bins bins) { 270 this.bins = bins; 271 } 272 273 /** 274 * Adds a value to the histogram. 275 */ 276 public void add(long value, long count) { 277 this.bins.add(value, count); 278 } 279 280 /** 281 * Computes the quantiles give the ratios. 282 */ 283 public long[] getQuantiles(double[] quantiles) { 284 return this.bins.getQuantiles(quantiles); 285 } 286 287 public long[] getQuantiles() { 288 return this.bins.getQuantiles(DEFAULT_QUANTILES); 289 } 290 291 public long getMin() { 292 return this.bins.getMin(); 293 } 294 295 public long getMax() { 296 return this.bins.max.get(); 297 } 298 299 public long getCount() { 300 return this.bins.count.sum(); 301 } 302 303 public long getMean() { 304 return this.bins.getMean(); 305 } 306 307 public long getNumAtOrBelow(long value) { 308 return this.bins.getNumAtOrBelow(value); 309 } 310 311 /** 312 * Resets the histogram for new counting. 313 */ 314 public Snapshot snapshotAndReset() { 315 final Bins oldBins = this.bins; 316 this.bins = new Bins(this.bins, this.bins.counts.length - 3, 0.01, 0.99); 317 final long[] percentiles = oldBins.getQuantiles(DEFAULT_QUANTILES); 318 final long count = oldBins.count.sum(); 319 320 return new Snapshot() { 321 @Override 322 public long[] getQuantiles(double[] quantiles) { 323 return oldBins.getQuantiles(quantiles); 324 } 325 326 @Override 327 public long[] getQuantiles() { 328 return percentiles; 329 } 330 331 @Override 332 public long getCount() { 333 return count; 334 } 335 336 @Override 337 public long getCountAtOrBelow(long val) { 338 return oldBins.getNumAtOrBelow(val); 339 } 340 341 @Override 342 public long get25thPercentile() { 343 return percentiles[0]; 344 } 345 346 @Override 347 public long get75thPercentile() { 348 return percentiles[2]; 349 } 350 351 @Override 352 public long get90thPercentile() { 353 return percentiles[3]; 354 } 355 356 @Override 357 public long get95thPercentile() { 358 return percentiles[4]; 359 } 360 361 @Override 362 public long get98thPercentile() { 363 return percentiles[5]; 364 } 365 366 @Override 367 public long get99thPercentile() { 368 return percentiles[6]; 369 } 370 371 @Override 372 public long get999thPercentile() { 373 return percentiles[7]; 374 } 375 376 @Override 377 public long getMedian() { 378 return percentiles[1]; 379 } 380 381 @Override 382 public long getMax() { 383 return oldBins.max.get(); 384 } 385 386 @Override 387 public long getMean() { 388 return oldBins.getMean(); 389 } 390 391 @Override 392 public long getMin() { 393 return oldBins.getMin(); 394 } 395 }; 396 } 397}