Design a rate limiter: the system around the algorithm
Design a rate limiter that holds across instances: GET then INCR admitted up to 129 requests against a limit of 100, and an atomic script admitted exactly 100.
A limiter that reads a Redis counter and then increments it admitted between 112 and 129 requests against a limit of 100. A unit test has one caller and passes, so the code looks finished:
var current = (long?)await db.StringGetAsync(key) ?? 0;
if (current >= limit)
{
return false;
}
await db.StringIncrementAsync(key);
return true;Four connections standing in for four instances, 16 concurrent clients on each, about 2,000 requests, Redis 8 in a local container. The shared-store rows ran five times each, with the bucket's refill set near zero so its capacity is the whole budget:
counter in each instance 400
GET, then INCR 128, 112, 128, 128, 129
INCR, compare the result 100, 100, 100, 100, 100
Lua token bucket 100, 100, 100, 100, 100Those rows have nothing to do with the choice of algorithm, which rate limiting algorithms covers. They come from the system around it: where the count is kept, what happens when the store stops answering, what the client gets told, and what a second region does to the number.
The first row is the default behavior of most in-process limiters. ASP.NET Core's documentation says counters are held in memory per instance, so the effective limit is the configured limit multiplied by the instance count. A limit that changes every time the autoscaler does is a guess about capacity.
So a caller over budget has to get the same answer whichever instance the request lands on, and that answer should cost little. Several designs get there, and each gives something up. Dividing the limit by the instance count needs no shared state, but it drifts with every scale event and punishes callers whose traffic lands unevenly. Pinning each caller to one instance keeps a local count honest until that instance restarts. A shared store gives one number at the price of a network call per request and a new dependency. Where the check runs is a separate choice: early in the path a refusal costs almost nothing and knows little, while deep in the application it knows what the endpoint costs and which plan the tenant is on, after work has been spent. The rest of this post follows the shared store, as it has the most failure modes to reason about.
Where the count is kept decides the real limit
A counter in each instance
- Instance 1: 100
- Instance 2: 100
- Instance 3: 100
- Instance 4: 100
Admitted against a limit of 100: 400
One shared count, one atomic decision
- Any instance sends the caller's key
- The store refills, compares and spends in one step
- The answer is the same however many instances run
Admitted against a limit of 100: 100
Then the store stops answering
-
No deadline of your own
5,992 ms
The client library's default timeout. Every request waits behind the limiter.
-
50 ms deadline, read route
50 ms, admit
Fails open. Capacity has headroom, and the decision is counted as degraded.
-
50 ms deadline, login route
50 ms, refuse
Fails closed. A guess that admits here costs more than a retry.
Then decide what a caller is. An IP address is cheap to check, but an office behind one NAT shares a single address and one caller can hold many. Your proxy chain can also lie about which address it saw, as X-Forwarded-For spoofing shows. An authenticated identity, where the route has one, is the party you made a promise to.
The second row admits 128 because 28 requests read a count below 100 before other instances'
increments landed. Swapping the order fixes it for a plain counter: INCR returns the new value, so
each request compares a number nobody else can have seen. Expiry reopens the gap. The
INCR documentation describes the race where a client
increments and dies before setting the expiry, leaving the key behind.
A token bucket reads, computes and writes, so it needs the whole sequence to run as one step on the server. Redis guarantees that for scripts: all other server activity is blocked while one runs, so its effects are either entirely in the past or entirely in the future.
local capacity = tonumber(ARGV[1])
local refill = tonumber(ARGV[2]) -- tokens per second
local t = redis.call('TIME') -- the server's clock, shared by every instance
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000
local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts = tonumber(state[2]) or now
tokens = math.min(capacity, tokens + (now - ts) * refill)
local allowed = 0
if tokens >= 1 then
tokens = tokens - 1
allowed = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / refill) + 1)
-- Lua numbers lose their fraction on the way out, so the wait travels as a string.
return { allowed, math.floor(tokens), tostring(math.max(0, (1 - tokens) / refill)) }TIME reads the store's clock, so four instances with skewed clocks cannot mint tokens for each other. EXPIRE runs inside the script, so an idle caller's state cannot
leak. The final string exists because Redis
drops the decimal part of any Lua
number it returns.
MEMORY USAGE reported 83 bytes for one bucket, which understates the real cost. Loading a million
buckets through this script on Redis 8, with a refill slow enough that none expired, took
used_memory from 1.56 MiB to 112.51 MiB, about 116 bytes per caller (116,333,984 bytes / 1,000,000),
and RSS reached 137.71 MiB. Since each script touches one key, a
cluster can spread callers across shards freely. The limit on scale is the single thread that
serves each shard, which is the reason to keep the script this short.
A limiter is now a synchronous dependency of every request, so its failure deserves a test. With the
container frozen by docker pause, a call with no deadline of its own threw
RedisTimeoutException after 5,992 ms. Each request behind that limiter would have waited six
seconds to learn nothing. Adding a 50 ms deadline brought the decision back in 50 ms.
With the store frozen, a limiter with no deadline of its own held a request for 5,992 ms. A 50 ms deadline reached the same non-answer in 50 ms, and each route's policy took it from there.
public async Task<Decision> CheckAsync(string key)
{
try
{
var reply = (RedisResult[])(await redis
.ScriptEvaluateAsync(Script, [$"rl:{key}"], [policy.Capacity, policy.RefillPerSecond])
.WaitAsync(Deadline))!; // 50 ms
return new Decision(
Allowed: (int)reply[0] == 1,
Remaining: (int)reply[1],
RetryAfterSeconds: double.Parse((string)reply[2]!, CultureInfo.InvariantCulture),
Degraded: false);
}
catch (Exception ex) when (ex is RedisException or TimeoutException)
{
// The store did not answer in time. This route's policy decides, not the exception.
return new Decision(policy.FailOpen, Remaining: 0, RetryAfterSeconds: 30, Degraded: true);
}
}Failing open suits read traffic with headroom: the limiter is briefly off, and capacity usually
survives. Envoy's global rate limit filter
leans the same way,
letting requests through on a service error unless failure_mode_deny is set, in which case the
caller gets a 500. Failing closed suits routes where one wrong admission costs real money or an
account, such as login attempts or SMS sends. A middle option is an in-process fallback with the
budget divided by instance count, so 100 becomes 25 per instance across four. It is the first row of
that table, used on purpose.
During an outage, 50 ms on every request still adds up. A circuit breaker stops calling the store after a run of failures and skips the wait until a probe succeeds.
The 429 response, Retry-After and client backoff are covered in
rate limiting algorithms. A shared store adds a count the response
can report. With a capacity of 100 and a refill of 10 per second in a minimal ASP.NET Core app, 400
requests on one connection produced 108 admissions, the 100 in the bucket plus 8 refilled during the
burst, and 292 refusals. The first refusal, trimmed to the relevant headers:
HTTP/1.1 429 Too Many Requests
Retry-After: 1
RateLimit-Policy: "per-key";q=100;w=10
RateLimit: "per-key";r=0The script's wait was a fraction of a second, rounded up because Retry-After counts whole seconds.
The RateLimit fields come from an
IETF draft, still an
Internet-Draft at version 11, so treat Retry-After as the contract. On a degraded decision, leave
RateLimit out, since the store gave no count to report.
Say the limit is 6,000 requests a minute per customer across three regions. Assume 1 ms to a store in the same region and 70 ms to one elsewhere. These are planning assumptions, so substitute yours.
one global store: +70 ms on every request from two of the three regions
split the budget: 60% / 30% / 10% of traffic = 3,600 / 1,800 / 600 per minute
share counts late: sync every 5 s, caller at 100 req/s in each region
unseen by any one region = 2 x 100 x 5 = 1,000 requests
worst case = 6,000 + 1,000 = 7,000, or 17% overThe global store gives an exact count and charges for it on every request, then ties all three regions to one region's availability. Few limits are worth that. Splitting the budget can never exceed 6,000, so it fits contractual quotas. Its cost appears when a customer's traffic shifts: they get refused at 600 in one region with thousands unspent elsewhere, until the next rebalance. Local counting with periodic sharing keeps latency at 1 ms and accepts the overshoot, which is fine for a limit protecting capacity and wrong for one you bill against.
Export admitted and refused counts per policy, store latency against the 50 ms deadline, and the count of degraded decisions. A nonzero degraded count means the limit is currently not being enforced, and that deserves an alert of its own. A top-refused-keys list separates one abusive customer from a limit set too low for everyone. Pausing the store in a test environment took one command here and produced the 5,992 ms above, a number no design review would have found.
The System Design Studio comes at this from a different failure in "Rate-Limit at the Gateway": one scraper saturates the app and every other user pays for it in timeouts. Where you put the limit is your call there, and how it works explains what the checks report about the topology you draw.
Practice System Design
- Open in the Studio: Route Through the App
System Design Studio Easy Free with an account
Route Through the App
Build a safe three-tier request path that keeps clients away from the database.
- Open the Pro kata: Rate-Limit at the Gateway
System Design Studio Medium Katabench Pro
Rate-Limit at the Gateway
One scraper hammers the API and every real user pays for it. Put a gateway in front that counts requests in a shared store and sheds abusive traffic before it reaches the app.
More like this: System Design Studio →