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