1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.hadoop.hbase.util;
19
20 import java.util.concurrent.atomic.AtomicBoolean;
21 import java.util.concurrent.atomic.AtomicLong;
22
23 import org.apache.hadoop.hbase.classification.InterfaceAudience;
24 import org.apache.hadoop.hbase.classification.InterfaceStability;
25
26
27
28
29
30 @InterfaceAudience.Public
31 @InterfaceStability.Evolving
32 public class FastLongHistogram {
33
34
35
36
37 public static final int DEFAULT_NBINS = 255;
38
39 public static final double[] DEFAULT_QUANTILES =
40 new double[]{0.25, 0.5, 0.75, 0.90, 0.95, 0.98, 0.99, 0.999};
41
42
43
44
45 private static class Bins {
46 private final Counter[] counts;
47
48 private final long binsMin;
49
50 private final long binsMax;
51 private final long bins10XMax;
52 private final AtomicLong min = new AtomicLong(Long.MAX_VALUE);
53 private final AtomicLong max = new AtomicLong(0L);
54
55 private final Counter count = new Counter(0);
56 private final Counter total = new Counter(0);
57
58
59
60 private final AtomicBoolean hasData = new AtomicBoolean(false);
61
62
63
64
65 public Bins(int numBins) {
66 counts = createCounters(numBins + 3);
67 this.binsMin = 1L;
68
69
70
71 this.binsMax = 1000;
72 this.bins10XMax = binsMax * 10;
73 }
74
75
76
77
78 public Bins(Bins last, int numOfBins, double minQ, double maxQ) {
79 long[] values = last.getQuantiles(new double[] { minQ, maxQ });
80 long wd = values[1] - values[0] + 1;
81
82 this.binsMin = Math.max(0L, (long) (values[0] - wd * minQ));
83 long binsMax = (long) (values[1] + wd * (1 - maxQ)) + 1;
84
85 this.binsMax = Math.max(binsMax, this.binsMin + numOfBins);
86 this.bins10XMax = Math.max((long) (values[1] + (binsMax - 1) * 9), this.binsMax + 1);
87
88 this.counts = createCounters(numOfBins + 3);
89 }
90
91 private Counter[] createCounters(int num) {
92 Counter[] counters = new Counter[num];
93 for (int i = 0; i < num; i++) {
94 counters[i] = new Counter();
95 }
96 return counters;
97 }
98
99 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
108 return 1 + (int) ((value - this.binsMin) * (this.counts.length - 3) /
109 (this.binsMax - this.binsMin));
110
111 }
112
113
114
115
116 public void add(long value, long count) {
117 if (value < 0) {
118
119
120
121
122
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
135 this.hasData.set(true);
136 }
137
138
139
140
141 public long[] getQuantiles(double[] quantiles) {
142 if (!this.hasData.get()) {
143
144 return new long[quantiles.length];
145 }
146
147
148
149
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].get();
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
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
189 double lastCum = cum;
190 cum += counts[i];
191
192
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
201 rIndex++;
202 if (rIndex >= quantiles.length) {
203 break countsLoop;
204 }
205 qCount = total * quantiles[rIndex];
206 }
207 }
208
209 for (; rIndex < quantiles.length; rIndex++) {
210 res[rIndex] = this.max.get();
211 }
212
213 return res;
214 }
215
216
217 long getNumAtOrBelow(long val) {
218 final int targetIndex = getIndex(val);
219 long totalToCurrentIndex = 0;
220 for (int i = 0; i <= targetIndex; i++) {
221 totalToCurrentIndex += this.counts[i].get();
222 }
223 return totalToCurrentIndex;
224 }
225 }
226
227
228 private volatile Bins bins;
229
230
231
232
233 public FastLongHistogram() {
234 this(DEFAULT_NBINS);
235 }
236
237
238
239
240
241
242 public FastLongHistogram(int numOfBins) {
243 this.bins = new Bins(numOfBins);
244 }
245
246
247
248
249
250
251
252
253 public FastLongHistogram(int numOfBins, long min, long max) {
254 this(numOfBins);
255 Bins bins = new Bins(numOfBins);
256 bins.add(min, 1);
257 bins.add(max, 1);
258 this.bins = new Bins(bins, numOfBins, 0.01, 0.999);
259 }
260
261 private FastLongHistogram(Bins bins) {
262 this.bins = bins;
263 }
264
265
266
267
268 public void add(long value, long count) {
269 this.bins.add(value, count);
270 }
271
272
273
274
275 public long[] getQuantiles(double[] quantiles) {
276 return this.bins.getQuantiles(quantiles);
277 }
278
279 public long[] getQuantiles() {
280 return this.bins.getQuantiles(DEFAULT_QUANTILES);
281 }
282
283 public long getMin() {
284 long min = this.bins.min.get();
285 return min == Long.MAX_VALUE ? 0 : min;
286 }
287
288 public long getMax() {
289 return this.bins.max.get();
290 }
291
292 public long getCount() {
293 return this.bins.count.get();
294 }
295
296 public long getMean() {
297 Bins bins = this.bins;
298 long count = bins.count.get();
299 long total = bins.total.get();
300 if (count == 0) {
301 return 0;
302 }
303 return total / count;
304 }
305
306 public long getNumAtOrBelow(long value) {
307 return this.bins.getNumAtOrBelow(value);
308 }
309
310
311
312
313 public FastLongHistogram reset() {
314 Bins oldBins = this.bins;
315 this.bins = new Bins(this.bins, this.bins.counts.length - 3, 0.01, 0.99);
316 return new FastLongHistogram(oldBins);
317 }
318 }