Sliding window rate limiter
On the roadmap:Intermediate · step 6: Protecting services
Allow at most N requests per key in any window of the last T milliseconds, and say how long to wait when refused.
In plain words
Allow at most N requests from a user in any recent window of time, and tell the caller how long to wait when they are over.
Why it matters
It protects a service from abuse and accidents without punishing normal bursts. The sliding window avoids the burst a fixed window lets through at its edges.
Where you meet it
- API gateways and public APIs
- Login and password-reset protection
- Cloud services that return 'too many requests'
You will be able to
- Store recent request times and drop old ones
- Return a retry-after value
- Compare with token bucket and fixed window
In interviews
Among the most common design questions. Know the algorithms and how to share the counts across servers.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- A map from key to the timestamps of recent requests
- Dropping timestamps older than the window
- An allow() result with remaining count and retry-after
- An injectable clock so tests are deterministic
export type Decision = { allowed: boolean; remaining: number; retryAfterMs: number };
export class SlidingWindowLimiter {
private hits = new Map<string, number[]>();
constructor(private limit: number, private windowMs: number, private now: () => number = Date.now) {}
allow(key: string): Decision {
const t = this.now();
const recent = (this.hits.get(key) ?? []).filter((x) => x > t - this.windowMs);
if (recent.length >= this.limit) {
this.hits.set(key, recent);
return { allowed: false, remaining: 0, retryAfterMs: recent[0] + this.windowMs - t };
}
recent.push(t);
this.hits.set(key, recent);
return { allowed: true, remaining: this.limit - recent.length, retryAfterMs: 0 };
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints sliding-window-rate-limiter ok when everything passes. You need Node.js installed.
mkdir sliding-window-rate-limiter && cd sliding-window-rate-limiter
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Production limiters keep their counters in a shared store such as Redis and update them atomically (a Lua script or a counter with an expiry), so every server sees the same count.
- Keeping every timestamp costs memory. Many systems use a sliding window counter, which blends two fixed windows, or a token bucket that allows short bursts.
- Good APIs answer with 429 and a Retry-After header, and decide what happens when the limiter itself is down: let traffic through, or block it.
Rate limiting algorithms
| How it works | Memory | Bursts | Pick it when | |
|---|---|---|---|---|
| Sliding window log (this lab) | Keeps the time of every recent request | One entry per request | Exact: never more than N in any window | Limits are strict and small |
| Fixed window counter | One counter per clock window | Tiny | Up to twice the limit across a window boundary | A coarse limit is fine |
| Sliding window counter | Blends the current and previous window counts | Tiny | Close to exact | Large scale with small memory |
| Token bucket | Tokens refill steadily and each request spends one | Tiny | Allows a burst up to the bucket size | APIs that should allow short bursts |
| Leaky bucket | Requests queue and leave at a steady rate | A queue | Smoothed out | You want a steady outgoing rate |
What it cannot do
Memory grows with the limit
Keeping every timestamp costs more as the allowed rate rises. Counters or buckets avoid this.
State lives per user
Millions of users means millions of entries to expire and clean up.
Several servers need a shared store
Each server counting alone would allow N per server. Production uses a shared store such as Redis.
It counts requests, not their cost
A heavy request and a light one use the same slot.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Replace the arrays with a sliding window counter to save memory
- Share the state in Redis with a Lua script
- Add a token bucket and compare burst behaviour