1package backoff
2
3import (
4	"math/rand"
5	"time"
6)
7
8/*
9ExponentialBackOff is an implementation of BackOff that increases the back off
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	    retry_interval * (random value in range [1 - randomization_factor, 1 + randomization_factor])
16
17In other words NextBackOff() will range between the randomization factor
18percentage below and above the retry interval. For example, using 2 seconds as the base retry
19interval and 0.5 as the randomization factor, the actual back off period used in the next retry
20attempt will be between 1 and 3 seconds.
21
22Note: max_interval caps the retry_interval and not the randomized_interval.
23
24If the time elapsed since an ExponentialBackOff instance is created goes past the
25max_elapsed_time then the method NextBackOff() starts returning backoff.Stop.
26The elapsed time can be reset by calling Reset().
27
28Example: The default retry_interval is .5 seconds, default randomization_factor is 0.5, default
29multiplier is 1.5 and the default max_interval is 1 minute. For 10 tries the sequence will be
30(values in seconds) and assuming we go over the max_elapsed_time on the 10th try:
31
32	request#     retry_interval     randomized_interval
33
34	1             0.5                [0.25,   0.75]
35	2             0.75               [0.375,  1.125]
36	3             1.125              [0.562,  1.687]
37	4             1.687              [0.8435, 2.53]
38	5             2.53               [1.265,  3.795]
39	6             3.795              [1.897,  5.692]
40	7             5.692              [2.846,  8.538]
41	8             8.538              [4.269, 12.807]
42	9            12.807              [6.403, 19.210]
43	10           19.210              backoff.Stop
44
45Implementation is not thread-safe.
46*/
47type ExponentialBackOff struct {
48	InitialInterval     time.Duration
49	RandomizationFactor float64
50	Multiplier          float64
51	MaxInterval         time.Duration
52	// After MaxElapsedTime the ExponentialBackOff stops.
53	// It never stops if MaxElapsedTime == 0.
54	MaxElapsedTime time.Duration
55	Clock          Clock
56
57	currentInterval time.Duration
58	startTime       time.Time
59}
60
61// Clock is an interface that returns current time for BackOff.
62type Clock interface {
63	Now() time.Time
64}
65
66// Default values for ExponentialBackOff.
67const (
68	DefaultInitialInterval     = 500 * time.Millisecond
69	DefaultRandomizationFactor = 0.5
70	DefaultMultiplier          = 1.5
71	DefaultMaxInterval         = 60 * time.Second
72	DefaultMaxElapsedTime      = 15 * time.Minute
73)
74
75// NewExponentialBackOff creates an instance of ExponentialBackOff using default values.
76func NewExponentialBackOff() *ExponentialBackOff {
77	return &ExponentialBackOff{
78		InitialInterval:     DefaultInitialInterval,
79		RandomizationFactor: DefaultRandomizationFactor,
80		Multiplier:          DefaultMultiplier,
81		MaxInterval:         DefaultMaxInterval,
82		MaxElapsedTime:      DefaultMaxElapsedTime,
83		Clock:               SystemClock,
84	}
85}
86
87type systemClock struct{}
88
89func (t systemClock) Now() time.Time {
90	return time.Now()
91}
92
93// SystemClock implements Clock interface that uses time.Now().
94var SystemClock = systemClock{}
95
96// Reset the interval back to the initial retry interval and restarts the timer.
97func (b *ExponentialBackOff) Reset() {
98	b.currentInterval = b.InitialInterval
99	b.startTime = b.Clock.Now()
100}
101
102// NextBackOff calculates the next back off interval using the formula:
103// 	randomized_interval = retry_interval +/- (randomization_factor * retry_interval)
104func (b *ExponentialBackOff) NextBackOff() time.Duration {
105	// Make sure we have not gone over the maximum elapsed time.
106	if b.MaxElapsedTime != 0 && b.GetElapsedTime() > b.MaxElapsedTime {
107		return Stop
108	}
109	defer b.incrementCurrentInterval()
110	return getRandomValueFromInterval(b.RandomizationFactor, rand.Float64(), b.currentInterval)
111}
112
113// GetElapsedTime returns the elapsed time since an ExponentialBackOff instance
114// is created and is reset when Reset() is called.
115//
116// The elapsed time is computed using time.Now().UnixNano().
117func (b *ExponentialBackOff) GetElapsedTime() time.Duration {
118	return b.Clock.Now().Sub(b.startTime)
119}
120
121// Increments the current interval by multiplying it with the multiplier.
122func (b *ExponentialBackOff) incrementCurrentInterval() {
123	// Check for overflow, if overflow is detected set the current interval to the max interval.
124	if float64(b.currentInterval) >= float64(b.MaxInterval)/b.Multiplier {
125		b.currentInterval = b.MaxInterval
126	} else {
127		b.currentInterval = time.Duration(float64(b.currentInterval) * b.Multiplier)
128	}
129}
130
131// Returns a random value from the interval:
132// 	[randomizationFactor * currentInterval, randomizationFactor * currentInterval].
133func getRandomValueFromInterval(randomizationFactor, random float64, currentInterval time.Duration) time.Duration {
134	var delta = randomizationFactor * float64(currentInterval)
135	var minInterval = float64(currentInterval) - delta
136	var maxInterval = float64(currentInterval) + delta
137	// Get a random value from the range [minInterval, maxInterval].
138	// The formula used below has a +1 because if the minInterval is 1 and the maxInterval is 3 then
139	// we want a 33% chance for selecting either 1, 2 or 3.
140	return time.Duration(minInterval + (random * (maxInterval - minInterval + 1)))
141}
142