| 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/common/common.h" |
| 31 |
#include "utils/latency/latency.h" |
| 32 |
|
| 33 |
#include <limits.h> |
| 34 |
#include <math.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 |
cdtime_t start_time; |
| 47 |
|
| 48 |
cdtime_t sum; |
| 49 |
size_t num; |
| 50 |
|
| 51 |
cdtime_t min; |
| 52 |
cdtime_t max; |
| 53 |
|
| 54 |
cdtime_t bin_width; |
| 55 |
int histogram[HISTOGRAM_NUM_BINS]; |
| 56 |
}; |
| 57 |
|
| 58 |
/* |
| 59 |
* Histogram represents the distribution of data, it has a list of "bins". |
| 60 |
* Each bin represents an interval and has a count (frequency) of |
| 61 |
* number of values fall within its interval. |
| 62 |
* |
| 63 |
* Histogram's range is determined by the number of bins and the bin width, |
| 64 |
* There are 1000 bins and all bins have the same width of default 1 |
| 65 |
* millisecond. When a value above this range is added, Histogram's range is |
| 66 |
* increased by increasing the bin width (note that number of bins remains |
| 67 |
* always at 1000). This operation of increasing bin width is little expensive |
| 68 |
* as each bin need to be visited to update its count. To reduce frequent change |
| 69 |
* of bin width, new bin width will be the next nearest power of 2. Example: 2, |
| 70 |
* 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 5086, ... |
| 71 |
* |
| 72 |
* So, if the required bin width is 300, then new bin width will be 512 as it is |
| 73 |
* the next nearest power of 2. |
| 74 |
*/ |
| 75 |
static void change_bin_width(latency_counter_t *lc, cdtime_t latency) /* {{{ */ |
| 76 |
{ |
| 77 |
/* This function is called because the new value is above histogram's range. |
| 78 |
* First find the required bin width: |
| 79 |
* requiredBinWidth = (value + 1) / numBins |
| 80 |
* then get the next nearest power of 2 |
| 81 |
* newBinWidth = 2^(ceil(log2(requiredBinWidth))) |
| 82 |
*/ |
| 83 |
double required_bin_width = |
| 84 |
((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 = |
| 87 |
(cdtime_t)(pow(2.0, ceil(required_bin_width_logbase2)) + .5); |
| 88 |
cdtime_t old_bin_width = lc->bin_width; |
| 89 |
|
| 90 |
lc->bin_width = new_bin_width; |
| 91 |
|
| 92 |
/* bin_width has been increased, now iterate through all bins and move the |
| 93 |
* old bin's count to new bin. */ |
| 94 |
if (lc->num > 0) // if the histogram has data then iterate else skip |
| 95 |
{ |
| 96 |
double width_change_ratio = |
| 97 |
((double)old_bin_width) / ((double)new_bin_width); |
| 98 |
|
| 99 |
for (size_t i = 0; i < HISTOGRAM_NUM_BINS; i++) { |
| 100 |
size_t new_bin = (size_t)(((double)i) * width_change_ratio); |
| 101 |
if (i == new_bin) |
| 102 |
continue; |
| 103 |
assert(new_bin < i); |
| 104 |
|
| 105 |
lc->histogram[new_bin] += lc->histogram[i]; |
| 106 |
lc->histogram[i] = 0; |
| 107 |
} |
| 108 |
} |
| 109 |
|
| 110 |
DEBUG("utils_latency: change_bin_width: latency = %.3f; " |
| 111 |
"old_bin_width = %.3f; new_bin_width = %.3f;", |
| 112 |
CDTIME_T_TO_DOUBLE(latency), 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 |
change_bin_width(lc, latency); |
| 157 |
bin = (latency - 1) / lc->bin_width; |
| 158 |
if (bin >= HISTOGRAM_NUM_BINS) { |
| 159 |
P_ERROR("latency_counter_add: Invalid bin: %" PRIu64, bin); |
| 160 |
return; |
| 161 |
} |
| 162 |
} |
| 163 |
lc->histogram[bin]++; |
| 164 |
} /* }}} void latency_counter_add */ |
| 165 |
|
| 166 |
void latency_counter_reset(latency_counter_t *lc) /* {{{ */ |
| 167 |
{ |
| 168 |
if (lc == NULL) |
| 169 |
return; |
| 170 |
|
| 171 |
cdtime_t bin_width = lc->bin_width; |
| 172 |
cdtime_t max_bin = (lc->max - 1) / lc->bin_width; |
| 173 |
|
| 174 |
/* |
| 175 |
If max latency is REDUCE_THRESHOLD times less than histogram's range, |
| 176 |
then cut it in half. REDUCE_THRESHOLD must be >= 2. |
| 177 |
Value of 4 is selected to reduce frequent changes of bin width. |
| 178 |
*/ |
| 179 |
#define REDUCE_THRESHOLD 4 |
| 180 |
if ((lc->num > 0) && (lc->bin_width >= HISTOGRAM_DEFAULT_BIN_WIDTH * 2) && |
| 181 |
(max_bin < HISTOGRAM_NUM_BINS / REDUCE_THRESHOLD)) { |
| 182 |
/* new bin width will be the previous power of 2 */ |
| 183 |
bin_width = bin_width / 2; |
| 184 |
|
| 185 |
DEBUG("utils_latency: latency_counter_reset: max_latency = %.3f; " |
| 186 |
"max_bin = %" PRIu64 "; old_bin_width = %.3f; new_bin_width = %.3f;", |
| 187 |
CDTIME_T_TO_DOUBLE(lc->max), max_bin, |
| 188 |
CDTIME_T_TO_DOUBLE(lc->bin_width), CDTIME_T_TO_DOUBLE(bin_width)); |
| 189 |
} |
| 190 |
|
| 191 |
memset(lc, 0, sizeof(*lc)); |
| 192 |
|
| 193 |
/* preserve bin width */ |
| 194 |
lc->bin_width = bin_width; |
| 195 |
lc->start_time = cdtime(); |
| 196 |
} /* }}} void latency_counter_reset */ |
| 197 |
|
| 198 |
cdtime_t latency_counter_get_min(latency_counter_t *lc) /* {{{ */ |
| 199 |
{ |
| 200 |
if (lc == NULL) |
| 201 |
return 0; |
| 202 |
return lc->min; |
| 203 |
} /* }}} cdtime_t latency_counter_get_min */ |
| 204 |
|
| 205 |
cdtime_t latency_counter_get_max(latency_counter_t *lc) /* {{{ */ |
| 206 |
{ |
| 207 |
if (lc == NULL) |
| 208 |
return 0; |
| 209 |
return lc->max; |
| 210 |
} /* }}} cdtime_t latency_counter_get_max */ |
| 211 |
|
| 212 |
cdtime_t latency_counter_get_sum(latency_counter_t *lc) /* {{{ */ |
| 213 |
{ |
| 214 |
if (lc == NULL) |
| 215 |
return 0; |
| 216 |
return lc->sum; |
| 217 |
} /* }}} cdtime_t latency_counter_get_sum */ |
| 218 |
|
| 219 |
size_t latency_counter_get_num(latency_counter_t *lc) /* {{{ */ |
| 220 |
{ |
| 221 |
if (lc == NULL) |
| 222 |
return 0; |
| 223 |
return lc->num; |
| 224 |
} /* }}} size_t latency_counter_get_num */ |
| 225 |
|
| 226 |
cdtime_t latency_counter_get_average(latency_counter_t *lc) /* {{{ */ |
| 227 |
{ |
| 228 |
double average; |
| 229 |
|
| 230 |
if ((lc == NULL) || (lc->num == 0)) |
| 231 |
return 0; |
| 232 |
|
| 233 |
average = CDTIME_T_TO_DOUBLE(lc->sum) / ((double)lc->num); |
| 234 |
return DOUBLE_TO_CDTIME_T(average); |
| 235 |
} /* }}} cdtime_t latency_counter_get_average */ |
| 236 |
|
| 237 |
cdtime_t latency_counter_get_percentile(latency_counter_t *lc, /* {{{ */ |
| 238 |
double percent) { |
| 239 |
double percent_upper; |
| 240 |
double percent_lower; |
| 241 |
double p; |
| 242 |
cdtime_t latency_lower; |
| 243 |
cdtime_t latency_interpolated; |
| 244 |
int sum; |
| 245 |
size_t i; |
| 246 |
|
| 247 |
if ((lc == NULL) || (lc->num == 0) || !((percent > 0.0) && (percent < 100.0))) |
| 248 |
return 0; |
| 249 |
|
| 250 |
/* Find index i so that at least "percent" events are within i+1 ms. */ |
| 251 |
percent_upper = 0.0; |
| 252 |
percent_lower = 0.0; |
| 253 |
sum = 0; |
| 254 |
for (i = 0; i < HISTOGRAM_NUM_BINS; i++) { |
| 255 |
percent_lower = percent_upper; |
| 256 |
sum += lc->histogram[i]; |
| 257 |
if (sum == 0) |
| 258 |
percent_upper = 0.0; |
| 259 |
else |
| 260 |
percent_upper = 100.0 * ((double)sum) / ((double)lc->num); |
| 261 |
|
| 262 |
if (percent_upper >= percent) |
| 263 |
break; |
| 264 |
} |
| 265 |
|
| 266 |
if (i >= HISTOGRAM_NUM_BINS) |
| 267 |
return 0; |
| 268 |
|
| 269 |
assert(percent_upper >= percent); |
| 270 |
assert(percent_lower < percent); |
| 271 |
|
| 272 |
if (i == 0) |
| 273 |
return lc->bin_width; |
| 274 |
|
| 275 |
latency_lower = ((cdtime_t)i) * lc->bin_width; |
| 276 |
p = (percent - percent_lower) / (percent_upper - percent_lower); |
| 277 |
|
| 278 |
latency_interpolated = |
| 279 |
latency_lower + DOUBLE_TO_CDTIME_T(p * CDTIME_T_TO_DOUBLE(lc->bin_width)); |
| 280 |
|
| 281 |
DEBUG("latency_counter_get_percentile: latency_interpolated = %.3f", |
| 282 |
CDTIME_T_TO_DOUBLE(latency_interpolated)); |
| 283 |
return latency_interpolated; |
| 284 |
} /* }}} cdtime_t latency_counter_get_percentile */ |
| 285 |
|
| 286 |
double latency_counter_get_rate(const latency_counter_t *lc, /* {{{ */ |
| 287 |
cdtime_t lower, cdtime_t upper, |
| 288 |
const cdtime_t now) { |
| 289 |
if ((lc == NULL) || (lc->num == 0)) |
| 290 |
return NAN; |
| 291 |
|
| 292 |
if (upper && (upper < lower)) |
| 293 |
return NAN; |
| 294 |
if (lower == upper) |
| 295 |
return 0; |
| 296 |
|
| 297 |
/* Buckets have an exclusive lower bound and an inclusive upper bound. That |
| 298 |
* means that the first bucket, index 0, represents (0-bin_width]. That means |
| 299 |
* that latency==bin_width needs to result in bin=0, that's why we need to |
| 300 |
* subtract one before dividing by bin_width. */ |
| 301 |
cdtime_t lower_bin = 0; |
| 302 |
if (lower) |
| 303 |
/* lower is *exclusive* => determine bucket for lower+1 */ |
| 304 |
lower_bin = ((lower + 1) - 1) / lc->bin_width; |
| 305 |
|
| 306 |
/* lower is greater than the longest latency observed => rate is zero. */ |
| 307 |
if (lower_bin >= HISTOGRAM_NUM_BINS) |
| 308 |
return 0; |
| 309 |
|
| 310 |
cdtime_t upper_bin = HISTOGRAM_NUM_BINS - 1; |
| 311 |
if (upper) |
| 312 |
upper_bin = (upper - 1) / lc->bin_width; |
| 313 |
|
| 314 |
if (upper_bin >= HISTOGRAM_NUM_BINS) { |
| 315 |
upper_bin = HISTOGRAM_NUM_BINS - 1; |
| 316 |
upper = 0; |
| 317 |
} |
| 318 |
|
| 319 |
double sum = 0; |
| 320 |
for (size_t i = lower_bin; i <= upper_bin; i++) |
| 321 |
sum += lc->histogram[i]; |
| 322 |
|
| 323 |
if (lower) { |
| 324 |
/* Approximate ratio of requests in lower_bin, that fall between |
| 325 |
* lower_bin_boundary and lower. This ratio is then subtracted from sum to |
| 326 |
* increase accuracy. */ |
| 327 |
cdtime_t lower_bin_boundary = lower_bin * lc->bin_width; |
| 328 |
assert(lower >= lower_bin_boundary); |
| 329 |
double lower_ratio = |
| 330 |
(double)(lower - lower_bin_boundary) / ((double)lc->bin_width); |
| 331 |
sum -= lower_ratio * lc->histogram[lower_bin]; |
| 332 |
} |
| 333 |
|
| 334 |
if (upper) { |
| 335 |
/* As above: approximate ratio of requests in upper_bin, that fall between |
| 336 |
* upper and upper_bin_boundary. */ |
| 337 |
cdtime_t upper_bin_boundary = (upper_bin + 1) * lc->bin_width; |
| 338 |
assert(upper <= upper_bin_boundary); |
| 339 |
double ratio = (double)(upper_bin_boundary - upper) / (double)lc->bin_width; |
| 340 |
sum -= ratio * lc->histogram[upper_bin]; |
| 341 |
} |
| 342 |
|
| 343 |
return sum / (CDTIME_T_TO_DOUBLE(now - lc->start_time)); |
| 344 |
} /* }}} double latency_counter_get_rate */ |