I made an exponential backoff that doesn't require setting InitialInterval

[Jonathan-Landeed]

I realized its very hard to set InitialInterval if you aren't really sure how fast your operation is going to fail. The 500ms default makes sense for network calls, but it might as well not exist for an operation that takes several minutes or more and is far too long for something that takes a few nanoseconds. If I lower InitialInterval too far, it won't become relevant until many retries have already occurred.

The sweet spot is when InitialInterval is about as long as it takes the operation to fail.

My first attempt was modifying Ticker to consume its own events if the operation loop isn't ready.

	select {
	case t.c <- tick:
	case <-t.stop:
		return nil
	default:
	}

Then I just set an extremely small InitialInterval and it worked decently well, but I didn't like how it spins its wheels right when it starts.

My second attempt was using an exponential backoff with currentInterval := (b.Multiplier - 1) * float64(time.Since(b.StartTime)), where b.Multiplier - 1 is the ratio of the sum of a geometric series to its next term when the number of terms approaches infinity. I liked the long-term behavior of this, but its inaccurate for the first few terms, resulting in very fast initial retries (immediate for Tickers if b.Multiplier is less than 2).

My current solution is to maintain both a count of the attempts and a startTime and use the exact formula:

	expMultiplier := math.Pow(b.Multiplier, float64(b.count))
	var currentInterval float64
	if expMultiplier == math.Inf(1) {
		currentInterval = (b.Multiplier - 1) * float64(time.Since(b.startTime))
	} else {
		currentInterval = expMultiplier * (b.Multiplier - 1) / (expMultiplier - 1) * float64(time.Since(b.startTime))
	}

This works quite well for operations of any duration, including operations that vary in duration. The wait between operations will trend towards an exponential of some average operation duration.

Would you be interested in a PR? I'm thinking I'd name it AdaptiveBackoff. I can also do a NonBlockingTicker if you'd like. Mentioned here #155

full example modifying ExponentialBackoff

package backoff

import (
	"math"
	"math/rand"
	"time"
)

/*
ExponentialBackOff is a backoff implementation that increases the backoff
period for each retry attempt using a randomization function that grows exponentially.

NextBackOff() is calculated using the following formula:

	randomized interval =
	    RetryInterval * (random value in range [1 - RandomizationFactor, 1 + RandomizationFactor])

In other words NextBackOff() will range between the randomization factor
percentage below and above the retry interval.

For example, given the following parameters:

	RetryInterval = 2
	RandomizationFactor = 0.5
	Multiplier = 2

the actual backoff period used in the next retry attempt will range between 1 and 3 seconds,
multiplied by the exponential, that is, between 2 and 6 seconds.

Note: MaxInterval caps the RetryInterval and not the randomized interval.

If the time elapsed since an ExponentialBackOff instance is created goes past the
MaxElapsedTime, then the method NextBackOff() starts returning backoff.Stop.

The elapsed time can be reset by calling Reset().

Example: Given the following default arguments, for 10 tries the sequence will be,
and assuming we go over the MaxElapsedTime on the 10th try:

	Request #  RetryInterval (seconds)  Randomized Interval (seconds)

	 1          0.5                     [0.25,   0.75]
	 2          0.75                    [0.375,  1.125]
	 3          1.125                   [0.562,  1.687]
	 4          1.687                   [0.8435, 2.53]
	 5          2.53                    [1.265,  3.795]
	 6          3.795                   [1.897,  5.692]
	 7          5.692                   [2.846,  8.538]
	 8          8.538                   [4.269, 12.807]
	 9         12.807                   [6.403, 19.210]
	10         19.210                   backoff.Stop

Note: Implementation is not thread-safe.
*/
type ExponentialBackOff struct {
	RandomizationFactor float64
	Multiplier          float64
	MaxInterval         time.Duration

	StartTime time.Time
	Count     int
}

// Default values for ExponentialBackOff.
const (
	DefaultRandomizationFactor = 0.5
	DefaultMultiplier          = 1.5
	DefaultMaxInterval         = 60 * time.Second
)

// NewExponentialBackOff creates an instance of ExponentialBackOff using default values.
func NewExponentialBackOff() *ExponentialBackOff {
	return &ExponentialBackOff{
		RandomizationFactor: DefaultRandomizationFactor,
		Multiplier:          DefaultMultiplier,
		MaxInterval:         DefaultMaxInterval,
		StartTime:           time.Now(),
		Count:               0,
	}
}

// Reset the interval back to the initial retry interval and restarts the timer.
// Reset must be called before using b.
func (b *ExponentialBackOff) Reset() {
	b.StartTime = time.Now()
	b.Count = 0
}

// NextBackOff calculates the next backoff interval using the formula:
//
//	Randomized interval = RetryInterval * (1 ± RandomizationFactor)
func (b *ExponentialBackOff) NextBackOff() time.Duration {
	if b.Count == 0 {
		b.Count++
		return time.Duration(0)
	}

	currentInterval := b.getCurrentInterval()
	next := getRandomValueFromInterval(0, rand.Float64(), currentInterval)
	b.Count++
	return next
}

// Returns the current interval using the formula:
//
//	RetryInterval = (Multiplier^Count * (Multiplier - 1)) / (Multiplier^Count - 1) * ElapsedTime
func (b *ExponentialBackOff) getCurrentInterval() float64 {
	// Use the full formula unless expMultiplier is approaching infinity.
	expMultiplier := math.Pow(b.Multiplier, float64(b.Count))
	var currentInterval float64
	if expMultiplier == math.Inf(1) {
		currentInterval = (b.Multiplier - 1) * float64(time.Since(b.StartTime))
	} else {
		currentInterval = expMultiplier * (b.Multiplier - 1) / (expMultiplier - 1) * float64(time.Since(b.StartTime))
	}

	// Check for overflow, if overflow is detected set the current interval to the max interval.
	if currentInterval > float64(b.MaxInterval) {
		return float64(b.MaxInterval)
	}
	return currentInterval
}

// Returns a random value from the following interval:
//
//	[currentInterval - randomizationFactor * currentInterval, currentInterval + randomizationFactor * currentInterval].
func getRandomValueFromInterval(randomizationFactor, random, currentInterval float64) time.Duration {
	if randomizationFactor == 0 {
		return time.Duration(currentInterval) // make sure no randomness is used when randomizationFactor is 0.
	}
	var delta = randomizationFactor * float64(currentInterval)
	var minInterval = float64(currentInterval) - delta
	var maxInterval = float64(currentInterval) + delta

	// Get a random value from the range [minInterval, maxInterval].
	// The formula used below has a +1 because if the minInterval is 1 and the maxInterval is 3 then
	// we want a 33% chance for selecting either 1, 2 or 3.
	return time.Duration(minInterval + (random * (maxInterval - minInterval + 1)))
}