Distributed Rate Limiting

Most of us know what rate limiting is: a service decides how many requests a client may make in a window of time and turns the rest away. On a single server that is a counter in memory and a few lines of code. Fewer people have had to think about distributed rate limiting, and it is the version that matters the moment a system runs on more than one machine. Amazon, Uber, Databricks and Cloudflare all enforce limits across fleets of servers, and each has built something quite different to do it.

Distributed rate limiting is the answer to that problem: one global limit, enforced consistently across many servers, containers or regions, rather than a separate limit per instance. It protects the same three things single-node limiting does, now at the scale of a fleet.

• The building. Backends can be overwhelmed by traffic spread across instances. A client sending 100 requests a second to each of 10 servers is running at ten times a global limit of 100.
• The other guests. In a multi-tenant system one noisy tenant should not degrade the service for everyone else, on any node.
• The bar tab. Compute, bandwidth and third-party API calls cost money in proportion to total throughput, not per-instance throughput.

Here is the failure that catches every team once. You build a clean in-memory rate limiter, test it, ship it. Then you scale to ten servers behind a load balancer, and your limit of 100 requests per second quietly becomes 1,000, because each server is counting on its own.

The fix is shared state: every server checks the same counter. But shared is not enough on its own. The counter also has to be atomic. Suppose a limiter reads the count, decides, then writes the new value back as three separate operations, and a client has exactly one request left.

The fix is to make the whole check-and-decrement one indivisible operation that runs where the data lives. This is why Redis plus Lua is the standard pairing. Redis runs a script to completion before it serves any other command, so no two servers can ever act on the same count.

-- KEYS[1] bucket key   ARGV: rate (tokens/s), capacity, tokens requested
local rate      = tonumber(ARGV[1])
local capacity  = tonumber(ARGV[2])
local requested = tonumber(ARGV[3])

-- The clock comes from Redis, not from the caller.
local t   = redis.call("TIME")
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local state  = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens = tonumber(state[1]) or capacity
local ts     = tonumber(state[2]) or now

-- Refill for the time since the last request, never past capacity.
tokens = math.min(capacity, tokens + math.max(0, now - ts) / 1000 * rate)

local allowed = 0
if tokens >= requested then
  tokens  = tokens - requested
  allowed = 1
end

redis.call("HSET", KEYS[1], "tokens", tokens, "ts", now)
redis.call("PEXPIRE", KEYS[1], math.ceil(capacity / rate * 1000))
return allowed

The whole decision runs inside Redis and cannot be interrupted. The PEXPIRE lets a bucket that has refilled to full disappear, since it no longer holds any information.

The caller is short. The interesting line is the error branch.

// Take reports whether a request costing n tokens may proceed.
func (b *RedisTokenBucket) Take(ctx context.Context, key string, n int) bool {
    // Run sends EVALSHA and falls back to EVAL only when a node has not seen
    // the script yet, so the script body crosses the network once per node.
    allowed, err := b.script.Run(ctx, b.client, []string{key}, b.rate, b.capacity, n).Int()
    if err != nil {
        // Fail open: a limiter outage must not turn into an API outage.
        b.FailOpens.Add(1) // export it, alert on it
        return true
    }
    return allowed == 1
}

The Lua script and the full Go type are in this post's codes/ directory.

A Redis call on every request is the simplest correct design, and it is where most systems start. It is not where the largest ones stay. Real architectures fall into three broad patterns, sorted by how much coordination sits on the request path.

The algorithms are the same ones used on a single node. Distribution changes where their state lives and what has to be atomic.

Token bucket: the arcade coin dispenser

Each client has a bucket of tokens, refilled at a steady rate up to a capacity, and each request spends one. It is the most common algorithm in distributed systems because it takes two intuitive parameters and tolerates bursts. Distributed twist: the bucket lives in a shared store and the refill-and-spend must be atomic, which is exactly the Lua script in section 3.

Used by: Stripe, AWS API Gateway, Databricks.

Sliding window counter: the bouncer's estimate

Keep two counters per key: the previous fixed window and the current one. Weight the previous window by how much of it the sliding window still overlaps, and add the current count.

// Cloudflare's worked example, limit 50/min: 42 requests last minute,
// 18 so far this minute, 15 seconds in.
//   42 * (60-15)/60 + 18 = 49.5  -> under 50, allowed
elapsed := now.Sub(windowStart)
overlap := 1 - float64(elapsed)/float64(window)
estimate := float64(prevCount)*overlap + float64(currCount)
allowed := estimate < float64(limit)

Distributed twist: two integers per key is small enough to keep for every source address hitting every domain, where a log of per-request timestamps would not be. The estimate assumes traffic in the previous window was evenly spread, and in practice that holds up well: Cloudflare measured it on 400 million requests and found an average difference of 6% from the true rate.

Used by: Cloudflare.

Fixed window: the parking meter

One counter per key per clock window, with an expiry. The simplest option there is.

key := fmt.Sprintf("rl:%s:%d", clientID, time.Now().Unix()/60)

// One MULTI/EXEC: a crash between a bare INCR and EXPIRE would leave a
// counter that never expires, and a client limited forever.
pipe := rdb.TxPipeline()
count := pipe.Incr(ctx, key)
pipe.Expire(ctx, key, 2*time.Minute)
if _, err := pipe.Exec(ctx); err != nil {
    return true // fail open
}
return count.Val() <= limit

Used by: Lyft's ratelimit service, GitHub's primary limits.

Leaky bucket: the funnel

The bucket fills with each request and drains at a fixed rate. It comes in two forms. As a queue, excess requests wait their turn and leave at a steady pace. As a meter, the bucket is only a level, and a request that finds it full is rejected straight away. Distributed twist: the level (or the queue) is the shared state, so it has the same atomicity requirement as a token bucket.

Used by: Shopify's REST Admin API, as a meter.

Cost-based bucket: the smart funnel

Not an algorithm so much as a change of unit. Instead of counting requests, count what each request costs, and take that many tokens from the bucket. The same Lua script works unchanged: the cost goes in as requested.

// Computed from the query document before anything executes, so every
// instance that sees the same query arrives at the same number.
cost := QueryCost(fields, isMutation)

if !bucket.Take(ctx, "rl:"+shopID, cost) {
    // Throttled. Return the cost and the restore rate so the client can
    // work out for itself how long to wait.
}

Distributed twist: the cost calculation must be deterministic. If two instances could price the same query differently, the shared bucket would drain at a rate that depends on which server you happened to reach.

Used by: Shopify's GraphQL Admin API, GitHub's GraphQL API.

The algorithms at a glance

Scale: around 80 million requests per second across more than 1,100 services.

Uber's earlier limiters were Redis-based and configured service by service. At its scale that stopped working for several reasons at once. Configurations were inconsistent between teams, updates often meant redeploying servers, and the Redis limiters added latency and a fleet of their own to run. Keeping global counters that way would have needed hundreds of Redis clusters, with every request incrementing and reading a counter over the network.

The replacement, the Global Rate Limiter (GRL), lives in the service mesh that already relays RPCs between Uber's services. It is a three-tier feedback loop.

What changed

• No remote counter on the hot path. Each mesh client decides on a drop ratio it already holds in memory.
• Soft limits instead of hard stops. Over the limit, GRL drops a percentage of traffic across all instances rather than slamming a bucket shut, so a caller slightly over its allowance loses slightly more requests, not all of them.
• Limits set by data. A Rate Limit Configurator computes limits from weeks of historical peaks plus headroom, and pushes them through the same control plane.

Results

• For one critical service, removing Redis cut P99.5 latency by up to 90% and P50 by about a millisecond.
• A critical service rode out a 15× traffic surge, from 22K to 367K requests per second, without degradation.

Databricks' original design was the textbook one: an Envoy ingress gateway calling a rate limit service, backed by a single Redis instance. Three problems followed.

• Tail latency. P99 network latency to Redis of 10–20 ms in some cloud regions, and worse under heavy traffic.
• A throughput ceiling. Past a point, optimisation stopped buying more headroom.
• A single point of failure in that one Redis instance.

The rebuild rests on three changes.

• In-memory sharding. Using Dicer, Databricks' auto-sharding system, clients route directly to the server that owns their key, and that server holds the counts in memory. Redis is gone entirely.
• Client-driven batch reporting. Clients rate limit locally and optimistically, and report aggregated counts periodically (every 100 ms, for example) instead of making a remote call per request. The server answers with guidance on what to reject.
• Token bucket instead of fixed windows. A bucket counts continuously and can even go negative, which absorbs the overshoot that batching introduces and allows controlled bursts.

Result: tail latency improved by up to 10× in some cases, and server-side traffic now grows sub-linearly with request volume.

Stripe's API moves money, so an overloaded API is not just slow, it is failed payments. Its answer is not one limiter but four, each aimed at a different way things go wrong.

The per-user limiters are token buckets in Redis, and they fail open: a bug in the limiter code or a Redis outage must never block requests.

Cloudflare's rate limiting protects someone else's infrastructure. The whole point is to block excess traffic before it reaches the customer's origin server, and that pushes the limiter out to the edge, to hundreds of points of presence (PoPs) around the world handling several billion requests a day.

Synchronising counters between PoPs on every request would be prohibitively slow. Cloudflare avoids it with a property of its network: with anycast routing, traffic from a given IP address normally reaches the same PoP. So each PoP can count on its own, with no cross-PoP synchronisation at all.

Within a PoP, Cloudflare uses the sliding window counter from section 5. The alternatives do not fit. A log of per-request timestamps for every source hitting every domain is far too much memory, and a fixed window is too easy to game at the boundary. Two counters per key fit in memory and are hard to exploit.

Cloudflare checked how much accuracy the approximation costs. Over 400 million requests from 270,000 sources, 0.003% of requests were wrongly allowed or wrongly limited, with an average difference of 6% between the real rate and the estimate.

AWS is not rate limiting its own API here. It is selling you a rate limiter, as a set of settings in a console. That changes what matters most.

API Gateway uses a token bucket, and the reason is easiest to see from the customer's side. A token bucket has exactly two knobs: a rate, the steady requests per second, and a burst, the bucket's capacity. Both are simple enough to put in a form. By default, an account gets 10,000 requests per second with a burst of 5,000, per Region, and the settings nest. API Gateway applies them in this order:

LaunchDarkly did not pick one design. It built three, each placed at a different point on the accuracy-versus-coordination line, because its workloads need different things.

Floodgate

Written in Go on top of Redis, but Redis never appears on the request path. Every decision is made locally on the machine serving the request. In the background, each node periodically pulls the current node count and the overall count from central storage, so its share of the global limit follows the fleet as it scales. Auto-scaling tends to happen in small steps, so the drift between syncs is not material.

Poisson

The most interesting of the three. The pipeline has a fixed number of shards and traffic is spread across them, so the count on any one shard is random. A simple limit ÷ shards split would wrongly reject traffic whenever a shard got more than its fair share. Instead LaunchDarkly precomputes the 95% inverse CDF of the Poisson distribution for each limit and shard count, and uses that as each shard's local limit. The result is a 95% chance of never over-enforcing, with no coordination at all. As LaunchDarkly puts it, it is not really a distributed system, so it cannot fail.

Shopify uses two different models on two APIs, and the reasons for each are clear.

For GraphQL, Shopify calculates a cost for each query before running it and deducts that from the bucket. The documented rules are simple. Scalar and enum fields cost nothing. Each object costs 1 point. A connection is sized by the page it asks for (first or last), so page size multiplies everything nested inside it. A mutation costs 10. Points restore at a rate set by the plan: 100 points per second on Standard, 1,000 on Shopify Plus.

A throttled response includes the query's cost and the restore rate, so a well-written client can work out exactly how long to wait instead of retrying blind.

Lyft open-sourced ratelimit, a Go/gRPC service that implements Envoy's rate limit API. It became the reference implementation for Envoy's global rate limiting, which makes it the design many teams deploy first, often without knowing it.

• Domains and descriptors. A domain is a container for a set of limits. A descriptor is a list of key/value pairs, such as database=users, that selects which limit applies. One request can carry several descriptors and is checked against every rule that matches.
• Fixed windows in Redis. Limits are written as requests per second, minute, hour or day, and counted in Redis. Commands are pipelined, so the several counters one request touches cost one write and one read.
• A local cache for over-limit keys. An optional in-process cache remembers keys that are already over their limit, so a client hammering past its allowance is rejected without another trip to Redis.

Read side by side, these architectures share a handful of principles.

At extreme scale, the shared store becomes the bottleneck

Uber and Databricks both began with Redis on the request path and both took it off. Uber moved decisions into the service mesh and pushed only a drop ratio; Databricks moved counts into sharded memory and batched the reports. Neither found a faster store. Both stopped consulting one per request.

Approximation is a feature you size, not a flaw you tolerate

Cloudflare measured its error at 6% on average. LaunchDarkly picked a 95% confidence level on purpose. AWS documents its limits as targets. The mature designs do not pretend to be exact; they state how inexact they are, and choose that on purpose.

Decide your failure mode before it happens

• Stripe and LaunchDarkly's Centralized limiter fail open: if Redis is gone, traffic flows.
• Floodgate fails safe, because its decisions never depended on reaching Redis in the first place.
• Poisson has no dependency to lose.

Fail open favours availability; fail closed favours protection. Whichever you pick, pick it deliberately, and alert when it happens.

Cardinality drives architecture

A handful of keys, such as per-service or per-plan limits, can afford an exact central counter. Millions of keys, such as per-IP limits on every domain, cannot, and push you towards compact approximations and local ownership. Split your limits by cardinality before choosing one design for all of them.

Limit the thing that actually costs you

• GitHub's secondary limits cap CPU time, not just request count.
• Shopify's GraphQL API limits calculated query cost.
• Stripe limits concurrency alongside rate, and sheds test mode and GETs before POSTs and critical calls.

All three got there because request count stopped tracking request expense.

Separate the commercial limit from the protective one

AWS makes the split visible: a usage plan's monthly quota and its per-second throttle are different settings. "You have used your plan" and "you are going too fast right now" need different responses from the client, and folding them into one number helps neither.

Predictability is a choice with a cost on both sides

Discord returns detailed rate limit headers so a well-behaved client can avoid ever being limited. GitHub's secondary limits deliberately say less, so abusive clients cannot tune themselves to sit just under the line. Both are defensible; they serve different client populations.

The algorithm follows the traffic, not the other way round

• Token buckets suit Stripe's API, where short bursts from legitimate clients are normal.
• Shopify REST uses a leaky bucket to hand its backend a steady flow.
• Cloudflare uses a sliding window counter because per-request logs are impossible at its cardinality.
• Uber drops a percentage instead of hard-stopping, so a caller slightly over its limit loses slightly more traffic, not all of it.

1. Uber Engineering, Uber's Rate Limiting System. uber.com
2. Databricks Engineering, High Performance Ratelimiting at Databricks. databricks.com
3. Stripe Engineering, Scaling your API with rate limiters. stripe.com
4. Cloudflare, How we built rate limiting capable of scaling to millions of domains. blog.cloudflare.com
5. AWS, Throttle requests to your REST APIs for better throughput in API Gateway. docs.aws.amazon.com
6. LaunchDarkly Engineering, A tale of three rate limiters. launchdarkly.com
7. Shopify, API rate limits. shopify.dev
8. Lyft, ratelimit. github.com/lyft/ratelimit
9. Envoy, Rate limiting. envoyproxy.io
10. GitHub, Rate limits for the REST API. docs.github.com
11. Discord, Rate Limits. discord.com
12. Redis, Rate limiting. redis.io

Specific numeric limits change often. The architectural patterns here are stable; the numbers are not, so check each provider's live documentation before building against them.