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