Fix line too long lint errors
[folly.git] / folly / test / TimeseriesHistogramTest.cpp
1 /*
2  * Copyright 2014 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 }