2 * Copyright 2016 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #include <folly/stats/TimeseriesHistogram.h>
18 #include <folly/stats/TimeseriesHistogram-defs.h>
22 #include <gtest/gtest.h>
25 using namespace folly;
26 using std::chrono::seconds;
37 const seconds kDurations[] = {
38 seconds(60), seconds(600), seconds(3600), seconds(0)
50 const seconds kDurations[] = {
51 seconds(60), seconds(3600), seconds(0)
55 typedef std::mt19937 RandomInt32;
57 TEST(TimeseriesHistogram, Percentile) {
58 RandomInt32 random(5);
59 // [10, 109], 12 buckets including above and below
61 TimeseriesHistogram<int> h(10, 10, 110,
62 MultiLevelTimeSeries<int>(
63 60, IntMTMHTS::NUM_LEVELS,
64 IntMTMHTS::kDurations));
66 EXPECT_EQ(0, h.getPercentileEstimate(0, IntMTMHTS::ALLTIME));
68 EXPECT_EQ(12, h.getNumBuckets());
69 EXPECT_EQ(10, h.getBucketSize());
70 EXPECT_EQ(10, h.getMin());
71 EXPECT_EQ(110, h.getMax());
73 for (int i = 0; i < h.getNumBuckets(); ++i) {
74 EXPECT_EQ(4, h.getBucket(i).numLevels());
78 h.addValue(seconds(0), 0);
79 h.addValue(seconds(0), maxVal);
80 for (int i = 0; i < 98; i++) {
81 h.addValue(seconds(0), random() % maxVal);
84 h.update(std::chrono::duration_cast<std::chrono::seconds>(
85 std::chrono::system_clock::now().time_since_epoch()));
86 // bucket 0 stores everything below min, so its minimum
87 // is the lowest possible number
88 EXPECT_EQ(std::numeric_limits<int>::min(),
89 h.getPercentileBucketMin(1, IntMTMHTS::ALLTIME));
90 EXPECT_EQ(110, h.getPercentileBucketMin(99, IntMTMHTS::ALLTIME));
92 EXPECT_EQ(-2, h.getPercentileEstimate(0, IntMTMHTS::ALLTIME));
93 EXPECT_EQ(-1, h.getPercentileEstimate(1, IntMTMHTS::ALLTIME));
94 EXPECT_EQ(119, h.getPercentileEstimate(99, IntMTMHTS::ALLTIME));
95 EXPECT_EQ(120, h.getPercentileEstimate(100, IntMTMHTS::ALLTIME));
99 TEST(TimeseriesHistogram, String) {
100 RandomInt32 random(5);
101 // [10, 109], 12 buckets including above and below
103 TimeseriesHistogram<int> hist(10, 10, 110,
104 MultiLevelTimeSeries<int>(
105 60, IntMTMHTS::NUM_LEVELS,
106 IntMTMHTS::kDurations));
109 hist.addValue(seconds(0), 0);
110 hist.addValue(seconds(0), maxVal);
111 for (int i = 0; i < 98; i++) {
112 hist.addValue(seconds(0), random() % maxVal);
115 hist.update(seconds(0));
117 const char* const kStringValues1[IntMTMHTS::NUM_LEVELS] = {
118 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
119 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
120 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
121 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
122 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
123 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
124 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
125 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
128 CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());
130 for (int level = 0; level < hist.getNumLevels(); ++level) {
131 EXPECT_EQ(kStringValues1[level], hist.getString(level));
134 const char* const kStringValues2[IntMTMHTS::NUM_LEVELS] = {
135 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
136 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
137 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
138 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
139 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
140 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
141 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
142 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
145 CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());
147 for (int level = 0; level < hist.getNumLevels(); ++level) {
148 EXPECT_EQ(kStringValues2[level], hist.getString(level));
153 TEST(TimeseriesHistogram, Clear) {
155 TimeseriesHistogram<int> hist(10, 0, 100,
156 MultiLevelTimeSeries<int>(
157 60, IntMTMHTS::NUM_LEVELS,
158 IntMTMHTS::kDurations));
160 for (int now = 0; now < 3600; now++) {
161 for (int i = 0; i < 100; i++) {
162 hist.addValue(seconds(now), i, 2); // adds each item 2 times
169 for (int b = 0; b < hist.getNumBuckets(); ++b) {
170 EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::MINUTE));
171 EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
172 EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::HOUR));
173 EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
176 for (int pct = 0; pct <= 100; pct++) {
177 EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
178 EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
179 EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
180 EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
182 EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::MINUTE));
183 EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::TEN_MINUTE));
184 EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::HOUR));
185 EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::ALLTIME));
191 TEST(TimeseriesHistogram, Basic) {
193 TimeseriesHistogram<int> hist(10, 0, 100,
194 MultiLevelTimeSeries<int>(
195 60, IntMTMHTS::NUM_LEVELS,
196 IntMTMHTS::kDurations));
198 for (int now = 0; now < 3600; now++) {
199 for (int i = 0; i < 100; i++) {
200 hist.addValue(seconds(now), i);
204 hist.update(seconds(3599));
205 for (int pct = 1; pct <= 100; pct++) {
206 int expected = (pct - 1) / 10 * 10;
207 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
208 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct,
209 IntMTMHTS::TEN_MINUTE));
210 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
211 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
214 for (int b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
215 EXPECT_EQ(600, hist.getBucket(b).count(IntMTMHTS::MINUTE));
216 EXPECT_EQ(6000, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
217 EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::HOUR));
218 EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
220 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
221 EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
224 EXPECT_EQ(6000, hist.count(IntMTMHTS::MINUTE));
225 EXPECT_EQ(60000, hist.count(IntMTMHTS::TEN_MINUTE));
226 EXPECT_EQ(360000, hist.count(IntMTMHTS::HOUR));
227 EXPECT_EQ(360000, hist.count(IntMTMHTS::ALLTIME));
229 // Each second we added 4950 total over 100 data points
230 EXPECT_EQ(297000, hist.sum(IntMTMHTS::MINUTE));
231 EXPECT_EQ(2970000, hist.sum(IntMTMHTS::TEN_MINUTE));
232 EXPECT_EQ(17820000, hist.sum(IntMTMHTS::HOUR));
233 EXPECT_EQ(17820000, hist.sum(IntMTMHTS::ALLTIME));
235 EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::MINUTE));
236 EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::TEN_MINUTE));
237 EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::HOUR));
238 EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::ALLTIME));
239 EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::MINUTE));
240 EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::TEN_MINUTE));
241 EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::HOUR));
242 EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::ALLTIME));
244 EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::MINUTE));
245 EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::TEN_MINUTE));
246 EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::HOUR));
247 EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::ALLTIME));
248 EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::MINUTE));
249 EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::TEN_MINUTE));
250 EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::HOUR));
251 EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::ALLTIME));
253 EXPECT_EQ(1000, hist.count(seconds(10), seconds(20)));
254 EXPECT_EQ(49500, hist.sum(seconds(10), seconds(20)));
255 EXPECT_EQ(4950, hist.rate(seconds(10), seconds(20)));
256 EXPECT_EQ(49.5, hist.avg<double>(seconds(10), seconds(20)));
258 EXPECT_EQ(200, hist.count(seconds(3550), seconds(3552)));
259 EXPECT_EQ(9900, hist.sum(seconds(3550), seconds(3552)));
260 EXPECT_EQ(4950, hist.rate(seconds(3550), seconds(3552)));
261 EXPECT_EQ(49.5, hist.avg<double>(seconds(3550), seconds(3552)));
263 EXPECT_EQ(0, hist.count(seconds(4550), seconds(4552)));
264 EXPECT_EQ(0, hist.sum(seconds(4550), seconds(4552)));
265 EXPECT_EQ(0, hist.rate(seconds(4550), seconds(4552)));
266 EXPECT_EQ(0, hist.avg<double>(seconds(4550), seconds(4552)));
272 TimeseriesHistogram<int> hist(10, 0, 100,
273 MultiLevelTimeSeries<int>(
274 60, IntMTMHTS::NUM_LEVELS,
275 IntMTMHTS::kDurations));
277 for (int now = 0; now < 3600; now++) {
278 for (int i = 0; i < 100; i++) {
279 hist.addValue(seconds(now), i, 2); // adds each item 2 times
283 hist.update(seconds(3599));
284 for (int pct = 1; pct <= 100; pct++) {
285 int expected = (pct - 1) / 10 * 10;
286 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
287 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct,
288 IntMTMHTS::TEN_MINUTE));
289 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
290 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
293 for (int b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
294 EXPECT_EQ(600 * 2, hist.getBucket(b).count(IntMTMHTS::MINUTE));
295 EXPECT_EQ(6000 * 2, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
296 EXPECT_EQ(36000 * 2, hist.getBucket(b).count(IntMTMHTS::HOUR));
297 EXPECT_EQ(36000 * 2, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
299 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
300 EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
307 TimeseriesHistogram<int> hist(10, 0, 100,
308 MultiLevelTimeSeries<int>(
309 60, IntMTMHTS::NUM_LEVELS,
310 IntMTMHTS::kDurations));
312 for (int now = 0; now < 3600; now++) {
313 for (int i = 0; i < 50; i++) {
314 hist.addValue(seconds(now), i * 2, 2); // adds each item 2 times
318 hist.update(seconds(3599));
319 for (int pct = 1; pct <= 100; pct++) {
320 int expected = (pct - 1) / 10 * 10;
321 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
322 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct,
323 IntMTMHTS::TEN_MINUTE));
324 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
325 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
328 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
329 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::TEN_MINUTE));
330 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::HOUR));
331 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::ALLTIME));
332 EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
335 hist.getBucket(hist.getNumBuckets() - 1).
336 count(IntMTMHTS::TEN_MINUTE));
337 EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
340 hist.getBucket(hist.getNumBuckets() - 1).count(
341 IntMTMHTS::ALLTIME));
343 for (int b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
344 EXPECT_EQ(600, hist.getBucket(b).count(IntMTMHTS::MINUTE));
345 EXPECT_EQ(6000, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
346 EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::HOUR));
347 EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
350 for (int i = 0; i < 100; ++i) {
351 hist.addValue(seconds(3599), 200 + i);
353 hist.update(seconds(3599));
355 hist.getBucket(hist.getNumBuckets() - 1).count(
356 IntMTMHTS::ALLTIME));
361 TEST(TimeseriesHistogram, QueryByInterval) {
362 TimeseriesHistogram<int> mhts(8, 8, 120,
363 MultiLevelTimeSeries<int>(
364 60, IntMHTS::NUM_LEVELS,
365 IntMHTS::kDurations));
367 mhts.update(seconds(0));
370 for (curTime = 0; curTime < 7200; curTime++) {
371 mhts.addValue(seconds(curTime), 1);
373 for (curTime = 7200; curTime < 7200 + 3540; curTime++) {
374 mhts.addValue(seconds(curTime), 10);
376 for (curTime = 7200 + 3540; curTime < 7200 + 3600; curTime++) {
377 mhts.addValue(seconds(curTime), 100);
380 mhts.update(seconds(7200 + 3600 - 1));
382 struct TimeInterval {
383 TimeInterval(int s, int e)
384 : start(s), end(e) {}
386 std::chrono::seconds start;
387 std::chrono::seconds end;
389 TimeInterval intervals[12] = {
390 { curTime - 60, curTime },
391 { curTime - 3600, curTime },
392 { curTime - 7200, curTime },
393 { curTime - 3600, curTime - 60 },
394 { curTime - 7200, curTime - 60 },
395 { curTime - 7200, curTime - 3600 },
396 { curTime - 50, curTime - 20 },
397 { curTime - 3020, curTime - 20 },
398 { curTime - 7200, curTime - 20 },
399 { curTime - 3000, curTime - 1000 },
400 { curTime - 7200, curTime - 1000 },
401 { curTime - 7200, curTime - 3600 },
404 int expectedSums[12] = {
405 6000, 41400, 32400, 35400, 32129, 16200, 3000, 33600, 32308, 20000, 27899,
409 int expectedCounts[12] = {
410 60, 3600, 7200, 3540, 7139, 3600, 30, 3000, 7178, 2000, 6199, 3600
413 // The first 7200 values added all fell below the histogram minimum,
414 // and went into the bucket that tracks all of the too-small values.
415 // This bucket reports a minimum value of the smallest possible integer.
416 int belowMinBucket = std::numeric_limits<int>::min();
418 int expectedValues[12][3] = {
421 { belowMinBucket, belowMinBucket, 8}, // alltime
423 { belowMinBucket, belowMinBucket, 8}, // alltime
424 { belowMinBucket, belowMinBucket, 8}, // alltime
427 { belowMinBucket, belowMinBucket, 8}, // alltime
429 { belowMinBucket, belowMinBucket, 8}, // alltime
430 { belowMinBucket, belowMinBucket, 8} // alltime
433 for (int i = 0; i < 12; i++) {
434 const auto& itv = intervals[i];
435 int s = mhts.sum(itv.start, itv.end);
436 EXPECT_EQ(expectedSums[i], s);
438 int c = mhts.count(itv.start, itv.end);
439 EXPECT_EQ(expectedCounts[i], c);
443 for (int i = 1; i <= 100; i++) {
444 EXPECT_EQ(96, mhts.getPercentileBucketMin(i, 0));
445 EXPECT_EQ(96, mhts.getPercentileBucketMin(i, seconds(curTime - 60),
447 EXPECT_EQ(8, mhts.getPercentileBucketMin(i, seconds(curTime - 3540),
448 seconds(curTime - 60)));
451 EXPECT_EQ(8, mhts.getPercentileBucketMin(1, 1));
452 EXPECT_EQ(8, mhts.getPercentileBucketMin(98, 1));
453 EXPECT_EQ(96, mhts.getPercentileBucketMin(99, 1));
454 EXPECT_EQ(96, mhts.getPercentileBucketMin(100, 1));
456 EXPECT_EQ(belowMinBucket, mhts.getPercentileBucketMin(1, 2));
457 EXPECT_EQ(belowMinBucket, mhts.getPercentileBucketMin(66, 2));
458 EXPECT_EQ(8, mhts.getPercentileBucketMin(67, 2));
459 EXPECT_EQ(8, mhts.getPercentileBucketMin(99, 2));
460 EXPECT_EQ(96, mhts.getPercentileBucketMin(100, 2));
462 // 0 is currently the value for bucket 0 (below min)
463 for (int i = 0; i < 12; i++) {
464 const auto& itv = intervals[i];
465 int v = mhts.getPercentileBucketMin(1, itv.start, itv.end);
466 EXPECT_EQ(expectedValues[i][0], v);
468 v = mhts.getPercentileBucketMin(50, itv.start, itv.end);
469 EXPECT_EQ(expectedValues[i][1], v);
471 v = mhts.getPercentileBucketMin(99, itv.start, itv.end);
472 EXPECT_EQ(expectedValues[i][2], v);
475 for (int i = 0; i < 12; i++) {
476 const auto& itv = intervals[i];
477 // Some of the older intervals that fall in the alltime bucket
478 // are off by 1 or 2 in their estimated counts.
479 size_t tolerance = 0;
480 if (itv.start <= seconds(curTime - 7200)) {
482 } else if (itv.start <= seconds(curTime - 3000)) {
485 size_t actualCount = (itv.end - itv.start).count();
486 size_t estimatedCount = mhts.count(itv.start, itv.end);
487 EXPECT_GE(actualCount, estimatedCount);
488 EXPECT_LE(actualCount - tolerance, estimatedCount);
492 TEST(TimeseriesHistogram, SingleUniqueValue) {
493 int values[] = {-1, 0, 500, 1000, 1500};
494 for (int ii = 0; ii < 5; ++ii) {
495 int value = values[ii];
496 TimeseriesHistogram<int> h(10, 0, 1000,
497 MultiLevelTimeSeries<int>(
498 60, IntMTMHTS::NUM_LEVELS,
499 IntMTMHTS::kDurations));
501 const int kNumIters = 1000;
502 for (int jj = 0; jj < kNumIters; ++jj) {
503 h.addValue(seconds(time(nullptr)), value);
505 h.update(seconds(time(nullptr)));
506 // since we've only added one unique value, all percentiles should
508 EXPECT_EQ(h.getPercentileEstimate(10, 0), value);
509 EXPECT_EQ(h.getPercentileEstimate(50, 0), value);
510 EXPECT_EQ(h.getPercentileEstimate(99, 0), value);
512 // Things get trickier if there are multiple unique values.
513 const int kNewValue = 750;
514 for (int kk = 0; kk < 2*kNumIters; ++kk) {
515 h.addValue(seconds(time(nullptr)), kNewValue);
517 h.update(seconds(time(nullptr)));
518 EXPECT_NEAR(h.getPercentileEstimate(50, 0), kNewValue+5, 5);
519 if (value >= 0 && value <= 1000) {
520 // only do further testing if value is within our bucket range,
521 // else estimates can be wildly off
522 if (kNewValue > value) {
523 EXPECT_NEAR(h.getPercentileEstimate(10, 0), value+5, 5);
524 EXPECT_NEAR(h.getPercentileEstimate(99, 0), kNewValue+5, 5);
526 EXPECT_NEAR(h.getPercentileEstimate(10, 0), kNewValue+5, 5);
527 EXPECT_NEAR(h.getPercentileEstimate(99, 0), value+5, 5);