2 * Copyright 2012 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.
16 #include "folly/stats/BucketedTimeSeries.h"
17 #include "folly/stats/BucketedTimeSeries-defs.h"
19 #include <glog/logging.h>
20 #include <gtest/gtest.h>
22 using std::chrono::seconds;
25 using folly::BucketedTimeSeries;
30 vector<ssize_t> bucketStarts;
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
41 // 1 second x 1 buckets
45 TEST(BucketedTimeSeries, getBucketInfo) {
46 for (const auto& data : testData) {
47 BucketedTimeSeries<int64_t> ts(data.numBuckets, seconds(data.duration));
49 for (uint32_t n = 0; n < 10000; n += 1234) {
50 seconds offset(n * data.duration);
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]);
58 nextBucketStart = seconds(data.duration);
61 seconds expectedStart = offset + bucketStart;
62 seconds expectedNextStart = offset + nextBucketStart;
63 seconds midpoint = (expectedStart + expectedNextStart) / 2;
65 vector<std::pair<string, seconds>> timePoints = {
66 {"expectedStart", expectedStart},
67 {"midpoint", midpoint},
68 {"expectedEnd", expectedNextStart - seconds(1)},
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();
77 // Check the data returned by getBucketInfo()
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();
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);
102 // Create a 100 second timeseries, with 10 buckets
103 BucketedTimeSeries<int64_t> ts(10, seconds(100));
107 // Add 1 value to each bucket
108 for (int n = 5; n <= 95; n += 10) {
109 ts.addValue(seconds(n + offset), 6);
112 EXPECT_EQ(10, ts.count());
113 EXPECT_EQ(60, ts.sum());
114 EXPECT_EQ(6, ts.avg());
117 // Update 2 buckets forwards. This should throw away 2 data points.
119 ts.update(seconds(110 + offset));
120 EXPECT_EQ(8, ts.count());
121 EXPECT_EQ(48, ts.sum());
122 EXPECT_EQ(6, ts.avg());
124 // The last time we added was 95.
125 // Try updating to 189. This should clear everything but the last bucket.
127 ts.update(seconds(151 + offset));
128 EXPECT_EQ(4, ts.count());
129 //EXPECT_EQ(6, ts.sum());
130 EXPECT_EQ(6, ts.avg());
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
136 ts.update(seconds(193 + offset));
137 EXPECT_EQ(0, ts.count());
138 EXPECT_EQ(0, ts.sum());
139 EXPECT_EQ(0, ts.avg());
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
145 ts.update(seconds(197 + offset));
146 EXPECT_EQ(0, ts.count());
147 EXPECT_EQ(0, ts.sum());
148 EXPECT_EQ(0, ts.avg());
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.
154 ts.update(seconds(230 + offset));
155 EXPECT_EQ(0, ts.count());
156 EXPECT_EQ(0, ts.sum());
157 EXPECT_EQ(0, ts.avg());
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.
165 testUpdate100x10(50);
166 testUpdate100x10(370);
167 testUpdate100x10(1937090);
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
174 BucketedTimeSeries<int64_t> ts(5, seconds(71));
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);
185 EXPECT_EQ(5, ts.count());
186 EXPECT_EQ(30, ts.sum());
187 EXPECT_EQ(6, ts.avg());
190 // Update 2 buckets forwards. This should throw away 2 data points.
192 ts.update(seconds(99));
193 EXPECT_EQ(3, ts.count());
194 EXPECT_EQ(18, ts.sum());
195 EXPECT_EQ(6, ts.avg());
197 // Update 3 buckets forwards. This should throw away 3 data points.
199 ts.update(seconds(100));
200 EXPECT_EQ(2, ts.count());
201 EXPECT_EQ(12, ts.sum());
202 EXPECT_EQ(6, ts.avg());
204 // Update 4 buckets forwards, just under the wrap limit.
205 // This should throw everything but the last bucket away.
207 ts.update(seconds(127));
208 EXPECT_EQ(1, ts.count());
209 EXPECT_EQ(6, ts.sum());
210 EXPECT_EQ(6, ts.avg());
212 // Update 5 buckets forwards, exactly at the wrap limit.
213 // This should throw everything away.
215 ts.update(seconds(128));
216 EXPECT_EQ(0, ts.count());
217 EXPECT_EQ(0, ts.sum());
218 EXPECT_EQ(0, ts.avg());
220 // Update very far forwards, wrapping multiple times.
221 // This should throw everything away.
223 ts.update(seconds(1234));
224 EXPECT_EQ(0, ts.count());
225 EXPECT_EQ(0, ts.sum());
226 EXPECT_EQ(0, ts.avg());
229 TEST(BucketedTimeSeries, elapsed) {
230 BucketedTimeSeries<int64_t> ts(60, seconds(600));
232 // elapsed() is 0 when no data points have been added
233 EXPECT_EQ(0, ts.elapsed().count());
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());
244 // elapsed() returns to 0 after clear()
246 EXPECT_EQ(0, ts.elapsed().count());
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());
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());
289 TEST(BucketedTimeSeries, rate) {
290 BucketedTimeSeries<int64_t> ts(60, seconds(600));
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);
297 EXPECT_EQ(900, ts.count());
298 EXPECT_EQ(180000, ts.sum());
299 EXPECT_EQ(200, ts.avg());
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);
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);
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);
322 TEST(BucketedTimeSeries, forEachBucket) {
323 typedef BucketedTimeSeries<int64_t>::Bucket Bucket;
325 BucketInfo(const Bucket* b, seconds s, seconds ns)
326 : bucket(b), start(s), nextStart(ns) {}
328 const Bucket* bucket;
333 for (const auto& data : testData) {
334 BucketedTimeSeries<int64_t> ts(data.numBuckets, seconds(data.duration));
336 vector<BucketInfo> info;
337 auto fn = [&](const Bucket& bucket, seconds bucketStart,
339 info.emplace_back(&bucket, bucketStart, bucketEnd);
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);
347 CHECK_EQ(data.numBuckets, info.size());
349 // Check the data passed in to the function
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) {
356 offset += data.duration;
359 EXPECT_EQ(data.bucketStarts[bucketIdx] + offset,
360 info[infoIdx].start.count()) <<
361 data.duration << "x" << data.numBuckets << ": bucketIdx=" <<
362 bucketIdx << ", infoIdx=" << infoIdx;
364 size_t nextBucketIdx = bucketIdx + 1;
365 ssize_t nextOffset = offset;
366 if (nextBucketIdx >= data.numBuckets) {
368 nextOffset += data.duration;
370 EXPECT_EQ(data.bucketStarts[nextBucketIdx] + nextOffset,
371 info[infoIdx].nextStart.count()) <<
372 data.duration << "x" << data.numBuckets << ": bucketIdx=" <<
373 bucketIdx << ", infoIdx=" << infoIdx;
375 EXPECT_EQ(&ts.getBucketByIndex(bucketIdx), info[infoIdx].bucket);
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);
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)));
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));
402 for (unsigned int i = 0; i < kDuration; ++i) {
403 // add value 'i' at time 'i'
404 b.addValue(seconds(i), i);
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}
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}
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() << ")";
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() << ")";
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() << ")";
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() << ")";
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);
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}
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}
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() << ")";
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() << ")";
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() << ")";
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() << ")";