Skip to content
Katabench
Try free
9 min read The Katabench team

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:

C#
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:

Text
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, 100

Those 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.

One limit needs one counter

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

  1. Any instance sends the caller's key
  2. The store refills, compares and spends in one step
  3. 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.

Measured against a local Redis container. A refused or degraded decision is an ordinary outcome each route has to plan for.

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 check and the update are one operation

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.

Lua
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.

Decide what happens when the store stops answering

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.

C#
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.

Tell the client what the counter knows

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
HTTP/1.1 429 Too Many Requests
Retry-After: 1
RateLimit-Policy: "per-key";q=100;w=10
RateLimit: "per-key";r=0

The 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.

Regions make the number approximate

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.

Text
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% over

The 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.

The numbers a limiter owes its operators

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

More like this: System Design Studio →

Get new katas and .NET tips in your inbox

A short note when fresh kata land, plus the C# and performance tricks behind the grading. No spam, unsubscribe anytime.