ProjectsRate Limiter
A small HTTP service with one open endpoint and one protected endpoint that limits how often each client may call it, built with four algorithms in turn and then shared across several servers. Building it teaches what each algorithm trades between bursts, accuracy and memory, how a service tells a client to slow down, why measuring time is harder than it looks, and why counters shared between servers need atomic updates.
From Coding Challenges #27 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 8 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
Step 2 gives every IP address its own bucket, and every later algorithm keeps its state per client in the same way.
Covers: protecting capacity and sharing it fairly · floods, scraping and password guessing · keying a limit by IP address, API key or account · many users behind one address · proxies and the X-Forwarded-For header · one entry per client, and forgetting idle ones
OWASP API Security Top 10: API4:2023 Unrestricted Resource Consumption ↗ · The perils of the "real" client IP (Adam Pritchard) ↗ · X-Forwarded-For header (MDN) ↗
Step 2 builds one bucket per IP address with a set capacity and refill rate, and expects a burst to pass and most of what follows to be rejected.
Covers: capacity as the largest burst · refill rate as the long-run average · computing the refill from elapsed time · keeping fractions of a token
Token bucket (Wikipedia) ↗ · Scaling your API with rate limiters (Stripe) ↗
Step 3 counts requests in windows that start on the clock, and its expected pattern, a run of successes just after each window starts and then rejections, comes straight from that reset.
Covers: windows that start on the clock · one counter per client per window · the burst across a window boundary · every client resetting at the same moment · letting old counters expire
An alternative approach to rate limiting (Figma) ↗ · Redis INCR: Pattern, rate limiter ↗
Step 4 keeps a log of timestamps per client and leaves the tests to you, so you decide how pruning, the limit and memory should behave.
Covers: a timestamp for each request · dropping entries older than the window · memory that grows with the limit and the number of clients · whether rejected requests count
An alternative approach to rate limiting (Figma) ↗ · Redis sorted sets ↗
Step 5 builds this estimate and asks for a test of the calculation, and step 6 shares it between servers because it needs only two numbers per client.
Covers: counts for the current and previous windows · weighting the previous count by how much of it still overlaps · the assumption that requests were spread evenly · how far the estimate can be off
How we built rate limiting capable of scaling to millions of domains (Cloudflare) ↗ · An alternative approach to rate limiting (Figma) ↗
Step 2 rejects requests that find the bucket empty with 429, and every later algorithm rejects in the same way, so clients need to know what it means and when to come back.
Covers: 429 Too Many Requests · the Retry-After header · telling clients their remaining quota · backing off with jitter · 429 versus 503
RFC 6585, section 4: 429 Too Many Requests ↗ · Retry-After header (MDN) ↗ · RateLimit header fields for HTTP (IETF draft) ↗
Step 3 starts windows on the clock, step 5 asks for a test of a calculation that depends on the current time, and in step 6 several servers with their own clocks must agree on one window.
Covers: the wall clock versus a monotonic clock · refills and log ages as elapsed time · window boundaries from the time of day · clocks that disagree between servers · a clock and window length that tests can control
clock_gettime(2), Linux manual page ↗ · How and why the leap second affected Cloudflare DNS (Cloudflare) ↗ · Clock synchronization (Wikipedia) ↗
Step 6 runs two or more servers that must enforce one limit together by sharing the sliding window counter through a store.
Covers: why each server's own memory isn't enough · a shared store and the network trip it adds · lost updates when two servers read, change and write · atomic increments, transactions and scripts run inside the store · keys that expire on their own · what to do when the store is down
Redis INCR: Pattern, rate limiter ↗ · Redis transactions ↗ · Race condition (Wikipedia) ↗
What you'll build · 7 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project for a small web service that you can run locally, and have a way to send it single requests and fast bursts of requests, such as curl and a load-testing tool.
Works whenThe service starts and answers a request.
Serve two endpoints that answer GET with any text: /limited, which later steps protect, and /unlimited, which stays open. Listen on the port given in the PORT environment variable, and use 8080 when it isn't set.
Works whenA GET to /limited and a GET to /unlimited each return 200 with a body.
Protect /limited with a token bucket for each client IP address, holding at most 10 tokens and refilled at 1 token a second, with tokens beyond the capacity thrown away. A request that finds its bucket empty gets 429, and /unlimited is never limited. Make the capacity and the refill rate settable, for example through environment variables, so a test can use small values.
Works whenA fast burst of requests from one client gets roughly the first 10 through and 429 for the rest. After a short wait a new request succeeds again, and /unlimited answers 200 throughout.
Concepts: the token bucket · why services limit rates, and who counts as one client · saying no
Replace the bucket with a fixed window counter: windows of a set length that start on the clock, so a 60-second window starts on each whole minute, a count per client for the current window, and 429 once the count passes the threshold. Make the window length and the threshold settable, so a test can use a window of a few seconds.
Works whenUnder steady load from one client, each window begins with a run of successes up to the threshold, followed by 429 until the next window starts.
Concepts: fixed windows and the burst at the boundary · time and clocks
Use a sliding window log instead: for each client, keep the time of each request, drop entries older than one window, and answer 429 when this request would take the count past the threshold. The window length and threshold stay settable. The tests are yours to design.
Works whenWithin one window, requests up to the threshold succeed and the next one gets 429. As soon as the oldest request is more than a window old, a new one succeeds, with no reset at fixed times.
Concepts: the sliding window log
Use a sliding window counter: keep counts for the current and previous fixed windows, estimate the requests in the last window length as the current count plus the previous count weighted by the part of the previous window that still overlaps it, and answer 429 when this request would take the estimate past the threshold. Write a test for the calculation itself.
Works whenA test with chosen counts and a chosen position in the current window gets the expected estimate without waiting on the real clock. Over HTTP, a burst past the threshold gets 429, and requests are let through again gradually as the window slides, not all at once at a window boundary.
Concepts: the sliding window counter · time and clocks
Run two or more instances of the service on different ports that share the sliding window counter's state through a store such as Redis, so together they enforce one limit per client. Each instance takes its port from PORT and the store's address from its settings, for example an environment variable.
Works whenWith a short window, using up a client's whole limit quickly through one instance makes that client's next request to another instance get 429.
Concepts: shared state across servers, and atomic updates · time and clocks