exponential.go raw

   1  package backoff
   2  
   3  import (
   4  	"math/rand/v2"
   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  Example: Given the following default arguments, for 9 tries the sequence will be:
  32  
  33  	Request #  RetryInterval (seconds)  Randomized Interval (seconds)
  34  
  35  	 1          0.5                     [0.25,   0.75]
  36  	 2          0.75                    [0.375,  1.125]
  37  	 3          1.125                   [0.562,  1.687]
  38  	 4          1.687                   [0.8435, 2.53]
  39  	 5          2.53                    [1.265,  3.795]
  40  	 6          3.795                   [1.897,  5.692]
  41  	 7          5.692                   [2.846,  8.538]
  42  	 8          8.538                   [4.269, 12.807]
  43  	 9         12.807                   [6.403, 19.210]
  44  
  45  Note: Implementation is not thread-safe.
  46  */
  47  type ExponentialBackOff struct {
  48  	InitialInterval     time.Duration
  49  	RandomizationFactor float64
  50  	Multiplier          float64
  51  	MaxInterval         time.Duration
  52  
  53  	currentInterval time.Duration
  54  }
  55  
  56  // Default values for ExponentialBackOff.
  57  const (
  58  	DefaultInitialInterval     = 500 * time.Millisecond
  59  	DefaultRandomizationFactor = 0.5
  60  	DefaultMultiplier          = 1.5
  61  	DefaultMaxInterval         = 60 * time.Second
  62  )
  63  
  64  // NewExponentialBackOff creates an instance of ExponentialBackOff using default values.
  65  func NewExponentialBackOff() *ExponentialBackOff {
  66  	return &ExponentialBackOff{
  67  		InitialInterval:     DefaultInitialInterval,
  68  		RandomizationFactor: DefaultRandomizationFactor,
  69  		Multiplier:          DefaultMultiplier,
  70  		MaxInterval:         DefaultMaxInterval,
  71  	}
  72  }
  73  
  74  // Reset the interval back to the initial retry interval and restarts the timer.
  75  // Reset must be called before using b.
  76  func (b *ExponentialBackOff) Reset() {
  77  	b.currentInterval = b.InitialInterval
  78  }
  79  
  80  // NextBackOff calculates the next backoff interval using the formula:
  81  //
  82  //	Randomized interval = RetryInterval * (1 ± RandomizationFactor)
  83  func (b *ExponentialBackOff) NextBackOff() time.Duration {
  84  	if b.currentInterval == 0 {
  85  		b.currentInterval = b.InitialInterval
  86  	}
  87  
  88  	next := getRandomValueFromInterval(b.RandomizationFactor, rand.Float64(), b.currentInterval)
  89  	b.incrementCurrentInterval()
  90  	return next
  91  }
  92  
  93  // Increments the current interval by multiplying it with the multiplier.
  94  func (b *ExponentialBackOff) incrementCurrentInterval() {
  95  	// Check for overflow, if overflow is detected set the current interval to the max interval.
  96  	if float64(b.currentInterval) >= float64(b.MaxInterval)/b.Multiplier {
  97  		b.currentInterval = b.MaxInterval
  98  	} else {
  99  		b.currentInterval = time.Duration(float64(b.currentInterval) * b.Multiplier)
 100  	}
 101  }
 102  
 103  // Returns a random value from the following interval:
 104  //
 105  //	[currentInterval - randomizationFactor * currentInterval, currentInterval + randomizationFactor * currentInterval].
 106  func getRandomValueFromInterval(randomizationFactor, random float64, currentInterval time.Duration) time.Duration {
 107  	if randomizationFactor == 0 {
 108  		return currentInterval // make sure no randomness is used when randomizationFactor is 0.
 109  	}
 110  	var delta = randomizationFactor * float64(currentInterval)
 111  	var minInterval = float64(currentInterval) - delta
 112  	var maxInterval = float64(currentInterval) + delta
 113  
 114  	// Get a random value from the range [minInterval, maxInterval].
 115  	// The formula used below has a +1 because if the minInterval is 1 and the maxInterval is 3 then
 116  	// we want a 33% chance for selecting either 1, 2 or 3.
 117  	return time.Duration(minInterval + (random * (maxInterval - minInterval + 1)))
 118  }
 119