Exponential backoff with jitter would probably not fix Github!

Github's been down a lot recently. They recently reported a doubling in monthly commits. I'll leave it as an exercise to the reader to judge whether that's a reasonable excuse for their downtime or not.

On the HackerNews comment thread I saw quite a few comments to the effect of "they need to implement exponential backoff with jitter." That's a nice idea in general, and it might help here. However, there's a good chance it will not help and may even make things worse!

Why would it make things worse? This talk from Marc Brooker is an excellent discussion of some of the issues. Particularly the fact that Github commits are an "Open System," terminology that comes from this referenced paper. On Github requests arrive independently from millions of uncoordinated actors. Forcing a failed client to back off does not stop the next independent client from sending a new request. Backoff only shifts that client's retry into the near future, where it stacks on top of fresh incoming traffic.

In Marc's talk, he explains that retrying (with jitter) n times just raises load up to n * 100%. Each failed request produces a new attempt and each new attempt fails (because the system is overloaded!). Instead of 100% load you've now raised the load to 400% if you perform 3 retries (1 original + 3 retries). The service becomes trapped in a metastable state of failure.

So what's the fix for this? I'm not sure if this actually applies to Github's case but a better retry algorithm follows.

Client side we implement a token bucket adaptive retry algorithm and server side we implement adaptive concurrency algorithms plus load shedding. Lets define these.

Client side:

• Every client maintains a token bucket.
• Successful calls deposit a small fraction of a token (e.g., +$0.01).
• Retries cost a full token (e.g., -$1.00).
• If the bucket is empty, the client fails fast immediately without retrying.

If you do the math, you'll find that this algorithm caps client requests at 101% of the limit. Muuuuch better than 400%.

Server Side (because we can't just trust the client):

• Reject excess incoming work, ideally at the edge and return something like a 429
• Apply something like TCP Vegas to drop excess requests with some intelligent algorithm.

Would this fix Github... not really. Neither exponential backoff nor more clever schemes actually provision sufficient resources but they do prevent some gnarly metastable failure states.

Also, I could have just commented this on HackerNews but I felt like this was interesting enough to post and I can't get into internet debates with anyone on my own blog! :)