update stats APIs to use TimePoint vs Duration correctly
[folly.git] / folly / stats / BucketedTimeSeries.h
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 #pragma once
18
19 #include <chrono>
20 #include <vector>
21
22 #include <folly/detail/Stats.h>
23
24 namespace folly {
25
26 /*
27  * A helper clock type to helper older code using BucketedTimeSeries with
28  * std::chrono::seconds transition to properly using clock types and time_point
29  * objects.
30  */
31 template <typename TT = std::chrono::seconds>
32 class LegacyStatsClock {
33  public:
34   using duration = TT;
35   using time_point = std::chrono::time_point<LegacyStatsClock, TT>;
36
37   // This clock does not actually implement now(), since the older API
38   // did not really specify what clock should be used.  (In practice most
39   // callers unfortuantely used wall clock time rather than a monotonic clock.)
40 };
41
42 /*
43  * This class represents a bucketed time series which keeps track of values
44  * added in the recent past, and merges these values together into a fixed
45  * number of buckets to keep a lid on memory use if the number of values
46  * added is very large.
47  *
48  * For example, a BucketedTimeSeries() with duration == 60s and 10 buckets
49  * will keep track of 10 6-second buckets, and discard all data added more
50  * than 1 minute ago.  As time ticks by, a 6-second bucket at a time will
51  * be discarded and new data will go into the newly opened bucket.  Internally,
52  * it uses a circular array of buckets that it reuses as time advances.
53  *
54  * This class assumes that time advances forwards.  The window of time tracked
55  * by the timeseries will advance forwards whenever a more recent timestamp is
56  * passed to addValue().  While it is possible to pass old time values to
57  * addValue(), this will never move the time window backwards.  If the old time
58  * value falls outside the tracked window of time, the data point will be
59  * ignored.
60  *
61  * This class is not thread-safe -- use your own synchronization!
62  */
63 template <typename VT, typename CT = LegacyStatsClock<std::chrono::seconds>>
64 class BucketedTimeSeries {
65  public:
66   using ValueType = VT;
67   using Clock = CT;
68   using Duration = typename Clock::duration;
69   using TimePoint = typename Clock::time_point;
70   using Bucket = detail::Bucket<ValueType>;
71
72   /*
73    * Create a new BucketedTimeSeries.
74    *
75    * This creates a new BucketedTimeSeries with the specified number of
76    * buckets, storing data for the specified amount of time.
77    *
78    * If the duration is 0, the BucketedTimeSeries will track data forever,
79    * and does not need the rolling buckets.  The numBuckets parameter is
80    * ignored when duration is 0.
81    */
82   BucketedTimeSeries(size_t numBuckets, Duration duration);
83
84   /*
85    * Adds the value 'val' at time 'now'
86    *
87    * This function expects time to generally move forwards.  The window of time
88    * tracked by this time series will move forwards with time.  If 'now' is
89    * more recent than any time previously seen, addValue() will automatically
90    * call update(now) to advance the time window tracked by this data
91    * structure.
92    *
93    * Values in the recent past may be added to the data structure by passing in
94    * a slightly older value of 'now', as long as this time point still falls
95    * within the tracked duration.  If 'now' is older than the tracked duration
96    * of time, the data point value will be ignored, and addValue() will return
97    * false without doing anything else.
98    *
99    * Returns true on success, or false if now was older than the tracked time
100    * window.
101    */
102   bool addValue(TimePoint now, const ValueType& val);
103
104   /*
105    * Adds the value 'val' the given number of 'times' at time 'now'
106    */
107   bool addValue(TimePoint now, const ValueType& val, int64_t times);
108
109   /*
110    * Adds the value 'total' as the sum of 'nsamples' samples
111    */
112   bool
113   addValueAggregated(TimePoint now, const ValueType& total, int64_t nsamples);
114
115   /*
116    * Updates the container to the specified time, doing all the necessary
117    * work to rotate the buckets and remove any stale data points.
118    *
119    * The addValue() methods automatically call update() when adding new data
120    * points.  However, when reading data from the timeseries, you should make
121    * sure to manually call update() before accessing the data.  Otherwise you
122    * may be reading stale data if update() has not been called recently.
123    *
124    * Returns the current bucket index after the update.
125    */
126   size_t update(TimePoint now);
127
128   /*
129    * Reset the timeseries to an empty state,
130    * as if no data points have ever been added to it.
131    */
132   void clear();
133
134   /*
135    * Get the latest time that has ever been passed to update() or addValue().
136    *
137    * If no data has ever been added to this timeseries, 0 will be returned.
138    */
139   TimePoint getLatestTime() const {
140     return latestTime_;
141   }
142
143   /*
144    * Get the time of the earliest data point stored in this timeseries.
145    *
146    * If no data has ever been added to this timeseries, 0 will be returned.
147    *
148    * If isAllTime() is true, this is simply the time when the first data point
149    * was recorded.
150    *
151    * For non-all-time data, the timestamp reflects the first data point still
152    * remembered.  As new data points are added, old data will be expired.
153    * getEarliestTime() returns the timestamp of the oldest bucket still present
154    * in the timeseries.  This will never be older than (getLatestTime() -
155    * duration()).
156    */
157   TimePoint getEarliestTime() const;
158
159   /*
160    * Return the number of buckets.
161    */
162   size_t numBuckets() const {
163     return buckets_.size();
164   }
165
166   /*
167    * Return the maximum duration of data that can be tracked by this
168    * BucketedTimeSeries.
169    */
170   Duration duration() const {
171     return duration_;
172   }
173
174   /*
175    * Returns true if this BucketedTimeSeries stores data for all-time, without
176    * ever rolling over into new buckets.
177    */
178   bool isAllTime() const {
179     return (duration_ == Duration(0));
180   }
181
182   /*
183    * Returns true if no calls to update() have been made since the last call to
184    * clear().
185    */
186   bool empty() const {
187     // We set firstTime_ greater than latestTime_ in the constructor and in
188     // clear, so we use this to distinguish if the timeseries is empty.
189     //
190     // Once a data point has been added, latestTime_ will always be greater
191     // than or equal to firstTime_.
192     return firstTime_ > latestTime_;
193   }
194
195   /*
196    * Get the amount of time tracked by this timeseries.
197    *
198    * For an all-time timeseries, this returns the length of time since the
199    * first data point was added to the time series.
200    *
201    * Otherwise, this never returns a value greater than the overall timeseries
202    * duration.  If the first data point was recorded less than a full duration
203    * ago, the time since the first data point is returned.  If a full duration
204    * has elapsed, and we have already thrown away some data, the time since the
205    * oldest bucket is returned.
206    *
207    * For example, say we are tracking 600 seconds worth of data, in 60 buckets.
208    * - If less than 600 seconds have elapsed since the first data point,
209    *   elapsed() returns the total elapsed time so far.
210    * - If more than 600 seconds have elapsed, we have already thrown away some
211    *   data.  However, we throw away a full bucket (10 seconds worth) at once,
212    *   so at any point in time we have from 590 to 600 seconds worth of data.
213    *   elapsed() will therefore return a value between 590 and 600.
214    *
215    * Note that you generally should call update() before calling elapsed(), to
216    * make sure you are not reading stale data.
217    */
218   Duration elapsed() const;
219
220   /*
221    * Get the amount of time tracked by this timeseries, between the specified
222    * start and end times.
223    *
224    * If the timeseries contains data for the entire time range specified, this
225    * simply returns (end - start).  However, if start is earlier than
226    * getEarliestTime(), this returns (end - getEarliestTime()).
227    */
228   Duration elapsed(TimePoint start, TimePoint end) const;
229
230   /*
231    * Return the sum of all the data points currently tracked by this
232    * BucketedTimeSeries.
233    *
234    * Note that you generally should call update() before calling sum(), to
235    * make sure you are not reading stale data.
236    */
237   const ValueType& sum() const {
238     return total_.sum;
239   }
240
241   /*
242    * Return the number of data points currently tracked by this
243    * BucketedTimeSeries.
244    *
245    * Note that you generally should call update() before calling count(), to
246    * make sure you are not reading stale data.
247    */
248   uint64_t count() const {
249     return total_.count;
250   }
251
252   /*
253    * Return the average value (sum / count).
254    *
255    * The return type may be specified to control whether floating-point or
256    * integer division should be performed.
257    *
258    * Note that you generally should call update() before calling avg(), to
259    * make sure you are not reading stale data.
260    */
261   template <typename ReturnType=double>
262   ReturnType avg() const {
263     return total_.template avg<ReturnType>();
264   }
265
266   /*
267    * Return the sum divided by the elapsed time.
268    *
269    * Note that you generally should call update() before calling rate(), to
270    * make sure you are not reading stale data.
271    */
272   template <typename ReturnType = double, typename Interval = Duration>
273   ReturnType rate() const {
274     return rateHelper<ReturnType, Interval>(total_.sum, elapsed());
275   }
276
277   /*
278    * Return the count divided by the elapsed time.
279    *
280    * The Interval template parameter causes the elapsed time to be converted to
281    * the Interval type before using it.  For example, if Interval is
282    * std::chrono::seconds, the return value will be the count per second.
283    * If Interval is std::chrono::hours, the return value will be the count per
284    * hour.
285    *
286    * Note that you generally should call update() before calling countRate(),
287    * to make sure you are not reading stale data.
288    */
289   template <typename ReturnType = double, typename Interval = Duration>
290   ReturnType countRate() const {
291     return rateHelper<ReturnType, Interval>(total_.count, elapsed());
292   }
293
294   /*
295    * Estimate the sum of the data points that occurred in the specified time
296    * period.
297    *
298    * The range queried is [start, end).
299    * That is, start is inclusive, and end is exclusive.
300    *
301    * Note that data outside of the timeseries duration will no longer be
302    * available for use in the estimation.  Specifying a start time earlier than
303    * getEarliestTime() will not have much effect, since only data points after
304    * that point in time will be counted.
305    *
306    * Note that the value returned is an estimate, and may not be precise.
307    */
308   ValueType sum(TimePoint start, TimePoint end) const;
309
310   /*
311    * Estimate the number of data points that occurred in the specified time
312    * period.
313    *
314    * The same caveats documented in the sum(TimePoint start, TimePoint end)
315    * comments apply here as well.
316    */
317   uint64_t count(TimePoint start, TimePoint end) const;
318
319   /*
320    * Estimate the average value during the specified time period.
321    *
322    * The same caveats documented in the sum(TimePoint start, TimePoint end)
323    * comments apply here as well.
324    */
325   template <typename ReturnType = double>
326   ReturnType avg(TimePoint start, TimePoint end) const;
327
328   /*
329    * Estimate the rate during the specified time period.
330    *
331    * The same caveats documented in the sum(TimePoint start, TimePoint end)
332    * comments apply here as well.
333    */
334   template <typename ReturnType = double, typename Interval = Duration>
335   ReturnType rate(TimePoint start, TimePoint end) const {
336     ValueType intervalSum = sum(start, end);
337     Duration interval = elapsed(start, end);
338     return rateHelper<ReturnType, Interval>(intervalSum, interval);
339   }
340
341   /*
342    * Estimate the rate of data points being added during the specified time
343    * period.
344    *
345    * The same caveats documented in the sum(TimePoint start, TimePoint end)
346    * comments apply here as well.
347    */
348   template <typename ReturnType = double, typename Interval = Duration>
349   ReturnType countRate(TimePoint start, TimePoint end) const {
350     uint64_t intervalCount = count(start, end);
351     Duration interval = elapsed(start, end);
352     return rateHelper<ReturnType, Interval>(intervalCount, interval);
353   }
354
355   /*
356    * Invoke a function for each bucket.
357    *
358    * The function will take as arguments the bucket index,
359    * the bucket start time, and the start time of the subsequent bucket.
360    *
361    * It should return true to continue iterating through the buckets, and false
362    * to break out of the loop and stop, without calling the function on any
363    * more buckets.
364    *
365    * bool function(const Bucket& bucket, TimePoint bucketStart,
366    *               TimePoint nextBucketStart)
367    */
368   template <typename Function>
369   void forEachBucket(Function fn) const;
370
371   /*
372    * Get the index for the bucket containing the specified time.
373    *
374    * Note that the index is only valid if this time actually falls within one
375    * of the current buckets.  If you pass in a value more recent than
376    * getLatestTime() or older than (getLatestTime() - elapsed()), the index
377    * returned will not be valid.
378    *
379    * This method may not be called for all-time data.
380    */
381   size_t getBucketIdx(TimePoint time) const;
382
383   /*
384    * Get the bucket at the specified index.
385    *
386    * This method may not be called for all-time data.
387    */
388   const Bucket& getBucketByIndex(size_t idx) const {
389     return buckets_[idx];
390   }
391
392   /*
393    * Compute the bucket index that the specified time falls into,
394    * as well as the bucket start time and the next bucket's start time.
395    *
396    * This method may not be called for all-time data.
397    */
398   void getBucketInfo(
399       TimePoint time,
400       size_t* bucketIdx,
401       TimePoint* bucketStart,
402       TimePoint* nextBucketStart) const;
403
404   /*
405    * Legacy APIs that accept a Duration parameters rather than TimePoint.
406    *
407    * These treat the Duration as relative to the clock epoch.
408    * Prefer using the correct TimePoint-based APIs instead.  These APIs will
409    * eventually be deprecated and removed.
410    */
411   bool addValue(Duration now, const ValueType& val) {
412     return addValueAggregated(TimePoint(now), val, 1);
413   }
414   bool addValue(Duration now, const ValueType& val, int64_t times) {
415     return addValueAggregated(TimePoint(now), val * times, times);
416   }
417   bool
418   addValueAggregated(Duration now, const ValueType& total, int64_t nsamples) {
419     return addValueAggregated(TimePoint(now), total, nsamples);
420   }
421   size_t update(Duration now) {
422     return update(TimePoint(now));
423   }
424
425  private:
426   template <typename ReturnType = double, typename Interval = Duration>
427   ReturnType rateHelper(ReturnType numerator, Duration elapsedTime) const {
428     return detail::rateHelper<ReturnType, Duration, Interval>(
429         numerator, elapsedTime);
430   }
431
432   TimePoint getEarliestTimeNonEmpty() const;
433   size_t updateBuckets(TimePoint now);
434
435   ValueType rangeAdjust(
436       TimePoint bucketStart,
437       TimePoint nextBucketStart,
438       TimePoint start,
439       TimePoint end,
440       ValueType input) const;
441
442   template <typename Function>
443   void forEachBucket(TimePoint start, TimePoint end, Function fn) const;
444
445   TimePoint firstTime_; // time of first update() since clear()/constructor
446   TimePoint latestTime_; // time of last update()
447   Duration duration_; // total duration ("window length") of the time series
448
449   Bucket total_;                 // sum and count of everything in time series
450   std::vector<Bucket> buckets_;  // actual buckets of values
451 };
452
453 } // folly