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