Wobble Bug in GitHub's Rate Limiter

TL;DR

GitHub's Redis-based rate limiter wobbled the x-ratelimit-reset header by a second because the API server computed the reset time as Time.now() + TTL, and the processing delay between asking Redis and responding changed the answer. The fix was to store the absolute reset timestamp in Redis and return it directly, removing the API server's clock from the calculation.

What is rate limiting and why does it matter?

Rate limiting is a technique used in computer systems, particularly in APIs, networks, and applications, to control the rate at which requests are processed or accepted. It is a crucial mechanism for maintaining the performance, reliability, and security of systems by preventing excessive usage or abuse.

How did GitHub build their rate limiter?

Rate limiting is a technique used in computer systems, particularly in APIs, networks, and applications, to control the rate at which requests are processed or accepted. It is a crucial mechanism for maintaining the performance, reliability, and security of systems by preventing excessive usage or abuse.

The move from Memcached to Redis

GitHub's initial rate limiter was built using Memcached. They originally had a single Memcached server which powered their caching use cases along with their rate limiter use cases.

One of the key problems the engineers at GitHub faced was that when data usage sometimes got too big, the Memcached server occasionally evicted rate-limiting keys. This led to a lot of discrepancies and inconsistencies in the user experience.

Another problem they faced was that when they started, their data lived in a single data center — but as they grew, it got distributed across multiple data centers. Now they wanted a separate Memcached cluster per data center, hence sharding was required, and they decided to re-architect their rate limiter with Redis.

The main reasons for choosing Redis were:

1. Simple sharding and replication setup.
2. Redis TTL for auto expiration of key.
3. Support for LUA.

What was the wobble bug?

The issue that happened was "wobbling". So If you hit the following curl on api.github.com ..

curl -I https://api.github.com/users/saksham-sharma-99

the response headers you'll get are as follows

...
access-control-allow-origin: *
strict-transport-security: max-age=31536000; includeSubdomains; preload
x-frame-options: deny
x-content-type-options: nosniff
x-xss-protection: 0
referrer-policy: origin-when-cross-origin, strict-origin-when-cross-origin
content-security-policy: default-src 'none'
server: github.com
x-ratelimit-limit: 60
x-ratelimit-remaining: 59
x-ratelimit-reset: 1724064530
x-ratelimit-resource: core
x-ratelimit-used: 1
accept-ranges: bytes
content-length: 1502
...

headers which are important for us are

• x-ratelimit-limit: maximum number of requests i am allowed to make until the next reset time
• x-ratelimit-remaining: number of request left with me or which i can make until the next reset time
• x-ratelimit-reset: the epoch time at which the rate-limit will be reset.

The problem that occurred was wobbling of the header x-ratelimit-reset: it sometimes returned 1724064530 and other times 1724064531.

This happened because of a very minor edge case that the engineers at GitHub sort of overlooked. The way this header is formed is:

1. Request hits the API server.
2. API server asks the Redis cluster for the TTL.
3. Redis cluster executes some LUA scripts and returns the TTL.
4. API server returns Time.now() + TTL in the x-ratelimit-reset header.

This all seems pretty direct at first glance, but it neglects a minor amount of processing time. Let's understand it with 2 scenarios, keeping the TTL as 5s.

1. When the first request enters the server at timestamp 1000

• lets say request enters the server at time timestamp 1000.
• (Step 2) and (Step 3) takes somewhere around 200ms to be executed.
• Hence (Step 4) starts executing at 1000.2 and returns x-ratelimit-reset headers as 1005.2, which is ~ 1005.

2. When the second request enters the server at timestamp 1001.9

• now since one second has passed, TTL is now 4s
• (Step 2) and (Step 3) takes somewhere around 200ms to be executed.
• Hence (Step 4) starts executing at 1002.1 and returns x-ratelimit-reset headers as 1006.2, which is ~ 1006.

As you can see clearly the x-ratelimit-reset wobbled from 1005 to 1006.

How did GitHub fix the wobble?

There were multiple fixes available for this

1. Cut down the TTL to milliseconds instead of seconds. But this would've reduced the wobbling instead of eradicating it
2. Instead of computing the x-ratelimit-reset at the API server, if Redis could send it directly then the problem could be solved using Redis' time command. Unfortunately it wasn't possible on versions 5 and below (which was required by some of their other components).

So they took the final option

3. Store the TTL in the database (at every reset time) and send it directly in the response instead of calculating it at the API server.

That's all in this one, folks — let me know where I messed up in writing this :)