exponential.go (5749B)
1 package backoff 2 3 import ( 4 "math/rand" 5 "time" 6 ) 7 8 /* 9 ExponentialBackOff is a backoff implementation that increases the backoff 10 period for each retry attempt using a randomization function that grows exponentially. 11 12 NextBackOff() is calculated using the following formula: 13 14 randomized interval = 15 RetryInterval * (random value in range [1 - RandomizationFactor, 1 + RandomizationFactor]) 16 17 In other words NextBackOff() will range between the randomization factor 18 percentage below and above the retry interval. 19 20 For example, given the following parameters: 21 22 RetryInterval = 2 23 RandomizationFactor = 0.5 24 Multiplier = 2 25 26 the actual backoff period used in the next retry attempt will range between 1 and 3 seconds, 27 multiplied by the exponential, that is, between 2 and 6 seconds. 28 29 Note: MaxInterval caps the RetryInterval and not the randomized interval. 30 31 If the time elapsed since an ExponentialBackOff instance is created goes past the 32 MaxElapsedTime, then the method NextBackOff() starts returning backoff.Stop. 33 34 The elapsed time can be reset by calling Reset(). 35 36 Example: Given the following default arguments, for 10 tries the sequence will be, 37 and 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 52 Note: Implementation is not thread-safe. 53 */ 54 type 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. 70 type Clock interface { 71 Now() time.Time 72 } 73 74 // Default values for ExponentialBackOff. 75 const ( 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. 84 func 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 98 type systemClock struct{} 99 100 func (t systemClock) Now() time.Time { 101 return time.Now() 102 } 103 104 // SystemClock implements Clock interface that uses time.Now(). 105 var 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. 109 func (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) 116 func (b *ExponentialBackOff) NextBackOff() time.Duration { 117 // Make sure we have not gone over the maximum elapsed time. 118 elapsed := b.GetElapsedTime() 119 next := getRandomValueFromInterval(b.RandomizationFactor, rand.Float64(), b.currentInterval) 120 b.incrementCurrentInterval() 121 if b.MaxElapsedTime != 0 && elapsed+next > b.MaxElapsedTime { 122 return b.Stop 123 } 124 return next 125 } 126 127 // GetElapsedTime returns the elapsed time since an ExponentialBackOff instance 128 // is created and is reset when Reset() is called. 129 // 130 // The elapsed time is computed using time.Now().UnixNano(). It is 131 // safe to call even while the backoff policy is used by a running 132 // ticker. 133 func (b *ExponentialBackOff) GetElapsedTime() time.Duration { 134 return b.Clock.Now().Sub(b.startTime) 135 } 136 137 // Increments the current interval by multiplying it with the multiplier. 138 func (b *ExponentialBackOff) incrementCurrentInterval() { 139 // Check for overflow, if overflow is detected set the current interval to the max interval. 140 if float64(b.currentInterval) >= float64(b.MaxInterval)/b.Multiplier { 141 b.currentInterval = b.MaxInterval 142 } else { 143 b.currentInterval = time.Duration(float64(b.currentInterval) * b.Multiplier) 144 } 145 } 146 147 // Returns a random value from the following interval: 148 // [currentInterval - randomizationFactor * currentInterval, currentInterval + randomizationFactor * currentInterval]. 149 func getRandomValueFromInterval(randomizationFactor, random float64, currentInterval time.Duration) time.Duration { 150 if randomizationFactor == 0 { 151 return currentInterval // make sure no randomness is used when randomizationFactor is 0. 152 } 153 var delta = randomizationFactor * float64(currentInterval) 154 var minInterval = float64(currentInterval) - delta 155 var maxInterval = float64(currentInterval) + delta 156 157 // Get a random value from the range [minInterval, maxInterval]. 158 // The formula used below has a +1 because if the minInterval is 1 and the maxInterval is 3 then 159 // we want a 33% chance for selecting either 1, 2 or 3. 160 return time.Duration(minInterval + (random * (maxInterval - minInterval + 1))) 161 }