Linear and Exponential Back-Off for Go

I’ve recently been working on extending my side project Connectrix to support receiving event data from Twitter. The natural fit was to use the Twitter Stream API to receive events via a push with low latency and low overhead. I looked around and found a couple of Go libraries for consuming the Twitter Stream, but one of them looked very hacky and far from idiomatic Go code, while the second was very large and made a lot of assumptions about the use case. So, I started to write my own low-level, hopefully idiomatic, library for connecting to these streams, the result is go-http-stream-reader.

One of the interesting things about the Twitter Stream API is that is enforces a rate limit, which needs to be managed by adhering to their published back off rules - if you don’t back off when told to then they will punish you for it by making you wait even longer.

From the Twitter Streaming API docs:

Once an established connection drops, attempt to reconnect immediately. If the reconnect fails, slow down your reconnect attempts according to the type of error experienced:

Back off linearly for TCP/IP level network errors. These problems are generally temporary and tend to clear quickly. Increase the delay in reconnects by 250ms each attempt, up to 16 seconds.

Back off exponentially for HTTP errors for which reconnecting would be appropriate. Start with a 5 second wait, doubling each attempt, up to 320 seconds.

Back off exponentially for HTTP 420 errors. Start with a 1 minute wait and double each attempt. Note that every HTTP 420 received increases the time you must wait until rate limiting will no longer will be in effect for your account.

To manage these back off rules I needed to implement an exponential back off algorithm. This algorithm is very trivial but it comes up frequently so I thought it would be good to create a little Go library to take care of it. The result of that is go-backoff. It implements linear, exponential and exponential with full jitter back off algorithms and makes it trivial to use them. For a more detailed look at the use cases for exponential back off algorithms and their behaviour then take a look at this great post from the Amazon AWS blog.

To use go-backoff it’s as simple as instantiating a backoff instance with the desired behaviour:

// Back off linearly, starting at 250ms, capping at 16 seconds
linear = backoff.NewLinear(250*time.Millisecond, 16*time.Second)

// Back off exponentially, starting at 5 seconds, capping at 320 seconds
exp = backoff.NewExponential(5*time.Second, 320*time.Second)

// Back off exponentially, starting at 1 minute, with no cap
expt = backoff.NewExponential(time.Minute, 0)

// Back off between 0 and exponentially, starting at 30 seconds, capping at 10 minutes
expj = backoff.NewExponentialFullJitter(30*time.Second, 10*time.Minute)

for {
  err := tryDoThing()
  if err != nil {
    glog.Debugf("Backing off %d second(s)", exp.NextDuration/time.Second)
    exp.Backoff()
  } else {
    exp.Reset()
    break
  }
}

You can find go-backoff on my GitHub here: go-backoff