Serge Bazanski | cc25bdf | 2018-10-25 14:02:58 +0200 | [diff] [blame] | 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 | random *rand.Rand |
| 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 | Clock: SystemClock, |
| 92 | random: rand.New(rand.NewSource(time.Now().UnixNano())), |
| 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 | func (b *ExponentialBackOff) Reset() { |
| 109 | b.currentInterval = b.InitialInterval |
| 110 | b.startTime = b.Clock.Now() |
| 111 | } |
| 112 | |
| 113 | // NextBackOff calculates the next backoff interval using the formula: |
| 114 | // Randomized interval = RetryInterval +/- (RandomizationFactor * RetryInterval) |
| 115 | func (b *ExponentialBackOff) NextBackOff() time.Duration { |
| 116 | // Make sure we have not gone over the maximum elapsed time. |
| 117 | if b.MaxElapsedTime != 0 && b.GetElapsedTime() > b.MaxElapsedTime { |
| 118 | return Stop |
| 119 | } |
| 120 | defer b.incrementCurrentInterval() |
| 121 | if b.random == nil { |
| 122 | b.random = rand.New(rand.NewSource(time.Now().UnixNano())) |
| 123 | } |
| 124 | return getRandomValueFromInterval(b.RandomizationFactor, b.random.Float64(), b.currentInterval) |
| 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 | // [randomizationFactor * currentInterval, randomizationFactor * currentInterval]. |
| 149 | func getRandomValueFromInterval(randomizationFactor, random float64, currentInterval time.Duration) time.Duration { |
| 150 | var delta = randomizationFactor * float64(currentInterval) |
| 151 | var minInterval = float64(currentInterval) - delta |
| 152 | var maxInterval = float64(currentInterval) + delta |
| 153 | |
| 154 | // Get a random value from the range [minInterval, maxInterval]. |
| 155 | // The formula used below has a +1 because if the minInterval is 1 and the maxInterval is 3 then |
| 156 | // we want a 33% chance for selecting either 1, 2 or 3. |
| 157 | return time.Duration(minInterval + (random * (maxInterval - minInterval + 1))) |
| 158 | } |