Designing a Distributed Rate Limiter with Redis

Clarify the limit before choosing an algorithm

Functional requirements

Start by defining what is being protected and whose traffic consumes the quota. The worked case is a Stripe-like public API: each API key may make 1,000 requests per minute, the limit is hard, and the 1,001st request is rejected immediately with HTTP 429 Too Many Requests. The limit must hold across 50 geographically distributed API servers, rather than allowing each server to apply an independent local quota. Internal service-to-service calls are a separate validation point: if they bypass the public API path, decide whether they need their own protection.

The identity dimension is not interchangeable. Per-API-key enforcement follows an authenticated customer, per-IP enforcement protects an edge address, and per-endpoint enforcement distinguishes a cheap read from an expensive operation. Decide whether the design needs only the API-key limit or a combination such as API key plus endpoint. Also decide whether a breach is always rejected or whether some traffic may be queued or degraded. For this example, rejection is immediate; queueing is out of scope because it would change the request's completion semantics.

The matrix makes the unresolved axes explicit instead of hiding them in an algorithm choice. The important constraint is the combination of per-key identity, hard rejection, gateway placement, and a global scope across the 50-server deployment. Confirm the response contract separately: 429 is specified, while the body and Retry-After behavior still need a product decision.

Non-functional requirements

The limiter sits on every request's hot path, so set its overhead budget before choosing a store or algorithm. Use less than 5 ms at p99 as the working latency target for the limiter itself. A design that enforces the quota correctly but consumes most of the request's latency budget is not acceptable. The deployment scope also creates a consistency requirement: requests arriving at different servers must consult enforcement state for the same API key rather than isolated counters.

Keep the first design bounded: solve static per-API-key limits for the public API, with the stated hard-rejection behavior and latency target. Leave adaptive limits, billing policy, and any internal-service quota scheme outside this decision until their requirements are specified. Those boundaries prevent an underspecified limiter from silently becoming a general traffic-control system.

Size the keys and the Redis hot path

Memory footprint

Start with the number of identities, not with a Redis instance size. Assume 10,000,000 API keys and one counter per key. The first step is therefore: 10,000,000 API keys × 1 counter = 10,000,000 counters. Using the worked estimate of approximately 100 bytes per counter record, including the key string, integer, and TTL metadata, the storage arithmetic is: 10,000,000 counters × 100 bytes/counter = 1,000,000,000 bytes ≈ 1 GB.

That footprint is manageable for the counter data itself: the estimate is about 1 GB, not tens or hundreds of gigabytes. Treat it as a capacity estimate rather than a promise about usable Redis memory; replication and failover add operational capacity requirements beyond the primary counter set.

The Redis hot path

Next, convert request traffic into store operations. Assume 100,000 API requests per second and one rate-limit update for every request. The write rate is: 100,000 API requests/second × 1 Redis write/request = 100,000 Redis writes/second. Compare that with the cited single-threaded Redis capacity of approximately 100,000–1,000,000 operations/second: 100,000 ÷ 100,000 = 1× at the low end, and 100,000 ÷ 1,000,000 = 0.1× at the high end. At 100,000 operations per second, the workload is at the low end of the range and uses one tenth of the upper-end capacity; the upper end is roughly 10× higher.

The counter store is on the single hot path: each API request must obtain a rate-limit decision before it can proceed upstream. Consequently, Redis processing and network latency are added to every API request's latency, while a Redis outage becomes a limiter availability decision for the whole API. This rules out treating the counter store as an optional asynchronous log. It must be sized and operated as a synchronous dependency, with replication and failover considered even though the primary memory and operation-rate estimates fit on one node.

Define the decision and rejection contract

The limiter is part of the gateway's middleware path, so the protected operation keeps its normal API shape. For the worked contract, the gateway evaluates the API key's budget before forwarding a request to the upstream service. An allowed request proceeds normally. A request that would exceed the budget is rejected immediately rather than queued or degraded.

Expose the decision to clients

Return the quota metadata on both successful and rejected responses. X-RateLimit-Limit communicates the maximum request budget, X-RateLimit-Remaining tells the client how much capacity is left, and X-RateLimit-Reset identifies when the current window resets. This lets an SDK decide whether to send another request, slow down, or wait, instead of discovering the policy only through errors.

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: <remaining>
X-RateLimit-Reset: <reset-time>
Retry-After: 60

{"error":"Rate limit exceeded"}

A rejection is an HTTP 429, not a generic server error: its JSON body gives clients a machine-readable error value of Rate limit exceeded. X-RateLimit-Remaining reports the remaining capacity, while X-RateLimit-Reset identifies the reset point. Retry-After tells a client when it may resume sending requests; a well-behaved client should honor it rather than retrying immediately and creating another burst.

The hard-rejection choice is deliberate for this contract. The gateway must make the decision before upstream execution, so rejected work consumes neither search-service capacity nor downstream retry capacity. The API key belongs in the request authentication context, while the limit and remaining count belong in response headers: clients can inspect them without parsing the error body, and the body can remain stable as the contract evolves.

Model token-bucket state and key dimensions

The limiter’s runtime record needs only the state required to make the next allow/deny decision. For a token bucket, store tokens and last_refill in a Redis Hash. tokens is the current fractional or whole-token balance; last_refill is the timestamp used to calculate how many tokens have accumulated since the previous decision. Tokens refill at a fixed rate, each accepted request consumes one token, and the bucket capacity bounds the burst a previously idle client can send while the refill rate smooths its long-run throughput.

Make the Redis key express the policy scope

A per-API-key policy and a per-endpoint policy cannot share an undifferentiated counter. Use a logical key that includes the dimensions you enforce, such as an API-key-plus-endpoint key. That gives /search and /checkout independent buckets for the same client, so a policy such as 100 requests per minute for /search and 10 requests per minute for /checkout can be enforced without one endpoint consuming the other’s allowance. If the policy is only per API key, omit the endpoint dimension deliberately rather than accidentally creating separate limits.

Redis is a suitable state store because the limiter repeatedly reads and updates small, short-lived records. Redis supports atomic operations such as INCR and key expiration; use the expiration operation required by the chosen algorithm. The token-bucket transition needs more than one field, however, so the refill calculation and token consumption must be evaluated together. The cleanup TTL should be chosen from the policy’s lifecycle: define its behavior explicitly and let inactive bucket keys disappear according to that policy. The model does not depend on a Redis default expiration.

The resulting record and transition are deliberately small. The hash below shows the two token-bucket fields, tokens and last_refill, and makes the identity boundary explicit. The script reads both fields, computes elapsed time, caps the refill at bucket capacity, and updates the token state in the same decision. If the implementation uses cleanup expiration, define its policy explicitly and apply it consistently to the bucket state.

-- Execute this server-side Lua script with EVAL and one bucket key.
local bucket_capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local tokens = tonumber(redis.call('HGET', KEYS[1], 'tokens')) or bucket_capacity
local last_refill = tonumber(redis.call('HGET', KEYS[1], 'last_refill')) or now
local elapsed = now - last_refill
local refilled = math.min(bucket_capacity, tokens + elapsed * refill_rate)

if refilled < 1 then
  redis.call('HMSET', KEYS[1], 'tokens', refilled, 'last_refill', now)
  return 0
end

redis.call('HMSET', KEYS[1], 'tokens', refilled - 1, 'last_refill', now)
return 1

The important modeling choice is not the literal value 950; it is that the balance and its timestamp form one state machine. Updating only tokens would leave the next refill calculation using stale time, while updating the fields in separate commands would expose an intermediate state to concurrent requests. Lua scripts are executed atomically by Redis, so the conditional read, refill, decrement, and timestamp write have one serialization point. A single-key token bucket also avoids the cross-slot coordination problem that appears when a script accesses multiple Redis Cluster keys.

Place the limiter on the request path

The shared request path

Put the limiter where every request to the protected public API already passes: the API gateway. The baseline path is Client → API Gateway rate-limit middleware → Redis counter store → upstream service. The gateway identifies the API key and endpoint, invokes the token-bucket decision for that logical key, and forwards the request only when Redis says it is allowed. A rejected request ends at the gateway instead of consuming upstream capacity; the client receives the rejection contract defined by the API, typically HTTP 429.

Redis is a separate component because the decision must be shared by all 50 geographically distributed API servers. An in-process counter would give each server its own view, so a client could spread requests across servers and exceed the intended limit. A sidecar can isolate the limiter from application code and scale independently, but it still needs a shared store when the limit spans servers. Embedded middleware remains useful for service-specific protection, yet internal service-to-service calls can bypass a gateway-only check. If those calls must also be constrained, enforce a corresponding policy in the sidecar or the receiving service.

On the allow path, the middleware sends one Redis request containing the token-bucket transition, such as a Lua script invoked with EVAL. The script reads the bucket state, accounts for elapsed refill time, consumes a token when available, and returns the decision and remaining state. The gateway then routes the original request to the upstream service. On the deny path, it does not call the service. This extra Redis hop is therefore on every request, making the store part of the limiter's latency and availability budget rather than an asynchronous bookkeeping system.

Token bucket fits when the API should permit controlled bursts while enforcing an average rate: idle clients can accumulate tokens, then spend them in a burst. A fixed window is simpler but exposes a boundary burst. A sliding-window log is accurate but stores every request timestamp, while a sliding-window counter uses constant state and smooths boundaries at the cost of approximation. Token bucket instead keeps compact state with slightly more transition logic, making its burst behavior explicit rather than accidental.

Close the race between checking and consuming

The limiter’s decision is a read–modify–write transition: read the current bucket state, decide whether the request is allowed, then consume capacity. That transition must be indivisible. If two API servers perform those steps as separate Redis commands, both can read the same near-limit state before either update is visible. Each server may then allow its request, letting the pair exceed the intended limit.

A fixed-window counter makes the gap easy to see. A request can increment a key, inspect the resulting count, and then set its expiration in a separate command. Under concurrency, the counter update and the allow/reject decision no longer form one transaction. The same problem appears in a token bucket: one server can read that one token remains while another server reads the same value, and both can pass unless the decrement is part of the same server-side transition.

Lua is the canonical mechanism for this multi-step decision. Redis executes a Lua script atomically on a single Redis shard, so no other command runs between the script’s reads and writes. The caller sends the script once with the key and bucket parameters; the script performs refill, availability checking, and consumption without exposing intermediate state.

The important detail is that rejection must not mutate the bucket. When the computed token count is below one, the script returns 0; when a token is available, it writes the decremented value and returns 1. The refill timestamp is updated in the same invocation as the token write, so a later request evaluates elapsed time from the state produced by the accepted transition.

-- Execute this server-side script with EVAL and one bucket key.
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local tokens = tonumber(redis.call('HGET', KEYS[1], 'tokens')) or capacity
local last_refill = tonumber(redis.call('HGET', KEYS[1], 'last_refill')) or now
local elapsed = now - last_refill
local available = math.min(capacity, tokens + elapsed * refill_rate)
if available < 1 then
  redis.call('HMSET', KEYS[1], 'tokens', available, 'last_refill', now)
  return 0
end
redis.call('HMSET', KEYS[1], 'tokens', available - 1, 'last_refill', now)
return 1

The alternative is optimistic concurrency with WATCH and MULTI/EXEC: watch the key, read it, construct the conditional update, and retry if another client changed the key before execution. This is valid, but contention causes transaction aborts and retries, each adding another round trip. Lua can branch on values it just read and complete the transition in a single round trip, making it simpler and more reliable for a hot rate-limit key.

Choose an algorithm for bursts and fairness

Start with the traffic shape you need

The algorithm is a policy choice, not an implementation detail. A fixed-window counter is easy to reason about, but it can admit a boundary burst: with a 1,000-request limit, a client can send 1,000 requests in the last second of minute N and another 1,000 in the first second of minute N+1. Both counters remain within their limits, while the backend receives 2,000 requests in two seconds.

Choose the compromise deliberately

A sliding-window log records each request timestamp and checks the requests still inside the window. That gives accurate decisions, but its storage grows with request volume; Redis's comparison characterizes it as O(n) entries. A sliding-window counter stores the current and previous window counts, then interpolates between them according to how far you are into the current window. It uses much less memory than a log and blunts the boundary burst, at the cost of an approximation.

For a user-facing API with legitimate short bursts, choose a token bucket when the policy is “average rate plus bounded burst.” Tokens refill at a fixed rate, each request consumes one token, and the bucket capacity sets the largest immediate burst. Once the bucket is empty, requests are rejected until tokens refill, unless you explicitly add a separate queueing mechanism. This permits bursts up to capacity while smoothing average throughput; Redis's comparison summarizes the behavior as Allows controlled bursts.

You can also apply two independent controls to the same API key: a token bucket for request rate and a concurrent-request limiter for work already in flight. The first limits how quickly requests start; the second limits how many expensive operations occupy the service simultaneously. This combination is more expressive than forcing one algorithm to represent both rate and concurrency.

When Redis is not on every request

A distributed token bucket can move some decisions to each API server. Each node keeps a local bucket and periodically receives a refill allocation from a central quota. That reduces Redis request volume, but the allocation is temporarily stale: one node may spend quota that another node has not yet observed. Accept this when approximate global enforcement is preferable to the latency and capacity cost of synchronizing every request. Keep the shared Redis bucket when the quota must be enforced closely across servers.

Make failure and multi-region behavior explicit

Choose what happens when Redis disappears

Redis is on the critical path, so its outage must produce an explicit decision rather than an accidental one. In fail-open mode, the limiter allows requests when it cannot read or update the counter. The public API remains reachable, but an unbounded retry storm or burst can flood the upstream service. In fail-closed mode, the limiter rejects requests because it cannot prove that they are within quota. That protects the upstream resource, but a Redis outage becomes an API outage for otherwise valid clients.

The circuit breaker should change the decision path after Redis failures cross an operational threshold, not silently hide the dependency failure. Log the transition, count allowed requests while degraded, and alert on the duration and volume of fail-open traffic. When Redis recovers, close the breaker only after health checks succeed. Replication and failover risk therefore belongs in the design: a replicated Redis deployment can reduce the chance that one node failure disables enforcement, but a failover can still create a period in which the counter state or availability is uncertain.

Choose between global precision and regional latency

A single cross-region Redis cluster gives every API server one quota authority, which makes a global limit easier to enforce. The cost is a cross-region call on every rate-limit decision, adding network latency to every API request and making the distant store part of the request path. Gravitee describes the same pressure directly: synchronous calls to a central rate-limiting service can add latency to every request.

Regional Redis clusters remove that cross-region round trip. Each region can decide locally, then synchronize quota state asynchronously. You trade lower request latency and better regional availability for inconsistent counts: during the synchronization delay, two regions can each believe that the same API key still has capacity. A user can therefore exceed a global quota by distributing requests across regions before the updates converge. This is the consistency-versus-availability choice in operational form: a strongly coordinated global counter rejects more accurately but depends on a remote authority; independent regional counters keep serving but permit bounded quota leakage.

Identify what breaks first and what it costs

The first bottleneck is latency, because every request synchronously consults and updates the counter store. That network hop sits directly between the gateway and the upstream service; its p99 becomes part of the API's p99. Treat the limiter as its own SLO boundary: measure Redis command latency and alert when p99 exceeds 5 ms, rather than hiding it inside total request latency. A local cache or sidecar removes that hop from most requests, but the price is temporarily weaker enforcement.

Capacity arrives before memory does

At the worked scale of 100 K RPS, one Redis node sits at the lower edge of the cited 100 K–1 M operations/second range—up to 10× below its upper end, but with no comfortable margin for failover, replication, traffic spikes, or more than one operation per request. The 10 M-key estimate is approximately 1 GB, so memory is not the first constraint in this example; the hot write path and its availability are. Sharding by API key spreads load, but it also makes failover, resharding, and hot keys operational concerns.

The placement comparison makes the cost ordering explicit. Centralized Redis gives every API server and internal caller one shared count, which is the strongest choice for a hard global limit, but every decision depends on the store. Regional Redis removes the cross-region hop and isolates a regional failure; synchronization can nevertheless let a client exceed its global quota by distributing requests across regions. Local or sidecar enforcement is the latency and Redis-RPS optimization: a local in-memory counter synced to Redis every 100 ms can diverge for that interval, and the divergence grows with the number of enforcing nodes.

Policy dimensions multiply the operational surface

Adding per-endpoint limits changes more than the key prefix. Each user, API key, IP, and endpoint combination can create another logical counter, while policy lookup must select the same rule at the gateway and at internal services. A gateway-only limiter is cheaper to operate, but service-to-service calls can bypass it; protecting both the global client quota and sensitive downstream resources requires coordinated global and local limits. The cost is more keys, more lookups, and more opportunities for policy drift.

Use a hard limiter when exceeding the quota must protect a fragile or expensive backend: reject immediately and return 429. For a softer limit, spend the scaling budget on queueing or graceful degradation instead of making every excess request contend for Redis. At larger throughput, local pre-approval or periodic synchronization can reduce central traffic, but the resulting stale quota lag means the limiter is no longer an exact global gate. Monitor Redis latency, memory, middleware errors, throttled requests, and 429s per endpoint so the first degradation is visible before the upstream service becomes the bottleneck.