src/rrd_hw_update.c

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