Step 1: Ask before you draw
Rate limiting means “at most N requests per time period, per someone”. Before choosing anything, find out:
- Who is limited? A user, an IP address, an API key, a whole tenant? (Bots can change IPs; users can share one office IP.)
- What is limited? Every request, or only some endpoints (login, search, sending messages)?
- How strict? Is “about 100 per minute” fine, or must it be exact? May short bursts go through?
- Where does it run? In each app server, in an API gateway in front of them, or both?
- What does the client see when it’s limited, and what if the limiter itself breaks?
Clarify the identity (user, API key, IP, tenant, or combinations, since limits are often layered), the granularity (global, per endpoint, per cost unit), accuracy vs cost (exact sliding windows vs approximations), burst tolerance, scale (requests per second, number of identities, regions), latency budget (the limiter is on every request’s path, so single-digit milliseconds), and the failure policy (fail open or closed per endpoint). State the interface early: allow(key, cost) → (allowed, remaining, retryAfter).
For this design: an API with 10 million users, limits per user per endpoint (for example 100 requests per minute, 5 login attempts per minute), short bursts allowed, enforced across many API servers.
Step 2: Pick an algorithm
| Algorithm | How it works | Good | Watch out |
|---|---|---|---|
| Fixed window counter | count requests per user per calendar minute | tiny state, simple | up to 2× the limit around a window boundary |
| Sliding window log | store a timestamp per request; count those in the last 60 s | exact | memory grows with the limit (100 timestamps per user) |
| Sliding window counter | weighted mix of the previous and current window’s counts | close to exact, 2 numbers per user | an approximation |
| Token bucket | a bucket of N tokens, refilled at a steady rate; each request takes one | allows bursts up to N, then a steady rate | two numbers per user; refill math must be right |
| Leaky bucket | requests queue and leave at a fixed rate | smooths traffic for downstream | adds latency; queue can fill |
The token bucketToken bucketA rate limiting algorithm that allows bursts up to a bucket size and then a steady rate of requests.Open in glossary → is the most common answer, and the easiest to picture: a bucket holds up to 10 tokens. Every request takes one token; if the bucket is empty, the request is rejected. Tokens drip back in at a steady rate, say one every 6 seconds. A user who was quiet can burst 10 requests at once, and after that gets about 10 per minute.
actor TokenBucket {
private let capacity: Double // the biggest burst
private let refillPerSecond: Double // the steady rate
private var tokens: Double
private var lastRefill = ContinuousClock.now
init(capacity: Double, refillPerSecond: Double) {
self.capacity = capacity
self.refillPerSecond = refillPerSecond
self.tokens = capacity
}
func tryAcquire(cost: Double = 1) -> Bool {
let now = ContinuousClock.now
let elapsed = lastRefill.duration(to: now)
let seconds = Double(elapsed.components.seconds) + Double(elapsed.components.attoseconds) / 1e18
tokens = min(capacity, tokens + seconds * refillPerSecond) // refill for the time that passed
lastRefill = now
guard tokens >= cost else { return false }
tokens -= cost
return true
}
}class TokenBucket(
private val capacity: Double, // the biggest burst
private val refillPerSecond: Double, // the steady rate
private val nanoTime: () -> Long = System::nanoTime,
) {
private var tokens = capacity
private var lastRefill = nanoTime()
@Synchronized
fun tryAcquire(cost: Double = 1.0): Boolean {
val now = nanoTime()
val elapsedSeconds = (now - lastRefill) / 1_000_000_000.0
tokens = minOf(capacity, tokens + elapsedSeconds * refillPerSecond) // refill for the time that passed
lastRefill = now
if (tokens < cost) return false
tokens -= cost
return true
}
}public final class TokenBucket {
private final double capacity; // the biggest burst
private final double refillPerSecond; // the steady rate
private double tokens;
private long lastRefill = System.nanoTime();
public TokenBucket(double capacity, double refillPerSecond) {
this.capacity = capacity;
this.refillPerSecond = refillPerSecond;
this.tokens = capacity;
}
public synchronized boolean tryAcquire(double cost) {
long now = System.nanoTime();
double elapsedSeconds = (now - lastRefill) / 1_000_000_000.0;
tokens = Math.min(capacity, tokens + elapsedSeconds * refillPerSecond); // refill for the time that passed
lastRefill = now;
if (tokens < cost) return false;
tokens -= cost;
return true;
}
}class TokenBucket {
private tokens: number;
private lastRefill = performance.now(); // monotonic, in milliseconds
constructor(
private readonly capacity: number, // the biggest burst
private readonly refillPerSecond: number, // the steady rate
) {
this.tokens = capacity;
}
tryAcquire(cost = 1): boolean { // one thread per process: no lock needed
const now = performance.now();
const elapsedSeconds = (now - this.lastRefill) / 1000;
this.tokens = Math.min(this.capacity, this.tokens + elapsedSeconds * this.refillPerSecond); // refill for the time that passed
this.lastRefill = now;
if (this.tokens < cost) return false;
this.tokens -= cost;
return true;
}
}There’s no background timer refilling buckets. Each request calculates how many tokens would have dripped in since the last request, which is why a bucket only needs two numbers: the token count and the time of the last refill. It uses a monotonic clock (nanoTime, ContinuousClock, performance.now()), which never jumps back when the device’s wall clock changes.
The boundary problem
The simplest algorithm, a counter per calendar minute, has a weakness you should mention in the interview:
Predict the output
The limit is 100 requests per minute, with a fixed window per calendar minute. A client sends 100 requests at 10:00:59 and 100 more at 10:01:00. How many are allowed?
The first 100 count against the 10:00 window, and at 10:01:00 a new window starts at zero, so the next 100 are allowed too: 200 requests in about one second, twice the limit. For many APIs that's acceptable (the average over time is still right). When it isn't, use a sliding window or a token bucket, whose capacity caps any burst.
The sliding window estimate
Predict the output
Limit: 100 requests per minute, sliding window counter. The previous minute had 80 requests; the current minute has had 30 so far, and we're 15 seconds into it. Is the next request allowed?
15 seconds into the minute, 45 seconds of the previous window still overlap the last 60 seconds, so 75% of the previous count is assumed to fall inside: 80 × 0.75 + 30 = 90. That's under 100, so the request is allowed. The estimate assumes the previous window's requests were evenly spread, which is why it's an approximation, and in practice a good one.
- Requirements: identity (user, key, IP, tenant), scope (global, endpoint, cost), accuracy, burst tolerance, latency budget (≤ 1–2 ms), failure policy. Interface:
allow(key, cost) → (allowed, remaining, retryAfter). - Algorithms: fixed window (2× boundary bursts), sliding log (exact, memory-heavy), sliding window counter (2 counters, good approximation), token bucket (bursts + steady rate, most common), leaky bucket (smoothing).
fun allowed(previousCount: Long, currentCount: Long, elapsedInWindow: Duration, window: Duration, limit: Long): Boolean {
val previousWeight = 1.0 - elapsedInWindow / window // share of the previous window still in range
val estimate = previousCount * previousWeight + currentCount
return estimate < limit
}static boolean allowed(long previousCount, long currentCount, long elapsedMs, long windowMs, long limit) {
double previousWeight = 1.0 - (double) elapsedMs / windowMs; // share of the previous window still in range
double estimate = previousCount * previousWeight + currentCount;
return estimate < limit;
}function allowed(previousCount: number, currentCount: number, elapsedMs: number, windowMs: number, limit: number): boolean {
const previousWeight = 1 - elapsedMs / windowMs; // share of the previous window still in range
const estimate = previousCount * previousWeight + currentCount;
return estimate < limit;
}Check this part
How does a token bucket allow short bursts?
What is the weakness of a fixed window counter per calendar minute?
Sliding window counter, limit 100/min: the previous minute had 80, the current one 30 so far, 15 seconds in. Is the next request allowed?
Why does the bucket measure time with
ContinuousClockinstead ofDate()?Why does the bucket measure time withSystem.nanoTime()instead ofcurrentTimeMillis()?Why does the bucket measure time withperformance.now()instead ofDate.now()?