1// Package ewma implements exponentially weighted moving averages.
2package ewma
3
4// Copyright (c) 2013 VividCortex, Inc. All rights reserved.
5// Please see the LICENSE file for applicable license terms.
6
7const (
8	// By default, we average over a one-minute period, which means the average
9	// age of the metrics in the period is 30 seconds.
10	AVG_METRIC_AGE float64 = 30.0
11
12	// The formula for computing the decay factor from the average age comes
13	// from "Production and Operations Analysis" by Steven Nahmias.
14	DECAY float64 = 2 / (float64(AVG_METRIC_AGE) + 1)
15
16	// For best results, the moving average should not be initialized to the
17	// samples it sees immediately. The book "Production and Operations
18	// Analysis" by Steven Nahmias suggests initializing the moving average to
19	// the mean of the first 10 samples. Until the VariableEwma has seen this
20	// many samples, it is not "ready" to be queried for the value of the
21	// moving average. This adds some memory cost.
22	WARMUP_SAMPLES uint8 = 10
23)
24
25// MovingAverage is the interface that computes a moving average over a time-
26// series stream of numbers. The average may be over a window or exponentially
27// decaying.
28type MovingAverage interface {
29	Add(float64)
30	Value() float64
31	Set(float64)
32}
33
34// NewMovingAverage constructs a MovingAverage that computes an average with the
35// desired characteristics in the moving window or exponential decay. If no
36// age is given, it constructs a default exponentially weighted implementation
37// that consumes minimal memory. The age is related to the decay factor alpha
38// by the formula given for the DECAY constant. It signifies the average age
39// of the samples as time goes to infinity.
40func NewMovingAverage(age ...float64) MovingAverage {
41	if len(age) == 0 || age[0] == AVG_METRIC_AGE {
42		return new(SimpleEWMA)
43	}
44	return &VariableEWMA{
45		decay: 2 / (age[0] + 1),
46	}
47}
48
49// A SimpleEWMA represents the exponentially weighted moving average of a
50// series of numbers. It WILL have different behavior than the VariableEWMA
51// for multiple reasons. It has no warm-up period and it uses a constant
52// decay.  These properties let it use less memory.  It will also behave
53// differently when it's equal to zero, which is assumed to mean
54// uninitialized, so if a value is likely to actually become zero over time,
55// then any non-zero value will cause a sharp jump instead of a small change.
56// However, note that this takes a long time, and the value may just
57// decays to a stable value that's close to zero, but which won't be mistaken
58// for uninitialized. See http://play.golang.org/p/litxBDr_RC for example.
59type SimpleEWMA struct {
60	// The current value of the average. After adding with Add(), this is
61	// updated to reflect the average of all values seen thus far.
62	value float64
63}
64
65// Add adds a value to the series and updates the moving average.
66func (e *SimpleEWMA) Add(value float64) {
67	if e.value == 0 { // this is a proxy for "uninitialized"
68		e.value = value
69	} else {
70		e.value = (value * DECAY) + (e.value * (1 - DECAY))
71	}
72}
73
74// Value returns the current value of the moving average.
75func (e *SimpleEWMA) Value() float64 {
76	return e.value
77}
78
79// Set sets the EWMA's value.
80func (e *SimpleEWMA) Set(value float64) {
81	e.value = value
82}
83
84// VariableEWMA represents the exponentially weighted moving average of a series of
85// numbers. Unlike SimpleEWMA, it supports a custom age, and thus uses more memory.
86type VariableEWMA struct {
87	// The multiplier factor by which the previous samples decay.
88	decay float64
89	// The current value of the average.
90	value float64
91	// The number of samples added to this instance.
92	count uint8
93}
94
95// Add adds a value to the series and updates the moving average.
96func (e *VariableEWMA) Add(value float64) {
97	switch {
98	case e.count < WARMUP_SAMPLES:
99		e.count++
100		e.value += value
101	case e.count == WARMUP_SAMPLES:
102		e.count++
103		e.value = e.value / float64(WARMUP_SAMPLES)
104		e.value = (value * e.decay) + (e.value * (1 - e.decay))
105	default:
106		e.value = (value * e.decay) + (e.value * (1 - e.decay))
107	}
108}
109
110// Value returns the current value of the average, or 0.0 if the series hasn't
111// warmed up yet.
112func (e *VariableEWMA) Value() float64 {
113	if e.count <= WARMUP_SAMPLES {
114		return 0.0
115	}
116
117	return e.value
118}
119
120// Set sets the EWMA's value.
121func (e *VariableEWMA) Set(value float64) {
122	e.value = value
123	if e.count <= WARMUP_SAMPLES {
124		e.count = WARMUP_SAMPLES + 1
125	}
126}
127