2 * Copyright 2013-present 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>
21 #include <folly/portability/GTest.h>
22 #include <folly/stats/TimeseriesHistogram-defs.h>
25 using namespace folly;
26 using std::chrono::seconds;
38 const seconds kDurations[] = {
44 } // namespace IntMTMHTS
54 const seconds kDurations[] = {
59 } // namespace IntMHTS
61 typedef std::mt19937 RandomInt32;
63 using StatsClock = folly::LegacyStatsClock<std::chrono::seconds>;
64 StatsClock::time_point mkTimePoint(int value) {
65 return StatsClock::time_point(StatsClock::duration(value));
69 TEST(TimeseriesHistogram, Percentile) {
70 RandomInt32 random(5);
71 // [10, 109], 12 buckets including above and below
73 TimeseriesHistogram<int> h(
77 MultiLevelTimeSeries<int>(
78 60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));
80 EXPECT_EQ(0, h.getPercentileEstimate(0, IntMTMHTS::ALLTIME));
82 EXPECT_EQ(12, h.getNumBuckets());
83 EXPECT_EQ(10, h.getBucketSize());
84 EXPECT_EQ(10, h.getMin());
85 EXPECT_EQ(110, h.getMax());
87 for (size_t i = 0; i < h.getNumBuckets(); ++i) {
88 EXPECT_EQ(4, h.getBucket(i).numLevels());
92 h.addValue(mkTimePoint(0), 0);
93 h.addValue(mkTimePoint(0), maxVal);
94 for (int i = 0; i < 98; i++) {
95 h.addValue(mkTimePoint(0), random() % maxVal);
98 h.update(mkTimePoint(1500000000));
99 // bucket 0 stores everything below min, so its minimum
100 // is the lowest possible number
102 std::numeric_limits<int>::min(),
103 h.getPercentileBucketMin(1, IntMTMHTS::ALLTIME));
104 EXPECT_EQ(110, h.getPercentileBucketMin(99, IntMTMHTS::ALLTIME));
106 EXPECT_EQ(-2, h.getPercentileEstimate(0, IntMTMHTS::ALLTIME));
107 EXPECT_EQ(-1, h.getPercentileEstimate(1, IntMTMHTS::ALLTIME));
108 EXPECT_EQ(119, h.getPercentileEstimate(99, IntMTMHTS::ALLTIME));
109 EXPECT_EQ(120, h.getPercentileEstimate(100, IntMTMHTS::ALLTIME));
113 TEST(TimeseriesHistogram, String) {
114 RandomInt32 random(5);
115 // [10, 109], 12 buckets including above and below
117 TimeseriesHistogram<int> hist(
121 MultiLevelTimeSeries<int>(
122 60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));
125 hist.addValue(mkTimePoint(0), 0);
126 hist.addValue(mkTimePoint(0), maxVal);
127 for (int i = 0; i < 98; i++) {
128 hist.addValue(mkTimePoint(0), random() % maxVal);
131 hist.update(mkTimePoint(0));
133 const char* const kStringValues1[IntMTMHTS::NUM_LEVELS] = {
134 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
135 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
136 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
137 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
138 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
139 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
140 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
141 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
144 CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());
146 for (size_t level = 0; level < hist.getNumLevels(); ++level) {
147 EXPECT_EQ(kStringValues1[level], hist.getString(level));
150 const char* const kStringValues2[IntMTMHTS::NUM_LEVELS] = {
151 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
152 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
153 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
154 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
155 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
156 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
157 "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
158 "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
161 CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());
163 for (size_t level = 0; level < hist.getNumLevels(); ++level) {
164 EXPECT_EQ(kStringValues2[level], hist.getString(level));
169 TEST(TimeseriesHistogram, Clear) {
171 TimeseriesHistogram<int> hist(
175 MultiLevelTimeSeries<int>(
176 60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));
178 for (int now = 0; now < 3600; now++) {
179 for (int i = 0; i < 100; i++) {
180 hist.addValue(mkTimePoint(now), i, 2); // adds each item 2 times
187 for (size_t b = 0; b < hist.getNumBuckets(); ++b) {
188 EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::MINUTE));
189 EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
190 EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::HOUR));
191 EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
194 for (int pct = 0; pct <= 100; pct++) {
195 EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
196 EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
197 EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
198 EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
200 EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::MINUTE));
201 EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::TEN_MINUTE));
202 EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::HOUR));
203 EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::ALLTIME));
208 TEST(TimeseriesHistogram, Basic) {
210 TimeseriesHistogram<int> hist(
214 MultiLevelTimeSeries<int>(
215 60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));
217 for (int now = 0; now < 3600; now++) {
218 for (int i = 0; i < 100; i++) {
219 hist.addValue(mkTimePoint(now), i);
223 hist.update(mkTimePoint(3599));
224 for (int pct = 1; pct <= 100; pct++) {
225 int expected = (pct - 1) / 10 * 10;
226 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
228 expected, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
229 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
230 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
233 for (size_t b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
234 EXPECT_EQ(600, hist.getBucket(b).count(IntMTMHTS::MINUTE));
235 EXPECT_EQ(6000, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
236 EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::HOUR));
237 EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
239 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
241 0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::MINUTE));
243 EXPECT_EQ(6000, hist.count(IntMTMHTS::MINUTE));
244 EXPECT_EQ(60000, hist.count(IntMTMHTS::TEN_MINUTE));
245 EXPECT_EQ(360000, hist.count(IntMTMHTS::HOUR));
246 EXPECT_EQ(360000, hist.count(IntMTMHTS::ALLTIME));
248 // Each second we added 4950 total over 100 data points
249 EXPECT_EQ(297000, hist.sum(IntMTMHTS::MINUTE));
250 EXPECT_EQ(2970000, hist.sum(IntMTMHTS::TEN_MINUTE));
251 EXPECT_EQ(17820000, hist.sum(IntMTMHTS::HOUR));
252 EXPECT_EQ(17820000, hist.sum(IntMTMHTS::ALLTIME));
254 EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::MINUTE));
255 EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::TEN_MINUTE));
256 EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::HOUR));
257 EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::ALLTIME));
258 EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::MINUTE));
259 EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::TEN_MINUTE));
260 EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::HOUR));
261 EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::ALLTIME));
263 EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::MINUTE));
264 EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::TEN_MINUTE));
265 EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::HOUR));
266 EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::ALLTIME));
267 EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::MINUTE));
268 EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::TEN_MINUTE));
269 EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::HOUR));
270 EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::ALLTIME));
272 EXPECT_EQ(1000, hist.count(mkTimePoint(10), mkTimePoint(20)));
273 EXPECT_EQ(49500, hist.sum(mkTimePoint(10), mkTimePoint(20)));
274 EXPECT_EQ(4950, hist.rate(mkTimePoint(10), mkTimePoint(20)));
275 EXPECT_EQ(49.5, hist.avg<double>(mkTimePoint(10), mkTimePoint(20)));
277 EXPECT_EQ(200, hist.count(mkTimePoint(3550), mkTimePoint(3552)));
278 EXPECT_EQ(9900, hist.sum(mkTimePoint(3550), mkTimePoint(3552)));
279 EXPECT_EQ(4950, hist.rate(mkTimePoint(3550), mkTimePoint(3552)));
280 EXPECT_EQ(49.5, hist.avg<double>(mkTimePoint(3550), mkTimePoint(3552)));
282 EXPECT_EQ(0, hist.count(mkTimePoint(4550), mkTimePoint(4552)));
283 EXPECT_EQ(0, hist.sum(mkTimePoint(4550), mkTimePoint(4552)));
284 EXPECT_EQ(0, hist.rate(mkTimePoint(4550), mkTimePoint(4552)));
285 EXPECT_EQ(0, hist.avg<double>(mkTimePoint(4550), mkTimePoint(4552)));
291 TimeseriesHistogram<int> hist(
295 MultiLevelTimeSeries<int>(
296 60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));
298 for (int now = 0; now < 3600; now++) {
299 for (int i = 0; i < 100; i++) {
300 hist.addValue(mkTimePoint(now), i, 2); // adds each item 2 times
304 hist.update(mkTimePoint(3599));
305 for (int pct = 1; pct <= 100; pct++) {
306 int expected = (pct - 1) / 10 * 10;
307 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
309 expected, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
310 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
311 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
314 for (size_t b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
315 EXPECT_EQ(600 * 2, hist.getBucket(b).count(IntMTMHTS::MINUTE));
316 EXPECT_EQ(6000 * 2, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
317 EXPECT_EQ(36000 * 2, hist.getBucket(b).count(IntMTMHTS::HOUR));
318 EXPECT_EQ(36000 * 2, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
320 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
322 0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::MINUTE));
328 TimeseriesHistogram<int> hist(
332 MultiLevelTimeSeries<int>(
333 60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));
335 for (int now = 0; now < 3600; now++) {
336 for (int i = 0; i < 50; i++) {
337 hist.addValue(mkTimePoint(now), i * 2, 2); // adds each item 2 times
341 hist.update(mkTimePoint(3599));
342 for (int pct = 1; pct <= 100; pct++) {
343 int expected = (pct - 1) / 10 * 10;
344 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
346 expected, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
347 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
348 EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
351 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
352 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::TEN_MINUTE));
353 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::HOUR));
354 EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::ALLTIME));
356 0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::MINUTE));
359 hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::TEN_MINUTE));
361 0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::HOUR));
363 0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::ALLTIME));
365 for (size_t b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
366 EXPECT_EQ(600, hist.getBucket(b).count(IntMTMHTS::MINUTE));
367 EXPECT_EQ(6000, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
368 EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::HOUR));
369 EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
372 for (int i = 0; i < 100; ++i) {
373 hist.addValue(mkTimePoint(3599), 200 + i);
375 hist.update(mkTimePoint(3599));
378 hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::ALLTIME));
382 TEST(TimeseriesHistogram, QueryByInterval) {
383 TimeseriesHistogram<int> mhts(
387 MultiLevelTimeSeries<int>(60, IntMHTS::NUM_LEVELS, IntMHTS::kDurations));
389 mhts.update(mkTimePoint(0));
392 for (curTime = 0; curTime < 7200; curTime++) {
393 mhts.addValue(mkTimePoint(curTime), 1);
395 for (curTime = 7200; curTime < 7200 + 3540; curTime++) {
396 mhts.addValue(mkTimePoint(curTime), 10);
398 for (curTime = 7200 + 3540; curTime < 7200 + 3600; curTime++) {
399 mhts.addValue(mkTimePoint(curTime), 100);
402 mhts.update(mkTimePoint(7200 + 3600 - 1));
404 struct TimeInterval {
405 TimeInterval(int s, int e) : start(mkTimePoint(s)), end(mkTimePoint(e)) {}
407 StatsClock::time_point start;
408 StatsClock::time_point end;
410 TimeInterval intervals[12] = {
411 {curTime - 60, curTime},
412 {curTime - 3600, curTime},
413 {curTime - 7200, curTime},
414 {curTime - 3600, curTime - 60},
415 {curTime - 7200, curTime - 60},
416 {curTime - 7200, curTime - 3600},
417 {curTime - 50, curTime - 20},
418 {curTime - 3020, curTime - 20},
419 {curTime - 7200, curTime - 20},
420 {curTime - 3000, curTime - 1000},
421 {curTime - 7200, curTime - 1000},
422 {curTime - 7200, curTime - 3600},
425 int expectedSums[12] = {
440 int expectedCounts[12] = {
441 60, 3600, 7200, 3540, 7139, 3600, 30, 3000, 7178, 2000, 6199, 3600,
444 // The first 7200 values added all fell below the histogram minimum,
445 // and went into the bucket that tracks all of the too-small values.
446 // This bucket reports a minimum value of the smallest possible integer.
447 int belowMinBucket = std::numeric_limits<int>::min();
449 int expectedValues[12][3] = {
452 {belowMinBucket, belowMinBucket, 8}, // alltime
454 {belowMinBucket, belowMinBucket, 8}, // alltime
455 {belowMinBucket, belowMinBucket, 8}, // alltime
458 {belowMinBucket, belowMinBucket, 8}, // alltime
460 {belowMinBucket, belowMinBucket, 8}, // alltime
461 {belowMinBucket, belowMinBucket, 8} // alltime
464 for (int i = 0; i < 12; i++) {
465 const auto& itv = intervals[i];
466 int s = mhts.sum(itv.start, itv.end);
467 EXPECT_EQ(expectedSums[i], s);
469 int c = mhts.count(itv.start, itv.end);
470 EXPECT_EQ(expectedCounts[i], c);
474 for (int i = 1; i <= 100; i++) {
475 EXPECT_EQ(96, mhts.getPercentileBucketMin(i, 0));
478 mhts.getPercentileBucketMin(
479 i, mkTimePoint(curTime - 60), mkTimePoint(curTime)));
482 mhts.getPercentileBucketMin(
483 i, mkTimePoint(curTime - 3540), mkTimePoint(curTime - 60)));
486 EXPECT_EQ(8, mhts.getPercentileBucketMin(1, 1));
487 EXPECT_EQ(8, mhts.getPercentileBucketMin(98, 1));
488 EXPECT_EQ(96, mhts.getPercentileBucketMin(99, 1));
489 EXPECT_EQ(96, mhts.getPercentileBucketMin(100, 1));
491 EXPECT_EQ(belowMinBucket, mhts.getPercentileBucketMin(1, 2));
492 EXPECT_EQ(belowMinBucket, mhts.getPercentileBucketMin(66, 2));
493 EXPECT_EQ(8, mhts.getPercentileBucketMin(67, 2));
494 EXPECT_EQ(8, mhts.getPercentileBucketMin(99, 2));
495 EXPECT_EQ(96, mhts.getPercentileBucketMin(100, 2));
497 // 0 is currently the value for bucket 0 (below min)
498 for (int i = 0; i < 12; i++) {
499 const auto& itv = intervals[i];
500 int v = mhts.getPercentileBucketMin(1, itv.start, itv.end);
501 EXPECT_EQ(expectedValues[i][0], v);
503 v = mhts.getPercentileBucketMin(50, itv.start, itv.end);
504 EXPECT_EQ(expectedValues[i][1], v);
506 v = mhts.getPercentileBucketMin(99, itv.start, itv.end);
507 EXPECT_EQ(expectedValues[i][2], v);
510 for (int i = 0; i < 12; i++) {
511 const auto& itv = intervals[i];
512 // Some of the older intervals that fall in the alltime bucket
513 // are off by 1 or 2 in their estimated counts.
514 size_t tolerance = 0;
515 if (itv.start <= mkTimePoint(curTime - 7200)) {
517 } else if (itv.start <= mkTimePoint(curTime - 3000)) {
520 size_t actualCount = (itv.end - itv.start).count();
521 size_t estimatedCount = mhts.count(itv.start, itv.end);
522 EXPECT_GE(actualCount, estimatedCount);
523 EXPECT_LE(actualCount - tolerance, estimatedCount);
527 TEST(TimeseriesHistogram, SingleUniqueValue) {
528 int values[] = {-1, 0, 500, 1000, 1500};
529 for (int ii = 0; ii < 5; ++ii) {
530 int value = values[ii];
531 TimeseriesHistogram<int> h(
535 MultiLevelTimeSeries<int>(
536 60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));
538 const int kNumIters = 1000;
539 for (int jj = 0; jj < kNumIters; ++jj) {
540 h.addValue(mkTimePoint(1), value);
542 h.update(mkTimePoint(1));
543 // since we've only added one unique value, all percentiles should
545 EXPECT_EQ(h.getPercentileEstimate(10, 0), value);
546 EXPECT_EQ(h.getPercentileEstimate(50, 0), value);
547 EXPECT_EQ(h.getPercentileEstimate(99, 0), value);
549 // Things get trickier if there are multiple unique values.
550 const int kNewValue = 750;
551 for (int kk = 0; kk < 2 * kNumIters; ++kk) {
552 h.addValue(mkTimePoint(1), kNewValue);
554 h.update(mkTimePoint(1));
555 EXPECT_NEAR(h.getPercentileEstimate(50, 0), kNewValue + 5, 5);
556 if (value >= 0 && value <= 1000) {
557 // only do further testing if value is within our bucket range,
558 // else estimates can be wildly off
559 if (kNewValue > value) {
560 EXPECT_NEAR(h.getPercentileEstimate(10, 0), value + 5, 5);
561 EXPECT_NEAR(h.getPercentileEstimate(99, 0), kNewValue + 5, 5);
563 EXPECT_NEAR(h.getPercentileEstimate(10, 0), kNewValue + 5, 5);
564 EXPECT_NEAR(h.getPercentileEstimate(99, 0), value + 5, 5);