folly/stats/BucketedTimeSeries.h

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