| 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 stops. |
| 60 |
// It never stops if MaxElapsedTime == 0. |
| 61 |
MaxElapsedTime time.Duration |
| 62 |
Clock Clock |
| 63 |
|
| 64 |
currentInterval time.Duration |
| 65 |
startTime time.Time |
| 66 |
} |
| 67 |
|
| 68 |
// Clock is an interface that returns current time for BackOff. |
| 69 |
type Clock interface { |
| 70 |
Now() time.Time |
| 71 |
} |
| 72 |
|
| 73 |
// Default values for ExponentialBackOff. |
| 74 |
const ( |
| 75 |
DefaultInitialInterval = 500 * time.Millisecond |
| 76 |
DefaultRandomizationFactor = 0.5 |
| 77 |
DefaultMultiplier = 1.5 |
| 78 |
DefaultMaxInterval = 60 * time.Second |
| 79 |
DefaultMaxElapsedTime = 15 * time.Minute |
| 80 |
) |
| 81 |
|
| 82 |
// NewExponentialBackOff creates an instance of ExponentialBackOff using default values. |
| 83 |
func NewExponentialBackOff() *ExponentialBackOff { |
| 84 |
b := &ExponentialBackOff{ |
| 85 |
InitialInterval: DefaultInitialInterval, |
| 86 |
RandomizationFactor: DefaultRandomizationFactor, |
| 87 |
Multiplier: DefaultMultiplier, |
| 88 |
MaxInterval: DefaultMaxInterval, |
| 89 |
MaxElapsedTime: DefaultMaxElapsedTime, |
| 90 |
Clock: SystemClock, |
| 91 |
} |
| 92 |
b.Reset() |
| 93 |
return b |
| 94 |
} |
| 95 |
|
| 96 |
type systemClock struct{} |
| 97 |
|
| 98 |
func (t systemClock) Now() time.Time { |
| 99 |
return time.Now() |
| 100 |
} |
| 101 |
|
| 102 |
// SystemClock implements Clock interface that uses time.Now(). |
| 103 |
var SystemClock = systemClock{} |
| 104 |
|
| 105 |
// Reset the interval back to the initial retry interval and restarts the timer. |
| 106 |
func (b *ExponentialBackOff) Reset() { |
| 107 |
b.currentInterval = b.InitialInterval |
| 108 |
b.startTime = b.Clock.Now() |
| 109 |
} |
| 110 |
|
| 111 |
// NextBackOff calculates the next backoff interval using the formula: |
| 112 |
// Randomized interval = RetryInterval +/- (RandomizationFactor * RetryInterval) |
| 113 |
func (b *ExponentialBackOff) NextBackOff() time.Duration { |
| 114 |
// Make sure we have not gone over the maximum elapsed time. |
| 115 |
if b.MaxElapsedTime != 0 && b.GetElapsedTime() > b.MaxElapsedTime { |
| 116 |
return Stop |
| 117 |
} |
| 118 |
defer b.incrementCurrentInterval() |
| 119 |
return getRandomValueFromInterval(b.RandomizationFactor, rand.Float64(), b.currentInterval) |
| 120 |
} |
| 121 |
|
| 122 |
// GetElapsedTime returns the elapsed time since an ExponentialBackOff instance |
| 123 |
// is created and is reset when Reset() is called. |
| 124 |
// |
| 125 |
// The elapsed time is computed using time.Now().UnixNano(). It is |
| 126 |
// safe to call even while the backoff policy is used by a running |
| 127 |
// ticker. |
| 128 |
func (b *ExponentialBackOff) GetElapsedTime() time.Duration { |
| 129 |
return b.Clock.Now().Sub(b.startTime) |
| 130 |
} |
| 131 |
|
| 132 |
// Increments the current interval by multiplying it with the multiplier. |
| 133 |
func (b *ExponentialBackOff) incrementCurrentInterval() { |
| 134 |
// Check for overflow, if overflow is detected set the current interval to the max interval. |
| 135 |
if float64(b.currentInterval) >= float64(b.MaxInterval)/b.Multiplier { |
| 136 |
b.currentInterval = b.MaxInterval |
| 137 |
} else { |
| 138 |
b.currentInterval = time.Duration(float64(b.currentInterval) * b.Multiplier) |
| 139 |
} |
| 140 |
} |
| 141 |
|
| 142 |
// Returns a random value from the following interval: |
| 143 |
// [randomizationFactor * currentInterval, randomizationFactor * currentInterval]. |
| 144 |
func getRandomValueFromInterval(randomizationFactor, random float64, currentInterval time.Duration) time.Duration { |
| 145 |
var delta = randomizationFactor * float64(currentInterval) |
| 146 |
var minInterval = float64(currentInterval) - delta |
| 147 |
var maxInterval = float64(currentInterval) + delta |
| 148 |
|
| 149 |
// Get a random value from the range [minInterval, maxInterval]. |
| 150 |
// The formula used below has a +1 because if the minInterval is 1 and the maxInterval is 3 then |
| 151 |
// we want a 33% chance for selecting either 1, 2 or 3. |
| 152 |
return time.Duration(minInterval + (random * (maxInterval - minInterval + 1))) |
| 153 |
} |