Design a Rate Limiter
A rate limiter controls how many requests a client or service may send in a period of time. Go over the limit and extra calls are blocked. You'll build all five classic algorithms, then scale the limiter to many servers.
- 4.1What a rate limiter does, and whyExamples of rules: Each user may publish at most 2 posts per second. One IP address may open at most 10 new accounts per day. One device…
- 4.2Where to put the rate limiterClient-side: unreliable. Requests can easily be forged by malicious actors, and you may not control the client. Server-side: inside the API…
- 4.3Algorithm 1: Token bucketWidely used (Amazon and Stripe use it) and simple: A bucket holds up to a fixed number of tokens (its capacity). A refiller adds tokens at…
- 4.4Algorithm 2: Leaking bucketLike the token bucket, but requests are processed at a fixed rate. It's usually built with a FIFO queue: When a request arrives, check if…
- 4.5Algorithm 3: Fixed window counterSplit the timeline into fixed windows (e.g. one per minute) and give each a counter. Each request increments the counter. Once the counter…
- 4.6Algorithm 4: Sliding window logThis fixes the edge problem of fixed windows: Keep a log of request timestamps (e.g. in a Redis sorted set). When a request arrives, remove…
- 4.7Algorithm 5: Sliding window counterA hybrid of fixed window and sliding log. It estimates the rolling window from two counters: requests in rolling window = requests in…
- 4.8High-level architecture and detailed designThe idea is simple: keep a counter per user/IP/API, and reject requests once it passes the limit. Where do counters live? A database is too…
- 4.9Rate limiting in a distributed environmentOne server is easy. Many servers and many threads bring two challenges: 1. Race condition "Read counter → check → write counter + 1" isn't…
- 4.10Performance, monitoring and wrap upPerformance optimization Multi-data-center setup is crucial: requests far from the limiter are slow. Cloud providers place many edge…