1package 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.
106func (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)
113func (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.
128func (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.
133func (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].
144func 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}
154