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