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 returns Stop.
60	// It never stops if MaxElapsedTime == 0.
61	MaxElapsedTime time.Duration
62	Stop           time.Duration
63	Clock          Clock
64
65	currentInterval time.Duration
66	startTime       time.Time
67}
68
69// Clock is an interface that returns current time for BackOff.
70type Clock interface {
71	Now() time.Time
72}
73
74// Default values for ExponentialBackOff.
75const (
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.
84func NewExponentialBackOff() *ExponentialBackOff {
85	b := &ExponentialBackOff{
86		InitialInterval:     DefaultInitialInterval,
87		RandomizationFactor: DefaultRandomizationFactor,
88		Multiplier:          DefaultMultiplier,
89		MaxInterval:         DefaultMaxInterval,
90		MaxElapsedTime:      DefaultMaxElapsedTime,
91		Stop:                Stop,
92		Clock:               SystemClock,
93	}
94	b.Reset()
95	return b
96}
97
98type systemClock struct{}
99
100func (t systemClock) Now() time.Time {
101	return time.Now()
102}
103
104// SystemClock implements Clock interface that uses time.Now().
105var SystemClock = systemClock{}
106
107// Reset the interval back to the initial retry interval and restarts the timer.
108// Reset must be called before using b.
109func (b *ExponentialBackOff) Reset() {
110	b.currentInterval = b.InitialInterval
111	b.startTime = b.Clock.Now()
112}
113
114// NextBackOff calculates the next backoff interval using the formula:
115// 	Randomized interval = RetryInterval * (1 ± RandomizationFactor)
116func (b *ExponentialBackOff) NextBackOff() time.Duration {
117	// Make sure we have not gone over the maximum elapsed time.
118	if b.MaxElapsedTime != 0 && b.GetElapsedTime() > b.MaxElapsedTime {
119		return b.Stop
120	}
121	defer b.incrementCurrentInterval()
122	return getRandomValueFromInterval(b.RandomizationFactor, rand.Float64(), b.currentInterval)
123}
124
125// GetElapsedTime returns the elapsed time since an ExponentialBackOff instance
126// is created and is reset when Reset() is called.
127//
128// The elapsed time is computed using time.Now().UnixNano(). It is
129// safe to call even while the backoff policy is used by a running
130// ticker.
131func (b *ExponentialBackOff) GetElapsedTime() time.Duration {
132	return b.Clock.Now().Sub(b.startTime)
133}
134
135// Increments the current interval by multiplying it with the multiplier.
136func (b *ExponentialBackOff) incrementCurrentInterval() {
137	// Check for overflow, if overflow is detected set the current interval to the max interval.
138	if float64(b.currentInterval) >= float64(b.MaxInterval)/b.Multiplier {
139		b.currentInterval = b.MaxInterval
140	} else {
141		b.currentInterval = time.Duration(float64(b.currentInterval) * b.Multiplier)
142	}
143}
144
145// Returns a random value from the following interval:
146// 	[randomizationFactor * currentInterval, randomizationFactor * currentInterval].
147func getRandomValueFromInterval(randomizationFactor, random float64, currentInterval time.Duration) time.Duration {
148	var delta = randomizationFactor * float64(currentInterval)
149	var minInterval = float64(currentInterval) - delta
150	var maxInterval = float64(currentInterval) + delta
151
152	// Get a random value from the range [minInterval, maxInterval].
153	// The formula used below has a +1 because if the minInterval is 1 and the maxInterval is 3 then
154	// we want a 33% chance for selecting either 1, 2 or 3.
155	return time.Duration(minInterval + (random * (maxInterval - minInterval + 1)))
156}
157