How we scaled the GitHub API with a sharded, replicated rate limiter in Redis

Why we rebuilt the rate limiter

About a year ago, GitHub's API rate limiter was running on a simple Memcached-based design: for each request, increment a counter keyed by the client's rate limit identity, and store a separate "reset at" timestamp. If the counter exceeded the limit and the reset time was still in the future, the request was rejected.

That design had two problems. First, our Memcached infrastructure was moving from a single shared cluster to one per datacenter. That works fine for application caching, but a rate limiter spanning multiple datacenters would produce inconsistent results when a client's requests got routed to different locations. Second, Memcached's eviction policy was breaking rate limit state. Because the same Memcached backend served both rate limiting and general application caching, a full cache could evict active rate limit keys. Clients would then receive fresh rate limit windows when they shouldn't have—and in some cases, only one of the two keys (counter or reset time) would be evicted, leaving clients with a valid usage count but a reset time that was suddenly in the past.

The Redis-based design

We settled on a new architecture using Redis. The key decisions:

• Shard within the application itself—each rate limit key is assigned to a specific Redis cluster at read/write time.
• Each cluster runs a single primary for writes, with replicas handling reads. Redis is often CPU-bound, and replicas help spread that load.
• Use Redis key expiration instead of storing "reset at" values in the database.
• Implement all storage logic in Lua scripts to guarantee atomicity—an improvement over the previous increment-and-check approach.

We also considered storing rate limit state in our MySQL-backed key-value store, but rejected that idea. Rate limit updates need write access to a primary database, and we didn't want to add significant write traffic to busy MySQL primaries. Redis also had the advantage of being a well-documented path: Redis's own documentation includes rate limiter patterns, and Stripe's engineering blog published a solid example implementation in Ruby and Redis.

Rollout and immediate fallout

The migration was structured as a classic feature-flag rollout. We isolated the old logic in a MemcachedBackend class, built a new RedisBackend class, and used a feature flag to gradually shift clients from one to the other. The flag could be adjusted without a deploy, which meant we could instantly revert to the old implementation if something went wrong.

The release itself went smoothly. Once the flag was fully enabled, we removed the flag, deleted MemcachedBackend, and wired RedisBackend directly into the Throttler class. Then the bug reports started.

Two reports stood out. Some clients noticed their X-RateLimit-Reset header values "wobbled"—the timestamp would shift by a second between otherwise identical requests. And some clients were getting rejection responses with X-RateLimit-Remaining: 5000 in the headers, which suggested they had plenty of headroom available even as their requests were being denied.

Fixing the reset-time wobble

The wobble came from a mixing of time sources. The Lua script returned the key's TTL from Redis, and then Ruby added that TTL to Time.now.to_i to produce the reset timestamp for the X-RateLimit-Reset header. The problem is that time passes between the Redis TTL call and the Ruby timestamp call. When that time gap crosses a clock-second boundary, the computed reset time drifts by a second:

We considered two alternatives. One was increasing precision by using Redis's PTTL command, but that only reduces the wobble—it doesn't eliminate it. Another was having Redis compute the absolute time entirely on its own using the TIME command inside the Lua script. But that would have made testing harder: with Ruby as the source of truth for time, our tests could use Timecop to simulate future timestamps without actually waiting for real Redis key expirations.

We ultimately decided to persist the "reset at" timestamp itself in Redis, rather than deriving it. The Lua script now stores the absolute reset time as a second value, which doubles the storage footprint but guarantees a stable reset timestamp because it's read back verbatim. We still apply a TTL to rate limit keys, but set it to one second after the stored reset time. That lets Redis handle cleanup of expired windows while the application owns the semantics of when a window actually resets.

Fixing inconsistent rejections

The X-RateLimit-Remaining: 5000 rejections traced back to a race between a read and a write. The throttling flow worked like this:

1. At the start of the request, check whether the client's current usage exceeds the limit. This is a read, so it hits a Redis replica.
2. Before delivering the response, increment the usage counter and read back the updated values for the response headers. This write goes to the primary.

The failure mode: step 1 hits a replica that still returns data for the client's previous rate limit window. The application sees an over-limit response and prepares a rejection. Then step 2 runs on the primary, where Redis has already expired that old window data and opened a fresh one. The header population reads the new window—hence the misleading X-RateLimit-Remaining: 5000.

This is a known Redis limitation: replicas don't expire keys until their primary tells them to, and primaries only expire keys lazily as they're accessed. The fix had two parts:

• As described above, manage window expiry in application code rather than relying solely on Redis TTLs. The application must be prepared to read stale data from replicas and discard it based on the stored "reset at" value.
• Restructure the rejection path so it doesn't make a second database call after deciding to reject a request. The headers should be populated from the data read in step 1, not from a subsequent write/read cycle that could observe a different window.

Final implementation

Our final Lua scripts implement this pattern end-to-end:

RATE_SCRIPT:
--   count a request for a client
--   and return the current state for the client
-- rename the inputs for clarity below
local rate_limit_key = KEYS[1]
local increment_amount = tonumber(ARGV[1])
local next_expires_at = tonumber(ARGV[2])
local current_time = tonumber(ARGV[3])
local expires_at_key = rate_limit_key .. ":exp"
local expires_at = tonumber(redis.call("get", expires_at_key))
if not expires_at or expires_at < current_time then
  -- this is either a brand new window,
  -- or this window has closed, but redis hasn't cleaned up the key yet
  -- (redis will clean it up in one more second)
  -- initialize a new rate limit window
  redis.call("set", rate_limit_key, 0)
  redis.call("set", expires_at_key, next_expires_at)
  -- tell Redis to clean this up _one second after_ the expires-at time.
  -- that way, clock differences between Ruby and Redis won't cause data to disappear.
  -- (Redis will only clean up these keys "long after" the window has passed)
  redis.call("expireat", rate_limit_key, next_expires_at + 1)
  redis.call("expireat", expires_at_key, next_expires_at + 1)
  -- since the database was updated, return the new value
  expires_at = next_expires_at
end
-- Now that the window is either known to already exist _or_ be freshly initialized,
-- increment the counter (`incrby` returns a number)
local current = redis.call("incrby", rate_limit_key, increment_amount)
return { current, expires_at }

-- CHECK_SCRIPT:
--   Getting both the value and the expiration
--   of key as needed by our algorithm needs to be ran
--   in an atomic way, hence the script.

-- rename the inputs for clarity below
local rate_limit_key = KEYS[1]
local expires_at_key = rate_limit_key .. ":exp"
local current_time = tonumber(ARGV[1])
local tries = tonumber(redis.call("get", rate_limit_key))
local expires_at = nil -- maybe overridden below
if not tries then
  -- this client hasn't initialized a window yet
  -- let this fall through to returning {nil, nil},
  -- where the application will provide defaults
else
  -- we found a number of tries, now check
  -- if this window is actually expired
  expires_at = tonumber(redis.call("get", expires_at_key))
  if not expires_at or expires_at < current_time then
    -- this window hasn't been cleaned up by Redis yet, but it has closed.
    -- (maybe it was _partly_ cleaned up, if we found `tries` but not `expires_at`)
    -- ignore the data in the database; return a fresh window instead
    tries = nil
    expires_at = nil
  end
end
-- Maybe {nil, nil} if the window is brand new (or expired)
return { tries, expires_at }

Known limitations and outlook

One shortcoming remains under consideration. Currently we don't increment the usage counter until the request finishes, because we don't charge clients for 304 Not Modified responses. A better design might increment at request start and then refund the count when the response turns out to be a 304. That would prevent the edge case where a client can exceed the limit while its last allowed request is still processing.

Apart from that, the new architecture has held up well in production. The replicated read paths spread CPU load across instances, the Lua scripts eliminated atomicity questions, and handling window reset logic in application code has removed both classes of bugs described above. The platform is ready for the next round of traffic growth.