DEV Community

Dilip V P
Dilip V P

Posted on

The Rate Limiter That Lets Through Double

#api #webdev #systemdesign #backend

A rate limiter sits in front of a service and decides how many requests each client is allowed to send. Within the limit, accepted. Over it, rejected with a 429 Too Many Requests.

To do that it has to track three things:

  • The key. Whose request is this? A user ID, an API key, or an IP address.
  • The window. How much of the recent past counts? Say the last one second.
  • The count. How many requests has this sender already made in that window?

The simplest version

Split time into fixed one second intervals. Keep one counter per user. Every request increments it. Once it reaches ten, reject the rest. When a new interval starts, reset to zero.

00:00.000  counter = 0
00:00.100  request  counter = 1
...
00:00.900  request  counter = 10   limit reached, reject from here
00:01.000  new interval, counter = 0
Enter fullscreen mode Exit fullscreen mode

One integer per user. Cheap, simple, and it looks correct.

The hole

Ten requests land in the last 50 milliseconds of one interval. The counter reads ten out of ten.

The interval ends. The counter resets to zero.

Ten more land in the first 50 milliseconds of the next interval. Fresh counter, ten out of ten again.

| interval 1              | interval 2              |
|                  x x x x| x x x x                 |
|                  10 reqs| 10 reqs                 |
                   ^ reset here
Enter fullscreen mode Exit fullscreen mode

Twenty requests inside a tenth of a second, against a limit of ten per second. Every single one passed a legal check. There is no bug in the code and no mistake in the configuration.

This is the boundary problem of the fixed window counter: around a reset, a client can send up to double the limit, legally.

Why it matters

It is not an edge case you can ignore. A client does not need to be malicious to hit it, and a client that is malicious can hit it deliberately every second, forever.

The fix is to stop letting the window reset underneath you. That is what the sliding window does: instead of asking "how many requests in this interval", it asks "how many in the last one second, measured back from right now". No reset, no doubling.

It costs more to store, which is where the other algorithms come in. But the fixed window's limit is the first thing worth understanding, because it is the implementation most of us write first.

Top comments (0)