1package backoff 2 3import ( 4 "math/rand" 5 "time" 6) 7 8/* 9ExponentialBackOff is a backoff implementation that increases the backoff 10period for each retry attempt using a randomization function that grows exponentially. 11 12NextBackOff() is calculated using the following formula: 13 14 randomized interval = 15 RetryInterval * (random value in range [1 - RandomizationFactor, 1 + RandomizationFactor]) 16 17In other words NextBackOff() will range between the randomization factor 18percentage below and above the retry interval. 19 20For example, given the following parameters: 21 22 RetryInterval = 2 23 RandomizationFactor = 0.5 24 Multiplier = 2 25 26the actual backoff period used in the next retry attempt will range between 1 and 3 seconds, 27multiplied by the exponential, that is, between 2 and 6 seconds. 28 29Note: MaxInterval caps the RetryInterval and not the randomized interval. 30 31If the time elapsed since an ExponentialBackOff instance is created goes past the 32MaxElapsedTime, then the method NextBackOff() starts returning backoff.Stop. 33 34The elapsed time can be reset by calling Reset(). 35 36Example: Given the following default arguments, for 10 tries the sequence will be, 37and assuming we go over the MaxElapsedTime on the 10th try: 38 39 Request # RetryInterval (seconds) Randomized Interval (seconds) 40 41 1 0.5 [0.25, 0.75] 42 2 0.75 [0.375, 1.125] 43 3 1.125 [0.562, 1.687] 44 4 1.687 [0.8435, 2.53] 45 5 2.53 [1.265, 3.795] 46 6 3.795 [1.897, 5.692] 47 7 5.692 [2.846, 8.538] 48 8 8.538 [4.269, 12.807] 49 9 12.807 [6.403, 19.210] 50 10 19.210 backoff.Stop 51 52Note: Implementation is not thread-safe. 53*/ 54type ExponentialBackOff struct { 55 InitialInterval time.Duration 56 RandomizationFactor float64 57 Multiplier float64 58 MaxInterval time.Duration 59 // After MaxElapsedTime the ExponentialBackOff returns Stop. 60 // It never stops if MaxElapsedTime == 0. 61 MaxElapsedTime time.Duration 62 Stop time.Duration 63 Clock Clock 64 65 currentInterval time.Duration 66 startTime time.Time 67} 68 69// Clock is an interface that returns current time for BackOff. 70type Clock interface { 71 Now() time.Time 72} 73 74// Default values for ExponentialBackOff. 75const ( 76 DefaultInitialInterval = 500 * time.Millisecond 77 DefaultRandomizationFactor = 0.5 78 DefaultMultiplier = 1.5 79 DefaultMaxInterval = 60 * time.Second 80 DefaultMaxElapsedTime = 15 * time.Minute 81) 82 83// NewExponentialBackOff creates an instance of ExponentialBackOff using default values. 84func NewExponentialBackOff() *ExponentialBackOff { 85 b := &ExponentialBackOff{ 86 InitialInterval: DefaultInitialInterval, 87 RandomizationFactor: DefaultRandomizationFactor, 88 Multiplier: DefaultMultiplier, 89 MaxInterval: DefaultMaxInterval, 90 MaxElapsedTime: DefaultMaxElapsedTime, 91 Stop: Stop, 92 Clock: SystemClock, 93 } 94 b.Reset() 95 return b 96} 97 98type systemClock struct{} 99 100func (t systemClock) Now() time.Time { 101 return time.Now() 102} 103 104// SystemClock implements Clock interface that uses time.Now(). 105var SystemClock = systemClock{} 106 107// Reset the interval back to the initial retry interval and restarts the timer. 108// Reset must be called before using b. 109func (b *ExponentialBackOff) Reset() { 110 b.currentInterval = b.InitialInterval 111 b.startTime = b.Clock.Now() 112} 113 114// NextBackOff calculates the next backoff interval using the formula: 115// Randomized interval = RetryInterval * (1 ± RandomizationFactor) 116func (b *ExponentialBackOff) NextBackOff() time.Duration { 117 // Make sure we have not gone over the maximum elapsed time. 118 if b.MaxElapsedTime != 0 && b.GetElapsedTime() > b.MaxElapsedTime { 119 return b.Stop 120 } 121 defer b.incrementCurrentInterval() 122 return getRandomValueFromInterval(b.RandomizationFactor, rand.Float64(), b.currentInterval) 123} 124 125// GetElapsedTime returns the elapsed time since an ExponentialBackOff instance 126// is created and is reset when Reset() is called. 127// 128// The elapsed time is computed using time.Now().UnixNano(). It is 129// safe to call even while the backoff policy is used by a running 130// ticker. 131func (b *ExponentialBackOff) GetElapsedTime() time.Duration { 132 return b.Clock.Now().Sub(b.startTime) 133} 134 135// Increments the current interval by multiplying it with the multiplier. 136func (b *ExponentialBackOff) incrementCurrentInterval() { 137 // Check for overflow, if overflow is detected set the current interval to the max interval. 138 if float64(b.currentInterval) >= float64(b.MaxInterval)/b.Multiplier { 139 b.currentInterval = b.MaxInterval 140 } else { 141 b.currentInterval = time.Duration(float64(b.currentInterval) * b.Multiplier) 142 } 143} 144 145// Returns a random value from the following interval: 146// [randomizationFactor * currentInterval, randomizationFactor * currentInterval]. 147func getRandomValueFromInterval(randomizationFactor, random float64, currentInterval time.Duration) time.Duration { 148 var delta = randomizationFactor * float64(currentInterval) 149 var minInterval = float64(currentInterval) - delta 150 var maxInterval = float64(currentInterval) + delta 151 152 // Get a random value from the range [minInterval, maxInterval]. 153 // The formula used below has a +1 because if the minInterval is 1 and the maxInterval is 3 then 154 // we want a 33% chance for selecting either 1, 2 or 3. 155 return time.Duration(minInterval + (random * (maxInterval - minInterval + 1))) 156} 157