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