Rate Limiting: how Redis, Cloudflare, Stripe, and Envoy do it
Token buckets and sliding windows are the easy part. The hard part is coordination.
Think about the entrance to a busy parking garage on a Friday evening. There is a gate that lifts, one car at a time. It does not ask whether you deserve a spot. It does not care that you drove farther than the car behind you. It counts. If the garage is full, the gate stays down, and you wait or you leave. The intelligence in that system is not the gate itself - it is the counting mechanism that knows how many cars are inside at any given moment.
Distributed systems face the same problem at a different scale. The gate is a rate limiter, and the mechanism that counts is harder to build than it looks. Stripe's rate limiter enforces multiple simultaneous limit dimensions at once - per-endpoint request rates, per-account totals, and concurrent request caps - all checked on every inbound request. Cloudflare counts traffic at the edge, inside each point of presence, without synchronizing those counts globally across its network of data centers. Both are doing the same conceptual thing as the parking garage gate, and both arrived at surprisingly different architectures to do it correctly.
The reason the architectures diverge is not the algorithm. Token buckets, sliding windows, leaky buckets - these are undergraduate material. The reason they diverge is the coordination problem. When you have thirty gateway nodes handling traffic, and each one maintains its own counter, and a user sends ten requests that happen to land on ten different nodes, what does "the user has sent ten requests" even mean? It means ten nodes each believe the user has sent one. Without shared state, your limit of ten requests per second becomes effectively three hundred.
Lyft's open-source envoyproxy/ratelimit service handles more than 2 million requests per second backed by a Redis coordination layer. Redis is the canonical answer to the coordination problem - a single-threaded in-memory store that can execute atomic Lua scripts, maintain sorted sets for timestamp tracking, and expire keys on a schedule. That combination gives you a place to put the count that every gateway node trusts equally. The tricky part is using it correctly, and the gap between "using Redis for rate limiting" and "using Redis correctly for rate limiting" is where most implementations introduce subtle bugs.
This post works through that gap. The algorithm choice matters, but it is the second question. The first question is how you coordinate counts across nodes without adding meaningful latency to every request. The answer to that question determines everything else: which data structure you use in Redis, how you handle the moment Redis becomes unavailable, and which production systems made which compromises.
Distributed rate limiting is a canonical system-design interview problem, but the interview answer and the production answer are not the same document. This is the production answer.
The scope
This post covers five algorithms - fixed window counter, sliding window log, sliding window counter, token bucket, and leaky bucket - and then works through the Redis-backed coordination model that makes any of them useful in a distributed setting. The algorithm section focuses on the failure mode of each, not the mechanics alone, because the failure mode is what determines which one you reach for.
On coordination, the post covers Lua script atomicity, key naming strategy, TTL discipline, clock skew, and the circuit breaker pattern for graceful degradation when Redis becomes unavailable. Four production implementations are examined in enough depth to extract transferable decisions: Stripe’s multi-tier token bucket, Cloudflare’s edge-local counting model, Lyft’s gRPC-backed Redis service, and Grab’s per-node frequency-capping shards.
The post scopes Redis in three operational modes. Standalone Redis is the simplest deployment - a single primary, no replication. Redis Sentinel adds automatic failover: a set of Sentinel processes monitor the primary and promote a replica when the primary dies, typically within thirty seconds. Redis Cluster distributes data across multiple primaries using hash slots, providing horizontal scale at the cost of operational complexity. Each represents a different trade-off between simplicity, availability, and throughput, and the right choice depends on your RPS ceiling.
What this post does not cover: API gateway product comparisons beyond the named anchors, load balancing, DDoS mitigation at the network layer (L3/L4), or authentication and authorization. Rate limiting sits at the application layer and operates on authenticated identity - it assumes you already know who is making the request.
The boundary between rate limiting and circuit breaking is worth naming precisely, because both appear in the same system-design discussions and share enough vocabulary to cause real confusion. A circuit breaker reacts to downstream failure rates: it opens when the service you are calling starts failing, protecting your system from cascading errors. A rate limiter reacts to upstream request rates: it opens when callers are sending more traffic than you can absorb, protecting your service from overload. Shared vocabulary - "open", "closed", "threshold", "failure count" - does not mean shared mechanism. They are complementary tools with different subjects; a circuit breaker's subject is the service it wraps, a rate limiter's subject is the caller it governs.
L3/L4 DDoS mitigation is excluded for a more fundamental reason than scope. At the network layer, traffic analysis operates on raw packet counts before the application layer has parsed an HTTP request, extracted a user ID, or verified a session token. There is no concept of "per-user" at that layer - only per-IP or per-connection. A rate limiter enforcing per-account limits requires authenticated identity, which only exists after the application stack has processed the request.
Non-Functional Requirements
A rate limiter without concrete targets is decorative. The NFRs below are drawn from production baselines, not hypotheticals, and each one connects to a specific failure if it is missed.
Latency. The rate-limit check must add no more than 1 millisecond at p99 to the request path. Redis command latency over a local network is typically in the 200–500 microsecond range under normal load. The budget allows for one Redis round trip per request and the Lua execution overhead on top. If this target is missed, the rate limiter becomes visible as a latency source in production traces, and teams begin talking about disabling it.
Throughput. The target ceiling is 100,000 requests per second sustained. Lyft's envoyproxy/ratelimit service establishes this as a real-world reference point for single-cluster Redis sizing. Above this threshold, sharding becomes necessary.
Accuracy. The sliding window counter algorithm introduces a bounded approximation error. In practice, measured error is approximately 0.003% - meaning a limit of 1,000 requests per minute may allow at most 1,000.03 requests under adversarial timing. This is acceptable for API rate limiting on most surfaces. The sorted-set sliding log is exact, but its memory scaling makes it impractical at the scale this post targets.
Memory. At 1 million users across three limit tiers (per-second, per-minute, per-hour), the sliding window counter requires approximately 600 MB of Redis memory. That is 1 million users × 3 tiers × 200 bytes per counter. This is the memory budget that eliminates the sorted-set sliding log from consideration at scale: at 1,000 requests per minute per user across 1 million users, the log approach requires approximately 100 GB.
Availability. The rate-limit path must achieve 99.99% availability. Critically, a Redis failure must not propagate to 100% request failure. The rate limiter is infrastructure for a gate - if the gate breaks, you do not want the building to catch fire. The circuit breaker pattern is the mechanism that prevents this coupling, and it requires an explicit policy decision: fail open (allow requests when Redis is unavailable) or fail closed (reject requests).
Headers. Every 429 response must carry the standard rate-limit headers: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, and Retry-After. These are not optional courtesies - they are the contract that allows clients to backoff correctly. A client that receives a 429 without a Retry-After header has no choice but to guess at a retry interval, which produces thundering-herd behavior at scale.
Scalability. Distributed sliding-window implementations show throughput plateauing without horizontal sharding strategies. The architecture section covers Redis Cluster as the answer, but the NFR is what motivates the requirement: a single Redis node can handle roughly 100,000 Lua operations per second, and that ceiling is reachable at this scale.
The trade-off embedded in this NFR set is accuracy versus memory. The sorted-set sliding log is exact, but it scales with requests per user, not users. The sliding window counter scales with users. For most API surfaces, the 0.003% error is irrelevant, and the memory savings are decisive.
Back-of-the-envelope numbers
Before choosing an algorithm or designing a Redis topology, it helps to know the shape of the problem in numbers. The estimates below assume 1 million registered users, 100,000 requests per second at peak, and three limit tiers per user: per-second, per-minute, and per-hour.
Key-space size
The key naming pattern for a rate limiter is rl:{user_id}:{endpoint}:{window_start}. With 1 million users, 5 monitored endpoints, and 3 time windows, the key space is 15 million keys.
1,000,000 users × 5 endpoints × 3 windows = 15,000,000 keysNot all 15 million keys exist at once. Keys carry a TTL equal to the window duration, so per-second keys expire every second, per-minute keys every minute, and per-hour keys every hour. The live key count at any instant is bounded by how many users are active within the most recent window.
Memory footprint per algorithm
Fixed window counter. One string key per user per window, holding a single integer. Redis string overhead is approximately 56 bytes; the integer itself is 4 bytes. At 1 million users across 3 windows: roughly 180 MB.
1,000,000 × 3 × 60 bytes = 180 MBSliding window log. A Redis sorted set where each member is a request timestamp. Memory scales with requests, not users. At 1,000 requests per minute per user across 1 million users, each timestamp entry costs approximately 100 bytes:
1,000 req/min × 1,000,000 users × 100 bytes = 100 GBThat is not a rounding error. The sorted-set log is exact, and that exactness comes at a memory cost that makes it impractical for public-facing APIs at this user scale. It is viable for internal services with low request rates or very small user populations.
Sliding window counter. Two string keys per user per tier - one for the current window, one for the previous. At approximately 200 bytes per user per tier across 3 tiers:
1,000,000 × 3 × 200 bytes = 600 MBThis is the recommended default. The memory footprint is manageable, the error rate is negligible in practice, and the implementation is a small Lua script.
Token bucket. A hash with two fields: tokens (remaining capacity) and last_ts (last refill timestamp). Redis hash overhead for two fields is approximately 88 bytes per user:
1,000,000 × 88 bytes ≈ 88 MBToken bucket has the smallest per-user footprint of all five algorithms. It collapses the time dimension entirely - instead of storing when each request arrived, it stores only how many tokens remain and when they were last replenished.
Side-by-side summary at 1 million users, 100,000 RPS peak:
Algorithm Memory Dominant factor
Fixed window counter ~180 MB users × tiers
Sliding window log ~100 GB users × requests/user
Sliding window counter ~600 MB users × tiers × 2 keys
Token bucket ~88 MB users only
Leaky bucket (list) ~500 MB users × queue depthThe three-order-of-magnitude gap between the sliding window log (100 GB) and the token bucket (88 MB) reflects a fundamental trade-off:
exact counting requires storing every event; approximate counting requires storing only a summary.
For a limit of 1,000 requests per minute, the 0.003% approximation error of the sliding window counter - at most 0.03 extra requests per user - is the price of a 165× reduction in memory.
🔁 If your team is sizing a rate limiter, the memory math above settles the algorithm debate before it even starts - worth passing on.
Redis operations per second
At 100,000 RPS, each request requires one Lua script execution - one Redis operation per rate-limit check.
100,000 RPS × 1 Lua EVAL = 100,000 Redis ops/secA single Redis node handles approximately 100,000 to 200,000 simple command operations per second, but Lua script execution has higher overhead than a raw GET or INCR. The realistic ceiling for Lua-heavy workloads is closer to 100,000 ops/sec. This means 100,000 RPS is right at the boundary of what a single Redis node can serve without degradation.
For multi-tier rate limiting - checking per-second, per-minute, and per-hour limits on every request - a naive implementation would require three sequential Lua calls per request, multiplying Redis load by three. The mitigation is pipelining: batch multiple Lua EVAL calls into a single TCP round trip.
⚖️ What if “just pick an algorithm” is the wrong first question?
Everything above is the setup - the problem, the targets, the memory math. The rest of this post is the production answer: the coordination architecture, copy-paste Lua scripts, the Redis-down circuit-breaker path, and exactly how Stripe, Cloudflare, Lyft, and Grab each compromised.
