Truncated exponential backoff function example

retry.go

package main

import (
	crand "crypto/rand"
	"errors"
	"flag"
	"fmt"
	"math"
	"math/big"
	"math/rand"
	"os"
	"time"
)

var (
	numRetries uint = 20
	verbose         = false
)

const (
	// Fun fact: Ethernet's base retry duration is 51.2µs. Another fun fact:
	// You have to write fractional durations in terms of a smaller time unit
	// that can express the duration without a fraction.
	baseRetry = 51200 * time.Nanosecond
)

func main() {
	flag.BoolVar(&verbose, "v", verbose, "Print additional information")
	flag.UintVar(&numRetries, "retries", numRetries, "Maximum number of retries")
	flag.Parse()
	initRand()

	seq := mkTruncExpBackoffSeq(numRetries, baseRetry, 7, 0.1)
	for i := uint(0); i < numRetries+1; i++ {
		d, err := seq()
		if err != nil {
			fmt.Fprintln(os.Stderr, "error:", err)
			break
		}
		time.Sleep(d)
		fmt.Printf("retry %02d: slept: %s\n", i+1, d)
	}
}

func initRand() {
	seed, err := crand.Int(crand.Reader, big.NewInt(math.MaxInt64))
	if err != nil {
		panic("cannot seed RNG: " + err.Error())
	}
	rand.Seed(seed.Int64())
}

var ErrRetriesExhausted = errors.New("retry attempts exhausted")

// mkTruncBackoffSeq will return a function that returns truncated binary
// exponential backoff time durations, up to a maximum of maxRetries, with a
// base delay of base, with delays truncated at the truncateAt retry, and with
// a plus-or-minus jitter percatage of the calculated duration.
//
// See:
// https://en.wikipedia.org/wiki/Exponential_backoff#Binary_exponential_backoff_algorithm
func mkTruncExpBackoffSeq(
	maxRetries uint,
	base time.Duration,
	truncateAt uint,
	jitterFrac float64) func() (time.Duration, error) {

	var retries uint
	return func() (time.Duration, error) {
		if retries++; retries > maxRetries {
			return 0, ErrRetriesExhausted
		}
		exp := retries
		if exp > truncateAt {
			if verbose {
				fmt.Printf("(truncated to 2^%d slots (max %.0f) ",
					truncateAt, math.Pow(2, float64(truncateAt))-1)
			}
			exp = truncateAt
		}
		var (
			slot   = rand.Int63n(int64(math.Pow(2, float64(exp))))
			base   = time.Duration(slot) * base
			jitter = time.Duration((rand.Float64() - 0.5) * jitterFrac * float64(base))
			final  = base + jitter
		)
		if verbose {
			fmt.Printf("retry %02d: slot: %d base: %s jitter: %s final: %s\n",
				retries, slot, base, jitter, final)
		}
		return final, nil
	}
}