├── .travis.yml
├── .github
    └── workflows
    │   └── semgrep.yml
├── LICENSE
├── README.md
├── backoff_test.go
└── backoff.go


/.travis.yml:
--------------------------------------------------------------------------------
 1 | sudo: false
 2 | language: go
 3 | go:
 4 |   - 1.6
 5 |   - 1.7
 6 |   - tip
 7 | 
 8 | before_script:
 9 |   - go get github.com/GeertJohan/fgt
10 |   - go get github.com/golang/lint/golint
11 |   - go get golang.org/x/tools/cmd/goimports
12 |   - go get honnef.co/go/staticcheck/cmd/staticcheck
13 | 
14 | script:
15 |   - find . -name \*.go | xargs fgt goimports -l
16 |   - fgt go vet ./...
17 |   - fgt golint ./...
18 |   - fgt staticcheck ./...
19 |   - go test ./...
20 | 
21 | notifications:
22 |   email:
23 |     recipients:
24 |     - kyle@cloudflare.com
25 | 


--------------------------------------------------------------------------------
/.github/workflows/semgrep.yml:
--------------------------------------------------------------------------------
 1 | 
 2 | on:
 3 |   pull_request: {}
 4 |   workflow_dispatch: {}
 5 |   push: 
 6 |     branches:
 7 |       - main
 8 |       - master
 9 |   schedule:
10 |     - cron: '0 0 * * *'
11 | name: Semgrep config
12 | jobs:
13 |   semgrep:
14 |     name: semgrep/ci
15 |     runs-on: ubuntu-20.04
16 |     env:
17 |       SEMGREP_APP_TOKEN: ${{ secrets.SEMGREP_APP_TOKEN }}
18 |       SEMGREP_URL: https://cloudflare.semgrep.dev
19 |       SEMGREP_APP_URL: https://cloudflare.semgrep.dev
20 |       SEMGREP_VERSION_CHECK_URL: https://cloudflare.semgrep.dev/api/check-version
21 |     container:
22 |       image: returntocorp/semgrep
23 |     steps:
24 |       - uses: actions/checkout@v3
25 |       - run: semgrep ci
26 | 


--------------------------------------------------------------------------------
/LICENSE:
--------------------------------------------------------------------------------
 1 | Copyright (c) 2016 CloudFlare Inc.
 2 | 
 3 | Redistribution and use in source and binary forms, with or without
 4 | modification, are permitted provided that the following conditions
 5 | are met:
 6 | 
 7 | Redistributions of source code must retain the above copyright notice,
 8 | this list of conditions and the following disclaimer.
 9 | 
10 | Redistributions in binary form must reproduce the above copyright notice,
11 | this list of conditions and the following disclaimer in the documentation
12 | and/or other materials provided with the distribution.
13 | 
14 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
18 | HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
19 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
20 | TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 | PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
22 | LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 | NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 | 


--------------------------------------------------------------------------------
/README.md:
--------------------------------------------------------------------------------
 1 | # backoff
 2 | ## Go implementation of "Exponential Backoff And Jitter"
 3 | 
 4 | This package implements the backoff strategy described in the AWS
 5 | Architecture Blog article
 6 | ["Exponential Backoff And Jitter"](http://www.awsarchitectureblog.com/2015/03/backoff.html). Essentially,
 7 | the backoff has an interval `time.Duration`; the *n<sup>th</sup>* call
 8 | to backoff will return an a `time.Duration` that is *2 <sup>n</sup> *
 9 | interval*. If jitter is enabled (which is the default behaviour), the
10 | duration is a random value between 0 and *2 <sup>n</sup> * interval*.
11 | The backoff is configured with a maximum duration that will not be
12 | exceeded; e.g., by default, the longest duration returned is
13 | `backoff.DefaultMaxDuration`.
14 | 
15 | ## Usage
16 | 
17 | A `Backoff` is initialised with a call to `New`. Using zero values
18 | causes it to use `DefaultMaxDuration` and `DefaultInterval` as the
19 | maximum duration and interval.
20 | 
21 | ```
22 | package something
23 | 
24 | import "github.com/cloudflare/backoff"
25 | 
26 | func retryable() {
27 |         b := backoff.New(0, 0)
28 |         for {
29 |                 err := someOperation()
30 |                 if err == nil {
31 |                     break
32 |                 }
33 | 
34 |                 log.Printf("error in someOperation: %v", err)
35 |                 <-time.After(b.Duration())
36 |         }
37 | 
38 |         log.Printf("succeeded after %d tries", b.Tries()+1)
39 |         b.Reset()
40 | }
41 | ```
42 | 
43 | It can also be used to rate limit code that should retry infinitely, but which does not
44 | use `Backoff` itself.
45 | 
46 | ```
47 | package something
48 | 
49 | import (
50 |     "time"
51 | 
52 |     "github.com/cloudflare/backoff"
53 | )
54 | 
55 | func retryable() {
56 |         b := backoff.New(0, 0)
57 |         b.SetDecay(30 * time.Second)
58 | 
59 |         for {
60 |                 // b will reset if someOperation returns later than
61 |                 // the last call to b.Duration() + 30s.
62 |                 err := someOperation()
63 |                 if err == nil {
64 |                     break
65 |                 }
66 | 
67 |                 log.Printf("error in someOperation: %v", err)
68 |                 <-time.After(b.Duration())
69 |         }
70 | }
71 | ```
72 | 
73 | ## Tunables
74 | 
75 | * `NewWithoutJitter` creates a Backoff that doesn't use jitter.
76 | 
77 | The default behaviour is controlled by two variables:
78 | 
79 | * `DefaultInterval` sets the base interval for backoffs created with
80 |   the zero `time.Duration` value in the `Interval` field.
81 | * `DefaultMaxDuration` sets the maximum duration for backoffs created
82 |   with the zero `time.Duration` value in the `MaxDuration` field.
83 | 
84 | 


--------------------------------------------------------------------------------
/backoff_test.go:
--------------------------------------------------------------------------------
  1 | package backoff
  2 | 
  3 | import (
  4 | 	"fmt"
  5 | 	"math"
  6 | 	"testing"
  7 | 	"time"
  8 | )
  9 | 
 10 | // If given New with 0's and no jitter, ensure that certain invariants are met:
 11 | //
 12 | //   - the default max duration and interval should be used
 13 | //   - noJitter should be true
 14 | //   - the RNG should not be initialised
 15 | //   - the first duration should be equal to the default interval
 16 | func TestDefaults(t *testing.T) {
 17 | 	b := NewWithoutJitter(0, 0)
 18 | 
 19 | 	if b.maxDuration != DefaultMaxDuration {
 20 | 		t.Fatalf("expected new backoff to use the default max duration (%s), but have %s", DefaultMaxDuration, b.maxDuration)
 21 | 	}
 22 | 
 23 | 	if b.interval != DefaultInterval {
 24 | 		t.Fatalf("exepcted new backoff to use the default interval (%s), but have %s", DefaultInterval, b.interval)
 25 | 	}
 26 | 
 27 | 	if b.noJitter != true {
 28 | 		t.Fatal("backoff should have been initialised without jitter")
 29 | 	}
 30 | 
 31 | 	dur := b.Duration()
 32 | 	if dur != DefaultInterval {
 33 | 		t.Fatalf("expected first duration to be %s, have %s", DefaultInterval, dur)
 34 | 	}
 35 | }
 36 | 
 37 | // Given a zero-value initialised Backoff, it should be transparently
 38 | // setup.
 39 | func TestSetup(t *testing.T) {
 40 | 	b := new(Backoff)
 41 | 	dur := b.Duration()
 42 | 	if dur < 0 || dur > (5*time.Minute) {
 43 | 		t.Fatalf("want duration between 0 and 5 minutes, have %s", dur)
 44 | 	}
 45 | }
 46 | 
 47 | // Ensure that tries incremenets as expected.
 48 | func TestTries(t *testing.T) {
 49 | 	b := NewWithoutJitter(5, 1)
 50 | 
 51 | 	for i := uint64(0); i < 3; i++ {
 52 | 		if b.n != i {
 53 | 			t.Fatalf("want tries=%d, have tries=%d", i, b.n)
 54 | 		}
 55 | 
 56 | 		pow := 1 << i
 57 | 		expected := time.Duration(pow)
 58 | 		dur := b.Duration()
 59 | 		if dur != expected {
 60 | 			t.Fatalf("want duration=%d, have duration=%d at i=%d", expected, dur, i)
 61 | 		}
 62 | 	}
 63 | 
 64 | 	for i := uint(3); i < 5; i++ {
 65 | 		dur := b.Duration()
 66 | 		if dur != 5 {
 67 | 			t.Fatalf("want duration=5, have %d at i=%d", dur, i)
 68 | 		}
 69 | 	}
 70 | }
 71 | 
 72 | // Ensure that a call to Reset will actually reset the Backoff.
 73 | func TestReset(t *testing.T) {
 74 | 	const iter = 10
 75 | 	b := New(1000, 1)
 76 | 	for i := 0; i < iter; i++ {
 77 | 		_ = b.Duration()
 78 | 	}
 79 | 
 80 | 	if b.n != iter {
 81 | 		t.Fatalf("expected tries=%d, have tries=%d", iter, b.n)
 82 | 	}
 83 | 
 84 | 	b.Reset()
 85 | 	if b.n != 0 {
 86 | 		t.Fatalf("expected tries=0 after reset, have tries=%d", b.n)
 87 | 	}
 88 | }
 89 | 
 90 | const decay = 5 * time.Millisecond
 91 | const max = 10 * time.Millisecond
 92 | const interval = time.Millisecond
 93 | 
 94 | func TestDecay(t *testing.T) {
 95 | 	const iter = 10
 96 | 
 97 | 	b := NewWithoutJitter(max, 1)
 98 | 	b.SetDecay(decay)
 99 | 
100 | 	var backoff time.Duration
101 | 	for i := 0; i < iter; i++ {
102 | 		backoff = b.Duration()
103 | 	}
104 | 
105 | 	if b.n != iter {
106 | 		t.Fatalf("expected tries=%d, have tries=%d", iter, b.n)
107 | 	}
108 | 
109 | 	// Don't decay below backoff
110 | 	b.lastTry = time.Now().Add(-backoff + 1)
111 | 	backoff = b.Duration()
112 | 	if b.n != iter+1 {
113 | 		t.Fatalf("expected tries=%d, have tries=%d", iter+1, b.n)
114 | 	}
115 | 
116 | 	// Reset after backoff + decay
117 | 	b.lastTry = time.Now().Add(-backoff - decay)
118 | 	b.Duration()
119 | 	if b.n != 1 {
120 | 		t.Fatalf("expected tries=%d, have tries=%d", 1, b.n)
121 | 	}
122 | }
123 | 
124 | // Ensure that decay works even if the retry counter is saturated.
125 | func TestDecaySaturation(t *testing.T) {
126 | 	b := NewWithoutJitter(1<<2, 1)
127 | 	b.SetDecay(decay)
128 | 
129 | 	var duration time.Duration
130 | 	for i := 0; i <= 2; i++ {
131 | 		duration = b.Duration()
132 | 	}
133 | 
134 | 	if duration != 1<<2 {
135 | 		t.Fatalf("expected duration=%v, have duration=%v", 1<<2, duration)
136 | 	}
137 | 
138 | 	b.lastTry = time.Now().Add(-duration - decay)
139 | 	b.n = math.MaxUint64
140 | 
141 | 	duration = b.Duration()
142 | 	if duration != 1 {
143 | 		t.Errorf("expected duration=%v, have duration=%v", 1, duration)
144 | 	}
145 | }
146 | 
147 | func ExampleBackoff_SetDecay() {
148 | 	b := NewWithoutJitter(max, interval)
149 | 	b.SetDecay(decay)
150 | 
151 | 	// try 0
152 | 	fmt.Println(b.Duration())
153 | 
154 | 	// try 1
155 | 	fmt.Println(b.Duration())
156 | 
157 | 	// try 2
158 | 	duration := b.Duration()
159 | 	fmt.Println(duration)
160 | 
161 | 	// try 3, below decay
162 | 	time.Sleep(duration)
163 | 	duration = b.Duration()
164 | 	fmt.Println(duration)
165 | 
166 | 	// try 4, resets
167 | 	time.Sleep(duration + decay)
168 | 	fmt.Println(b.Duration())
169 | 
170 | 	// Output: 1ms
171 | 	// 2ms
172 | 	// 4ms
173 | 	// 8ms
174 | 	// 1ms
175 | }
176 | 


--------------------------------------------------------------------------------
/backoff.go:
--------------------------------------------------------------------------------
  1 | // Package backoff contains an implementation of an intelligent backoff
  2 | // strategy. It is based on the approach in the AWS architecture blog
  3 | // article titled "Exponential Backoff And Jitter", which is found at
  4 | // http://www.awsarchitectureblog.com/2015/03/backoff.html.
  5 | //
  6 | // Essentially, the backoff has an interval `time.Duration`; the nth
  7 | // call to backoff will return a `time.Duration` that is 2^n *
  8 | // interval. If jitter is enabled (which is the default behaviour),
  9 | // the duration is a random value between 0 and 2^n * interval.  The
 10 | // backoff is configured with a maximum duration that will not be
 11 | // exceeded.
 12 | //
 13 | // The `New` function will attempt to use the system's cryptographic
 14 | // random number generator to seed a Go math/rand random number
 15 | // source. If this fails, the package will panic on startup.
 16 | package backoff
 17 | 
 18 | import (
 19 | 	"crypto/rand"
 20 | 	"encoding/binary"
 21 | 	"io"
 22 | 	"math"
 23 | 	mrand "math/rand"
 24 | 	"sync"
 25 | 	"time"
 26 | )
 27 | 
 28 | var prngMu sync.Mutex
 29 | var prng *mrand.Rand
 30 | 
 31 | // DefaultInterval is used when a Backoff is initialised with a
 32 | // zero-value Interval.
 33 | var DefaultInterval = 5 * time.Minute
 34 | 
 35 | // DefaultMaxDuration is maximum amount of time that the backoff will
 36 | // delay for.
 37 | var DefaultMaxDuration = 6 * time.Hour
 38 | 
 39 | // A Backoff contains the information needed to intelligently backoff
 40 | // and retry operations using an exponential backoff algorithm. It should
 41 | // be initialised with a call to `New`.
 42 | //
 43 | // Only use a Backoff from a single goroutine, it is not safe for concurrent
 44 | // access.
 45 | type Backoff struct {
 46 | 	// maxDuration is the largest possible duration that can be
 47 | 	// returned from a call to Duration.
 48 | 	maxDuration time.Duration
 49 | 
 50 | 	// interval controls the time step for backing off.
 51 | 	interval time.Duration
 52 | 
 53 | 	// noJitter controls whether to use the "Full Jitter"
 54 | 	// improvement to attempt to smooth out spikes in a high
 55 | 	// contention scenario. If noJitter is set to true, no
 56 | 	// jitter will be introduced.
 57 | 	noJitter bool
 58 | 
 59 | 	// decay controls the decay of n. If it is non-zero, n is
 60 | 	// reset if more than the last backoff + decay has elapsed since
 61 | 	// the last try.
 62 | 	decay time.Duration
 63 | 
 64 | 	n       uint64
 65 | 	lastTry time.Time
 66 | }
 67 | 
 68 | // New creates a new backoff with the specified max duration and
 69 | // interval. Zero values may be used to use the default values.
 70 | //
 71 | // Panics if either max or interval is negative.
 72 | func New(max time.Duration, interval time.Duration) *Backoff {
 73 | 	if max < 0 || interval < 0 {
 74 | 		panic("backoff: max or interval is negative")
 75 | 	}
 76 | 
 77 | 	b := &Backoff{
 78 | 		maxDuration: max,
 79 | 		interval:    interval,
 80 | 	}
 81 | 	b.setup()
 82 | 	return b
 83 | }
 84 | 
 85 | // NewWithoutJitter works similarly to New, except that the created
 86 | // Backoff will not use jitter.
 87 | func NewWithoutJitter(max time.Duration, interval time.Duration) *Backoff {
 88 | 	b := New(max, interval)
 89 | 	b.noJitter = true
 90 | 	return b
 91 | }
 92 | 
 93 | func init() {
 94 | 	var buf [8]byte
 95 | 	var n int64
 96 | 
 97 | 	_, err := io.ReadFull(rand.Reader, buf[:])
 98 | 	if err != nil {
 99 | 		panic(err.Error())
100 | 	}
101 | 
102 | 	n = int64(binary.LittleEndian.Uint64(buf[:]))
103 | 
104 | 	src := mrand.NewSource(n)
105 | 	prng = mrand.New(src)
106 | }
107 | 
108 | func (b *Backoff) setup() {
109 | 	if b.interval == 0 {
110 | 		b.interval = DefaultInterval
111 | 	}
112 | 
113 | 	if b.maxDuration == 0 {
114 | 		b.maxDuration = DefaultMaxDuration
115 | 	}
116 | }
117 | 
118 | // Duration returns a time.Duration appropriate for the backoff,
119 | // incrementing the attempt counter.
120 | func (b *Backoff) Duration() time.Duration {
121 | 	b.setup()
122 | 
123 | 	b.decayN()
124 | 
125 | 	t := b.duration(b.n)
126 | 
127 | 	if b.n < math.MaxUint64 {
128 | 		b.n++
129 | 	}
130 | 
131 | 	if !b.noJitter {
132 | 		prngMu.Lock()
133 | 		t = time.Duration(prng.Int63n(int64(t)))
134 | 		prngMu.Unlock()
135 | 	}
136 | 
137 | 	return t
138 | }
139 | 
140 | // requires b to be locked.
141 | func (b *Backoff) duration(n uint64) (t time.Duration) {
142 | 	// Saturate pow
143 | 	pow := time.Duration(math.MaxInt64)
144 | 	if n < 63 {
145 | 		pow = 1 << n
146 | 	}
147 | 
148 | 	t = b.interval * pow
149 | 	if t/pow != b.interval || t > b.maxDuration {
150 | 		t = b.maxDuration
151 | 	}
152 | 
153 | 	return
154 | }
155 | 
156 | // Reset resets the attempt counter of a backoff.
157 | //
158 | // It should be called when the rate-limited action succeeds.
159 | func (b *Backoff) Reset() {
160 | 	b.lastTry = time.Time{}
161 | 	b.n = 0
162 | }
163 | 
164 | // SetDecay sets the duration after which the try counter will be reset.
165 | // Panics if decay is smaller than 0.
166 | //
167 | // The decay only kicks in if at least the last backoff + decay has elapsed
168 | // since the last try.
169 | func (b *Backoff) SetDecay(decay time.Duration) {
170 | 	if decay < 0 {
171 | 		panic("backoff: decay < 0")
172 | 	}
173 | 
174 | 	b.decay = decay
175 | }
176 | 
177 | // requires b to be locked
178 | func (b *Backoff) decayN() {
179 | 	if b.decay == 0 {
180 | 		return
181 | 	}
182 | 
183 | 	if b.lastTry.IsZero() {
184 | 		b.lastTry = time.Now()
185 | 		return
186 | 	}
187 | 
188 | 	lastDuration := b.duration(b.n - 1)
189 | 	decayed := time.Since(b.lastTry) > lastDuration+b.decay
190 | 	b.lastTry = time.Now()
191 | 
192 | 	if !decayed {
193 | 		return
194 | 	}
195 | 
196 | 	b.n = 0
197 | }
198 | 


--------------------------------------------------------------------------------