folly/test/TimeseriesHistogramTest.cpp

   1 /*
   2  * Copyright 2016 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 <random>
  21
  22 #include <gtest/gtest.h>
  23
  24 using namespace std;
  25 using namespace folly;
  26 using std::chrono::seconds;
  27
  28 namespace IntMTMHTS {
  29   enum Levels {
  30     MINUTE,
  31     TEN_MINUTE,
  32     HOUR,
  33     ALLTIME,
  34     NUM_LEVELS,
  35   };
  36
  37   const seconds kDurations[] = {
  38     seconds(60), seconds(600), seconds(3600), seconds(0)
  39   };
  40 };
  41
  42 namespace IntMHTS {
  43   enum Levels {
  44     MINUTE,
  45     HOUR,
  46     ALLTIME,
  47     NUM_LEVELS,
  48   };
  49
  50   const seconds kDurations[] = {
  51     seconds(60), seconds(3600), seconds(0)
  52   };
  53 };
  54
  55 typedef std::mt19937 RandomInt32;
  56
  57 TEST(TimeseriesHistogram, Percentile) {
  58   RandomInt32 random(5);
  59   // [10, 109], 12 buckets including above and below
  60   {
  61     TimeseriesHistogram<int> h(10, 10, 110,
  62                                MultiLevelTimeSeries<int>(
  63                                  60, IntMTMHTS::NUM_LEVELS,
  64                                  IntMTMHTS::kDurations));
  65
  66     EXPECT_EQ(0, h.getPercentileEstimate(0, IntMTMHTS::ALLTIME));
  67
  68     EXPECT_EQ(12, h.getNumBuckets());
  69     EXPECT_EQ(10, h.getBucketSize());
  70     EXPECT_EQ(10, h.getMin());
  71     EXPECT_EQ(110, h.getMax());
  72
  73     for (int i = 0; i < h.getNumBuckets(); ++i) {
  74       EXPECT_EQ(4, h.getBucket(i).numLevels());
  75     }
  76
  77     int maxVal = 120;
  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);
  82     }
  83
  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));
  91
  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));
  96   }
  97 }
  98
  99 TEST(TimeseriesHistogram, String) {
 100   RandomInt32 random(5);
 101   // [10, 109], 12 buckets including above and below
 102   {
 103     TimeseriesHistogram<int> hist(10, 10, 110,
 104                                   MultiLevelTimeSeries<int>(
 105                                     60, IntMTMHTS::NUM_LEVELS,
 106                                     IntMTMHTS::kDurations));
 107
 108     int maxVal = 120;
 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);
 113     }
 114
 115     hist.update(seconds(0));
 116
 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",
 126     };
 127
 128     CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());
 129
 130     for (int level = 0; level < hist.getNumLevels(); ++level) {
 131       EXPECT_EQ(kStringValues1[level], hist.getString(level));
 132     }
 133
 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",
 143     };
 144
 145     CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());
 146
 147     for (int level = 0; level < hist.getNumLevels(); ++level) {
 148       EXPECT_EQ(kStringValues2[level], hist.getString(level));
 149     }
 150   }
 151 }
 152
 153 TEST(TimeseriesHistogram, Clear) {
 154   {
 155     TimeseriesHistogram<int> hist(10, 0, 100,
 156                                   MultiLevelTimeSeries<int>(
 157                                     60, IntMTMHTS::NUM_LEVELS,
 158                                     IntMTMHTS::kDurations));
 159
 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
 163       }
 164     }
 165
 166     // check clearing
 167     hist.clear();
 168
 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));
 174     }
 175
 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));
 181
 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));
 186     }
 187   }
 188 }
 189
 190
 191 TEST(TimeseriesHistogram, Basic) {
 192   {
 193     TimeseriesHistogram<int> hist(10, 0, 100,
 194                                   MultiLevelTimeSeries<int>(
 195                                     60, IntMTMHTS::NUM_LEVELS,
 196                                     IntMTMHTS::kDurations));
 197
 198     for (int now = 0; now < 3600; now++) {
 199       for (int i = 0; i < 100; i++) {
 200         hist.addValue(seconds(now), i);
 201       }
 202     }
 203
 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));
 212     }
 213
 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));
 219     }
 220     EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
 221     EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
 222                 IntMTMHTS::MINUTE));
 223
 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));
 228
 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));
 234
 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));
 243
 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));
 252
 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)));
 257
 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)));
 262
 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)));
 267   }
 268
 269   // -----------------
 270
 271   {
 272     TimeseriesHistogram<int> hist(10, 0, 100,
 273                                   MultiLevelTimeSeries<int>(
 274                                     60, IntMTMHTS::NUM_LEVELS,
 275                                     IntMTMHTS::kDurations));
 276
 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
 280       }
 281     }
 282
 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));
 291    }
 292
 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));
 298     }
 299     EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
 300     EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
 301                 IntMTMHTS::MINUTE));
 302   }
 303
 304   // -----------------
 305
 306   {
 307     TimeseriesHistogram<int> hist(10, 0, 100,
 308                                   MultiLevelTimeSeries<int>(
 309                                     60, IntMTMHTS::NUM_LEVELS,
 310                                     IntMTMHTS::kDurations));
 311
 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
 315       }
 316     }
 317
 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));
 326     }
 327
 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(
 333                 IntMTMHTS::MINUTE));
 334     EXPECT_EQ(0,
 335               hist.getBucket(hist.getNumBuckets() - 1).
 336                 count(IntMTMHTS::TEN_MINUTE));
 337     EXPECT_EQ(0, hist.getBucket(hist.getNumBuckets() - 1).count(
 338                 IntMTMHTS::HOUR));
 339     EXPECT_EQ(0,
 340               hist.getBucket(hist.getNumBuckets() - 1).count(
 341                 IntMTMHTS::ALLTIME));
 342
 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));
 348     }
 349
 350     for (int i = 0; i < 100; ++i) {
 351       hist.addValue(seconds(3599), 200 + i);
 352     }
 353     hist.update(seconds(3599));
 354     EXPECT_EQ(100,
 355               hist.getBucket(hist.getNumBuckets() - 1).count(
 356                 IntMTMHTS::ALLTIME));
 357
 358   }
 359 }
 360
 361 TEST(TimeseriesHistogram, QueryByInterval) {
 362   TimeseriesHistogram<int> mhts(8, 8, 120,
 363                                 MultiLevelTimeSeries<int>(
 364                                   60, IntMHTS::NUM_LEVELS,
 365                                   IntMHTS::kDurations));
 366
 367   mhts.update(seconds(0));
 368
 369   int curTime;
 370   for (curTime = 0; curTime < 7200; curTime++) {
 371     mhts.addValue(seconds(curTime), 1);
 372   }
 373   for (curTime = 7200; curTime < 7200 + 3540; curTime++) {
 374     mhts.addValue(seconds(curTime), 10);
 375   }
 376   for (curTime = 7200 + 3540; curTime < 7200 + 3600; curTime++) {
 377     mhts.addValue(seconds(curTime), 100);
 378   }
 379
 380   mhts.update(seconds(7200 + 3600 - 1));
 381
 382   struct TimeInterval {
 383     TimeInterval(int s, int e)
 384       : start(s), end(e) {}
 385
 386     std::chrono::seconds start;
 387     std::chrono::seconds end;
 388   };
 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 },
 402   };
 403
 404   int expectedSums[12] = {
 405     6000, 41400, 32400, 35400, 32129, 16200, 3000, 33600, 32308, 20000, 27899,
 406     16200
 407   };
 408
 409   int expectedCounts[12] = {
 410     60, 3600, 7200, 3540, 7139, 3600, 30, 3000, 7178, 2000, 6199, 3600
 411   };
 412
 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();
 417
 418   int expectedValues[12][3] = {
 419     {96, 96, 96},
 420     { 8,  8, 96},
 421     { belowMinBucket,  belowMinBucket,  8}, // alltime
 422     { 8,  8,  8},
 423     { belowMinBucket,  belowMinBucket,  8}, // alltime
 424     { belowMinBucket,  belowMinBucket,  8}, // alltime
 425     {96, 96, 96},
 426     { 8,  8, 96},
 427     { belowMinBucket,  belowMinBucket,  8}, // alltime
 428     { 8,  8,  8},
 429     { belowMinBucket,  belowMinBucket,  8}, // alltime
 430     { belowMinBucket,  belowMinBucket,  8}  // alltime
 431   };
 432
 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);
 437
 438     int c = mhts.count(itv.start, itv.end);
 439     EXPECT_EQ(expectedCounts[i], c);
 440   }
 441
 442   // 3 levels
 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),
 446                                               seconds(curTime)));
 447     EXPECT_EQ(8, mhts.getPercentileBucketMin(i, seconds(curTime - 3540),
 448                                              seconds(curTime - 60)));
 449   }
 450
 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));
 455
 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));
 461
 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);
 467
 468     v = mhts.getPercentileBucketMin(50, itv.start, itv.end);
 469     EXPECT_EQ(expectedValues[i][1], v);
 470
 471     v = mhts.getPercentileBucketMin(99, itv.start, itv.end);
 472     EXPECT_EQ(expectedValues[i][2], v);
 473   }
 474
 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)) {
 481       tolerance = 2;
 482     } else if (itv.start <= seconds(curTime - 3000)) {
 483       tolerance = 1;
 484     }
 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);
 489   }
 490 }
 491
 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));
 500
 501     const int kNumIters = 1000;
 502     for (int jj = 0; jj < kNumIters; ++jj) {
 503       h.addValue(seconds(time(nullptr)), value);
 504     }
 505     h.update(seconds(time(nullptr)));
 506     // since we've only added one unique value, all percentiles should
 507     // be that value
 508     EXPECT_EQ(h.getPercentileEstimate(10, 0), value);
 509     EXPECT_EQ(h.getPercentileEstimate(50, 0), value);
 510     EXPECT_EQ(h.getPercentileEstimate(99, 0), value);
 511
 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);
 516     }
 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);
 525       } else {
 526         EXPECT_NEAR(h.getPercentileEstimate(10, 0), kNewValue+5, 5);
 527         EXPECT_NEAR(h.getPercentileEstimate(99, 0), value+5, 5);
 528       }
 529     }
 530   }
 531 }