A Bug in GitHub's Redis-Based Rate Limiter: The Wobbling X-RateLimit-Reset Header

Introduction to Rate Limiting and GitHub’s Journey

Rate limits are crucial for maintaining the stability of any product and protecting against abuse. GitHub, like many other large-scale services, implements rate limiting to manage API usage. Initially, GitHub’s rate limiter was powered by Memcached, but they later transitioned to Redis, where they encountered a peculiar but insightful bug.

GitHub’s Initial Rate Limiter: Memcached

GitHub’s initial setup utilized a single Memcached cluster within a single data center. This cluster served both general caching needs and rate limiting use cases. While seemingly efficient, this consolidated approach presented several challenges:

Problems with Memcached

1. Key Eviction Conflicts: As the volume of data cached by application use cases grew, Memcached’s eviction policies sometimes inadvertently removed keys essential for rate limiting. This led to discrepancies and inconsistencies in the user experience, as rate limits would behave unpredictably.
2. Single Data Center Constraint: GitHub, like many scaling companies, evolved from a single data center architecture to a multi-data center setup. However, their rate limiter remained tied to a single Memcached cluster. This meant application servers across different data centers had to connect back to this one central Memcached instance, introducing latency and single points of failure.
3. Sharding Requirements: To support a multi-data center architecture and distribute load, GitHub needed to shard their application servers and caching infrastructure. The existing Memcached setup was not conducive to this requirement.

These limitations prompted GitHub to re-evaluate their rate limiting architecture and seek a more robust alternative.

Transition to Redis for Rate Limiting

Recognizing the need for a more scalable and flexible solution, GitHub decided to migrate their rate limiting infrastructure to Redis. Redis is a popular choice for rate limiting due to its performance and feature set. The key reasons for GitHub’s switch included:

1. Simple Sharding and Replication: Redis offers straightforward mechanisms for sharding data and creating replicas, simplifying the setup for distributed environments.
2. Application-Level Sharding and Routing: GitHub’s architecture allowed their API servers to intelligently shard and route requests to the correct Redis node. For instance, if rate limiting by user ID, the API server could determine which Redis node (and in which data center) held the rate limit key for that specific user, using algorithms like consistent hashing.
3. Read Replica Support for High Read Workloads: Rate limiting is a read-heavy operation, as every API request requires a rate limit check. Redis makes it easy to create read replicas from master nodes, significantly improving read throughput and overall system responsiveness.
4. Inbuilt TTL for Auto-Expiration: Redis’s native Time-To-Live (TTL) feature allows keys to automatically expire after a set duration. This was crucial for rate limiting keys, enabling automatic cleanup of dead or expired rate limit entries without manual intervention.
5. Lua Script Support for Atomic Operations: Redis supports Lua scripting, which allows complex business logic to be executed atomically within the Redis server. This ensures that rate limit updates (e.g., decrementing counters, setting TTLs) are performed as a single, indivisible operation, preventing race conditions.

With these advantages, Redis seemed like an obvious choice for GitHub’s re-architected rate limiter. However, during staggered releases, an interesting bug emerged.

The “Wobbling” Bug in GitHub’s Rate Limiter

GitHub’s API responses are known for their rich headers, including detailed rate limiting information. Key headers include X-RateLimit-Limit (total requests allowed), X-RateLimit-Remaining (requests left), and X-RateLimit-Reset (Epoch timestamp when the rate limit resets).

The Problem: Inconsistent X-RateLimit-Reset

The bug manifested as a “wobbling” behavior in the X-RateLimit-Reset header. Users observed that the reset timestamp would fluctuate between consecutive API calls. For example, it might show 17237165 at one moment, then 17237166 (one second later), and then revert to 17237165. This inconsistency was problematic for heavy users who relied on this header for their application logic.

Ideal Behavior: The X-RateLimit-Reset value should remain constant and stable until the actual reset time is reached. It should not change or “wobble” within the same rate limit window.

Deep Dive: Root Cause of the Wobbling

To understand the wobbling, we need to examine how GitHub’s Redis-based rate limiter calculated the X-RateLimit-Reset header.

GitHub’s Redis Interaction for Rate Limiting

1. Lua Script Execution: Upon every API request, the GitHub API server fires a Lua script on Redis. This script updates the relevant rate limit counters for a given key (e.g., user ID) and returns the remaining TTL (Time-To-Live) of that key in Redis.
2. API Server Calculation: The API server receives the TTL from Redis. It then calculates the X-RateLimit-Reset value by adding the current server time (time.now) to the received TTL: X-RateLimit-Reset = time.now + TTL.

The Problematic Calculation: Network Latency and Clock Skew

The root cause of the wobbling lies in the time that elapses between when the request is sent to Redis, processed, and the response is received back at the API server. This involves network latency and processing time, which are non-zero in a distributed system.

Let’s illustrate with an example, using smaller numbers for clarity (assume timestamps are in seconds):

Scenario 1: Happy Path (No Wobble)

• Request 1:

  • Client initiates request at 1000. API server sends to Redis.
  • Travel + Lua script execution + response takes 200ms total.
  • Redis sets key with TTL = 5s at 1000.1 (after 100ms travel).
  • API server receives response at 1000.2. It gets TTL = 5.
  • API server calculates X-RateLimit-Reset = 1000.2 + 5 = 105 (after converting to integer).

• Request 2:

  • Client initiates request at 1001.8. API server sends to Redis.
  • Travel + Lua script execution + response takes 100ms total.
  • Redis checks key at 1001.85 (after 50ms travel). Since 1 second has passed since 1000.1, the TTL is now 4s.
  • API server receives response at 1001.95. It gets TTL = 4.
  • API server calculates X-RateLimit-Reset = 1001.95 + 4 = 105 (after converting to integer).

In this happy path, despite different latencies, the X-RateLimit-Reset remains 105.

Scenario 2: Edge Case (Wobble Occurs)

• Request 1: Same as above, X-RateLimit-Reset = 105.

• Request 2 (Wobble Trigger):

  • Client initiates request at 1001.9. API server sends to Redis.
  • Travel + Lua script execution + response takes 100ms total.
  • Redis checks key at 1001.95 (after 50ms travel). Since 1 second has passed since 1000.1, the TTL is still 4s.
  • API server receives response at 1002.05 (approximately 1002). It gets TTL = 4.
  • API server calculates X-RateLimit-Reset = 1002.05 + 4 = 106 (after converting to integer).

Here, the X-RateLimit-Reset value wobbled from 105 to 106. This happens because the time.now on the API server, when the calculation time.now + TTL occurs, has crossed a second boundary relative to the time when the TTL was initially set or last updated in Redis, combined with the network latency. This is a classic example of the challenges posed by distributed system clocks and the fallacy of zero latency.

GitHub’s Solution: Prioritizing Accuracy

GitHub considered a few potential solutions:

• Increase Precision: Operating at millisecond precision instead of seconds would minimize the wobble but not entirely eliminate it.
• Redis Sends Absolute Reset Time: Having Redis directly calculate and send the absolute reset time (time.now + TTL from Redis’s perspective) was considered. However, this was difficult to test and not supported by older Redis versions (5 and below) that some of GitHub’s infrastructure components still used.

Given the user impact, GitHub prioritized accuracy for the X-RateLimit-Reset header. They implemented an ingenious solution that involved a slight increase in storage footprint:

1. Persisting reset_at: For every rate limit key, GitHub added an additional key in Redis to store the absolute reset_at timestamp. This value is the exact Epoch time when the rate limit is supposed to reset, calculated once and persisted.
2. Lua Script Returns Both: The Lua script executed on Redis now returns both the remaining TTL (for Redis’s internal expiration) and the persisted reset_at value.
3. API Server Uses Persisted Value: The API server receives both values. For the X-RateLimit-Reset header, it directly uses the stable, persisted reset_at value from Redis. The TTL is still used by Redis for its auto-expiration mechanism.
4. Offset for Edge Cases: To further ensure stability and avoid any residual edge cases, the reset_at value is set 1 second from the computed time, providing a small buffer.

By persisting the absolute reset time, GitHub eliminated the runtime calculation on the API server that was susceptible to network latency and clock skew. This ensures that the X-RateLimit-Reset header remains stable and accurate, resolving the wobbling bug.

Conclusion

This case study from GitHub’s rate limiter highlights the subtle yet significant challenges in distributed systems, particularly concerning time synchronization and network latency. The “wobbling” bug serves as a powerful reminder that assumptions about zero latency or perfectly synchronized clocks can lead to unexpected behavior. GitHub’s solution, prioritizing accuracy by persisting the absolute reset time, demonstrates a practical approach to building robust and reliable distributed services.