1 /*****************************************************************************
2 * rrd_hw_update.c Functions for updating a Holt-Winters RRA
3 ****************************************************************************/
5 #include "rrd_format.h"
6 #include "rrd_config.h"
7 #include "rrd_hw_math.h"
8 #include "rrd_hw_update.h"
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 }
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 }
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]);
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;
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;
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;
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;
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);
98 /* update the slope */
99 coefs[CDP_hw_slope].u_val =
100 functions->slope(current_rra->par[RRA_hw_beta].u_val, coefs);
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 }
111 /* store the prediction for writing */
112 coefs[CDP_scratch_idx].u_val = prediction;
113 return 0;
114 }
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]);
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;
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];
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 }
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;
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. */
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);
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 }
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;
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 }
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]);
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;
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];
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;
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 }
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 }
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;
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)) {
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 */
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 }
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 }
455 }
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;
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;
473 return (rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val);
474 }