src/utils_latency.c

   1 /**
   2  * collectd - src/utils_latency.c
   3  * Copyright (C) 2013       Florian Forster
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in
  13  * all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  *
  23  * Authors:
  24  *   Florian Forster <ff at octo.it>
  25  **/
  26
  27 #include "collectd.h"
  28
  29 #include "plugin.h"
  30 #include "utils_latency.h"
  31 #include "common.h"
  32
  33 #include <math.h>
  34 #include <limits.h>
  35
  36 #ifndef LLONG_MAX
  37 # define LLONG_MAX 9223372036854775807LL
  38 #endif
  39
  40 #ifndef HISTOGRAM_DEFAULT_BIN_WIDTH
  41 /* 1048576 = 2^20 ^= 1/1024 s */
  42 # define HISTOGRAM_DEFAULT_BIN_WIDTH 1048576
  43 #endif
  44
  45 struct latency_counter_s
  46 {
  47   cdtime_t start_time;
  48
  49   cdtime_t sum;
  50   size_t num;
  51
  52   cdtime_t min;
  53   cdtime_t max;
  54
  55   cdtime_t bin_width;
  56   int histogram[HISTOGRAM_NUM_BINS];
  57 };
  58
  59 /*
  60 * Histogram represents the distribution of data, it has a list of "bins".
  61 * Each bin represents an interval and has a count (frequency) of
  62 * number of values fall within its interval.
  63 *
  64 * Histogram's range is determined by the number of bins and the bin width,
  65 * There are 1000 bins and all bins have the same width of default 1 millisecond.
  66 * When a value above this range is added, Histogram's range is increased by
  67 * increasing the bin width (note that number of bins remains always at 1000).
  68 * This operation of increasing bin width is little expensive as each bin need
  69 * to be visited to update it's count. To reduce frequent change of bin width,
  70 * new bin width will be the next nearest power of 2. Example: 2, 4, 8, 16, 32,
  71 * 64, 128, 256, 512, 1024, 2048, 5086, ...
  72 *
  73 * So, if the required bin width is 300, then new bin width will be 512 as it is
  74 * the next nearest power of 2.
  75 */
  76 static void change_bin_width (latency_counter_t *lc, cdtime_t latency) /* {{{ */
  77 {
  78   /* This function is called because the new value is above histogram's range.
  79    * First find the required bin width:
  80    *           requiredBinWidth = (value + 1) / numBins
  81    * then get the next nearest power of 2
  82    *           newBinWidth = 2^(ceil(log2(requiredBinWidth)))
  83    */
  84   double required_bin_width = ((double) (latency + 1)) / ((double) HISTOGRAM_NUM_BINS);
  85   double required_bin_width_logbase2 = log (required_bin_width) / log (2.0);
  86   cdtime_t new_bin_width = (cdtime_t) (pow (2.0, ceil (required_bin_width_logbase2)) + .5);
  87   cdtime_t old_bin_width = lc->bin_width;
  88
  89   lc->bin_width = new_bin_width;
  90
  91   /* bin_width has been increased, now iterate through all bins and move the
  92    * old bin's count to new bin. */
  93   if (lc->num > 0) // if the histogram has data then iterate else skip
  94   {
  95       double width_change_ratio = ((double) old_bin_width) / ((double) new_bin_width);
  96
  97       for (size_t i = 0; i < HISTOGRAM_NUM_BINS; i++)
  98       {
  99          size_t new_bin = (size_t) (((double) i) * width_change_ratio);
 100          if (i == new_bin)
 101              continue;
 102          assert (new_bin < i);
 103
 104          lc->histogram[new_bin] += lc->histogram[i];
 105          lc->histogram[i] = 0;
 106       }
 107   }
 108
 109   DEBUG("utils_latency: change_bin_width: latency = %.3f; "
 110       "old_bin_width = %.3f; new_bin_width = %.3f;",
 111       CDTIME_T_TO_DOUBLE (latency),
 112       CDTIME_T_TO_DOUBLE (old_bin_width),
 113       CDTIME_T_TO_DOUBLE (new_bin_width));
 114 } /* }}} void change_bin_width */
 115
 116 latency_counter_t *latency_counter_create (void) /* {{{ */
 117 {
 118   latency_counter_t *lc;
 119
 120   lc = calloc (1, sizeof (*lc));
 121   if (lc == NULL)
 122     return (NULL);
 123
 124   lc->bin_width = HISTOGRAM_DEFAULT_BIN_WIDTH;
 125   latency_counter_reset (lc);
 126   return (lc);
 127 } /* }}} latency_counter_t *latency_counter_create */
 128
 129 void latency_counter_destroy (latency_counter_t *lc) /* {{{ */
 130 {
 131   sfree (lc);
 132 } /* }}} void latency_counter_destroy */
 133
 134 void latency_counter_add (latency_counter_t *lc, cdtime_t latency) /* {{{ */
 135 {
 136   cdtime_t bin;
 137
 138   if ((lc == NULL) || (latency == 0) || (latency > ((cdtime_t) LLONG_MAX)))
 139     return;
 140
 141   lc->sum += latency;
 142   lc->num++;
 143
 144   if ((lc->min == 0) && (lc->max == 0))
 145     lc->min = lc->max = latency;
 146   if (lc->min > latency)
 147     lc->min = latency;
 148   if (lc->max < latency)
 149     lc->max = latency;
 150
 151   /* A latency of _exactly_ 1.0 ms is stored in the buffer 0, so
 152    * subtract one from the cdtime_t value so that exactly 1.0 ms get sorted
 153    * accordingly. */
 154   bin = (latency - 1) / lc->bin_width;
 155   if (bin >= HISTOGRAM_NUM_BINS)
 156   {
 157       change_bin_width (lc, latency);
 158       bin = (latency - 1) / lc->bin_width;
 159       if (bin >= HISTOGRAM_NUM_BINS)
 160       {
 161           ERROR ("utils_latency: latency_counter_add: Invalid bin: %"PRIu64, bin);
 162           return;
 163       }
 164   }
 165   lc->histogram[bin]++;
 166 } /* }}} void latency_counter_add */
 167
 168 void latency_counter_reset (latency_counter_t *lc) /* {{{ */
 169 {
 170   if (lc == NULL)
 171     return;
 172
 173   cdtime_t bin_width = lc->bin_width;
 174   cdtime_t max_bin = (lc->max - 1) / lc->bin_width;
 175
 176 /*
 177   If max latency is REDUCE_THRESHOLD times less than histogram's range,
 178   then cut it in half. REDUCE_THRESHOLD must be >= 2.
 179   Value of 4 is selected to reduce frequent changes of bin width.
 180 */
 181 #define REDUCE_THRESHOLD 4
 182   if ((lc->num > 0) && (lc->bin_width >= HISTOGRAM_DEFAULT_BIN_WIDTH * 2)
 183      && (max_bin < HISTOGRAM_NUM_BINS / REDUCE_THRESHOLD))
 184   {
 185     /* new bin width will be the previous power of 2 */
 186     bin_width = bin_width / 2;
 187
 188     DEBUG("utils_latency: latency_counter_reset: max_latency = %.3f; "
 189           "max_bin = %"PRIu64"; old_bin_width = %.3f; new_bin_width = %.3f;",
 190         CDTIME_T_TO_DOUBLE (lc->max),
 191         max_bin,
 192         CDTIME_T_TO_DOUBLE (lc->bin_width),
 193         CDTIME_T_TO_DOUBLE (bin_width));
 194   }
 195
 196   memset (lc, 0, sizeof (*lc));
 197
 198   /* preserve bin width */
 199   lc->bin_width = bin_width;
 200   lc->start_time = cdtime ();
 201 } /* }}} void latency_counter_reset */
 202
 203 cdtime_t latency_counter_get_min (latency_counter_t *lc) /* {{{ */
 204 {
 205   if (lc == NULL)
 206     return (0);
 207   return (lc->min);
 208 } /* }}} cdtime_t latency_counter_get_min */
 209
 210 cdtime_t latency_counter_get_max (latency_counter_t *lc) /* {{{ */
 211 {
 212   if (lc == NULL)
 213     return (0);
 214   return (lc->max);
 215 } /* }}} cdtime_t latency_counter_get_max */
 216
 217 cdtime_t latency_counter_get_sum (latency_counter_t *lc) /* {{{ */
 218 {
 219   if (lc == NULL)
 220     return (0);
 221   return (lc->sum);
 222 } /* }}} cdtime_t latency_counter_get_sum */
 223
 224 size_t latency_counter_get_num (latency_counter_t *lc) /* {{{ */
 225 {
 226   if (lc == NULL)
 227     return (0);
 228   return (lc->num);
 229 } /* }}} size_t latency_counter_get_num */
 230
 231 cdtime_t latency_counter_get_average (latency_counter_t *lc) /* {{{ */
 232 {
 233   double average;
 234
 235   if ((lc == NULL) || (lc->num == 0))
 236     return (0);
 237
 238   average = CDTIME_T_TO_DOUBLE (lc->sum) / ((double) lc->num);
 239   return (DOUBLE_TO_CDTIME_T (average));
 240 } /* }}} cdtime_t latency_counter_get_average */
 241
 242 cdtime_t latency_counter_get_percentile (latency_counter_t *lc, /* {{{ */
 243     double percent)
 244 {
 245   double percent_upper;
 246   double percent_lower;
 247   double p;
 248   cdtime_t latency_lower;
 249   cdtime_t latency_interpolated;
 250   int sum;
 251   size_t i;
 252
 253   if ((lc == NULL) || (lc->num == 0) || !((percent > 0.0) && (percent < 100.0)))
 254     return (0);
 255
 256   /* Find index i so that at least "percent" events are within i+1 ms. */
 257   percent_upper = 0.0;
 258   percent_lower = 0.0;
 259   sum = 0;
 260   for (i = 0; i < HISTOGRAM_NUM_BINS; i++)
 261   {
 262     percent_lower = percent_upper;
 263     sum += lc->histogram[i];
 264     if (sum == 0)
 265       percent_upper = 0.0;
 266     else
 267       percent_upper = 100.0 * ((double) sum) / ((double) lc->num);
 268
 269     if (percent_upper >= percent)
 270       break;
 271   }
 272
 273   if (i >= HISTOGRAM_NUM_BINS)
 274     return (0);
 275
 276   assert (percent_upper >= percent);
 277   assert (percent_lower < percent);
 278
 279   if (i == 0)
 280     return (lc->bin_width);
 281
 282   latency_lower = ((cdtime_t) i) * lc->bin_width;
 283   p = (percent - percent_lower) / (percent_upper - percent_lower);
 284
 285   latency_interpolated = latency_lower
 286     + DOUBLE_TO_CDTIME_T (p * CDTIME_T_TO_DOUBLE (lc->bin_width));
 287
 288   DEBUG ("latency_counter_get_percentile: latency_interpolated = %.3f",
 289       CDTIME_T_TO_DOUBLE (latency_interpolated));
 290   return (latency_interpolated);
 291 } /* }}} cdtime_t latency_counter_get_percentile */
 292
 293 double latency_counter_get_rate(const latency_counter_t *lc, /* {{{ */
 294                                 cdtime_t lower, cdtime_t upper,
 295                                 const cdtime_t now) {
 296   if ((lc == NULL) || (lc->num == 0))
 297     return (NAN);
 298
 299   if (upper && (upper < lower))
 300     return (NAN);
 301   if (lower == upper)
 302     return (0);
 303
 304   /* Buckets have an exclusive lower bound and an inclusive upper bound. That
 305    * means that the first bucket, index 0, represents (0-bin_width]. That means
 306    * that latency==bin_width needs to result in bin=0, that's why we need to
 307    * subtract one before dividing by bin_width. */
 308   cdtime_t lower_bin = 0;
 309   if (lower)
 310     /* lower is *exclusive* => determine bucket for lower+1 */
 311     lower_bin = ((lower + 1) - 1) / lc->bin_width;
 312
 313   /* lower is greater than the longest latency observed => rate is zero. */
 314   if (lower_bin >= HISTOGRAM_NUM_BINS)
 315     return (0);
 316
 317   cdtime_t upper_bin = HISTOGRAM_NUM_BINS - 1;
 318   if (upper)
 319     upper_bin = (upper - 1) / lc->bin_width;
 320
 321   if (upper_bin >= HISTOGRAM_NUM_BINS) {
 322     upper_bin = HISTOGRAM_NUM_BINS - 1;
 323     upper = 0;
 324   }
 325
 326   double sum = 0;
 327   for (size_t i = lower_bin; i <= upper_bin; i++)
 328     sum += lc->histogram[i];
 329
 330   if (lower) {
 331     /* Approximate ratio of requests in lower_bin, that fall between
 332      * lower_bin_boundary and lower. This ratio is then subtracted from sum to
 333      * increase accuracy. */
 334     cdtime_t lower_bin_boundary = lower_bin * lc->bin_width;
 335     assert(lower >= lower_bin_boundary);
 336     double lower_ratio =
 337         (double)(lower - lower_bin_boundary) / ((double)lc->bin_width);
 338     sum -= lower_ratio * lc->histogram[lower_bin];
 339   }
 340
 341   if (upper) {
 342     /* As above: approximate ratio of requests in upper_bin, that fall between
 343      * upper and upper_bin_boundary. */
 344     cdtime_t upper_bin_boundary = (upper_bin + 1) * lc->bin_width;
 345     assert(upper <= upper_bin_boundary);
 346     double ratio = (double)(upper_bin_boundary - upper) / (double)lc->bin_width;
 347     sum -= ratio * lc->histogram[upper_bin];
 348   }
 349
 350   return sum / (CDTIME_T_TO_DOUBLE(now - lc->start_time));
 351 } /* }}} double latency_counter_get_rate */
 352
 353 /* vim: set sw=2 sts=2 et fdm=marker : */