vendor/github.com/cenkalti/backoff/exponential.go

   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 }