Designing a distributed rate limiter

My first version of a rate limiter was an in-memory map of counters. That explains the algorithm, but it stops being a global limit as soon as the service runs on several instances.

client requests      │      ▼load balancer  ┌───┼───┐  ▼   ▼   ▼app1 app2 app3

If every instance independently allows 100 requests per minute, the system may allow close to 300. Restarting an instance also resets its state. A distributed rate limiter needs a shared decision boundary or a controlled way to divide one global budget among local decision makers.

The difficult part is not choosing Redis. It is defining the policy, making each state transition atomic, deciding the acceptable consistency and specifying what happens when the limiter itself is slow or unavailable.

Start with an exact policy

“100 requests per minute” leaves several questions unanswered. A clearer policy looks like this:

For each authenticated tenant, allow an average of 100 requests per second to the payments API. Permit a burst of 20. A transfer costs five units while a status lookup costs one. Return a retry time when capacity is exhausted.

That statement defines:

Identity: authenticated tenant.
Scope: payments API.
Sustained rate: 100 units per second.
Burst: 20 immediately available units.
Cost: operation-dependent.
Response: a rejection that tells the caller when to retry.

Before choosing an algorithm, I write down six policy dimensions.

1. Who is limited?

Possible identities include:

user IDtenant IDAPI keysource IPdevice IDservice identity

An IP address is easy to obtain but often represents many users behind NAT. It can also change or be forged through incorrectly trusted proxy headers. Authentication credentials provide a stronger identity when available.

2. What is being limited?

The same tenant may need different limits for reads, writes and expensive operations. The key can include route, method, product tier or another policy dimension:

rate-limit:{tenant}:payments:POST-transfer

Raw URLs are dangerous keys because IDs and query values create unbounded cardinality. Use a normalized route name such as POST:/transfers/{id}.

3. What counts as one unit?

Request counting assumes all work costs the same. A better limiter can consume weighted units:

status lookup       = 1 unitsearch request      = 2 unitslarge export        = 20 unitsmodel inference     = estimated input + output units

The cost must be known before admission or conservatively reserved and adjusted afterward.

4. Are bursts allowed?

A fixed window allows accidental boundary bursts. A token bucket makes burst capacity explicit. A leaky-bucket queue can smooth output when the downstream system needs a steady arrival rate.

5. How global must the limit be?

“Global” can mean:

Across goroutines in one process.
Across instances in one region.
Across every region.
Across several related endpoints.

The wider the scope, the more coordination sits on the request path.

6. What accuracy is required?

A billing or security quota may require tight enforcement. An overload-protection limiter can tolerate small temporary overshoot if that removes a cross-region dependency from every request.

This is a product and reliability decision, not only an implementation detail.

Algorithm and architecture are separate choices

The algorithm decides how time and capacity behave:

Algorithm	State	Accuracy	Burst behavior
Fixed window	One counter	Boundary approximation	Can double-burst at a boundary
Sliding log	Accepted timestamps	Exact rolling interval	Strict rolling limit
Sliding counter	Two counters	Weighted approximation	Smoother boundary
Token bucket	Tokens plus last refill	Exact rate model	Controlled burst capacity
Leaky bucket	Water level or queue	Exact rate model	Rejects or delays overflow

The architecture decides where the state lives and who can update it:

local mapshared Redisdedicated rate-limit serviceregional quota allocationsedge-local bucket plus global check

The algorithms with runnable Go implementations are covered in Learning rate limiter algorithms in Go. This note focuses on distributing the decision safely.

A baseline synchronous architecture

The simplest global design puts one rate-limit check on the request path:

client  │  ▼gateway or application  │  RateLimit(key, cost)  ▼rate-limit service  │  atomic state transition  ▼Redis primary / cluster shard  │  ├── allowed → continue to application  └── denied  → return 429

The application or gateway builds a descriptor from trusted request data. The rate-limit service resolves the matching policy and performs an atomic update against the correct Redis key.

Separating the rate-limit service from the application has advantages:

Policy logic can be shared across languages and services.
Redis access and scripts are centralized.
Configuration can change without redeploying every application.
Decision latency and failures have one observable boundary.

It also introduces another network hop and another service that must scale with request traffic.

For a small system, calling Redis directly from the application can be reasonable. The same atomicity and failure rules still apply.

The read–decide–write race

Consider a token bucket containing one token. Two application instances run this sequence concurrently:

app A reads tokens = 1app B reads tokens = 1app A decides allowapp B decides allowapp A writes tokens = 0app B writes tokens = 0

Two requests were admitted using one token. A transaction must treat the following as one state transition:

read previous statecalculate elapsed refillcheck capacityconsume cost when allowedwrite new stateset expiryreturn decision

Network round trips cannot be allowed between these steps.

An atomic Redis token bucket

Redis scripts and Redis Functions execute atomically on the server. That makes them useful for a short read–decide–write transition.

The state for one bucket can be a hash:

tokens       current available capacitylast_refill  timestamp used for the last refill calculation

This Lua script uses the Redis server's clock so application hosts do not supply conflicting timestamps:

-- KEYS[1] bucket key-- ARGV[1] capacity-- ARGV[2] refill tokens per millisecond-- ARGV[3] request cost-- ARGV[4] key TTL in milliseconds local key = KEYS[1]local capacity = tonumber(ARGV[1])local refill_rate = tonumber(ARGV[2])local cost = tonumber(ARGV[3])local ttl_ms = tonumber(ARGV[4]) local clock = redis.call("TIME")local now_ms = tonumber(clock[1]) * 1000 +    math.floor(tonumber(clock[2]) / 1000) local values = redis.call("HMGET", key, "tokens", "last_refill")local tokens = tonumber(values[1])local last_refill = tonumber(values[2]) if tokens == nil then    tokens = capacity    last_refill = now_msend local elapsed = math.max(0, now_ms - last_refill)tokens = math.min(capacity, tokens + elapsed * refill_rate) local allowed = 0local retry_after_ms = 0 if tokens >= cost then    tokens = tokens - cost    allowed = 1else    retry_after_ms = math.ceil((cost - tokens) / refill_rate)end redis.call("HSET", key,    "tokens", tokens,    "last_refill", now_ms)redis.call("PEXPIRE", key, ttl_ms) return {allowed, tostring(tokens), retry_after_ms}

The script enforces several invariants:

0 ≤ tokens ≤ capacityelapsed time never removes tokensone admitted request consumes its complete costthe read and update cannot interleave with another request

Returning tokens as text avoids losing the fractional part through Redis Lua's integer response conversion. The caller parses three values into a decision:

type Decision struct {	Allowed    bool	Remaining float64	RetryAfter time.Duration}

The TTL should exceed the time needed to refill an empty bucket. Once a full bucket has remained inactive long enough, deleting it is safe because recreating it full produces the same logical state.

Why a script must stay small

Atomic Redis scripting uses blocking execution semantics. A slow script delays other clients of that Redis server. Rate-limit scripts should do bounded work over a small number of fields. Never scan a large keyspace or process an unbounded timestamp log inside the request path.

Redis 7 introduced Functions as a server-managed alternative to application-owned EVAL scripts. Functions improve deployment and version management. The atomicity requirement remains the same.

Fixed-window state in Redis

A fixed-window limiter appears to need only:

INCR keyEXPIRE key 60

Those two commands are individually atomic, but the pair is not one atomic policy transition. A client can increment the key and fail before setting expiry. The counter may then live forever.

A short script can increment and set expiry only when creating the window. Another approach is a native command that combines the needed bound and expiration behavior when the deployed Redis version supports it.

The key should identify the fixed window:

rate-limit:{tenant}:transfer:29300142

Including the window number avoids extending the lifetime of an old counter. Expiry still cleans up historical keys.

Sliding logs and sorted sets

An exact sliding-window log can use a sorted set:

score  = request timestampmember = unique request ID

One atomic operation must:

Remove entries older than the cutoff.
Count remaining entries.
Add the current request if capacity exists.
Refresh key expiry.
Return the decision and oldest relevant timestamp.

The exact log has memory proportional to admitted requests. A hot tenant with a limit of one million requests per minute may retain close to one million entries. The data structure can be correct but economically wrong.

Use exact logs for lower-volume policies that genuinely need auditability or rolling precision. Token buckets and sliding counters have constant state per key.

Sharding the limiter

One Redis primary eventually becomes a throughput and availability boundary. Redis Cluster partitions keys into hash slots and assigns slots to primary nodes.

The rate-limit key naturally provides a shard key:

hash(rate-limit:{tenant}:{policy}) → cluster slot → Redis primary

Requests for different tenants spread across shards. Every update for one key still reaches the same shard, which preserves atomic state transitions for that bucket.

The hot-key limit

Sharding does not split one key. A single global policy such as:

rate-limit:all-users:search

routes every decision to one Redis shard. Adding cluster nodes does not help that key.

Options include:

Divide the global budget into regional or instance allocations.
Use a small local limiter before the global key.
Aggregate usage asynchronously and accept bounded overshoot.
Change the policy from one global key to tenant or route keys.

The policy determines whether splitting is legal. A strict global maximum cannot be partitioned without coordinating the partitions.

Multi-key decisions in a cluster

A request may need to satisfy several limits:

tenant-wide limitroute-specific limitglobal emergency limit

In Redis Cluster, an atomic script normally needs its keys in one hash slot. Hash tags can force related keys into the same slot:

rate-limit:{tenant-42}:allrate-limit:{tenant-42}:transfers

That enables a tenant-wide and route limit to be checked together. It also deliberately places all of that tenant's policy keys on one shard.

A truly global key and tenant key do not naturally share a slot. Checking them sequentially creates partial consumption: the first bucket may consume capacity before the second denies. Possible responses are:

Accept conservative overcharging as a policy property.
Check the most restrictive limit first.
Allocate the global budget into shard-local leases.
Use a separate coordinator for the strict multi-key decision.
Redesign the policy so one request has one authoritative bucket.

There is no free atomic transaction across independently sharded owners.

Replication does not mean strict consistency

Redis replication improves availability, but a replica can lag its primary. Reading rate-limit state from replicas can admit traffic based on stale capacity. Admission checks should go to the authoritative writable owner.

Failover also raises a harder question: can recently acknowledged writes be missing on the promoted replica? The exact answer depends on the Redis deployment, persistence settings and acknowledgement policy. A design that requires zero overshoot must examine those guarantees rather than assuming “Redis is replicated” is sufficient.

For overload protection, a small amount of failover overshoot may be acceptable. For a contractual quota, the system may need stronger accounting or reconciliation.

Cross-region limiting

A synchronous request to one global Redis cluster provides a clear owner, but distant regions pay network latency on every application request. A network partition can also make an entire region unable to obtain decisions.

There are three broad models.

1. One global synchronous owner

region A ─┐region B ─┼→ global limiter → one authoritative stateregion C ─┘

This gives the tightest global decision but adds cross-region latency and creates a wide failure dependency.

2. Independent regional limits

global limit 900/sregion A local limit 300/sregion B local limit 300/sregion C local limit 300/s

Every region decides locally. Latency and availability improve, but static division wastes capacity when traffic is uneven.

3. Leased or assigned regional quotas

A global controller periodically assigns budgets based on observed demand:

global budget    │    ├── lease 500/s → region A    ├── lease 300/s → region B    └── lease 100/s → region C

Regions enforce their assigned quota locally and report usage. The controller adjusts future assignments. This removes a global RPC from the hot path and handles uneven demand better than static division.

The trade-off is bounded inconsistency. During a partition, regions may continue spending leases that the controller cannot immediately rebalance. Lease TTLs limit how long stale assignments remain valid.

Envoy's rate-limit quota model follows this broad shape: data-plane instances report usage and receive quota assignments that can be updated over a streaming connection.

Combining local and global limiting

A practical gateway can use two stages:

request   │   ▼local token bucket   │ protects the global service from extreme bursts   ▼global rate-limit check   │ enforces shared tenant policy   ▼application

The local bucket is not a replacement for the global decision. It is a fast coarse filter. It can immediately reject an obviously abusive burst before that burst becomes load on Redis or the rate-limit service.

Envoy documents this local-plus-global arrangement. The local stage also provides partial protection when the global service is degraded.

The local capacity must be chosen carefully. If every one of 100 gateways has a local burst of 20, the fleet can admit a 2,000-request instantaneous burst before the global layer reacts.

Batching and token leasing

Calling Redis once per request makes the limiter easy to reason about:

one request → one atomic global decision

At very high traffic, that can be too expensive. An application instance can reserve a batch of tokens:

instance asks global store for 100 tokensglobal bucket atomically removes 100instance admits the next 100 units locally

This reduces remote operations by up to the batch size. It also introduces unused reserved capacity and failure loss. If ten instances each hold 100 tokens, up to 1,000 units sit outside the global owner.

Leases can expire and be periodically renewed, but returning unused tokens safely is difficult after uncertainty. A timed-out reservation request may have succeeded remotely even if the caller never saw the response.

Batching is an explicit trade: lower decision cost in exchange for bounded under-utilization or overshoot.

Time is shared state too

Rate algorithms use elapsed time, so the clock affects correctness.

If every application sends its local wall-clock timestamp, skew can create or remove capacity. A host whose clock jumps forward may refill a bucket too much. A later request from a slower clock can appear to move backward.

Using Redis TIME inside the atomic operation gives one clock per authoritative shard. The script should still clamp negative elapsed time to zero because a failover can move the key to a host with a different wall clock.

For local in-process buckets, Go's time.Time carries a monotonic reading when produced by time.Now, which is useful for elapsed-duration calculations. Serializing the value across processes loses that local monotonic relationship.

Global time is never free. The design should name which clock owns the decision and how backward movement is handled.

Failure behavior is part of the policy

The rate limiter is usually called before the protected service. If it becomes slow, it can become the outage it was meant to prevent.

Every policy needs an explicit failure mode.

Fail open

Allow the request when the limiter cannot decide.

advantage: application remains availablerisk: downstream overload or quota bypass

This can suit ordinary reads where availability is more important than exact quota.

Fail closed

Deny the request when the limiter cannot decide.

advantage: protects expensive or sensitive operationsrisk: limiter outage becomes application outage

This can suit abuse-sensitive writes, costly third-party calls or contractual hard limits.

Use a stale local budget

Continue with the last valid quota assignment for a short TTL. This is useful in leased architectures, but the permitted uncertainty must be bounded.

Shadow mode

Calculate decisions and record what would have been denied without enforcing them. Shadow mode is valuable before launching a new policy because it reveals unexpected high-cardinality keys and legitimate traffic bursts.

The error path should distinguish:

OVER_LIMIT       valid decision: caller used its capacityUNAVAILABLE      limiter could not make a decisionINVALID_POLICY   configuration or descriptor error

Treating every Redis timeout as “over limit” hides outages. Treating every timeout as “allow” hides loss of protection.

Timeouts and ambiguous outcomes

The rate-limit RPC needs a deadline shorter than the application's remaining request budget. Envoy's global filter exposes a rate-limit-service timeout and a failure-mode setting for this reason.

A timeout does not prove the Redis update failed:

client sends consume requestRedis applies itresponse is delayed or lostclient times outclient retriessame logical request may consume twice

Atomic execution prevents concurrent double spending inside one operation. It does not provide exactly-once delivery across network retries.

Possible strategies are:

Accept conservative double charging because it is rare and safe for overload protection.
Attach a request ID and retain a bounded deduplication record.
Avoid automatic retries for ambiguous consume operations.
Reserve capacity through an idempotent lease protocol.

Deduplication adds memory and another lifecycle to manage. It is justified only when the product requires it.

Returning a useful HTTP response

When an HTTP request exceeds its rate, return 429 Too Many Requests. RFC 6585 allows a Retry-After header that tells the client how long to wait.

HTTP/1.1 429 Too Many RequestsContent-Type: application/jsonRetry-After: 2 {"error":"rate limit exceeded","retry_after_seconds":2}

The response should be based on the policy that actually denied the request. If several limits apply, the longest required wait is usually the useful retry time.

Do not expose an internal Redis key or sensitive tenant classification. Return a stable policy name if clients need to distinguish quotas.

Clients should use the provided delay and add jitter before retrying. Retrying every rejected request at the exact reset instant creates another synchronized burst.

Rate limiting is not every overload control

Several controls solve related but different problems.

Control	Limits	Useful when
Rate limiter	Arrivals per unit of time	A caller or operation sends too much traffic
Concurrency limiter	Work currently in flight	Latency grows with simultaneous work
Circuit breaker	Calls to an unhealthy dependency	Repeated failures should stop temporarily
Queue bound	Waiting work	Backlog would consume memory or violate latency
Load shedding	Work accepted under saturation	The service must protect essential traffic

A service can be under its request-per-second limit and still overload if each request becomes ten times slower. A concurrency limit reacts to that in-flight buildup more directly.

A robust boundary may combine all of them:

authenticate→ apply caller rate policy→ check queue or concurrency capacity→ avoid unhealthy dependency through circuit breaker→ admit or shed work

Capacity planning

A synchronous global design performs approximately one limiter operation per checked request. The service must account for:

Peak decision rate, not only average traffic.
Redis script CPU time.
Network connections and pool limits.
Key count and bytes per key.
Replication and persistence overhead.
Hot-key concentration.
Expiry work.
Policy configuration lookups.

If one million active tenants each have five policy keys, the system may hold five million buckets. TTL avoids retaining inactive tenants forever, but active cardinality remains.

Benchmark with realistic key distribution. A uniform test hides a hot enterprise tenant. A single-key test hides cluster scalability. Include policy reloads, Redis failover and network timeout behavior.

Observability

Useful metrics include:

decisions allowed by policydecisions denied by policylimiter errorsfail-open allowsfail-closed deniesdecision latency percentilesRedis latency and errors by shardhot keys or hot policy classesactive key cardinalityscript execution timeremaining-capacity distributionquota lease utilization

Avoid placing raw user IDs in metric labels because that creates unbounded time-series cardinality. Log sampled or hashed identities when debugging needs them.

Measure the protected service too. A limiter with a low denial rate can still be ineffective if downstream concurrency and latency continue rising.

Alerts should separate:

A real increase in over-limit traffic.
A rate-limit-service outage.
Redis saturation.
A policy rollout that unexpectedly matches more requests.

Correctness tests

The storage implementation should be tested against invariants rather than only example timestamps.

Algorithm properties

capacity never becomes negativecapacity never exceeds configured maximumidle time cannot refill beyond maximuman accepted request consumes its cost exactly once inside one operationbackward time does not create capacitydifferent keys do not share stateexpired inactive state recreates to the correct full state

Concurrent tests

Start many goroutines against one key with a bucket capacity of 100. Exactly 100 units should be admitted before any refill. Run the test through several application connections so it exercises server-side atomicity rather than a client mutex.

Failure tests

Inject:

Redis timeouts before and after writes.
Primary failover.
Stale replica reads if they are accidentally enabled.
A missing cached script.
Policy configuration changes during traffic.
Region-to-controller disconnection for quota leases.
Clock movement between Redis owners.

Verify not only availability but the maximum overshoot or under-utilization the policy permits.

A practical design progression

I would build the system in stages.

Stage 1: local implementation

Implement and test the algorithm with an injected clock. This makes boundary behavior explicit.

Stage 2: one atomic Redis key

Move one bucket transition into a short script or Function. Add TTL and return a structured decision.

Stage 3: dedicated service boundary

Centralize descriptor construction, policy lookup, Redis access, metrics and failure behavior when several applications need the same limiter.

Stage 4: Redis sharding

Shard by tenant-policy key. Find hot keys and decide whether global policies must be decomposed.

Stage 5: local protection

Add a coarse local bucket to protect the global service from extreme bursts. Keep the global check for shared accuracy.

Stage 6: quota leases only when required

Move decisions local through quota assignment when global per-request coordination becomes the bottleneck. Document the permitted overshoot and lease-expiry behavior.

Starting with leases or multi-region consensus before measuring the baseline usually creates complexity without knowing which trade-off is necessary.

The compact mental model

Policy defines who, what, rate, burst, cost and failure behavior.Algorithm defines how capacity changes over time.One owner must make each bucket transition atomically.Sharding spreads different keys but cannot split one hot key.Replication improves availability but does not automatically provide strict decisions.Cross-region accuracy costs latency or requires bounded local quotas.Local limiting protects the global limiter; it does not replace shared enforcement.Timeouts create ambiguous outcomes, so retries need an explicit rule.429 describes a valid rejection; dependency failure is a different event.

A distributed rate limiter is a small state machine placed on a critical path. Its usefulness comes from predictable behavior during contention and failure, not only from returning the right answer in a single-threaded example.