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