src/rrd_hw_update.c

   1 /*****************************************************************************
   2  * rrd_hw_update.c  Functions for updating a Holt-Winters RRA
   3  ****************************************************************************/
   4
   5 #include "rrd_tool.h"
   6 #include "rrd_format.h"
   7 #ifndef WIN32
   8 #include "rrd_config.h"
   9 #endif
  10 #include "rrd_hw_math.h"
  11 #include "rrd_hw_update.h"
  12
  13 static void init_slope_intercept(
  14     unival *coefs,
  15     unsigned short CDP_scratch_idx)
  16 {
  17 #ifdef DEBUG
  18     fprintf(stderr, "Initialization of slope/intercept\n");
  19 #endif
  20     coefs[CDP_hw_intercept].u_val = coefs[CDP_scratch_idx].u_val;
  21     coefs[CDP_hw_last_intercept].u_val = coefs[CDP_scratch_idx].u_val;
  22     /* initialize the slope to 0 */
  23     coefs[CDP_hw_slope].u_val = 0.0;
  24     coefs[CDP_hw_last_slope].u_val = 0.0;
  25     /* initialize null count to 1 */
  26     coefs[CDP_null_count].u_cnt = 1;
  27     coefs[CDP_last_null_count].u_cnt = 1;
  28 }
  29
  30 static int hw_is_violation(
  31     rrd_value_t observed,
  32     rrd_value_t prediction,
  33     rrd_value_t deviation,
  34     rrd_value_t delta_pos,
  35     rrd_value_t delta_neg)
  36 {
  37     return (observed > prediction + delta_pos * deviation
  38             || observed < prediction - delta_neg * deviation);
  39 }
  40
  41 int update_hwpredict(
  42     rrd_t *rrd,
  43     unsigned long cdp_idx,
  44     unsigned long rra_idx,
  45     unsigned long ds_idx,
  46     unsigned short CDP_scratch_idx,
  47     hw_functions_t * functions)
  48 {
  49     rrd_value_t prediction;
  50     unsigned long dependent_rra_idx, seasonal_cdp_idx;
  51     unival   *coefs = rrd->cdp_prep[cdp_idx].scratch;
  52     rra_def_t *current_rra = &(rrd->rra_def[rra_idx]);
  53     rrd_value_t seasonal_coef;
  54
  55     /* save coefficients from current prediction */
  56     coefs[CDP_hw_last_intercept].u_val = coefs[CDP_hw_intercept].u_val;
  57     coefs[CDP_hw_last_slope].u_val = coefs[CDP_hw_slope].u_val;
  58     coefs[CDP_last_null_count].u_cnt = coefs[CDP_null_count].u_cnt;
  59
  60     /* retrieve the current seasonal coef */
  61     dependent_rra_idx = current_rra->par[RRA_dependent_rra_idx].u_cnt;
  62     seasonal_cdp_idx = dependent_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
  63
  64     seasonal_coef = (dependent_rra_idx < rra_idx)
  65         ? rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_hw_last_seasonal].u_val
  66         : rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_hw_seasonal].u_val;
  67
  68     /* compute the prediction */
  69     if (isnan(coefs[CDP_hw_intercept].u_val)
  70         || isnan(coefs[CDP_hw_slope].u_val)
  71         || isnan(seasonal_coef)) {
  72         prediction = DNAN;
  73
  74         /* bootstrap initialization of slope and intercept */
  75         if (isnan(coefs[CDP_hw_intercept].u_val) &&
  76             !isnan(coefs[CDP_scratch_idx].u_val)) {
  77             init_slope_intercept(coefs, CDP_scratch_idx);
  78         }
  79         /* if seasonal coefficient is NA, then don't update intercept, slope */
  80     } else {
  81         prediction = functions->predict(coefs[CDP_hw_intercept].u_val,
  82                                         coefs[CDP_hw_slope].u_val,
  83                                         coefs[CDP_null_count].u_cnt,
  84                                         seasonal_coef);
  85 #ifdef DEBUG
  86         fprintf(stderr,
  87                 "computed prediction: %f (intercept %f, slope %f, season %f)\n",
  88                 prediction, coefs[CDP_hw_intercept].u_val,
  89                 coefs[CDP_hw_slope].u_val, seasonal_coef);
  90 #endif
  91         if (isnan(coefs[CDP_scratch_idx].u_val)) {
  92             /* NA value, no updates of intercept, slope;
  93              * increment the null count */
  94             (coefs[CDP_null_count].u_cnt)++;
  95         } else {
  96             /* update the intercept */
  97             coefs[CDP_hw_intercept].u_val =
  98                 functions->intercept(current_rra->par[RRA_hw_alpha].u_val,
  99                                      coefs[CDP_scratch_idx].u_val,
 100                                      seasonal_coef, coefs);
 101
 102             /* update the slope */
 103             coefs[CDP_hw_slope].u_val =
 104                 functions->slope(current_rra->par[RRA_hw_beta].u_val, coefs);
 105
 106             /* reset the null count */
 107             coefs[CDP_null_count].u_cnt = 1;
 108 #ifdef DEBUG
 109             fprintf(stderr, "Updating intercept = %f, slope = %f\n",
 110                     coefs[CDP_hw_intercept].u_val, coefs[CDP_hw_slope].u_val);
 111 #endif
 112         }
 113     }
 114
 115     /* store the prediction for writing */
 116     coefs[CDP_scratch_idx].u_val = prediction;
 117     return 0;
 118 }
 119
 120 int update_seasonal(
 121     rrd_t *rrd,
 122     unsigned long cdp_idx,
 123     unsigned long rra_idx,
 124     unsigned long ds_idx,
 125     unsigned short CDP_scratch_idx,
 126     rrd_value_t *seasonal_coef,
 127     hw_functions_t * functions)
 128 {
 129 /* TODO: extract common if subblocks in the wake of I/O optimization */
 130     rrd_value_t intercept, seasonal;
 131     rra_def_t *current_rra = &(rrd->rra_def[rra_idx]);
 132     rra_def_t *hw_rra =
 133         &(rrd->rra_def[current_rra->par[RRA_dependent_rra_idx].u_cnt]);
 134
 135     /* obtain cdp_prep index for HWPREDICT */
 136     unsigned long hw_cdp_idx = (current_rra->par[RRA_dependent_rra_idx].u_cnt)
 137         * (rrd->stat_head->ds_cnt) + ds_idx;
 138     unival   *coefs = rrd->cdp_prep[hw_cdp_idx].scratch;
 139
 140     /* update seasonal coefficient in cdp prep areas */
 141     seasonal = rrd->cdp_prep[cdp_idx].scratch[CDP_hw_seasonal].u_val;
 142     rrd->cdp_prep[cdp_idx].scratch[CDP_hw_last_seasonal].u_val = seasonal;
 143     rrd->cdp_prep[cdp_idx].scratch[CDP_hw_seasonal].u_val =
 144         seasonal_coef[ds_idx];
 145
 146     if (isnan(rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val)) {
 147         /* no update, store the old value unchanged,
 148          * doesn't matter if it is NA */
 149         rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = seasonal;
 150         return 0;
 151     }
 152
 153     /* update seasonal value for disk */
 154     if (current_rra->par[RRA_dependent_rra_idx].u_cnt < rra_idx) {
 155         /* associated HWPREDICT has already been updated */
 156         /* check for possible NA values */
 157         if (isnan(coefs[CDP_hw_last_intercept].u_val)
 158             || isnan(coefs[CDP_hw_last_slope].u_val)) {
 159             /* this should never happen, as HWPREDICT was already updated */
 160             rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = DNAN;
 161         } else if (isnan(seasonal)) {
 162             /* initialization: intercept is not currently being updated */
 163 #ifdef DEBUG
 164             fprintf(stderr, "Initialization of seasonal coef %lu\n",
 165                     rrd->rra_ptr[rra_idx].cur_row);
 166 #endif
 167             rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
 168                 functions->init_seasonality(rrd->cdp_prep[cdp_idx].
 169                                             scratch[CDP_scratch_idx].u_val,
 170                                             coefs[CDP_hw_last_intercept].
 171                                             u_val);
 172         } else {
 173             intercept = coefs[CDP_hw_intercept].u_val;
 174
 175             rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
 176                 functions->seasonality(current_rra->par[RRA_seasonal_gamma].
 177                                        u_val,
 178                                        rrd->cdp_prep[cdp_idx].
 179                                        scratch[CDP_scratch_idx].u_val,
 180                                        intercept, seasonal);
 181 #ifdef DEBUG
 182             fprintf(stderr,
 183                     "Updating seasonal = %f (params: gamma %f, new intercept %f, old seasonal %f)\n",
 184                     rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val,
 185                     current_rra->par[RRA_seasonal_gamma].u_val,
 186                     intercept, seasonal);
 187 #endif
 188         }
 189     } else {
 190         /* SEASONAL array is updated first, which means the new intercept
 191          * hasn't be computed; so we compute it here. */
 192
 193         /* check for possible NA values */
 194         if (isnan(coefs[CDP_hw_intercept].u_val)
 195             || isnan(coefs[CDP_hw_slope].u_val)) {
 196             /* Initialization of slope and intercept will occur.
 197              * force seasonal coefficient to 0 or 1. */
 198             rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
 199                 functions->identity;
 200         } else if (isnan(seasonal)) {
 201             /* initialization: intercept will not be updated
 202              * CDP_hw_intercept = CDP_hw_last_intercept; just need to
 203              * subtract/divide by this baseline value. */
 204 #ifdef DEBUG
 205             fprintf(stderr, "Initialization of seasonal coef %lu\n",
 206                     rrd->rra_ptr[rra_idx].cur_row);
 207 #endif
 208             rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
 209                 functions->init_seasonality(rrd->cdp_prep[cdp_idx].
 210                                             scratch[CDP_scratch_idx].u_val,
 211                                             coefs[CDP_hw_intercept].u_val);
 212         } else {
 213             /* Note that we must get CDP_scratch_idx from SEASONAL array, as CDP_scratch_idx
 214              * for HWPREDICT array will be DNAN. */
 215             intercept = functions->intercept(hw_rra->par[RRA_hw_alpha].u_val,
 216                                              rrd->cdp_prep[cdp_idx].
 217                                              scratch[CDP_scratch_idx].u_val,
 218                                              seasonal, coefs);
 219
 220             rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
 221                 functions->seasonality(current_rra->par[RRA_seasonal_gamma].
 222                                        u_val,
 223                                        rrd->cdp_prep[cdp_idx].
 224                                        scratch[CDP_scratch_idx].u_val,
 225                                        intercept, seasonal);
 226         }
 227     }
 228 #ifdef DEBUG
 229     fprintf(stderr, "seasonal coefficient set= %f\n",
 230             rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val);
 231 #endif
 232     return 0;
 233 }
 234
 235 int update_devpredict(
 236     rrd_t *rrd,
 237     unsigned long cdp_idx,
 238     unsigned long rra_idx,
 239     unsigned long ds_idx,
 240     unsigned short CDP_scratch_idx)
 241 {
 242     /* there really isn't any "update" here; the only reason this information
 243      * is stored separately from DEVSEASONAL is to preserve deviation predictions
 244      * for a longer duration than one seasonal cycle. */
 245     unsigned long seasonal_cdp_idx =
 246         (rrd->rra_def[rra_idx].par[RRA_dependent_rra_idx].u_cnt)
 247         * (rrd->stat_head->ds_cnt) + ds_idx;
 248
 249     if (rrd->rra_def[rra_idx].par[RRA_dependent_rra_idx].u_cnt < rra_idx) {
 250         /* associated DEVSEASONAL array already updated */
 251         rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val
 252             =
 253             rrd->cdp_prep[seasonal_cdp_idx].
 254             scratch[CDP_last_seasonal_deviation].u_val;
 255     } else {
 256         /* associated DEVSEASONAL not yet updated */
 257         rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val
 258             =
 259             rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_seasonal_deviation].
 260             u_val;
 261     }
 262     return 0;
 263 }
 264
 265 int update_devseasonal(
 266     rrd_t *rrd,
 267     unsigned long cdp_idx,
 268     unsigned long rra_idx,
 269     unsigned long ds_idx,
 270     unsigned short CDP_scratch_idx,
 271     rrd_value_t *seasonal_dev,
 272     hw_functions_t * functions)
 273 {
 274     rrd_value_t prediction = 0, seasonal_coef = DNAN;
 275     rra_def_t *current_rra = &(rrd->rra_def[rra_idx]);
 276
 277     /* obtain cdp_prep index for HWPREDICT */
 278     unsigned long hw_rra_idx = current_rra->par[RRA_dependent_rra_idx].u_cnt;
 279     unsigned long hw_cdp_idx = hw_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
 280     unsigned long seasonal_cdp_idx;
 281     unival   *coefs = rrd->cdp_prep[hw_cdp_idx].scratch;
 282
 283     rrd->cdp_prep[cdp_idx].scratch[CDP_last_seasonal_deviation].u_val =
 284         rrd->cdp_prep[cdp_idx].scratch[CDP_seasonal_deviation].u_val;
 285     /* retrieve the next seasonal deviation value, could be NA */
 286     rrd->cdp_prep[cdp_idx].scratch[CDP_seasonal_deviation].u_val =
 287         seasonal_dev[ds_idx];
 288
 289     /* retrieve the current seasonal_coef (not to be confused with the
 290      * current seasonal deviation). Could make this more readable by introducing
 291      * some wrapper functions. */
 292     seasonal_cdp_idx =
 293         (rrd->rra_def[hw_rra_idx].par[RRA_dependent_rra_idx].u_cnt)
 294         * (rrd->stat_head->ds_cnt) + ds_idx;
 295     if (rrd->rra_def[hw_rra_idx].par[RRA_dependent_rra_idx].u_cnt < rra_idx)
 296         /* SEASONAL array already updated */
 297         seasonal_coef =
 298             rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_hw_last_seasonal].
 299             u_val;
 300     else
 301         /* SEASONAL array not yet updated */
 302         seasonal_coef =
 303             rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_hw_seasonal].u_val;
 304
 305     /* compute the abs value of the difference between the prediction and
 306      * observed value */
 307     if (hw_rra_idx < rra_idx) {
 308         /* associated HWPREDICT has already been updated */
 309         if (isnan(coefs[CDP_hw_last_intercept].u_val) ||
 310             isnan(coefs[CDP_hw_last_slope].u_val) || isnan(seasonal_coef)) {
 311             /* one of the prediction values is uinitialized */
 312             rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = DNAN;
 313             return 0;
 314         } else {
 315             prediction =
 316                 functions->predict(coefs[CDP_hw_last_intercept].u_val,
 317                                    coefs[CDP_hw_last_slope].u_val,
 318                                    coefs[CDP_last_null_count].u_cnt,
 319                                    seasonal_coef);
 320         }
 321     } else {
 322         /* associated HWPREDICT has NOT been updated */
 323         if (isnan(coefs[CDP_hw_intercept].u_val) ||
 324             isnan(coefs[CDP_hw_slope].u_val) || isnan(seasonal_coef)) {
 325             /* one of the prediction values is uinitialized */
 326             rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = DNAN;
 327             return 0;
 328         } else {
 329             prediction = functions->predict(coefs[CDP_hw_intercept].u_val,
 330                                             coefs[CDP_hw_slope].u_val,
 331                                             coefs[CDP_null_count].u_cnt,
 332                                             seasonal_coef);
 333         }
 334     }
 335
 336     if (isnan(rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val)) {
 337         /* no update, store existing value unchanged, doesn't
 338          * matter if it is NA */
 339         rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
 340             rrd->cdp_prep[cdp_idx].scratch[CDP_last_seasonal_deviation].u_val;
 341     } else
 342         if (isnan
 343             (rrd->cdp_prep[cdp_idx].scratch[CDP_last_seasonal_deviation].
 344              u_val)) {
 345         /* initialization */
 346 #ifdef DEBUG
 347         fprintf(stderr, "Initialization of seasonal deviation\n");
 348 #endif
 349         rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
 350             functions->init_seasonal_deviation(prediction,
 351                                                rrd->cdp_prep[cdp_idx].
 352                                                scratch[CDP_scratch_idx].
 353                                                u_val);
 354     } else {
 355         /* exponential smoothing update */
 356         rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
 357             functions->seasonal_deviation(rrd->rra_def[rra_idx].
 358                                           par[RRA_seasonal_gamma].u_val,
 359                                           prediction,
 360                                           rrd->cdp_prep[cdp_idx].
 361                                           scratch[CDP_scratch_idx].u_val,
 362                                           rrd->cdp_prep[cdp_idx].
 363                                           scratch
 364                                           [CDP_last_seasonal_deviation].
 365                                           u_val);
 366     }
 367     return 0;
 368 }
 369
 370 /* Check for a failure based on a threshold # of violations within the specified
 371  * window. */
 372 int update_failures(
 373     rrd_t *rrd,
 374     unsigned long cdp_idx,
 375     unsigned long rra_idx,
 376     unsigned long ds_idx,
 377     unsigned short CDP_scratch_idx,
 378     hw_functions_t * functions)
 379 {
 380     /* detection of a violation depends on 3 RRAs:
 381      * HWPREDICT, SEASONAL, and DEVSEASONAL */
 382     rra_def_t *current_rra = &(rrd->rra_def[rra_idx]);
 383     unsigned long dev_rra_idx = current_rra->par[RRA_dependent_rra_idx].u_cnt;
 384     rra_def_t *dev_rra = &(rrd->rra_def[dev_rra_idx]);
 385     unsigned long hw_rra_idx = dev_rra->par[RRA_dependent_rra_idx].u_cnt;
 386     rra_def_t *hw_rra = &(rrd->rra_def[hw_rra_idx]);
 387     unsigned long seasonal_rra_idx = hw_rra->par[RRA_dependent_rra_idx].u_cnt;
 388     unsigned long temp_cdp_idx;
 389     rrd_value_t deviation = DNAN;
 390     rrd_value_t seasonal_coef = DNAN;
 391     rrd_value_t prediction = DNAN;
 392     char      violation = 0;
 393     unsigned short violation_cnt = 0, i;
 394     char     *violations_array;
 395
 396     /* usual checks to determine the order of the RRAs */
 397     temp_cdp_idx = dev_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
 398     if (rra_idx < seasonal_rra_idx) {
 399         /* DEVSEASONAL not yet updated */
 400         deviation =
 401             rrd->cdp_prep[temp_cdp_idx].scratch[CDP_seasonal_deviation].u_val;
 402     } else {
 403         /* DEVSEASONAL already updated */
 404         deviation =
 405             rrd->cdp_prep[temp_cdp_idx].scratch[CDP_last_seasonal_deviation].
 406             u_val;
 407     }
 408     if (!isnan(deviation)) {
 409
 410         temp_cdp_idx = seasonal_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
 411         if (rra_idx < seasonal_rra_idx) {
 412             /* SEASONAL not yet updated */
 413             seasonal_coef =
 414                 rrd->cdp_prep[temp_cdp_idx].scratch[CDP_hw_seasonal].u_val;
 415         } else {
 416             /* SEASONAL already updated */
 417             seasonal_coef =
 418                 rrd->cdp_prep[temp_cdp_idx].scratch[CDP_hw_last_seasonal].
 419                 u_val;
 420         }
 421         /* in this code block, we know seasonal coef is not DNAN, because deviation is not
 422          * null */
 423
 424         temp_cdp_idx = hw_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
 425         if (rra_idx < hw_rra_idx) {
 426             /* HWPREDICT not yet updated */
 427             prediction =
 428                 functions->predict(rrd->cdp_prep[temp_cdp_idx].
 429                                    scratch[CDP_hw_intercept].u_val,
 430                                    rrd->cdp_prep[temp_cdp_idx].
 431                                    scratch[CDP_hw_slope].u_val,
 432                                    rrd->cdp_prep[temp_cdp_idx].
 433                                    scratch[CDP_null_count].u_cnt,
 434                                    seasonal_coef);
 435         } else {
 436             /* HWPREDICT already updated */
 437             prediction =
 438                 functions->predict(rrd->cdp_prep[temp_cdp_idx].
 439                                    scratch[CDP_hw_last_intercept].u_val,
 440                                    rrd->cdp_prep[temp_cdp_idx].
 441                                    scratch[CDP_hw_last_slope].u_val,
 442                                    rrd->cdp_prep[temp_cdp_idx].
 443                                    scratch[CDP_last_null_count].u_cnt,
 444                                    seasonal_coef);
 445         }
 446
 447         /* determine if the observed value is a violation */
 448         if (!isnan(rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val)) {
 449             if (hw_is_violation
 450                 (rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val,
 451                  prediction, deviation, current_rra->par[RRA_delta_pos].u_val,
 452                  current_rra->par[RRA_delta_neg].u_val)) {
 453                 violation = 1;
 454             }
 455         } else {
 456             violation = 1;  /* count DNAN values as violations */
 457         }
 458
 459     }
 460
 461     /* determine if a failure has occurred and update the failure array */
 462     violation_cnt = violation;
 463     violations_array = (char *) ((void *) rrd->cdp_prep[cdp_idx].scratch);
 464     for (i = current_rra->par[RRA_window_len].u_cnt; i > 1; i--) {
 465         /* shift */
 466         violations_array[i - 1] = violations_array[i - 2];
 467         violation_cnt += violations_array[i - 1];
 468     }
 469     violations_array[0] = violation;
 470
 471     if (violation_cnt < current_rra->par[RRA_failure_threshold].u_cnt)
 472         /* not a failure */
 473         rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = 0.0;
 474     else
 475         rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = 1.0;
 476
 477     return (rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val);
 478 }