folly/test/TimeseriesHistogramTest.cpp

   1 /*
   2  * Copyright 2015 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 #include <folly/stats/TimeseriesHistogram.h>
  18 #include <folly/stats/TimeseriesHistogram-defs.h>
  19
  20 #include <gtest/gtest.h>
  21
  22 using namespace std;
  23 using namespace folly;
  24 using std::chrono::seconds;
  25
  26 namespace IntMTMHTS {
  27   enum Levels {
  28     MINUTE,
  29     TEN_MINUTE,
  30     HOUR,
  31     ALLTIME,
  32     NUM_LEVELS,
  33   };
  34
  35   const seconds kDurations[] = {
  36     seconds(60), seconds(600), seconds(3600), seconds(0)
  37   };
  38 };
  39
  40 namespace IntMHTS {
  41   enum Levels {
  42     MINUTE,
  43     HOUR,
  44     ALLTIME,
  45     NUM_LEVELS,
  46   };
  47
  48   const seconds kDurations[] = {
  49     seconds(60), seconds(3600), seconds(0)
  50   };
  51 };
  52
  53 typedef std::mt19937 RandomInt32;
  54
  55 TEST(TimeseriesHistogram, Percentile) {
  56   RandomInt32 random(5);
  57   // [10, 109], 12 buckets including above and below
  58   {
  59     TimeseriesHistogram<int> h(10, 10, 110,
  60                                MultiLevelTimeSeries<int>(
  61                                  60, IntMTMHTS::NUM_LEVELS,
  62                                  IntMTMHTS::kDurations));
  63
  64     EXPECT_EQ(0, h.getPercentileEstimate(0, IntMTMHTS::ALLTIME));
  65
  66     EXPECT_EQ(12, h.getNumBuckets());
  67     EXPECT_EQ(10, h.getBucketSize());
  68     EXPECT_EQ(10, h.getMin());
  69     EXPECT_EQ(110, h.getMax());
  70
  71     for (int i = 0; i < h.getNumBuckets(); ++i) {
  72       EXPECT_EQ(4, h.getBucket(i).numLevels());
  73     }
  74
  75     int maxVal = 120;
  76     h.addValue(seconds(0), 0);
  77     h.addValue(seconds(0), maxVal);
  78     for (int i = 0; i < 98; i++) {
  79       h.addValue(seconds(0), random() % maxVal);
  80     }
  81
  82     h.update(std::chrono::duration_cast<std::chrono::seconds>(
  83                std::chrono::system_clock::now().time_since_epoch()));
  84     // bucket 0 stores everything below min, so its minimum
  85     // is the lowest possible number
  86     EXPECT_EQ(std::numeric_limits<int>::min(),
  87               h.getPercentileBucketMin(1, IntMTMHTS::ALLTIME));
  88     EXPECT_EQ(110, h.getPercentileBucketMin(99, IntMTMHTS::ALLTIME));
  89
  90     EXPECT_EQ(-2, h.getPercentileEstimate(0, IntMTMHTS::ALLTIME));
  91     EXPECT_EQ(-1, h.getPercentileEstimate(1, IntMTMHTS::ALLTIME));
  92     EXPECT_EQ(119, h.getPercentileEstimate(99, IntMTMHTS::ALLTIME));
  93     EXPECT_EQ(120, h.getPercentileEstimate(100, IntMTMHTS::ALLTIME));
  94   }
  95 }
  96
  97 TEST(TimeseriesHistogram, String) {
  98   RandomInt32 random(5);
  99   // [10, 109], 12 buckets including above and below
 100   {
 101     TimeseriesHistogram<int> hist(10, 10, 110,
 102                                   MultiLevelTimeSeries<int>(
 103                                     60, IntMTMHTS::NUM_LEVELS,
 104                                     IntMTMHTS::kDurations));
 105
 106     int maxVal = 120;
 107     hist.addValue(seconds(0), 0);
 108     hist.addValue(seconds(0), maxVal);
 109     for (int i = 0; i < 98; i++) {
 110       hist.addValue(seconds(0), random() % maxVal);
 111     }
 112
 113     hist.update(seconds(0));
 114
 115     const char* const kStringValues1[IntMTMHTS::NUM_LEVELS] =  {
 116       "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
 117         "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
 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     };
 125
 126     CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());
 127
 128     for (int level = 0; level < hist.getNumLevels(); ++level) {
 129       EXPECT_EQ(kStringValues1[level], hist.getString(level));
 130     }
 131
 132     const char* const kStringValues2[IntMTMHTS::NUM_LEVELS] =  {
 133       "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
 134         "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
 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     };
 142
 143     CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());
 144
 145     for (int level = 0; level < hist.getNumLevels(); ++level) {
 146       EXPECT_EQ(kStringValues2[level], hist.getString(level));
 147     }
 148   }
 149 }
 150
 151 TEST(TimeseriesHistogram, Clear) {
 152   {
 153     TimeseriesHistogram<int> hist(10, 0, 100,
 154                                   MultiLevelTimeSeries<int>(
 155                                     60, IntMTMHTS::NUM_LEVELS,
 156                                     IntMTMHTS::kDurations));
 157
 158     for (int now = 0; now < 3600; now++) {
 159       for (int i = 0; i < 100; i++) {
 160         hist.addValue(seconds(now), i, 2);  // adds each item 2 times
 161       }
 162     }
 163
 164     // check clearing
 165     hist.clear();
 166
 167     for (int b = 0; b < hist.getNumBuckets(); ++b) {
 168       EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::MINUTE));
 169       EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
 170       EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::HOUR));
 171       EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
 172     }
 173
 174     for (int pct = 0; pct <= 100; pct++) {
 175       EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
 176       EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
 177       EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
 178       EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
 179
 180       EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::MINUTE));
 181       EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::TEN_MINUTE));
 182       EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::HOUR));
 183       EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::ALLTIME));
 184     }
 185   }
 186 }
 187
 188
 189 TEST(TimeseriesHistogram, Basic) {
 190   {
 191     TimeseriesHistogram<int> hist(10, 0, 100,
 192                                   MultiLevelTimeSeries<int>(
 193                                     60, IntMTMHTS::NUM_LEVELS,
 194                                     IntMTMHTS::kDurations));
 195
 196     for (int now = 0; now < 3600; now++) {
 197       for (int i = 0; i < 100; i++) {
 198         hist.addValue(seconds(now), i);
 199       }
 200     }
 201
 202     hist.update(seconds(3599));
 203     for (int pct = 1; pct <= 100; pct++) {
 204       int expected = (pct - 1) / 10 * 10;
 205       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
 206       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct,
 207                                                       IntMTMHTS::TEN_MINUTE));
 208       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
 209       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
 210     }
 211
 212     for (int b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
 213       EXPECT_EQ(600, hist.getBucket(b).count(IntMTMHTS::MINUTE));
 214       EXPECT_EQ(6000, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
 215       EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::HOUR));
 216       EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
 217     }
 218     EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
 219     EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
 220                 IntMTMHTS::MINUTE));
 221   }
 222
 223   // -----------------
 224
 225   {
 226     TimeseriesHistogram<int> hist(10, 0, 100,
 227                                   MultiLevelTimeSeries<int>(
 228                                     60, IntMTMHTS::NUM_LEVELS,
 229                                     IntMTMHTS::kDurations));
 230
 231     for (int now = 0; now < 3600; now++) {
 232       for (int i = 0; i < 100; i++) {
 233         hist.addValue(seconds(now), i, 2);  // adds each item 2 times
 234       }
 235     }
 236
 237     hist.update(seconds(3599));
 238     for (int pct = 1; pct <= 100; pct++) {
 239       int expected = (pct - 1) / 10 * 10;
 240       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
 241       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct,
 242                                                       IntMTMHTS::TEN_MINUTE));
 243       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
 244       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
 245    }
 246
 247     for (int b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
 248       EXPECT_EQ(600 * 2, hist.getBucket(b).count(IntMTMHTS::MINUTE));
 249       EXPECT_EQ(6000 * 2, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
 250       EXPECT_EQ(36000 * 2, hist.getBucket(b).count(IntMTMHTS::HOUR));
 251       EXPECT_EQ(36000 * 2, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
 252     }
 253     EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
 254     EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
 255                 IntMTMHTS::MINUTE));
 256   }
 257
 258   // -----------------
 259
 260   {
 261     TimeseriesHistogram<int> hist(10, 0, 100,
 262                                   MultiLevelTimeSeries<int>(
 263                                     60, IntMTMHTS::NUM_LEVELS,
 264                                     IntMTMHTS::kDurations));
 265
 266     for (int now = 0; now < 3600; now++) {
 267       for (int i = 0; i < 50; i++) {
 268         hist.addValue(seconds(now), i * 2, 2);  // adds each item 2 times
 269       }
 270     }
 271
 272     hist.update(seconds(3599));
 273     for (int pct = 1; pct <= 100; pct++) {
 274       int expected = (pct - 1) / 10 * 10;
 275       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
 276       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct,
 277                                                       IntMTMHTS::TEN_MINUTE));
 278       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
 279       EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
 280     }
 281
 282     EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
 283     EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::TEN_MINUTE));
 284     EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::HOUR));
 285     EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::ALLTIME));
 286     EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
 287                 IntMTMHTS::MINUTE));
 288     EXPECT_EQ(0,
 289               hist.getBucket(hist.getNumBuckets() - 1).
 290                 count(IntMTMHTS::TEN_MINUTE));
 291     EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
 292                 IntMTMHTS::HOUR));
 293     EXPECT_EQ(0,
 294               hist.getBucket(hist.getNumBuckets() - 1).count(
 295                 IntMTMHTS::ALLTIME));
 296
 297     for (int b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
 298       EXPECT_EQ(600, hist.getBucket(b).count(IntMTMHTS::MINUTE));
 299       EXPECT_EQ(6000, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
 300       EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::HOUR));
 301       EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
 302     }
 303
 304     for (int i = 0; i < 100; ++i) {
 305       hist.addValue(seconds(3599), 200 + i);
 306     }
 307     hist.update(seconds(3599));
 308     EXPECT_EQ(100,
 309               hist.getBucket(hist.getNumBuckets() - 1).count(
 310                 IntMTMHTS::ALLTIME));
 311
 312   }
 313 }
 314
 315 TEST(TimeseriesHistogram, QueryByInterval) {
 316   TimeseriesHistogram<int> mhts(8, 8, 120,
 317                                 MultiLevelTimeSeries<int>(
 318                                   60, IntMHTS::NUM_LEVELS,
 319                                   IntMHTS::kDurations));
 320
 321   mhts.update(seconds(0));
 322
 323   int curTime;
 324   for (curTime = 0; curTime < 7200; curTime++) {
 325     mhts.addValue(seconds(curTime), 1);
 326   }
 327   for (curTime = 7200; curTime < 7200 + 3540; curTime++) {
 328     mhts.addValue(seconds(curTime), 10);
 329   }
 330   for (curTime = 7200 + 3540; curTime < 7200 + 3600; curTime++) {
 331     mhts.addValue(seconds(curTime), 100);
 332   }
 333
 334   mhts.update(seconds(7200 + 3600 - 1));
 335
 336   struct TimeInterval {
 337     TimeInterval(int s, int e)
 338       : start(s), end(e) {}
 339
 340     std::chrono::seconds start;
 341     std::chrono::seconds end;
 342   };
 343   TimeInterval intervals[12] = {
 344     { curTime - 60, curTime },
 345     { curTime - 3600, curTime },
 346     { curTime - 7200, curTime },
 347     { curTime - 3600, curTime - 60 },
 348     { curTime - 7200, curTime - 60 },
 349     { curTime - 7200, curTime - 3600 },
 350     { curTime - 50, curTime - 20 },
 351     { curTime - 3020, curTime - 20 },
 352     { curTime - 7200, curTime - 20 },
 353     { curTime - 3000, curTime - 1000 },
 354     { curTime - 7200, curTime - 1000 },
 355     { curTime - 7200, curTime - 3600 },
 356   };
 357
 358   int expectedSums[12] = {
 359     6000, 41400, 32400, 35400, 32129, 16200, 3000, 33600, 32308, 20000, 27899,
 360     16200
 361   };
 362
 363   int expectedCounts[12] = {
 364     60, 3600, 7200, 3540, 7139, 3600, 30, 3000, 7178, 2000, 6199, 3600
 365   };
 366
 367   // The first 7200 values added all fell below the histogram minimum,
 368   // and went into the bucket that tracks all of the too-small values.
 369   // This bucket reports a minimum value of the smallest possible integer.
 370   int belowMinBucket = std::numeric_limits<int>::min();
 371
 372   int expectedValues[12][3] = {
 373     {96, 96, 96},
 374     { 8,  8, 96},
 375     { belowMinBucket,  belowMinBucket,  8}, // alltime
 376     { 8,  8,  8},
 377     { belowMinBucket,  belowMinBucket,  8}, // alltime
 378     { belowMinBucket,  belowMinBucket,  8}, // alltime
 379     {96, 96, 96},
 380     { 8,  8, 96},
 381     { belowMinBucket,  belowMinBucket,  8}, // alltime
 382     { 8,  8,  8},
 383     { belowMinBucket,  belowMinBucket,  8}, // alltime
 384     { belowMinBucket,  belowMinBucket,  8}  // alltime
 385   };
 386
 387   for (int i = 0; i < 12; i++) {
 388     const auto& itv = intervals[i];
 389     int s = mhts.sum(itv.start, itv.end);
 390     EXPECT_EQ(expectedSums[i], s);
 391
 392     int c = mhts.count(itv.start, itv.end);
 393     EXPECT_EQ(expectedCounts[i], c);
 394   }
 395
 396   // 3 levels
 397   for (int i = 1; i <= 100; i++) {
 398     EXPECT_EQ(96, mhts.getPercentileBucketMin(i, 0));
 399     EXPECT_EQ(96, mhts.getPercentileBucketMin(i, seconds(curTime - 60),
 400                                               seconds(curTime)));
 401     EXPECT_EQ(8, mhts.getPercentileBucketMin(i, seconds(curTime - 3540),
 402                                              seconds(curTime - 60)));
 403   }
 404
 405   EXPECT_EQ(8, mhts.getPercentileBucketMin(1, 1));
 406   EXPECT_EQ(8, mhts.getPercentileBucketMin(98, 1));
 407   EXPECT_EQ(96, mhts.getPercentileBucketMin(99, 1));
 408   EXPECT_EQ(96, mhts.getPercentileBucketMin(100, 1));
 409
 410   EXPECT_EQ(belowMinBucket, mhts.getPercentileBucketMin(1, 2));
 411   EXPECT_EQ(belowMinBucket, mhts.getPercentileBucketMin(66, 2));
 412   EXPECT_EQ(8, mhts.getPercentileBucketMin(67, 2));
 413   EXPECT_EQ(8, mhts.getPercentileBucketMin(99, 2));
 414   EXPECT_EQ(96, mhts.getPercentileBucketMin(100, 2));
 415
 416   // 0 is currently the value for bucket 0 (below min)
 417   for (int i = 0; i < 12; i++) {
 418     const auto& itv = intervals[i];
 419     int v = mhts.getPercentileBucketMin(1, itv.start, itv.end);
 420     EXPECT_EQ(expectedValues[i][0], v);
 421
 422     v = mhts.getPercentileBucketMin(50, itv.start, itv.end);
 423     EXPECT_EQ(expectedValues[i][1], v);
 424
 425     v = mhts.getPercentileBucketMin(99, itv.start, itv.end);
 426     EXPECT_EQ(expectedValues[i][2], v);
 427   }
 428
 429   for (int i = 0; i < 12; i++) {
 430     const auto& itv = intervals[i];
 431     int c = mhts.count(itv.start, itv.end);
 432     // Some of the older intervals that fall in the alltime bucket
 433     // are off by 1 or 2 in their estimated counts.
 434     size_t tolerance = 0;
 435     if (itv.start <= seconds(curTime - 7200)) {
 436       tolerance = 2;
 437     } else if (itv.start <= seconds(curTime - 3000)) {
 438       tolerance = 1;
 439     }
 440     size_t actualCount = (itv.end - itv.start).count();
 441     size_t estimatedCount = mhts.count(itv.start, itv.end);
 442     EXPECT_GE(actualCount, estimatedCount);
 443     EXPECT_LE(actualCount - tolerance, estimatedCount);
 444   }
 445 }
 446
 447 TEST(TimeseriesHistogram, SingleUniqueValue) {
 448   int values[] = {-1, 0, 500, 1000, 1500};
 449   for (int ii = 0; ii < 5; ++ii) {
 450     int value = values[ii];
 451     TimeseriesHistogram<int> h(10, 0, 1000,
 452                                MultiLevelTimeSeries<int>(
 453                                  60, IntMTMHTS::NUM_LEVELS,
 454                                  IntMTMHTS::kDurations));
 455
 456     const int kNumIters = 1000;
 457     for (int jj = 0; jj < kNumIters; ++jj) {
 458       h.addValue(seconds(time(nullptr)), value);
 459     }
 460     h.update(seconds(time(nullptr)));
 461     // since we've only added one unique value, all percentiles should
 462     // be that value
 463     EXPECT_EQ(h.getPercentileEstimate(10, 0), value);
 464     EXPECT_EQ(h.getPercentileEstimate(50, 0), value);
 465     EXPECT_EQ(h.getPercentileEstimate(99, 0), value);
 466
 467     // Things get trickier if there are multiple unique values.
 468     const int kNewValue = 750;
 469     for (int kk = 0; kk < 2*kNumIters; ++kk) {
 470       h.addValue(seconds(time(nullptr)), kNewValue);
 471     }
 472     h.update(seconds(time(nullptr)));
 473     EXPECT_NEAR(h.getPercentileEstimate(50, 0), kNewValue+5, 5);
 474     if (value >= 0 && value <= 1000) {
 475       // only do further testing if value is within our bucket range,
 476       // else estimates can be wildly off
 477       if (kNewValue > value) {
 478         EXPECT_NEAR(h.getPercentileEstimate(10, 0), value+5, 5);
 479         EXPECT_NEAR(h.getPercentileEstimate(99, 0), kNewValue+5, 5);
 480       } else {
 481         EXPECT_NEAR(h.getPercentileEstimate(10, 0), kNewValue+5, 5);
 482         EXPECT_NEAR(h.getPercentileEstimate(99, 0), value+5, 5);
 483       }
 484     }
 485   }
 486 }