Design a Rate Limiter

You met rate limits as a client in Debugging, Lesson 09 (the surprise 429 error). Now you will design the part that sends it.

Words you need first

• Rate limiter is a part of a system that counts the requests from each caller and rejects the ones above an allowed number in a period of time. Think of a door guard who lets in 100 people a minute and asks the rest to wait.
• Request is one message from a client (a browser or app) to a server asking for something. HTTP 429 Too Many Requests is the status code (a three-digit number in the answer) that means "you sent too many requests, slow down".
• API key is a secret string that identifies which app or customer is calling an API.
• IP address is the number that identifies a device on a network, such as 203.0.113.7.
• Redis is a fast data store that keeps data in memory. Many servers can share it. It can count and expire values quickly.
• Burst is many requests sent in a very short time.
• Throttling is another word for slowing callers down. A limiter can throttle (delay) or reject. This lesson mostly rejects.

1. Requirements

Functional (what the system does)

• Limit requests for each key. A key is the label that says whose requests are counted together. It can be a user ID, an API key, an IP address, or a mix. You can also limit by route. For example, login attempts get a stricter limit than reads.
• Support more than one rule. For example: 100 requests per minute and 5,000 per day, with short bursts allowed.
• Reject extra requests with HTTP 429 and tell the client when to try again.
• Let you set limits for each plan or endpoint, and change them without a new release.

Non-functional (how well it must work)

• Very low delay. It runs on every request. Aim for under 1 to 2 ms added.
• Correct across many servers. If you have 10 instances, each must not allow the full limit.
• Highly available. The limiter must not be the reason the site goes down.
• Low memory use, even with millions of keys.
• High availability means the limiter keeps working when one of its parts breaks. Delay (also called latency) is the extra time one request waits.

It helps to tell similar ideas apart:

In one line: a rate limit counts requests per time period. A concurrency limit counts requests running right now. A quota counts total use over a long period.

2. Where does it live?

Most teams use layers (several limiters, one behind the other). At the edge, they set rough IP limits to stop floods. In the app or gateway, they set exact limits for each user and endpoint, using a shared store like Redis.

3. The algorithms

Fixed window counter

Count the requests for each key in the current fixed time window (for example, each calendar minute). Reject when the count goes over the limit.

key = userId + ":" + floor(now / 60s)count = INCR key ; set expiry 60s on first incrementif count > 100 → reject

• Pro: very simple and cheap. One counter for each key for each window.
• Con: boundary burst. A client can send 100 requests at 0:59 and another 100 at 1:00. Each minute stays within the limit, but that is 200 requests in about one second, double the rate you wanted.

Sliding window log

Store a timestamp for each request. On each new request, remove timestamps older than the window, then count what is left.

• Pro: exact (the window really moves with time, so "no more than N in any 60 seconds" is always true).
• Con: it uses a lot of memory (one entry for each request for each key) and more work for each request. It is fine for small limits.

Sliding window counter (the practical middle way)

Keep counters for the current window and the previous window. Count part of the previous window, based on how much of it still overlaps the sliding window. For example, 30 seconds into the current minute, half of the previous minute still overlaps, so count half of its requests:

estimated = prevCount × (1 − elapsedFractionOfCurrentWindow) + currentCountreject if estimated ≥ limit

• Pro: two numbers for each key. It smooths the boundary burst and is accurate in practice.
• Con: it is an estimate. It assumes that the requests in the previous window were spread out evenly.

Token bucket (the most common)

Picture a bucket that holds up to capacity tokens. New tokens drop in at a steady rate. Each request takes one token. If the bucket is empty, the request is rejected.

capacity = 100 tokens, refill = 100 tokens / minute  (≈ 1.67 per second)Idle for a while → bucket fills up → a client can burst up to 100 at once, then is limited to the refill rate.

• Pro: it allows bursts (good for real clients) and still keeps the average rate. It stores only two values for each key (the tokens and the last refill time). Stripe has written about running its rate limiters as token buckets on Redis, and AWS API Gateway describes its throttling as a token bucket.
• Con: it has two settings to tune. You must choose the burst size on purpose.

Leaky bucket

Requests go into a queue (a waiting line where the first request in is the first one out). That queue is the bucket. It empties at a constant rate. If the queue is full, new requests are dropped.

• Pro: it gives a smooth, steady flow out. This protects a weak service behind it (nginx limit_req is based on this idea).
• Con: a burst fills the queue and makes queued requests wait. If the queue is long, old requests can block newer ones.

Comparison

4. A token bucket you can run

First, here is the logic in plain JavaScript (one process), so you can understand it and test it:

function makeTokenBucket({ capacity, refillPerSec }) {  const buckets = new Map(); // key -> { tokens, last }  return function allow(key, now = Date.now(), cost = 1) {    const b = buckets.get(key) ?? { tokens: capacity, last: now };    const elapsed = (now - b.last) / 1000;    b.tokens = Math.min(capacity, b.tokens + elapsed * refillPerSec); // refill lazily on access    b.last = now;    const allowed = b.tokens >= cost;    if (allowed) b.tokens -= cost;    buckets.set(key, b);    return { allowed, remaining: Math.floor(b.tokens), retryAfterSec: allowed ? 0 : Math.ceil((cost - b.tokens) / refillPerSec) };  };}const allow = makeTokenBucket({ capacity: 5, refillPerSec: 1 });let t = 0;const results = [];for (let i = 0; i < 7; i++) results.push(allow("u1", t).allowed);   // 7 requests at the same instantconsole.log(results.join(","));                                      // true,true,true,true,true,false,falseconsole.log(allow("u1", t + 2000).allowed);                          // true  (2 tokens refilled after 2 s)console.log(allow("u1", t + 2000).remaining);                        // 0     (this call used the second refilled token)

Notice the lazy refill: tokens are added only when a request comes in, not by a timer. The code works out how many tokens were added from the time that has passed since the last request. This is why millions of keys are cheap.

5. Making it correct across many servers

Ten API instances need one shared view. So the counters live in a central, fast store: Redis. The danger is a race (also called a race condition: two things happen at the same time and the result depends on which one is faster, so it can be wrong). Two instances read the same count, both allow the request, both write, and the limit is passed. The check and the update must be atomic, which means they happen as one step that nothing can interrupt.

Fixed window with Redis (simple, atomic enough)

const key = `rl:${userId}:${Math.floor(Date.now() / 60_000)}`;const count = await redis.incr(key);              // atomicif (count === 1) await redis.expire(key, 60);     // ⚠ a crash between INCR and EXPIRE leaves a key that never expiresif (count > 100) return reject();

The INCR and EXPIRE pair is not atomic. It is better to use one atomic step: SET key 0 EX 60 NX and then INCR, or a Lua script.

Token bucket with a Lua script (atomic)

Lua is a small scripting language. Redis can run a Lua script on the server, and it runs the whole script atomically. Nothing else runs in the middle, so reading and then updating a value is safe from races.

-- KEYS[1] = bucket key; ARGV = capacity, refillPerSec, nowMs, costlocal capacity = tonumber(ARGV[1])local rate     = tonumber(ARGV[2])local now      = tonumber(ARGV[3])local cost     = tonumber(ARGV[4])local data   = redis.call("HMGET", KEYS[1], "tokens", "ts")local tokens = tonumber(data[1])local ts     = tonumber(data[2])if tokens == nil then tokens = capacity; ts = now endlocal elapsed = math.max(0, now - ts) / 1000tokens = math.min(capacity, tokens + elapsed * rate)local allowed = 0if tokens >= cost then tokens = tokens - cost; allowed = 1 endredis.call("HSET", KEYS[1], "tokens", tokens, "ts", now)redis.call("PEXPIRE", KEYS[1], math.ceil(capacity / rate * 1000) * 2)   -- idle buckets disappearreturn { allowed, math.floor(tokens) }

// Express middleware (Express is a Node.js web framework; ioredis is a Node.js Redis client)const sha = await redis.script("LOAD", luaSource);export const rateLimit = (capacity: number, perSec: number) => async (req, res, next) => {  const key = `rl:${req.user?.id ?? req.ip}:${req.route?.path ?? "global"}`;  try {    const [allowed, remaining] = (await redis.evalsha(sha, 1, key, capacity, perSec, Date.now(), 1)) as [number, number];    res.set({ "X-RateLimit-Limit": String(capacity), "X-RateLimit-Remaining": String(remaining) });    if (!allowed) {      res.set("Retry-After", String(Math.ceil(1 / perSec)));      return res.status(429).type("application/problem+json").json({ type: "https://api.example.com/errors/rate-limited", title: "Too many requests", status: 429 });    }    next();  } catch {    next(); // fail open: see "When the limiter itself fails"  }};

(If the clocks on your app servers may not match, use the time from Redis (redis.call("TIME")) instead of each server's own clock.)

Other multi-server options

• A local limiter in each instance with the limit divided (limit ÷ number of instances). There is no network call. But it is not accurate when load is uneven or when the number of instances changes.
• Approximate, eventually consistent sync (the copies of the data may differ for a short time, but they agree later). Each instance counts on its own and sometimes sends the counts to Redis. It has very low delay and allows a small overshoot. It is good at huge scale, when you do not need exact numbers.
• Sticky routing by key. You send each user ID to one instance, so that instance owns the counter for that key. This breaks easily when instances change.
• Redis Cluster. Keys are split over servers by hash slot (Redis Cluster has 16,384 slots, and each key belongs to one slot, chosen by a hash of the key). A Lua script must use keys in one slot. If a script needs several keys, use hash tags like {user42}. Add replicas for availability. Know that after a failover you can lose a few recent counts.

6. Keys, rules and configuration

• Choose the key to match the threat.
  • Use an API key or user ID for logged-in traffic. It is fair and exact.
  • Use the IP for anonymous traffic and for credential stuffing (trying stolen username and password pairs on many sites), but be careful (see below).
  • Use IP + route for login and OTP (one-time password, a short code sent to the user) endpoints.
  • Use a global key to protect a weak dependency, such as an SMS provider.
• Rules as data. Keep them in config or a database (plan-free: 100/min, burst 100; login-per-ip: 10/min). Cache them locally and reload them while running. When a request has more than one rule, check all of them. Reject if any rule fails.
• Cost-based limits. An expensive endpoint uses more tokens (cost = 10).
• Tiered limits. Free and paid plans get different limits. Internal services are exempt or get higher limits.

7. What the client sees

HTTP/1.1 429 Too Many RequestsRetry-After: 18X-RateLimit-Limit: 100X-RateLimit-Remaining: 0X-RateLimit-Reset: 18Content-Type: application/problem+json{ "type": "https://api.example.com/errors/rate-limited", "title": "Too many requests", "status": 429 }

• Use status 429 (not 403). Add a Retry-After header, which tells the client how long to wait (a number of seconds, or an HTTP date). The HTTP specification defines it. 429 is defined in RFC 6585. 403 Forbidden means "you are not allowed at all", so it is the wrong signal here.
• Rate-limit headers let clients slow down before they hit the wall. A header is a named line of extra information sent with an HTTP request or answer. Today most APIs use the unofficial names X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset. Their exact meaning differs between APIs (for example, Reset can be seconds left or a clock time). An IETF draft (a proposal, not yet final) defines two new fields, RateLimit-Policy (the rules) and RateLimit (what is left now). Because it is still a draft, say "emerging" in an interview.
• Add an error body that a program can read (application/problem+json is a standard JSON format for HTTP errors), and a request ID (a unique label for this request, useful in logs).

What the client should do:

• Respect Retry-After.
• Retry with exponential backoff with jitter. This means waiting longer after each failure, plus a small random extra time, so clients do not all retry together.
• Do not retry non-idempotent requests blindly. A request is idempotent if sending it twice has the same effect as sending it once (reading a page, or setting a value). A non-idempotent request, such as "charge the card", can do harm if it runs twice.
• Show a friendly message ("Try again in 18 seconds").
• Spread out background work.
• Remove duplicate requests, which means sending one request where several identical ones were about to go out (Debugging, Lesson 05).

8. When the limiter itself fails

What should happen if Redis is down or slow?

Choose this for each rule. Set a short timeout on the limiter call (a few ms). Raise a loud alert. Think about a fallback limiter in local memory with careful limits. Then you lose some quality, but not all protection.

9. Scenario: legitimate users sharing one IP get blocked

Hundreds of employees behind a company NAT, or a mobile carrier's CGNAT, share one public IP. (NAT, network address translation, lets many devices share one public address. CGNAT is the same idea at a large scale, run by a mobile or internet provider.) A limit for each IP treats them all as one abuser.

Fixes:

1. Do not use IP as the only key for logged-in traffic. Limit by user ID or API key. Keep IP limits only as a wide outer layer.
2. Log the user in first, then apply user-level rules. Give logged-in users higher IP-level limits.
3. Give higher limits or an allow-list to known company ranges and partners.
4. Combine signals (IP + device or cookie fingerprint + account; a fingerprint is a value built from traits of the device or browser) to find anonymous abuse. Use challenges (a CAPTCHA is a test that a human can pass and a program cannot; proof-of-work makes the client do a small calculation) instead of hard blocks for suspicious traffic.
5. Get the client IP right. A proxy or load balancer (a server that spreads requests over many servers) sits in front of your app, so the connection comes from the proxy, not the user. Read the user's address from the X-Forwarded-For header only when it comes from trusted proxies. If not, attackers fake the header to avoid limits or to blame others.
6. Watch the 429 rate for each key type, so you notice innocent users getting blocked.

10. Scaling and observability

• Throughput: 100,000 requests per second means 100,000 limiter checks per second. One Redis node can do roughly 100,000 or more simple operations per second. Use a cluster (many Redis servers that share the keys) and keep each check to one round trip (one network trip to Redis and back, here one Lua call). Or reduce the load with local pre-filters.
• Delay budget: keep the limiter in the same availability zone (an isolated location inside a cloud region, made of one or more data centres), reuse connections, and use short timeouts.
• Memory: two fields for each key, with a TTL (time to live: the time after which Redis deletes the key). So only active keys use memory. A key like this takes very roughly 100 to 200 bytes in Redis, so 10 million active keys ≈ 1 to 2 GB. Measure with your real key names.
• Hot keys: a hot key is a key with far more traffic than the others. One abusive key sends all its traffic to one shard (one Redis server that holds part of the keys). Blocking at the edge stops it earlier.
• Metrics: allowed vs rejected for each rule, limiter delay and errors, and the most limited keys. Alert on sudden jumps. Write the limiter decision in the logs with the request ID.
• Testing: unit-test the algorithms with a clock you control. Load-test the Redis path. Chaos-test (break things on purpose) to see how the limiter behaves when it fails.

Common mistakes

1. Limiting only on the client side.
2. Fixed windows without knowing about boundary bursts.
3. Reading and then updating across servers in a non-atomic way (a race that goes over the limit).
4. INCR without a reliable EXPIRE, which leaks keys.
5. Limiting only by IP, which punishes shared networks.
6. Trusting X-Forwarded-For from the open internet.
7. No decision about fail-open vs fail-closed.
8. No Retry-After, so clients retry at once and make things worse.
9. Using 403 instead of 429.

Interview questions

Key takeaways

• A limiter is key + rule + algorithm + shared state + response.
• Token bucket (bursts + average rate) is the usual default. Sliding window counter avoids boundary bursts. Fixed window is simple but bursty. Leaky bucket smooths the output.
• Make the check atomic in Redis (Lua), refill lazily, and expire idle keys.
• Return 429 with Retry-After and rate-limit headers. Clients should back off with jitter.
• Decide fail open vs fail closed for each endpoint. Do not rely on IP alone, and do not trust headers that can be faked.

What's next

Lesson 03: Design Pagination. This is another API design that looks easy until the data is large and keeps changing: offset versus cursor (keyset) pagination.