Your rate limiter says 100 req/s. Your users get 400.

Your rate limiter says 100 req/s, yet users get 400 because the limiter runs per instance, not per service. When an application scales horizontally with multiple instances, each running its own in-process limiter set to 100 req/s, the effective rate limit multiplies by the instance count. Four instances each enforcing 100 req/s allow 400 req/s total, which breaks the intended global limit. Autoscaling worsens this—the effective limit grows as traffic increases, instead of staying fixed.

Token bucket and sliding window are algorithms: they decide when a request should be rejected based on counting or timing rules. "Redis-backed" is not an algorithm but a choice about where the limiter's state is stored—inside the app process or shared externally. Many explanations mix these up, misleading readers. The real design space is a 2×2 grid: one axis is algorithm, the other is state location.

This means the algorithm decides who to reject and the state location decides if your stated limit is enforced globally or per instance.

Design 1: Token Bucket with In-Process State

Instead of continuously increasing tokens on a timer, token bucket uses "lazy refill": when a request arrives, it calculates tokens accrued since last_refill_at based on elapsed time and refill rate. It then limits tokens to the bucket capacity before deciding whether to allow the request. This uses constant time and memory per client and avoids runtime overheads of timers.

It's important to understand that a full token bucket after an idle period is by design. It allows a client to send a burst of requests immediately after quiet time rather than limiting strictly to a per-second average. This behavior is a feature, not a bug, though many mistakenly see it otherwise.

Stripe runs four limiters in production. The request rate limiter uses the token bucket algorithm described here. In addition, they use a concurrent-requests limiter for CPU-heavy endpoints, and two load shedders reserving capacity for critical traffic, rejecting low-priority requests with 503s under load. This layered approach handles multiple resource limits simultaneously.

Design 2: Sliding Window Counter with In-Process State

An exact sliding window implementation keeps logs of all request timestamps per client, which is accurate but impractical—it uses memory proportional to the number of requests (O(n)). High-volume clients sending thousands of requests quickly exhaust memory.

The sliding window counter approximates by combining counts from the current and last window, weighted by elapsed time:

estimated = current + previous × (1 − elapsed / window)

This keeps fixed-size state (about 24 bytes per client) regardless of request volume.

For example, suppose a client made 42 requests in the previous window and 18 in the current one. If 15 seconds out of 60 have elapsed, the estimate is:

42 × 0.75 + 18 = 49.5

This calculation smooths spikes at window boundaries.

Cloudflare tested this method over 400 million requests from 270,000 clients. They observed a 0.003% error rate, with an average 6% difference between estimated and actual counts, and critically, zero false positives. This low-error, false-positive-free tradeoff justifies use for traffic shaping.

This method can undercount when prior windows have uneven traffic—for instance, if a client dumps all requests in the last second of a window, the estimate will be too low due to the uniform weighting assumption. Understanding this helps interpret rates near boundaries.

Design 3: Redis-Backed Shared State Implementation

To avoid race conditions, checks and increments must happen atomically inside Redis, typically using Lua scripts. Separate GET then INCR commands can race and yield inaccurate results under concurrent clients.

TTL must be set within the same Lua script to avoid race conditions caused by separate EXPIRE commands, which can collide with evictions and leave keys permanently live, breaking cleanup logic.

GitHub uses client-side request sharding, with one primary Redis handling writes and several replicas handling reads. All complex logic runs inside Lua scripts preserving atomicity while scaling horizontally.

-- Lua script example: atomic check-and-increment for token bucket
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local burst_tokens = tonumber(ARGV[4])

local state = redis.call('HMGET', key, 'tokens', 'last_refill_at')
local tokens = tonumber(state[1]) or burst_tokens
local last = tonumber(state[2]) or 0

local delta = math.max(0, now - last)
local new_tokens = math.min(burst_tokens, tokens + delta * refill_rate)

if new_tokens < 1 then
  return {0, new_tokens, last + delta}
else
  new_tokens = new_tokens - 1
  redis.call('HMSET', key, 'tokens', new_tokens, 'last_refill_at', now)
  redis.call('EXPIRE', key, math.ceil(60))
  return {1, new_tokens, now}
end

GitHub encountered bugs illustrating the subtlety of Redis-backed limiters:

1. Reading from Redis replicas lagging behind the primary caused clients to receive reject responses while headers falsely claimed thousands of remaining requests.

2. Reset timestamps combined Redis TTL and Ruby Time.now from separate measurements. Passed time between calls caused header timestamps to occasionally differ by a second, confusing clients. Persisting reset timestamps fixed this.

Memcached evictions in GitHub's earlier setup silently erased rate limit keys during memory pressure, disabling rate limits unintentionally. This underlines the necessity of resilient, eviction-safe stores.

Shared Redis state adds latency due to network round trips. The rate limiter must never be slower or less reliable than the resource it protects.

When Redis is unreachable, you must choose fail-open (allow traffic) or fail-closed (reject traffic) strategies. Neither is universally right; choose per use case and log decisions clearly.

Cloudflare avoids single-point failures by partitioning counters per point of presence (PoP). Anycast routing sends clients consistently to the same PoP, enabling isolated limits that balance scalability and precision.

Benchmarking the Three Designs

Token bucket in-process limiters enforce instance-local limits, allowing total throughput proportional to instances.

Sliding window in-process counters reduce boundary bursts but still scale limit linearly with instances.

Redis-backed shared state tightens global limits correctly but adds network latency.

Production Breakages: Real Bugs from GitHub and Stripe Deployments

Rate limiters that rely on shared state must ensure atomicity to avoid race conditions. GitHub enforces this with Lua scripts in Redis, combining check, refill, and increment operations atomically.

Stripe's layered architecture uses an in-process token bucket limiter alongside other limiters and load shedders to handle multiple resource dimensions and manage capacity under load.

GitHub experienced two notable Redis-related bugs that demonstrate common pitfalls:

• Replica Lag Bug: Reading rate limit state from Redis replicas lagged behind the primary writes. This caused clients to be rejected due to updated limit state while their headers reported exaggerated remaining quotas, undermining trust in rate-limit feedback.

• Timestamp Wobble Bug: Reset time headers were computed by adding Redis TTL and Ruby’s current time from separate calls, introducing timing skew. This occasionally made consecutive responses show reset times differing by one second, confusing clients and clients’ retry logic. Persisting the reset timestamp on window creation and reusing it eliminated this wobble.

These underscore the complexity inherent in distributed rate limiting with shared state.

GitHub’s previous Memcached-backed rate limiter shared memory with app caches. Under memory pressure, eviction silently removed live rate-limit keys, effectively disabling limits without notice. This problem underscores the need to avoid caching systems that can evict critical limiter state.

Each check adding a network round trip can increase latency and impact reliability. The rate limiter should never be slower or less reliable than the resource it protects.

When the shared state store is unreachable, systems must choose whether to fail open (allow all requests) or fail closed (reject all requests). Neither choice fits all scenarios. Protecting availability favors fail open; protecting abuse scenarios favors fail closed. Whichever path you choose, log these events clearly for incident response.

Lua scripts are used because Redis does not natively support multi-command atomic transactions on arbitrary data structures outside of Lua scripting. While complex, Lua is the easiest way to guarantee atomicity, combine check, increment and TTL sets, and keep logic close to the data store. Alternatives such as Redis modules or external locking introduce their own complexity and latency, reducing reliability.