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