Rate Limiter Design, in depth: requirements, placement, rule model, counter choice, capacity and shadow rollout

Requirements first: write the limits as a contract

Start by writing the limits down as a contract, because every later choice depends on it. A useful requirements sheet answers four questions for each limit: who is counted (API key, user, IP address, tenant, or the whole service), what is counted (requests, tokens, bytes, or cost units), over what window, and what happens when the limit is hit (reject, queue, or degrade).

Take a concrete public API as the running example. Peak traffic is 50,000 requests per second across 2 million API keys, of which about 200,000 are active in any minute. The product team wants each key held to 600 requests per minute with short bursts allowed, anonymous traffic held to 60 requests per minute per IP address, and the expensive /search endpoint held to 5,000 requests per second in total to protect its index cluster. The latency budget for the limiter is 2 ms at p99, and a false rejection of a paying customer is treated as worse than letting 5 percent extra traffic through.

That last sentence matters most: this limiter is a protection device, not a billing meter, so approximate counting is acceptable and it should fail open. A limiter that enforces a paid quota exactly needs a different design, closer to a quota system with reservations and reconciliation.

Where the limiter sits

There are five places a limit can live, and a good design uses more than one. Each layer sees different information and costs differently to run.

For the example API, the edge enforces the anonymous per-IP limit because it needs no account lookup and drops floods before they cost anything. The gateway enforces per-key limits, because it is the first point where the key has been authenticated, and the global /search cap, because only a shared counter can see the total. Each service keeps a simple in-process limit on concurrent requests, which needs no network call and catches overload the request-rate limits miss. The API gateway article covers the filter chain the limiter plugs into.

Rule of thumb: put each limit at the earliest layer that can compute its key. A per-key limit at the edge would have to trust an unauthenticated header, which an attacker will rotate.

A rule model you can change during an incident

Hard-coding limits in handler code makes them invisible and impossible to change during an incident. Instead, describe each request as a list of descriptors, key-value pairs extracted at the gateway, and match rules against them. Envoy's global rate limit service uses this model, and it generalises well.

# rules.yaml -- reviewed in code review, versioned, pushed to every gateway
domain: public_api
rules:
  - name: anon_per_ip
    match: {auth: anonymous}
    key: [ip]
    limit: {requests: 60, per: 60s}
    mode: enforce
  - name: key_default
    match: {auth: api_key}
    key: [api_key]
    limit: {requests: 600, per: 60s}
    mode: enforce
  - name: key_override_acme
    match: {auth: api_key, tenant: acme}
    key: [api_key]
    limit: {requests: 3000, per: 60s}
    overrides: key_default
    mode: enforce
  - name: search_global
    match: {route: /search}
    key: []
    limit: {requests: 5000, per: 1s}
    mode: shadow

Matching is all-apply: every matching rule is evaluated and any one can reject, which suits independent protections such as a per-key limit plus a global endpoint cap. The explicit overrides field gives most-specific-wins where needed, so a larger customer's 3,000 per minute replaces the default instead of stacking under it.

Each rule compiles to a counter key such as rl:key_default:k_8f2a:28512340: rule name, the descriptor values, and the window number. The rule service validates rules (no rule without a key on a high-cardinality route unless it is global on purpose, no limit of zero without an expiry), compiles them into a lookup table keyed by match fields, and pushes the table to gateways. The hot path never reads a database. If the push fails, gateways keep the last good version and alert.

Choosing the counter, with a worked trace

For per-key limits measured in minutes, the sliding window counter is usually the right default: two integers per key, no burst at window edges like a fixed window, and far less memory than a log of timestamps. It estimates the count in the last window by weighting the previous fixed window by how much of it still overlaps.

estimate = prev_count * (1 - elapsed / window) + curr_count
allow if estimate + cost <= limit

Trace it for key_default with a limit of 600 per 60 s. The previous minute saw 480 requests. We are 15 s into the current minute, which has seen 230 so far. The previous window still overlaps 45 of the last 60 seconds, so its weight is 0.75 and the estimate is 480 x 0.75 + 230 = 360 + 230 = 590. The next request makes 591, which is allowed. Nine more at the same instant bring the estimate to exactly 600, and the one after that is rejected.

The approximation assumes the previous window's requests were spread evenly. If all 480 arrived in its first 10 seconds, the true count over the last 60 s is only 230, so the limiter rejects traffic it should allow. If they all arrived in its last 15 seconds, the true count is 710 and the limiter lets through about 18 percent too much. Measure the error for your traffic by replaying logs through an exact sliding log offline and comparing decisions.

Use a token bucket (or GCRA, its single-number form) when you care about bursts on a scale of seconds, such as the global /search cap per second, and a sliding log only for low limits where exactness matters, such as five password attempts per hour. The counter store logic for the sliding window counter is short:

-- KEYS[1] = current window key, KEYS[2] = previous window key
-- ARGV: limit, window_ms, now_ms, cost
local limit, window, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
local curr = tonumber(redis.call('GET', KEYS[1]) or '0')
local prev = tonumber(redis.call('GET', KEYS[2]) or '0')
local elapsed = now % window
local est = prev * (1 - elapsed / window) + curr
if est + cost > limit then
  return {0, math.ceil(window - elapsed)}       -- denied, ms until the window rolls
end
redis.call('INCRBY', KEYS[1], cost)
redis.call('PEXPIRE', KEYS[1], window * 2)
return {1, 0}

Both keys must hash to the same Redis Cluster slot, so wrap the shared part in a hash tag, for example rl:{key_default:k_8f2a}:28512340. The script uses the gateway's clock in now_ms; if gateway clocks drift by more than a second or two, use Redis TIME inside the script instead.

The hot path in the gateway

The gateway filter does four things per request: extract descriptors, look up matching rules, evaluate them, and act on the result. Evaluating all matching rules in one pipelined round trip keeps latency to a single network hop.

def check(request, rules, store, now_ms):
    desc = extract(request)                  # {"auth": "api_key", "api_key": "k_8f2a", "route": "/search"}
    matched = rules.match(desc)              # compiled table; overrides already resolved
    calls = [(r, r.keys(desc, now_ms)) for r in matched]
    try:
        results = store.eval_pipeline(calls, timeout_ms=5)
    except StoreUnavailable:
        metrics.inc("ratelimit.store_error")
        return Allow(reason="fail_open")     # protection limiter: fail open, shed in-process
    for rule, (ok, retry_ms) in zip(matched, results):
        metrics.inc("ratelimit.decision", rule=rule.name, ok=ok, mode=rule.mode)
        if not ok and rule.mode == "enforce":
            return Deny(status=429, retry_after_s=max(1, retry_ms // 1000), rule=rule.name)
    return Allow()

Counters for rules that passed are not refunded when a later rule fails; the slight overcount is harmless and a refund costs another round trip. Shadow rules are logged but never acted on, which is how you will roll the system out safely

Capacity sizing for the counter store

Size the counter store from the requirements sheet, not from a guess. Two quantities matter: memory, driven by active keys, and operations per second, driven by request rate times rules evaluated.

• Memory. About 200,000 active keys with two window counters each, plus perhaps 300,000 anonymous IP counters, is roughly a million small keys. Redis overhead for a short key with an integer value is on the order of 60 to 100 bytes, so the working set is around 100 MB. Memory is not the constraint.
• Operations. Each gateway request evaluates one or two rules in one pipelined call, and each script does two reads and a write. At 50,000 requests per second with an average of 1.5 rules, that is 75,000 script executions per second. A single Redis primary handles tens of thousands of short Lua scripts per second per core, so plan for four to six primaries in a cluster to keep each under half load at peak, and benchmark with your own script before committing.
• Hot keys. search_global puts 5,000 increments per second on one shard, which is fine; at 100,000 per second, split it into N sub-keys with limit/N each, or use local leases.

Rolling it out: shadow mode first

Never turn a new limiter on in enforce mode. Every rule starts in shadow mode: it is evaluated and logged as a would-be denial, but the request proceeds. Run shadow mode for at least one full business cycle, usually a week, then look at who would have been rejected.

1. Group shadow denials by key and rule. A few keys with huge counts are usually abuse or broken retry loops; contact their owners first.
2. Look for legitimate patterns that break the rule, such as nightly batch exports or a mobile app that fires twenty calls when it opens. Either raise the limit, add an override, or work with the team to change the client.
3. Switch the rule to enforce for a small slice, for example keys whose hash falls in the first 5 percent, and watch 429 rates, support tickets and retry storms.
4. Widen to all keys and document the limit and its headers in the public API reference.

Every 429 should return Retry-After and a machine-readable rule identifier, so client teams can tell a per-key limit from a global cap.

Failure modes

Most limiter incidents fall into a small number of patterns.

• Counter store outage. With fail-open, traffic flows unprotected, so the in-process concurrency caps must be strong enough to stop a backend melting. With fail-closed, a Redis outage becomes a total API outage. For a protection limiter, fail open, alert loudly, and keep the local caps.
• Wrong key. Keying anonymous traffic on IP rejects whole offices and mobile carriers behind NAT. Keying on a client-supplied header lets attackers rotate it. Key on the most stable authenticated identity available and treat IP limits as coarse flood protection.
• Retry amplification. Clients that retry 429s immediately turn a limit into a traffic multiplier. Honour Retry-After in your own SDKs, add jitter, and count retries against the same key.
• Rule push drift. Half the gateways on a new rule version and half on the old give inconsistent answers. Version every push, expose the version in metrics, and alarm on mixed versions for more than a few minutes.
• Limits nobody owns. A rule added during an incident and never removed silently caps a customer months later. Require an owner and a review date on every rule.

Trade-offs

The main trade-offs are explicit choices, not defaults. Accuracy against cost: a sliding log is exact but stores every timestamp; the window counter stores two numbers. Central against local: a shared store gives a true global view at the price of a network hop and a dependency; local counters are free but see one instance, so 600 across 20 gateways becomes 30 each and breaks when traffic is uneven. Fail open against fail closed, as above. And simplicity against fairness: plain per-key limits are easy to explain, while weighted fair sharing between tenants, covered in rate versus concurrency limits and tenant fairness, protects small tenants better but is harder to reason about.

What to do next

1. Write the requirements sheet for every limit: who, what, window, action, and whether a false reject or a false allow is worse.
2. Map each limit to the earliest layer that can compute its key, and add in-process concurrency caps in every service regardless.
3. Move limits into a reviewed, versioned rule file with owners and review dates; compile and push it to gateways.
4. Pick the counter per rule: sliding window counter for per-key minutes, token bucket or GCRA for per-second bursts, sliding log only for small exact limits.
5. Size the store from active keys and rule evaluations per second, use hash tags for related keys, and split any global key above a few thousand increments per second.
6. Ship every rule in shadow mode first, review shadow denials for a week, then enforce gradually.
7. Return 429 with Retry-After and a rule identifier, and alarm on store errors, mixed rule versions and sudden changes in denial rate.