Rate Limiter

Track: Load and timing. 7 stages. Languages: Go, Python, JavaScript, Rust.

Build a limiter that controls how many requests each caller can make. Every caller is identified by a key. A key can burst through a handful of requests at once, but over time it can only keep up with a steady rate, never more. Implement New(ratePerSec, burst) and Allow(key) -> bool using your language's names.

Your limiter will be called from many workers at the same time, so each request must be let through or denied correctly even when several calls land together. Standard library only. (This is also why Lua is not offered for this challenge: its standard library has no threads.)

The tester runs your code for real, against a real clock, not a sped up or fake one. It times how long your calls actually took and judges your limiter against that real time, not against a fixed number of milliseconds. If your machine is a little slow or busy that day, you are judged against what really happened during your run, not against an idealized one.

There is more than one correct way to build this. One way that works well: give each key a small amount of allowance that starts full. Every time some real time passes, add a little allowance back, up to the starting amount and never more. Each allowed request spends one unit of that allowance. When the allowance runs out, deny the request.

One way that looks reasonable but is not: count requests and reset the count to zero every time the clock crosses a fixed point, for example the start of a new second. That can let through close to double the promised amount, when one burst lands right before the reset and another lands right after it. Because that double burst only happens when the reset lands in just the wrong place, this kind of limiter can pass rl1 to rl6 by luck, even though it is the wrong design. Run it in production and it can let through twice the traffic you promised. Stage rl7 sends short bursts again and again, so a reset lands in the wrong place sooner or later, and it catches this design.

Each key needs its own allowance, never shared with any other key. A design that keeps one shared allowance for every key will pass every stage below that only uses one key, then fail the stage that uses two keys at once. You do need to let go of old keys eventually, for example by dropping the ones you have not seen in a while once you are tracking too many, since a caller could otherwise send requests under endless made up keys to use unlimited memory. For help with the ideas, read the notes. New to code that many callers run at the same time? Read Many callers at once first.

In JavaScript, only one piece of your code runs at a time, so a check and a spend with no await between them can never be split. A real Node.js server keeps its limits in a store like Redis, and that is where the race happens. So in JavaScript, New(rate, burst, db) gets a store from the tester, and you keep every key's allowance in it with await db.get(key) and await db.set(key, value). allow is async. Values are copied as JSON, like in Redis. While one call waits at an await, other calls run. If allow reads a key's allowance, waits, and then writes it back, another call can read the same old allowance in between, and both spend the same unit. When one worker sends requests, the tester runs two copies of your code that share one db and sends the requests to them in turn, like two servers. Allowance kept only in a local variable or Map is not seen by the other copy, so too many requests get through. The db belongs to the tester, so you do not need to drop old keys from it.

Where it is used

• Stripe wrote in 2017 that it limits how many API requests each user can send with a token bucket, so one user's spike or a broken script cannot slow the API down for everyone else.
• Amazon API Gateway also uses a token bucket: a rate for the steady flow, a burst size for short peaks, and an answer of 429 Too Many Requests when both are used up.
• nginx can limit requests per client IP address (limit_req), for example in front of a search page that is expensive to run.

Stages

rl1: the first request is allowed (very easy)

One worker sends one request, with nothing else going on. A key that has never been used before starts with its full allowance, so this first request must be allowed. Example: New(50, 5), then Allow("k") -> true.

The tester will verify: the first request for a brand new key is allowed.

rl2: a small burst gets through (easy)

One worker fires 7 requests one after another, with no pause between them. The burst size is 5, so about 5 of them should get through right away, and the rest should be denied until some time passes. Example: New(50, 5), then call Allow("k") seven times with no delay in between. The first 5 calls return true, the next 2 return false.

The tester will verify: at least 5 requests are allowed, and no more than about 5 or 6, since almost no real time passes between the calls.

rl3: the rate holds under heavy traffic (medium)

4 workers each fire 250 requests, 4 milliseconds apart, all using the same key. That is 1,000 requests over about one second of real time, far more than the limiter should allow. Out of those 1,000, somewhere between about 40 and 56 should be allowed over that one second.

The tester will verify: the number allowed lands in that range, scaled to the real time your run actually took. Too many means the cap is not holding, too few means the refill is too slow.

The tester also runs 400 short rounds on fresh keys. Each key starts with an allowance of 1,000 and refills at 1 per second. One call spends the first unit, then 8 callers start together. Each keeps asking until it is denied. Exactly 1,000 requests should get through in total, including the first call. Each caller counts its own answers.

This also checks that each unit goes to one caller, not several callers who read the same old allowance. Only rounds shorter than half a second count, before a whole unit can refill. If it cannot collect enough short rounds within its retry budget, it tries grading again rather than blaming your code. Check and spend in one atomic step, using a lock, an atomic update, or one owner of the state.

rl4: a burst, a pause, then a steady stream (medium)

One worker fires 10 requests with no delay, well past the 5 request burst size, so some must be denied. Then it waits 120 milliseconds, then fires 25 more requests 30 milliseconds apart. That pace is slower than the allowed rate, so every single one of those 25 should be allowed.

The tester will verify: at least one request was denied during the first burst, and every one of the 25 later, paced requests was allowed.

rl5: heavy traffic on two keys at once (hard)

6 workers fire 200 requests each, 5 milliseconds apart, about 1,200 requests over about one second, split between two different keys. Each key on its own should allow somewhere between about 40 and 56 requests over that time, the same range as rl3, and together both keys should allow somewhere between about 83 and 112, with at least one denial and at least one request allowed somewhere in the run.

The tester will verify: the rate holds in that same kind of range for each key on its own, and for both keys added together.

rl6: Allow speed (L2, hard)

Keep Allow fast even under heavy use. Every answer must still be correct. In JavaScript the db answers at once in this stage, so only your own code is timed. Note that rl1 to rl5 are timed too: they all assume Allow is fast compared to how often requests arrive. Heavy work inside Allow, such as holding a lock for longer than needed, can make those earlier stages fail as well, not just this one. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.

The tester will verify: your code takes at most 1.5 times as long as our solution in the same language, and every answer stays correct. How many memory allocations you use is also shown, but it never decides a pass or a fail.

rl7: a quiet client, then a flood (L3, hard)

A caller that was quiet for a long time does not get a bigger burst. And a counter that resets at fixed points lets two bursts through at the edge. One worker, one key:

1 request, then 400 ms of silence, then 30 requests at once     -> at most the burst gets through
25 times: 1 request, 100 ms of silence, 15 requests 2 ms apart  -> at most the burst, plus what
                                                                   refilled during those 30 ms

The tester will verify: no stretch of back-to-back requests lets through more than the burst plus what refilled during that stretch, and the overall rate holds.

Rules

• Standard library only.
• Your limiter will be called from many workers at once. Give out each unit of allowance to exactly one caller, even when calls overlap, and never pause or sleep inside Allow.
• Track allowance separately for each key, and let go of keys you stop seeing so memory does not grow without bound.
• Measure elapsed time with your language's steady, always moving clock, such as a monotonic clock or a performance counter, never a calendar clock that tells you the date and time of day. A calendar clock can jump backward or forward, for example when the system time gets corrected, and that jump can freeze your refill or hand out a free burst.

Read the Rate Limiter notes in the wiki