folly/test/TimeseriesTest.cpp

   1 /*
   2  * Copyright 2012 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 #include "folly/stats/BucketedTimeSeries.h"
  17 #include "folly/stats/BucketedTimeSeries-defs.h"
  18
  19 #include <glog/logging.h>
  20 #include <gtest/gtest.h>
  21
  22 using std::chrono::seconds;
  23 using std::string;
  24 using std::vector;
  25 using folly::BucketedTimeSeries;
  26
  27 struct TestData {
  28   size_t duration;
  29   size_t numBuckets;
  30   vector<ssize_t> bucketStarts;
  31 };
  32 vector<TestData> testData = {
  33   // 71 seconds x 4 buckets
  34   { 71, 4, {0, 18, 36, 54}},
  35   // 100 seconds x 10 buckets
  36   { 100, 10, {0, 10, 20, 30, 40, 50, 60, 70, 80, 90}},
  37   // 10 seconds x 10 buckets
  38   { 10, 10, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}},
  39   // 10 seconds x 1 buckets
  40   { 10, 1, {0}},
  41   // 1 second x 1 buckets
  42   { 1, 1, {0}},
  43 };
  44
  45 TEST(BucketedTimeSeries, getBucketInfo) {
  46   for (const auto& data : testData) {
  47     BucketedTimeSeries<int64_t> ts(data.numBuckets, seconds(data.duration));
  48
  49     for (uint32_t n = 0; n < 10000; n += 1234) {
  50       seconds offset(n * data.duration);
  51
  52       for (uint32_t idx = 0; idx < data.numBuckets; ++idx) {
  53         seconds bucketStart(data.bucketStarts[idx]);
  54         seconds nextBucketStart;
  55         if (idx + 1 < data.numBuckets) {
  56             nextBucketStart = seconds(data.bucketStarts[idx + 1]);
  57         } else {
  58             nextBucketStart = seconds(data.duration);
  59         }
  60
  61         seconds expectedStart = offset + bucketStart;
  62         seconds expectedNextStart = offset + nextBucketStart;
  63         seconds midpoint = (expectedStart + expectedNextStart) / 2;
  64
  65         vector<std::pair<string, seconds>> timePoints = {
  66           {"expectedStart", expectedStart},
  67           {"midpoint", midpoint},
  68           {"expectedEnd", expectedNextStart - seconds(1)},
  69         };
  70
  71         for (const auto& point : timePoints) {
  72           // Check that getBucketIdx() returns the expected index
  73           EXPECT_EQ(idx, ts.getBucketIdx(point.second)) <<
  74             data.duration << "x" << data.numBuckets << ": " <<
  75             point.first << "=" << point.second.count();
  76
  77           // Check the data returned by getBucketInfo()
  78           size_t returnedIdx;
  79           seconds returnedStart;
  80           seconds returnedNextStart;
  81           ts.getBucketInfo(expectedStart, &returnedIdx,
  82                            &returnedStart, &returnedNextStart);
  83           EXPECT_EQ(idx, returnedIdx) <<
  84             data.duration << "x" << data.numBuckets << ": " <<
  85             point.first << "=" << point.second.count();
  86           EXPECT_EQ(expectedStart.count(), returnedStart.count()) <<
  87             data.duration << "x" << data.numBuckets << ": " <<
  88             point.first << "=" << point.second.count();
  89           EXPECT_EQ(expectedNextStart.count(), returnedNextStart.count()) <<
  90             data.duration << "x" << data.numBuckets << ": " <<
  91             point.first << "=" << point.second.count();
  92         }
  93       }
  94     }
  95   }
  96 }
  97
  98 void testUpdate100x10(size_t offset) {
  99   // This test code only works when offset is a multiple of the bucket width
 100   CHECK_EQ(0, offset % 10);
 101
 102   // Create a 100 second timeseries, with 10 buckets
 103   BucketedTimeSeries<int64_t> ts(10, seconds(100));
 104
 105   auto setup = [&] {
 106     ts.clear();
 107     // Add 1 value to each bucket
 108     for (int n = 5; n <= 95; n += 10) {
 109       ts.addValue(seconds(n + offset), 6);
 110     }
 111
 112     EXPECT_EQ(10, ts.count());
 113     EXPECT_EQ(60, ts.sum());
 114     EXPECT_EQ(6, ts.avg());
 115   };
 116
 117   // Update 2 buckets forwards.  This should throw away 2 data points.
 118   setup();
 119   ts.update(seconds(110 + offset));
 120   EXPECT_EQ(8, ts.count());
 121   EXPECT_EQ(48, ts.sum());
 122   EXPECT_EQ(6, ts.avg());
 123
 124   // The last time we added was 95.
 125   // Try updating to 189.  This should clear everything but the last bucket.
 126   setup();
 127   ts.update(seconds(151 + offset));
 128   EXPECT_EQ(4, ts.count());
 129   //EXPECT_EQ(6, ts.sum());
 130   EXPECT_EQ(6, ts.avg());
 131
 132   // The last time we added was 95.
 133   // Try updating to 193: This is nearly one full loop around,
 134   // back to the same bucket.  update() needs to clear everything
 135   setup();
 136   ts.update(seconds(193 + offset));
 137   EXPECT_EQ(0, ts.count());
 138   EXPECT_EQ(0, ts.sum());
 139   EXPECT_EQ(0, ts.avg());
 140
 141   // The last time we added was 95.
 142   // Try updating to 197: This is slightly over one full loop around,
 143   // back to the same bucket.  update() needs to clear everything
 144   setup();
 145   ts.update(seconds(197 + offset));
 146   EXPECT_EQ(0, ts.count());
 147   EXPECT_EQ(0, ts.sum());
 148   EXPECT_EQ(0, ts.avg());
 149
 150   // The last time we added was 95.
 151   // Try updating to 230: This is well over one full loop around,
 152   // and everything should be cleared.
 153   setup();
 154   ts.update(seconds(230 + offset));
 155   EXPECT_EQ(0, ts.count());
 156   EXPECT_EQ(0, ts.sum());
 157   EXPECT_EQ(0, ts.avg());
 158 }
 159
 160 TEST(BucketedTimeSeries, update100x10) {
 161   // Run testUpdate100x10() multiple times, with various offsets.
 162   // This makes sure the update code works regardless of which bucket it starts
 163   // at in the modulo arithmetic.
 164   testUpdate100x10(0);
 165   testUpdate100x10(50);
 166   testUpdate100x10(370);
 167   testUpdate100x10(1937090);
 168 }
 169
 170 TEST(BucketedTimeSeries, update71x5) {
 171   // Create a 71 second timeseries, with 5 buckets
 172   // This tests when the number of buckets does not divide evenly into the
 173   // duration.
 174   BucketedTimeSeries<int64_t> ts(5, seconds(71));
 175
 176   auto setup = [&] {
 177     ts.clear();
 178     // Add 1 value to each bucket
 179     ts.addValue(seconds(11), 6);
 180     ts.addValue(seconds(24), 6);
 181     ts.addValue(seconds(42), 6);
 182     ts.addValue(seconds(43), 6);
 183     ts.addValue(seconds(66), 6);
 184
 185     EXPECT_EQ(5, ts.count());
 186     EXPECT_EQ(30, ts.sum());
 187     EXPECT_EQ(6, ts.avg());
 188   };
 189
 190   // Update 2 buckets forwards.  This should throw away 2 data points.
 191   setup();
 192   ts.update(seconds(99));
 193   EXPECT_EQ(3, ts.count());
 194   EXPECT_EQ(18, ts.sum());
 195   EXPECT_EQ(6, ts.avg());
 196
 197   // Update 3 buckets forwards.  This should throw away 3 data points.
 198   setup();
 199   ts.update(seconds(100));
 200   EXPECT_EQ(2, ts.count());
 201   EXPECT_EQ(12, ts.sum());
 202   EXPECT_EQ(6, ts.avg());
 203
 204   // Update 4 buckets forwards, just under the wrap limit.
 205   // This should throw everything but the last bucket away.
 206   setup();
 207   ts.update(seconds(127));
 208   EXPECT_EQ(1, ts.count());
 209   EXPECT_EQ(6, ts.sum());
 210   EXPECT_EQ(6, ts.avg());
 211
 212   // Update 5 buckets forwards, exactly at the wrap limit.
 213   // This should throw everything away.
 214   setup();
 215   ts.update(seconds(128));
 216   EXPECT_EQ(0, ts.count());
 217   EXPECT_EQ(0, ts.sum());
 218   EXPECT_EQ(0, ts.avg());
 219
 220   // Update very far forwards, wrapping multiple times.
 221   // This should throw everything away.
 222   setup();
 223   ts.update(seconds(1234));
 224   EXPECT_EQ(0, ts.count());
 225   EXPECT_EQ(0, ts.sum());
 226   EXPECT_EQ(0, ts.avg());
 227 }
 228
 229 TEST(BucketedTimeSeries, elapsed) {
 230   BucketedTimeSeries<int64_t> ts(60, seconds(600));
 231
 232   // elapsed() is 0 when no data points have been added
 233   EXPECT_EQ(0, ts.elapsed().count());
 234
 235   // With exactly 1 data point, elapsed() should report 1 second of data
 236   seconds start(239218);
 237   ts.addValue(start + seconds(0), 200);
 238   EXPECT_EQ(1, ts.elapsed().count());
 239   // Adding a data point 10 seconds later should result in an elapsed time of
 240   // 11 seconds (the time range is [0, 10], inclusive).
 241   ts.addValue(start + seconds(10), 200);
 242   EXPECT_EQ(11, ts.elapsed().count());
 243
 244   // elapsed() returns to 0 after clear()
 245   ts.clear();
 246   EXPECT_EQ(0, ts.elapsed().count());
 247
 248   // Restart, with the starting point on an easier number to work with
 249   ts.addValue(seconds(10), 200);
 250   EXPECT_EQ(1, ts.elapsed().count());
 251   ts.addValue(seconds(580), 200);
 252   EXPECT_EQ(571, ts.elapsed().count());
 253   ts.addValue(seconds(590), 200);
 254   EXPECT_EQ(581, ts.elapsed().count());
 255   ts.addValue(seconds(598), 200);
 256   EXPECT_EQ(589, ts.elapsed().count());
 257   ts.addValue(seconds(599), 200);
 258   EXPECT_EQ(590, ts.elapsed().count());
 259   ts.addValue(seconds(600), 200);
 260   EXPECT_EQ(591, ts.elapsed().count());
 261   ts.addValue(seconds(608), 200);
 262   EXPECT_EQ(599, ts.elapsed().count());
 263   ts.addValue(seconds(609), 200);
 264   EXPECT_EQ(600, ts.elapsed().count());
 265   // Once we reach 600 seconds worth of data, when we move on to the next
 266   // second a full bucket will get thrown out.  Now we drop back down to 591
 267   // seconds worth of data
 268   ts.addValue(seconds(610), 200);
 269   EXPECT_EQ(591, ts.elapsed().count());
 270   ts.addValue(seconds(618), 200);
 271   EXPECT_EQ(599, ts.elapsed().count());
 272   ts.addValue(seconds(619), 200);
 273   EXPECT_EQ(600, ts.elapsed().count());
 274   ts.addValue(seconds(620), 200);
 275   EXPECT_EQ(591, ts.elapsed().count());
 276   ts.addValue(seconds(123419), 200);
 277   EXPECT_EQ(600, ts.elapsed().count());
 278   ts.addValue(seconds(123420), 200);
 279   EXPECT_EQ(591, ts.elapsed().count());
 280   ts.addValue(seconds(123425), 200);
 281   EXPECT_EQ(596, ts.elapsed().count());
 282
 283   // Time never moves backwards.
 284   // Calling update with an old timestamp will just be ignored.
 285   ts.update(seconds(29));
 286   EXPECT_EQ(596, ts.elapsed().count());
 287 }
 288
 289 TEST(BucketedTimeSeries, rate) {
 290   BucketedTimeSeries<int64_t> ts(60, seconds(600));
 291
 292   // Add 3 values every 2 seconds, until fill up the buckets
 293   for (size_t n = 0; n < 600; n += 2) {
 294     ts.addValue(seconds(n), 200, 3);
 295   }
 296
 297   EXPECT_EQ(900, ts.count());
 298   EXPECT_EQ(180000, ts.sum());
 299   EXPECT_EQ(200, ts.avg());
 300
 301   // Really we only entered 599 seconds worth of data: [0, 598] (inclusive)
 302   EXPECT_EQ(599, ts.elapsed().count());
 303   EXPECT_NEAR(300.5, ts.rate(), 0.005);
 304   EXPECT_NEAR(1.5, ts.countRate(), 0.005);
 305
 306   // If we add 1 more second, now we will have 600 seconds worth of data
 307   ts.update(seconds(599));
 308   EXPECT_EQ(600, ts.elapsed().count());
 309   EXPECT_NEAR(300, ts.rate(), 0.005);
 310   EXPECT_EQ(300, ts.rate<int>());
 311   EXPECT_NEAR(1.5, ts.countRate(), 0.005);
 312
 313   // However, 1 more second after that and we will have filled up all the
 314   // buckets, and have to drop one.
 315   ts.update(seconds(600));
 316   EXPECT_EQ(591, ts.elapsed().count());
 317   EXPECT_NEAR(299.5, ts.rate(), 0.01);
 318   EXPECT_EQ(299, ts.rate<int>());
 319   EXPECT_NEAR(1.5, ts.countRate(), 0.005);
 320 }
 321
 322 TEST(BucketedTimeSeries, forEachBucket) {
 323   typedef BucketedTimeSeries<int64_t>::Bucket Bucket;
 324   struct BucketInfo {
 325     BucketInfo(const Bucket* b, seconds s, seconds ns)
 326       : bucket(b), start(s), nextStart(ns) {}
 327
 328     const Bucket* bucket;
 329     seconds start;
 330     seconds nextStart;
 331   };
 332
 333   for (const auto& data : testData) {
 334     BucketedTimeSeries<int64_t> ts(data.numBuckets, seconds(data.duration));
 335
 336     vector<BucketInfo> info;
 337     auto fn = [&](const Bucket& bucket, seconds bucketStart,
 338                   seconds bucketEnd) {
 339       info.emplace_back(&bucket, bucketStart, bucketEnd);
 340       return true;
 341     };
 342
 343     // If we haven't yet added any data, the current bucket will start at 0,
 344     // and all data previous buckets will have negative times.
 345     ts.forEachBucket(fn);
 346
 347     CHECK_EQ(data.numBuckets, info.size());
 348
 349     // Check the data passed in to the function
 350     size_t infoIdx = 0;
 351     size_t bucketIdx = 1;
 352     ssize_t offset = -data.duration;
 353     for (size_t n = 0; n < data.numBuckets; ++n) {
 354       if (bucketIdx >= data.numBuckets) {
 355         bucketIdx = 0;
 356         offset += data.duration;
 357       }
 358
 359       EXPECT_EQ(data.bucketStarts[bucketIdx] + offset,
 360                 info[infoIdx].start.count()) <<
 361         data.duration << "x" << data.numBuckets << ": bucketIdx=" <<
 362         bucketIdx << ", infoIdx=" << infoIdx;
 363
 364       size_t nextBucketIdx = bucketIdx + 1;
 365       ssize_t nextOffset = offset;
 366       if (nextBucketIdx >= data.numBuckets) {
 367         nextBucketIdx = 0;
 368         nextOffset += data.duration;
 369       }
 370       EXPECT_EQ(data.bucketStarts[nextBucketIdx] + nextOffset,
 371                 info[infoIdx].nextStart.count()) <<
 372         data.duration << "x" << data.numBuckets << ": bucketIdx=" <<
 373         bucketIdx << ", infoIdx=" << infoIdx;
 374
 375       EXPECT_EQ(&ts.getBucketByIndex(bucketIdx), info[infoIdx].bucket);
 376
 377       ++bucketIdx;
 378       ++infoIdx;
 379     }
 380   }
 381 }
 382
 383 TEST(BucketedTimeSeries, queryByIntervalSimple) {
 384   BucketedTimeSeries<int> a(3, seconds(12));
 385   for (int i = 0; i < 8; i++) {
 386     a.addValue(seconds(i), 1);
 387   }
 388   // We added 1 at each second from 0..7
 389   // Query from the time period 0..2.
 390   // This is entirely in the first bucket, which has a sum of 4.
 391   // The code knows only part of the bucket is covered, and correctly
 392   // estimates the desired sum as 3.
 393   EXPECT_EQ(2, a.sum(seconds(0), seconds(2)));
 394 }
 395
 396 TEST(BucketedTimeSeries, queryByInterval) {
 397   // Set up a BucketedTimeSeries tracking 6 seconds in 3 buckets
 398   const int kNumBuckets = 3;
 399   const int kDuration = 6;
 400   BucketedTimeSeries<double> b(kNumBuckets, seconds(kDuration));
 401
 402   for (unsigned int i = 0; i < kDuration; ++i) {
 403     // add value 'i' at time 'i'
 404     b.addValue(seconds(i), i);
 405   }
 406
 407   // Current bucket state:
 408   // 0: time=[0, 2): values=(0, 1), sum=1, count=2
 409   // 1: time=[2, 4): values=(2, 3), sum=5, count=1
 410   // 2: time=[4, 6): values=(4, 5), sum=9, count=2
 411   double expectedSums1[kDuration + 1][kDuration + 1] = {
 412     {0,  4.5,   9, 11.5,  14, 14.5,  15},
 413     {0,  4.5,   7,  9.5,  10, 10.5,  -1},
 414     {0,  2.5,   5,  5.5,   6,   -1,  -1},
 415     {0,  2.5,   3,  3.5,  -1,   -1,  -1},
 416     {0,  0.5,   1,   -1,  -1,   -1,  -1},
 417     {0,  0.5,  -1,   -1,  -1,   -1,  -1},
 418     {0,   -1,  -1,   -1,  -1,   -1,  -1}
 419   };
 420   int expectedCounts1[kDuration + 1][kDuration + 1] = {
 421     {0,  1,  2,  3,  4,  5,  6},
 422     {0,  1,  2,  3,  4,  5, -1},
 423     {0,  1,  2,  3,  4, -1, -1},
 424     {0,  1,  2,  3, -1, -1, -1},
 425     {0,  1,  2, -1, -1, -1, -1},
 426     {0,  1, -1, -1, -1, -1, -1},
 427     {0, -1, -1, -1, -1, -1, -1}
 428   };
 429
 430   seconds currentTime = b.getLatestTime() + seconds(1);
 431   for (int i = 0; i <= kDuration + 1; i++) {
 432     for (int j = 0; j <= kDuration - i; j++) {
 433       seconds start = currentTime - seconds(i + j);
 434       seconds end = currentTime - seconds(i);
 435       double expectedSum = expectedSums1[i][j];
 436       EXPECT_EQ(expectedSum, b.sum(start, end)) <<
 437         "i=" << i << ", j=" << j <<
 438         ", interval=[" << start.count() << ", " << end.count() << ")";
 439
 440       uint64_t expectedCount = expectedCounts1[i][j];
 441       EXPECT_EQ(expectedCount, b.count(start, end)) <<
 442         "i=" << i << ", j=" << j <<
 443         ", interval=[" << start.count() << ", " << end.count() << ")";
 444
 445       double expectedAvg = expectedCount ? expectedSum / expectedCount : 0;
 446       EXPECT_EQ(expectedAvg, b.avg(start, end)) <<
 447         "i=" << i << ", j=" << j <<
 448         ", interval=[" << start.count() << ", " << end.count() << ")";
 449
 450       double expectedRate = j ? expectedSum / j : 0;
 451       EXPECT_EQ(expectedRate, b.rate(start, end)) <<
 452         "i=" << i << ", j=" << j <<
 453         ", interval=[" << start.count() << ", " << end.count() << ")";
 454     }
 455   }
 456
 457   // Add 3 more values.
 458   // This will overwrite 1 full bucket, and put us halfway through the next.
 459   for (unsigned int i = kDuration; i < kDuration + 3; ++i) {
 460     b.addValue(seconds(i), i);
 461   }
 462
 463   // Current bucket state:
 464   // 0: time=[6,  8): values=(6, 7), sum=13, count=2
 465   // 1: time=[8, 10): values=(8),    sum=8, count=1
 466   // 2: time=[4,  6): values=(4, 5), sum=9, count=2
 467   double expectedSums2[kDuration + 1][kDuration + 1] = {
 468     {0,    8, 14.5,   21, 25.5,  30,  30},
 469     {0,  6.5,   13, 17.5,   22,  22,  -1},
 470     {0,  6.5,   11, 15.5, 15.5,  -1,  -1},
 471     {0,  4.5,    9,    9,   -1,  -1,  -1},
 472     {0,  4.5,  4.5,   -1,   -1,  -1,  -1},
 473     {0,    0,   -1,   -1,   -1,  -1,  -1},
 474     {0,   -1,   -1,   -1,   -1,  -1,  -1}
 475   };
 476   int expectedCounts2[kDuration + 1][kDuration + 1] = {
 477     {0,  1,  2,  3,  4,  5,  5},
 478     {0,  1,  2,  3,  4,  4, -1},
 479     {0,  1,  2,  3,  3, -1, -1},
 480     {0,  1,  2,  2, -1, -1, -1},
 481     {0,  1,  1, -1, -1, -1, -1},
 482     {0,  0, -1, -1, -1, -1, -1},
 483     {0, -1, -1, -1, -1, -1, -1}
 484   };
 485
 486   currentTime = b.getLatestTime() + seconds(1);
 487   for (int i = 0; i <= kDuration + 1; i++) {
 488     for (int j = 0; j <= kDuration - i; j++) {
 489       seconds start = currentTime - seconds(i + j);
 490       seconds end = currentTime - seconds(i);
 491       double expectedSum = expectedSums2[i][j];
 492       EXPECT_EQ(expectedSum, b.sum(start, end)) <<
 493         "i=" << i << ", j=" << j <<
 494         ", interval=[" << start.count() << ", " << end.count() << ")";
 495
 496       uint64_t expectedCount = expectedCounts2[i][j];
 497       EXPECT_EQ(expectedCount, b.count(start, end)) <<
 498         "i=" << i << ", j=" << j <<
 499         ", interval=[" << start.count() << ", " << end.count() << ")";
 500
 501       double expectedAvg = expectedCount ? expectedSum / expectedCount : 0;
 502       EXPECT_EQ(expectedAvg, b.avg(start, end)) <<
 503         "i=" << i << ", j=" << j <<
 504         ", interval=[" << start.count() << ", " << end.count() << ")";
 505
 506       double expectedRate = j ? expectedSum / j : 0;
 507       EXPECT_EQ(expectedRate, b.rate(start, end)) <<
 508         "i=" << i << ", j=" << j <<
 509         ", interval=[" << start.count() << ", " << end.count() << ")";
 510     }
 511   }
 512 }