b672866f34e167b5a60398188bd7df77b0505867
[folly.git] / 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 <folly/portability/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 }