folly/stats/MultiLevelTimeSeries.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 <stdexcept>
  21 #include <string>
  22 #include <vector>
  23
  24 #include <folly/String.h>
  25 #include <folly/stats/BucketedTimeSeries.h>
  26 #include <glog/logging.h>
  27
  28 namespace folly {
  29
  30 /*
  31  * This class represents a timeseries which keeps several levels of data
  32  * granularity (similar in principle to the loads reported by the UNIX
  33  * 'uptime' command).  It uses several instances (one per level) of
  34  * BucketedTimeSeries as the underlying storage.
  35  *
  36  * This can easily be used to track sums (and thus rates or averages) over
  37  * several predetermined time periods, as well as all-time sums.  For example,
  38  * you would use to it to track query rate or response speed over the last
  39  * 5, 15, 30, and 60 minutes.
  40  *
  41  * The MultiLevelTimeSeries takes a list of level durations as an input; the
  42  * durations must be strictly increasing.  Furthermore a special level can be
  43  * provided with a duration of '0' -- this will be an "all-time" level.  If
  44  * an all-time level is provided, it MUST be the last level present.
  45  *
  46  * The class assumes that time advances forward --  you can't retroactively add
  47  * values for events in the past -- the 'now' argument is provided for better
  48  * efficiency and ease of unittesting.
  49  *
  50  * The class is not thread-safe -- use your own synchronization!
  51  */
  52 template <typename VT, typename CT = LegacyStatsClock<std::chrono::seconds>>
  53 class MultiLevelTimeSeries {
  54  public:
  55   using ValueType = VT;
  56   using Clock = CT;
  57   using Duration = typename Clock::duration;
  58   using TimePoint = typename Clock::time_point;
  59   using Level = folly::BucketedTimeSeries<ValueType, Clock>;
  60
  61   /*
  62    * Create a new MultiLevelTimeSeries.
  63    *
  64    * This creates a new MultiLevelTimeSeries that tracks time series data at the
  65    * specified time durations (level). The time series data tracked at each
  66    * level is then further divided by numBuckets for memory efficiency.
  67    *
  68    * The durations must be strictly increasing. Furthermore a special level can
  69    * be provided with a duration of '0' -- this will be an "all-time" level. If
  70    * an all-time level is provided, it MUST be the last level present.
  71    */
  72   MultiLevelTimeSeries(
  73       size_t numBuckets,
  74       size_t numLevels,
  75       const Duration levelDurations[]);
  76
  77   MultiLevelTimeSeries(
  78       size_t numBuckets,
  79       std::initializer_list<Duration> durations);
  80
  81   /*
  82    * Return the number of buckets used to track time series at each level.
  83    */
  84   size_t numBuckets() const {
  85     // The constructor ensures that levels_ has at least one item
  86     return levels_[0].numBuckets();
  87   }
  88
  89   /*
  90    * Return the number of levels tracked by MultiLevelTimeSeries.
  91    */
  92   size_t numLevels() const { return levels_.size(); }
  93
  94   /*
  95    * Get the BucketedTimeSeries backing the specified level.
  96    *
  97    * Note: you should generally call update() or flush() before accessing the
  98    * data. Otherwise you may be reading stale data if update() or flush() has
  99    * not been called recently.
 100    */
 101   const Level& getLevel(int level) const {
 102     CHECK(level >= 0);
 103     CHECK_LT(level, levels_.size());
 104     return levels_[level];
 105   }
 106
 107   /*
 108    * Get the highest granularity level that is still large enough to contain
 109    * data going back to the specified start time.
 110    *
 111    * Note: you should generally call update() or flush() before accessing the
 112    * data. Otherwise you may be reading stale data if update() or flush() has
 113    * not been called recently.
 114    */
 115   const Level& getLevel(TimePoint start) const {
 116     for (const auto& level : levels_) {
 117       if (level.isAllTime()) {
 118         return level;
 119       }
 120       // Note that we use duration() here rather than elapsed().
 121       // If duration is large enough to contain the start time then this level
 122       // is good enough, even if elapsed() indicates that no data was recorded
 123       // before the specified start time.
 124       if (level.getLatestTime() - level.duration() <= start) {
 125         return level;
 126       }
 127     }
 128     // We should always have an all-time level, so this is never reached.
 129     LOG(FATAL) << "No level of timeseries covers internval"
 130                << " from " << start.time_since_epoch().count() << " to now";
 131     return levels_.back();
 132   }
 133
 134   /*
 135    * Get the BucketedTimeSeries backing the specified level.
 136    *
 137    * Note: you should generally call update() or flush() before accessing the
 138    * data. Otherwise you may be reading stale data if update() or flush() has
 139    * not been called recently.
 140    */
 141   const Level& getLevelByDuration(Duration duration) const {
 142     // since the number of levels is expected to be small (less than 5 in most
 143     // cases), a simple linear scan would be efficient and is intentionally
 144     // chosen here over other alternatives for lookup.
 145     for (const auto& level : levels_) {
 146       if (level.duration() == duration) {
 147         return level;
 148       }
 149     }
 150     throw std::out_of_range(folly::to<std::string>(
 151         "No level of duration ", duration.count(), " found"));
 152   }
 153
 154   /*
 155    * Return the sum of all the data points currently tracked at this level.
 156    *
 157    * Note: you should generally call update() or flush() before accessing the
 158    * data. Otherwise you may be reading stale data if update() or flush() has
 159    * not been called recently.
 160    */
 161   ValueType sum(int level) const {
 162     return getLevel(level).sum();
 163   }
 164
 165   /*
 166    * Return the average (sum / count) of all the data points currently tracked
 167    * at this level.
 168    *
 169    * The return type may be specified to control whether floating-point or
 170    * integer division should be performed.
 171    *
 172    * Note: you should generally call update() or flush() before accessing the
 173    * data. Otherwise you may be reading stale data if update() or flush() has
 174    * not been called recently.
 175    */
 176   template <typename ReturnType=double>
 177   ReturnType avg(int level) const {
 178     return getLevel(level).template avg<ReturnType>();
 179   }
 180
 181   /*
 182    * Return the rate (sum divided by elaspsed time) of the all data points
 183    * currently tracked at this level.
 184    *
 185    * Note: you should generally call update() or flush() before accessing the
 186    * data. Otherwise you may be reading stale data if update() or flush() has
 187    * not been called recently.
 188    */
 189   template <typename ReturnType = double, typename Interval = Duration>
 190   ReturnType rate(int level) const {
 191     return getLevel(level).template rate<ReturnType, Interval>();
 192   }
 193
 194   /*
 195    * Return the number of data points currently tracked at this level.
 196    *
 197    * Note: you should generally call update() or flush() before accessing the
 198    * data. Otherwise you may be reading stale data if update() or flush() has
 199    * not been called recently.
 200    */
 201   int64_t count(int level) const {
 202     return getLevel(level).count();
 203   }
 204
 205   /*
 206    * Return the count divided by the elapsed time tracked at this level.
 207    *
 208    * Note: you should generally call update() or flush() before accessing the
 209    * data. Otherwise you may be reading stale data if update() or flush() has
 210    * not been called recently.
 211    */
 212   template <typename ReturnType = double, typename Interval = Duration>
 213   ReturnType countRate(int level) const {
 214     return getLevel(level).template countRate<ReturnType, Interval>();
 215   }
 216
 217   /*
 218    * Return the sum of all the data points currently tracked at this level.
 219    *
 220    * This method is identical to sum(int level) above but takes in the
 221    * duration that the user is interested in querying as the parameter.
 222    *
 223    * Note: you should generally call update() or flush() before accessing the
 224    * data. Otherwise you may be reading stale data if update() or flush() has
 225    * not been called recently.
 226    */
 227   ValueType sum(Duration duration) const {
 228     return getLevelByDuration(duration).sum();
 229   }
 230
 231   /*
 232    * Return the average (sum / count) of all the data points currently tracked
 233    * at this level.
 234    *
 235    * This method is identical to avg(int level) above but takes in the
 236    * duration that the user is interested in querying as the parameter.
 237    *
 238    * Note: you should generally call update() or flush() before accessing the
 239    * data. Otherwise you may be reading stale data if update() or flush() has
 240    * not been called recently.
 241    */
 242   template <typename ReturnType = double>
 243   ReturnType avg(Duration duration) const {
 244     return getLevelByDuration(duration).template avg<ReturnType>();
 245   }
 246
 247   /*
 248    * Return the rate (sum divided by elaspsed time) of the all data points
 249    * currently tracked at this level.
 250    *
 251    * This method is identical to rate(int level) above but takes in the
 252    * duration that the user is interested in querying as the parameter.
 253    *
 254    * Note: you should generally call update() or flush() before accessing the
 255    * data. Otherwise you may be reading stale data if update() or flush() has
 256    * not been called recently.
 257    */
 258   template <typename ReturnType = double, typename Interval = Duration>
 259   ReturnType rate(Duration duration) const {
 260     return getLevelByDuration(duration).template rate<ReturnType, Interval>();
 261   }
 262
 263   /*
 264    * Return the number of data points currently tracked at this level.
 265    *
 266    * This method is identical to count(int level) above but takes in the
 267    * duration that the user is interested in querying as the parameter.
 268    *
 269    * Note: you should generally call update() or flush() before accessing the
 270    * data. Otherwise you may be reading stale data if update() or flush() has
 271    * not been called recently.
 272    */
 273   int64_t count(Duration duration) const {
 274     return getLevelByDuration(duration).count();
 275   }
 276
 277   /*
 278    * Return the count divided by the elapsed time tracked at this level.
 279    *
 280    * This method is identical to countRate(int level) above but takes in the
 281    * duration that the user is interested in querying as the parameter.
 282    *
 283    * Note: you should generally call update() or flush() before accessing the
 284    * data. Otherwise you may be reading stale data if update() or flush() has
 285    * not been called recently.
 286    */
 287   template <typename ReturnType = double, typename Interval = Duration>
 288   ReturnType countRate(Duration duration) const {
 289     return getLevelByDuration(duration)
 290         .template countRate<ReturnType, Interval>();
 291   }
 292
 293   /*
 294    * Estimate the sum of the data points that occurred in the specified time
 295    * period at this level.
 296    *
 297    * The range queried is [start, end).
 298    * That is, start is inclusive, and end is exclusive.
 299    *
 300    * Note that data outside of the timeseries duration will no longer be
 301    * available for use in the estimation.  Specifying a start time earlier than
 302    * getEarliestTime() will not have much effect, since only data points after
 303    * that point in time will be counted.
 304    *
 305    * Note that the value returned is an estimate, and may not be precise.
 306    *
 307    * Note: you should generally call update() or flush() before accessing the
 308    * data. Otherwise you may be reading stale data if update() or flush() has
 309    * not been called recently.
 310    */
 311   ValueType sum(TimePoint start, TimePoint end) const {
 312     return getLevel(start).sum(start, end);
 313   }
 314
 315   /*
 316    * Estimate the average value during the specified time period.
 317    *
 318    * The same caveats documented in the sum(TimePoint start, TimePoint end)
 319    * comments apply here as well.
 320    *
 321    * Note: you should generally call update() or flush() before accessing the
 322    * data. Otherwise you may be reading stale data if update() or flush() has
 323    * not been called recently.
 324    */
 325   template <typename ReturnType = double>
 326   ReturnType avg(TimePoint start, TimePoint end) const {
 327     return getLevel(start).template avg<ReturnType>(start, end);
 328   }
 329
 330   /*
 331    * Estimate the rate during the specified time period.
 332    *
 333    * The same caveats documented in the sum(TimePoint start, TimePoint end)
 334    * comments apply here as well.
 335    *
 336    * Note: you should generally call update() or flush() before accessing the
 337    * data. Otherwise you may be reading stale data if update() or flush() has
 338    * not been called recently.
 339    */
 340   template <typename ReturnType = double>
 341   ReturnType rate(TimePoint start, TimePoint end) const {
 342     return getLevel(start).template rate<ReturnType>(start, end);
 343   }
 344
 345   /*
 346    * Estimate the count during the specified time period.
 347    *
 348    * The same caveats documented in the sum(TimePoint start, TimePoint end)
 349    * comments apply here as well.
 350    *
 351    * Note: you should generally call update() or flush() before accessing the
 352    * data. Otherwise you may be reading stale data if update() or flush() has
 353    * not been called recently.
 354    */
 355   int64_t count(TimePoint start, TimePoint end) const {
 356     return getLevel(start).count(start, end);
 357   }
 358
 359   /*
 360    * Adds the value 'val' at time 'now' to all levels.
 361    *
 362    * Data points added at the same time point is cached internally here and not
 363    * propagated to the underlying levels until either flush() is called or when
 364    * update from a different time comes.
 365    *
 366    * This function expects time to always move forwards: it cannot be used to
 367    * add historical data points that have occurred in the past.  If now is
 368    * older than the another timestamp that has already been passed to
 369    * addValue() or update(), now will be ignored and the latest timestamp will
 370    * be used.
 371    */
 372   void addValue(TimePoint now, const ValueType& val);
 373
 374   /*
 375    * Adds the value 'val' at time 'now' to all levels.
 376    */
 377   void addValue(TimePoint now, const ValueType& val, int64_t times);
 378
 379   /*
 380    * Adds the value 'total' at time 'now' to all levels as the sum of
 381    * 'nsamples' samples.
 382    */
 383   void
 384   addValueAggregated(TimePoint now, const ValueType& total, int64_t nsamples);
 385
 386   /*
 387    * Update all the levels to the specified time, doing all the necessary
 388    * work to rotate the buckets and remove any stale data points.
 389    *
 390    * When reading data from the timeseries, you should make sure to manually
 391    * call update() before accessing the data. Otherwise you may be reading
 392    * stale data if update() has not been called recently.
 393    */
 394   void update(TimePoint now);
 395
 396   /*
 397    * Reset all the timeseries to an empty state as if no data points have ever
 398    * been added to it.
 399    */
 400   void clear();
 401
 402   /*
 403    * Flush all cached updates.
 404    */
 405   void flush();
 406
 407   /*
 408    * Legacy APIs that accept a Duration parameters rather than TimePoint.
 409    *
 410    * These treat the Duration as relative to the clock epoch.
 411    * Prefer using the correct TimePoint-based APIs instead.  These APIs will
 412    * eventually be deprecated and removed.
 413    */
 414   void update(Duration now) {
 415     update(TimePoint(now));
 416   }
 417   void addValue(Duration now, const ValueType& value) {
 418     addValue(TimePoint(now), value);
 419   }
 420   void addValue(Duration now, const ValueType& value, int64_t times) {
 421     addValue(TimePoint(now), value, times);
 422   }
 423   void
 424   addValueAggregated(Duration now, const ValueType& total, int64_t nsamples) {
 425     addValueAggregated(TimePoint(now), total, nsamples);
 426   }
 427
 428  private:
 429   std::vector<Level> levels_;
 430
 431   // Updates within the same time interval are cached
 432   // They are flushed out when updates from a different time comes,
 433   // or flush() is called.
 434   TimePoint cachedTime_;
 435   ValueType cachedSum_;
 436   int cachedCount_;
 437 };
 438
 439 } // folly