folly/stats/BucketedTimeSeries.h

   1 /*
   2  * Copyright 2017 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, uint64_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, uint64_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>(ReturnType(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>(
 292         ReturnType(total_.count), elapsed());
 293   }
 294
 295   /*
 296    * Estimate the sum of the data points that occurred in the specified time
 297    * period.
 298    *
 299    * The range queried is [start, end).
 300    * That is, start is inclusive, and end is exclusive.
 301    *
 302    * Note that data outside of the timeseries duration will no longer be
 303    * available for use in the estimation.  Specifying a start time earlier than
 304    * getEarliestTime() will not have much effect, since only data points after
 305    * that point in time will be counted.
 306    *
 307    * Note that the value returned is an estimate, and may not be precise.
 308    */
 309   ValueType sum(TimePoint start, TimePoint end) const;
 310
 311   /*
 312    * Estimate the number of data points that occurred in the specified time
 313    * period.
 314    *
 315    * The same caveats documented in the sum(TimePoint start, TimePoint end)
 316    * comments apply here as well.
 317    */
 318   uint64_t count(TimePoint start, TimePoint end) const;
 319
 320   /*
 321    * Estimate the average value during the specified time period.
 322    *
 323    * The same caveats documented in the sum(TimePoint start, TimePoint end)
 324    * comments apply here as well.
 325    */
 326   template <typename ReturnType = double>
 327   ReturnType avg(TimePoint start, TimePoint end) const;
 328
 329   /*
 330    * Estimate the rate during the specified time period.
 331    *
 332    * The same caveats documented in the sum(TimePoint start, TimePoint end)
 333    * comments apply here as well.
 334    */
 335   template <typename ReturnType = double, typename Interval = Duration>
 336   ReturnType rate(TimePoint start, TimePoint end) const {
 337     ValueType intervalSum = sum(start, end);
 338     Duration interval = elapsed(start, end);
 339     return rateHelper<ReturnType, Interval>(intervalSum, interval);
 340   }
 341
 342   /*
 343    * Estimate the rate of data points being added during the specified time
 344    * period.
 345    *
 346    * The same caveats documented in the sum(TimePoint start, TimePoint end)
 347    * comments apply here as well.
 348    */
 349   template <typename ReturnType = double, typename Interval = Duration>
 350   ReturnType countRate(TimePoint start, TimePoint end) const {
 351     uint64_t intervalCount = count(start, end);
 352     Duration interval = elapsed(start, end);
 353     return rateHelper<ReturnType, Interval>(
 354         ReturnType(intervalCount), interval);
 355   }
 356
 357   /*
 358    * Invoke a function for each bucket.
 359    *
 360    * The function will take as arguments the bucket index,
 361    * the bucket start time, and the start time of the subsequent bucket.
 362    *
 363    * It should return true to continue iterating through the buckets, and false
 364    * to break out of the loop and stop, without calling the function on any
 365    * more buckets.
 366    *
 367    * bool function(const Bucket& bucket, TimePoint bucketStart,
 368    *               TimePoint nextBucketStart)
 369    */
 370   template <typename Function>
 371   void forEachBucket(Function fn) const;
 372
 373   /*
 374    * Get the index for the bucket containing the specified time.
 375    *
 376    * Note that the index is only valid if this time actually falls within one
 377    * of the current buckets.  If you pass in a value more recent than
 378    * getLatestTime() or older than (getLatestTime() - elapsed()), the index
 379    * returned will not be valid.
 380    *
 381    * This method may not be called for all-time data.
 382    */
 383   size_t getBucketIdx(TimePoint time) const;
 384
 385   /*
 386    * Get the bucket at the specified index.
 387    *
 388    * This method may not be called for all-time data.
 389    */
 390   const Bucket& getBucketByIndex(size_t idx) const {
 391     return buckets_[idx];
 392   }
 393
 394   /*
 395    * Compute the bucket index that the specified time falls into,
 396    * as well as the bucket start time and the next bucket's start time.
 397    *
 398    * This method may not be called for all-time data.
 399    */
 400   void getBucketInfo(
 401       TimePoint time,
 402       size_t* bucketIdx,
 403       TimePoint* bucketStart,
 404       TimePoint* nextBucketStart) const;
 405
 406   /*
 407    * Legacy APIs that accept a Duration parameters rather than TimePoint.
 408    *
 409    * These treat the Duration as relative to the clock epoch.
 410    * Prefer using the correct TimePoint-based APIs instead.  These APIs will
 411    * eventually be deprecated and removed.
 412    */
 413   bool addValue(Duration now, const ValueType& val) {
 414     return addValueAggregated(TimePoint(now), val, 1);
 415   }
 416   bool addValue(Duration now, const ValueType& val, uint64_t times) {
 417     return addValueAggregated(TimePoint(now), val * ValueType(times), times);
 418   }
 419   bool
 420   addValueAggregated(Duration now, const ValueType& total, uint64_t nsamples) {
 421     return addValueAggregated(TimePoint(now), total, nsamples);
 422   }
 423   size_t update(Duration now) {
 424     return update(TimePoint(now));
 425   }
 426
 427  private:
 428   template <typename ReturnType = double, typename Interval = Duration>
 429   ReturnType rateHelper(ReturnType numerator, Duration elapsedTime) const {
 430     return detail::rateHelper<ReturnType, Duration, Interval>(
 431         numerator, elapsedTime);
 432   }
 433
 434   TimePoint getEarliestTimeNonEmpty() const;
 435   size_t updateBuckets(TimePoint now);
 436
 437   ValueType rangeAdjust(
 438       TimePoint bucketStart,
 439       TimePoint nextBucketStart,
 440       TimePoint start,
 441       TimePoint end,
 442       ValueType input) const;
 443
 444   template <typename Function>
 445   void forEachBucket(TimePoint start, TimePoint end, Function fn) const;
 446
 447   TimePoint firstTime_; // time of first update() since clear()/constructor
 448   TimePoint latestTime_; // time of last update()
 449   Duration duration_; // total duration ("window length") of the time series
 450
 451   Bucket total_;                 // sum and count of everything in time series
 452   std::vector<Bucket> buckets_;  // actual buckets of values
 453 };
 454
 455 } // folly