README
¶
backoff
Backoff algorithms are used to space out repeated retries of the same block of code. By gradually decreasing the retry rate, backoff algorithms aim to avoid congestion. This Go backoff library provides a set of backoff algorithms well-known in the computer networks research community. These algorithms are acceptable for use in generalized computation. All algorithms use a uniform distribution of backoff times.
This library provides the following backoff algorithms:
ExponentialFibonacciMILDPLEBPFB
each with properties:
type <all backoff algorithms> struct {
Retries int
MaxRetries int
Delay time.Duration
Interval time.Duration // time.Second, time.Millisecond, etc.
Slots []time.Duration
}
all of which are based off a Backoff interface defined as:
type Backoff interface {
Next() bool
Retry(func() error) error // Surface the resulting error to the user.
Reset()
}
so you may define additional backoff algorithms of your choice.
Exponential Backoff
Gradually decrease the retry rate in an exponential manner with base 2. The algorithm is defined as n = 2^c - 1 where n is the backoff delay and c is the number of retries.
Example usage:
e := backoff.Exponential()
e.Interval = 1 * time.Millisecond
e.MaxRetries = 5
fooFunc := func() error {
// Do some work here
}
err := e.Retry(fooFunc)
e.Reset()
Fibonacci Backoff
Gradually decrease the retry rate using a fibonacci sequence. The algorithm is defined as n = fib(c - 1) + fib(c - 2); f(0) = 0, f(1) = 1; n >= 0 where n is the backoff delay and c is the retry slot.
f := backoff.Fibonacci()
f.Interval = 1 * time.Millisecond
f.MaxRetries = 5
fooFunc := func() error {
// Do some work here
}
err := f.Retry(fooFunc)
f.Reset()
Additionally, the FibonacciBackoff struct exposes its delay slots in the form of a slice of time.Duration.
log.Printf("%+v", f.Slots)
MILD - Multiplicative Increase and Linear Decrease
Gradually increase the retry delay by a factor of 1.5. However, upon successful transmission, decrement the index of the delay slots so that the current delay is the previous value. The retry mechanism thus will not result in a success until the slot index has been decremented to 0. Conversely, the retry mechanism will fail as usual, upon reaching the failed maximum number of retries. The algorithm is defined as follows: n = min(1.5, n, len(slots)) upon failure; n = max(slots(c) - 1, 0) upon success; n(0) = 0, n(1) = 1 where n is the backoff delay, c is the retry slot, and slots is an array of retry delays.
f := backoff.MILD()
f.Interval = 1 * time.Millisecond
f.MaxRetries = 5
fooFunc := func() error {
// Do some work here
}
err := f.Retry(fooFunc)
f.Reset()
Author
Jeff Chao, @thejeffchao, http://thejeffchao.com
Documentation
¶
Overview ¶
Package backoff is a utility for repeatedly retrying functions with support from a variety of backoff algorithms.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Backoff ¶
type Backoff interface {
// Compute and return the next backoff delay.
Next() bool
// Retry a function until an error or backoff delay condition is met.
Retry(func() error) error
// Reset the backoff delay to its initial value.
Reset()
}
Backoff is an interface for any type that can implement a backoff algorithm and maintain its current state.
type ExponentialBackoff ¶
type ExponentialBackoff struct {
Retries int
MaxRetries int
Delay time.Duration
Interval time.Duration // time.Second, time.Millisecond, etc.
}
ExponentialBackoff implements the Backoff interface. It represents an instance that keeps track of retries, delays, and intervals for the fibonacci backoff algorithm. This struct is instantiated by the Exponential() function.
func Exponential ¶
func Exponential() *ExponentialBackoff
Exponential creates a new instance of ExponentialBackoff.
func (*ExponentialBackoff) Next ¶
func (e *ExponentialBackoff) Next() bool
Next gets the next backoff delay. This method will increment the retries and check if the maximum number of retries has been met. If this condition is satisfied, then the function will return. Otherwise, the next backoff delay will be computed.
The exponential backoff delay is computed as follows: `n = 2^c - 1` where `n` is the backoff delay and `c` is the number of retries.
Example, given a 1 second interval:
Retry # Backoff delay (in seconds) 0 0 1 1 2 3 3 7 4 15 5 31
func (*ExponentialBackoff) Reset ¶
func (e *ExponentialBackoff) Reset()
Reset will reset the retry count and the backoff delay back to its initial state.
func (*ExponentialBackoff) Retry ¶
func (e *ExponentialBackoff) Retry(f func() error) error
Retry will retry a function until the maximum number of retries is met. This method expects the function `f` to return an error. If the failure condition is met, this method will surface the error outputted from `f`, otherwise nil will be returned as normal.
type FibonacciBackoff ¶
type FibonacciBackoff struct {
Retries int
MaxRetries int
Delay time.Duration
Interval time.Duration // time.Second, time.Millisecond, etc.
Slots []time.Duration
}
FibonacciBackoff implements the Backoff interface. It represents an instance that keeps track of retries, delays, and intervals for the fibonacci backoff algorithm. This struct is instantiated by the Fibonacci() function.
func Fibonacci ¶
func Fibonacci() *FibonacciBackoff
Fibonacci creates a new instance of FibonacciBackoff.
func (*FibonacciBackoff) Next ¶
func (fb *FibonacciBackoff) Next() bool
Next gets the next backoff delay. This method will increment the retries and check if the maximum number of retries has been met. If this condition is satisfied, then the function will return. Otherwise, the next backoff delay will be computed.
The fibonacci backoff delay is computed as follows: `n = fib(c - 1) + fib(c - 2); f(0) = 0, f(1) = 1; n >= 0.` where `n` is the backoff delay and `c` is the retry slot.
This method maintains a slice of time.Duration to save on fibonacci computation.
Example, given a 1 second interval:
Retry # Backoff delay (in seconds) 1 0 2 1 3 1 4 2 5 3 6 5 7 8 8 13
func (*FibonacciBackoff) Reset ¶
func (fb *FibonacciBackoff) Reset()
Reset will reset the retry count, the backoff delay, and backoff slots back to its initial state.
func (*FibonacciBackoff) Retry ¶
func (fb *FibonacciBackoff) Retry(f func() error) error
Retry will retry a function until the maximum number of retries is met. This method expects the function `f` to return an error. If the failure condition is met, this method will surface the error outputted from `f`, otherwise nil will be returned as normal.
type MILDBackoff ¶
type MILDBackoff struct {
Retries int
MaxRetries int
Delay time.Duration
Interval time.Duration // time.Second, time.Millisecond, etc.
Slots []time.Duration
}
MILDBackoff implements the Backoff interface. It represents an instance that keeps track of retries, delays, and intervals for the fibonacci backoff algorithm. This struct is instantiated by the MILD() function.
func (*MILDBackoff) Next ¶
func (m *MILDBackoff) Next() bool
Next gets the next backoff delay. This method will increment the retries and check if the maximum number of retries has been met. If this condition is satisfied, then the function will return. Otherwise, the next backoff delay will be computed.
The MILD backoff delay is computed as follows: `n = min(1.5 * n, len(slots)) upon failure; n = max(slots(c) - 1, 0) upon success; n(0) = 0, n(1) = 1` where `n` is the backoff delay, `c` is the retry slot, and `slots` is an array of retry delays.
This means a method must repeatedly succeed until `slots` is empty for the overall backoff mechanism to terminate. Conversely, a repeated number of failures until the maximum number of retries will result in a failure.
Example, given a 1 second interval, with max retries of 5:
Retry # Backoff delay (in seconds) success/fail 1 1 fail 2 1.5 fail 3 1 success 4 1.5 fail 5 2.25 fail Retry # Backoff delay (in seconds) success/fail 1 1 fail 2 1.5 fail 3 1 success 4 0 success 5 - success
func (*MILDBackoff) Reset ¶
func (m *MILDBackoff) Reset()
Reset will reset the retry count, the backoff delay, and backoff slots back to its initial state.
func (*MILDBackoff) Retry ¶
func (m *MILDBackoff) Retry(f func() error) error
Retry will retry a function until the maximum number of retries is met. This method expects the function `f` to return an error. If the failure condition is met, this method will surface the error outputted from `f`, otherwise nil will be returned as normal.
Source Files