Rate Limiter

In plain words

A rate limiter decides, for every request, whether this caller has done too much recently — and says no if so. It protects a system from abuse, from a buggy client in a loop, and from itself. The two questions are how to count (the algorithm) and where the count lives when there are many servers doing the counting. The rate limiting concept covers the algorithms in depth; this problem is about building the service.

The unusual constraint

per request, to the counter store

1 op

budget for the whole check

< 1 ms

per key for a token bucket

2 numbers

keys × rules = counters to hold

40 K

How a request flows

Decision 1: the algorithm

Token bucket is the usual answer: two numbers, refilled lazily from elapsed time, and its burst allowance matches how real clients behave — quiet, then a flurry. Sliding window counter is the other good answer when you must forbid bursts entirely.

Decision 2: where the count lives

Ten gateway instances each enforcing 100/min locally enforce 1,000/min. The count must be shared, and the read-decide-write must be one operation.

-- KEYS[1] = bucket:{api_key}   ARGV = capacity, refill_per_sec, now_ms
local capacity, refill, now = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local b = redis.call('HMGET', KEYS[1], 'tokens', 'updated')
local tokens = tonumber(b[1]) or capacity
local updated = tonumber(b[2]) or now

-- tokens that arrived while nobody was looking
tokens = math.min(capacity, tokens + (now - updated) / 1000 * refill)

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

redis.call('HSET', KEYS[1], 'tokens', tokens, 'updated', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / refill * 1000) * 2)  -- idle keys clean themselves up
return { allowed, math.floor(tokens) }

Decision 3: what to do when Redis is down

async function check(key: string): Promise<Decision> {
  try {
    return await redis.evalsha(BUCKET_SHA, [`bucket:${key}`], [CAPACITY, REFILL, Date.now()]);
  } catch (err) {
    metrics.increment("ratelimit.store_unavailable");
    return { allowed: true, remaining: -1 };   // open, and someone gets paged
  }
}

Decision 4: what to send back

A 429 with Retry-After is the baseline. Returning X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset on every response — not just rejections — is what actually makes clients well-behaved: a client that can see its remaining budget slows down before it is rejected at all. Add a little randomness to Retry-After, or every rejected client retries in the same second.

Where this design breaks

• Keying on IP. Everyone behind one NAT (one public address shared by a whole office or carrier) shares a bucket; an attacker with many addresses gets many buckets. Key on the API key or user; IP is a last resort.
• Hot keys. One enormous customer's counter is one Redis key on one shard. Split it per gateway (bucket:{key}:{gw}) and give each a share.
• Many rules per key. 100/min, 5,000/hour, 50,000/day is three scripts. Send them as one batch (a pipeline) so it is still one round trip.
• Retry storms. Every rejected client retrying at exactly Retry-After is a synchronised wave — see retries, backoff and jitter.

Take this with you

• The one idea: the check runs on every request, so it must cost one cheap atomic operation — and the count must be shared, or N servers enforce N× the limit.
• In an interview, name token bucket, explain the fixed-window edge case, and say where the counter lives and what happens when that store is down.
• At work, return the X-RateLimit-* headers on every response, and decide on purpose whether your limiter fails open or closed.