Core Concepts

The Thundering Herd Problem

A million requests land on your API in the same second.

Databases queue up. Threads exhaust. Latency climbs until health checks fail and the service goes down.

Rate limiting is the guard at the door. It decides how many requests each client may make in a window of time, and rejects the rest with a 429 response.

In system design interviews, this is the first defense you name against traffic spikes and denial-of-service attacks.

What A Limiter Must Decide

Every algorithm answers the same three questions.

Who is the client? Usually an API key, user ID, or IP address.

How much is allowed? A count of requests per unit of time.

What happens on overflow? Reject, queue, or shape the traffic.

Different algorithms differ only in how they track the count. Keep that framing in an interview and the comparisons become easy.

Fixed Window Counting

The simplest approach. Divide time into fixed blocks and keep one counter per client per block.

Allow 100 requests per minute. At the top of each minute, the counter resets to zero.

It costs one integer in memory and one atomic increment per request.

The flaw appears at the boundary. A client can send 100 requests in the last second of one minute and 100 in the first second of the next, delivering 200 requests in two seconds.

Sliding Window Logs

Fix the boundary problem by dropping fixed blocks entirely.

Store a timestamp for every request in a sorted set. On each new request, remove entries older than the window, then count what remains.

If the count is below the limit, accept and append the new timestamp.

Accuracy is perfect. The cost is memory: you store one entry per request per client, which becomes expensive at high volume.

The Sliding Window Counter

The practical middle ground, and a strong interview answer.

Keep only two counters: the current fixed window and the previous one. Then blend them by how far you are into the current window.

If you are 30% into the current minute, the estimate is the current count plus 70% of the previous count.

Memory stays at two integers. Boundary bursts are smoothed away. The trade is a small approximation error, since it assumes requests were spread evenly in the previous window.

Token Bucket

A bucket holds tokens up to a fixed capacity. Tokens refill at a steady rate.

Each request removes one token. No token available means the request is rejected.

The key property is burst tolerance. An idle client accumulates a full bucket, then may spend it all at once.

Notice that the bucket rim caps how large a burst can be, while the drip rate above it sets the long-run average.

That suits real user traffic, which arrives in clumps rather than a smooth stream. Capacity controls the burst size; refill rate controls the long-run average.

Leaky Bucket

Same bucket, different physics. Requests enter a queue and leave through a hole at a constant rate.

Output is perfectly smooth. Downstream services receive a steady, predictable stream no matter how jagged the input is.

When the queue is full, new requests are dropped.

Interviewers often ask for the contrast with token bucket. Token bucket permits bursts; leaky bucket eliminates them, at the cost of added queueing latency.

Choosing By Traffic Shape

Interview answers improve when you pick an algorithm from requirements rather than habit.

Ask two questions. Does the client need to burst? Does the downstream service need a smooth, protected input rate?

Bursty clients with a resilient backend fit token bucket. A fragile backend that must never exceed a fixed throughput fits leaky bucket.

When neither burst nor smoothing dominates, the sliding window counter is the cheap, accurate default.

Distributed Rate Limiting

One server is easy. Twenty servers behind a load balancer are the real interview question.

Local counters let a client exceed the limit by a factor equal to the server count. Twenty servers each allowing 100 requests permits 2,000.

The usual fix is shared state in Redis with atomic increment operations.

That introduces a network hop per request and a race condition risk, which is why counters are updated atomically rather than read then written.

What To Say In The Interview

State the limit and the identity key first. For example, 100 requests per minute per API key.

Name the algorithm and justify it from the traffic shape, not from familiarity.

Cover the response contract: a 429 status, a Retry-After header, and remaining-quota headers.

Then raise the distributed problem yourself. Shared Redis state, atomic increments, and the extra network hop.

The candidates who stand out are the ones who name the trade-off before being asked.

When a client exceeds a rate limit, the limiter commonly returns a 429 response.

• True
• False

Answer: True

This statement is correct. A rate limiter rejects requests above the allowance, commonly using HTTP status 429. An API may also include Retry-After and remaining-quota headers.

Rate-limiting algorithms track usage differently: fixed window counting uses _____, sliding window logs store _____, and a sliding window counter keeps _____.

Answer: Rate-limiting algorithms track usage differently: fixed window counting uses fixed blocks, sliding window logs store request timestamps, and a sliding window counter keeps two counters.

Fixed window counting stores one counter for each fixed time block. Sliding window logs retain every request timestamp in the active window. The sliding window counter keeps only the current and previous window counts, using a weighted estimate.

A client may send 100 requests during the last second of one fixed minute and 100 during the first second of the next. What is the main result?

• The limiter permits 200 requests in about two seconds
• The limiter delays the second 100 requests until the next minute ends
• The limiter stores every request timestamp for exact counting
• The limiter smooths the requests into a constant output rate

Answer: The limiter permits 200 requests in about two seconds

The client can send 200 requests within two seconds because the counter resets at the minute boundary. This is the boundary-burst flaw of fixed window counting.