Articles

The rate limiter you just built has one job: look at a request and say yes or no. It is a small program, but it is the same small program that sits in front of every API gateway, load balancer, and login form on the internet. When a server answers “429 Too Many Requests”, that answer came from this program. This article starts from the fixed-window counter you wrote, shows the one place it breaks, and walks through the three algorithms production systems use instead.

Why the counter has to say no

A rate limiter is an admission-control device. It answers one question: has this client already had its share? Sinha and Chopra state the purpose plainly:

Rate limiting is an essential mechanism for API management and security. By restricting the number of requests a client can make within a specified timeframe, rate limiting helps prevent abuse and overuse of your API.

The reason is not politeness. A server that admits every request can be drowned - a single buggy client or a deliberate attacker can hold the connection pool hostage while legitimate users wait. The limiter is what turns “the server is down” into “this one client is throttled.” It is the same idea as the backpressure in the bounded-job-queue project: say no at the edge, so the middle never has to.

The first instinct: a fixed window

The natural first version is a counter that resets on a schedule. Pick a window - say ten seconds - and count the requests inside it. When the window rolls over, zero the counter and start again. The state is two numbers: where the window started, and how many requests have arrived since.

defmodule FixedWindow do
  @window 10
  @max 3

  def allow?(state, now) do
    if now - state.window_start >= @window do
      {:allow, %{window_start: now, count: 1}}
    else
      if state.count < @max do
        {:allow, %{state | count: state.count + 1}}
      else
        {:deny, state}
      end
    end
  end
end

Run it against a client that sends three requests at the end of one window and three at the start of the next:

time	verdict
9.0	allow
9.5	allow
9.9	allow
10.1	allow
10.2	allow
10.3	allow

Six requests, all admitted, in 1.3 seconds - at a limit of three per ten seconds. The counter did its job and still let twice the intended rate through.

The window edge

The bug is the boundary. The fixed window draws an invisible line every ten seconds, and the counter forgets everything the moment a request lands on the far side of the line. The requests at 9.9 and 10.1 are 0.2 seconds apart, but they fall in different windows, so the second one starts from a clean slate.

This is not a rare corner. It is the first thing a determined client tries, because the boundary is predictable. A client that can count can line its requests up so that half land just before the boundary and half just after, doubling its allowance forever. The fixed window’s count is correct within any single window; it is wrong across two, and a limit that is wrong across two is wrong everywhere that matters.

The site’s article on what O(n) actually promises names the shape of the error: the fixed window measures the rate over a window that is allowed to start at a boundary, when the guarantee a rate limiter actually makes is over any ten-second span.

A sliding window

The fix is to stop drawing boundaries and count a rolling span instead: how many requests arrived in the last ten seconds, measured from now, wherever now falls. Keep a queue of the admitted timestamps, evict the ones older than the window, and count what is left.

defmodule SlidingWindow do
  @window 10
  @max 3

  def allow?(log, now) do
    log = Enum.filter(log, &(&1 > now - @window))

    if length(log) < @max do
      {:allow, log ++ [now]}
    else
      {:deny, log}
    end
  end
end

The same six timestamps now come out differently:

time	verdict
9.0	allow
9.5	allow
9.9	allow
10.1	deny
10.2	deny
10.3	deny

At 10.1 the three requests from 9.0, 9.5, and 9.9 are all still inside the last ten seconds, so the fourth is refused. Three in any ten-second span, no matter where the span starts.

Your rate-limiter project already makes this rolling decision - its allow? filters past for timestamps inside the last ten seconds and counts them. What this version changes is the bookkeeping. The project keeps the whole list and scans it on every check; the sliding-window log keeps only the timestamps that can still matter. A production version stores the log in a two-ended queue so eviction and insertion each cost $O(1)$ , the same structure the stacks, queues, and associative arrays article names.

The two buckets

The sliding window is correct but pays $O(1)$ per stored timestamp. When the limiter fronts a service that sees millions of requests a second, even a queue is too much state. The two bucket algorithms shrink the state to a single number.

Sinha and Chopra list them with the sliding window as the standard set:

Token bucket algorithm: This algorithm visualizes rate limits as a bucket with a fixed number of tokens. Each request consumes a token, and new tokens are added to the bucket at a set rate. Requests are rejected if there are no available tokens.

Leaky bucket algorithm: Similar to the token bucket, the leaky bucket algorithm has a bucket but with a hole at the bottom. Tokens are added at a set rate, but they also leak out at a constant rate. Requests are rejected if the bucket is full.

The two buckets differ in what they allow a client to do in a burst. A token bucket fills with tokens at a steady rate and holds a fixed maximum, so a client that has been idle can spend the whole bucket at once - a burst is allowed, then the client waits while the bucket refills. A leaky bucket forces a constant outflow: requests queue up and are served at the fixed rate, so a burst is smoothed rather than permitted. Token buckets admit bursts; leaky buckets erase them.

Both keep the state to two numbers - the current count and a timestamp of the last refill - and spend $O(1)$ per request. The cost is precision: the bucket forgets when inside the window each request arrived, so it can approximate the window but not reproduce it exactly.

Choosing one

Algorithm	State	Cost	Burst behavior	The catch
Fixed window	two numbers	$O(1)$	allows a double burst at the boundary	wrong across two windows
Sliding window	a queue of timestamps	$O(1)$ per entry	no burst; exact count	memory grows with the rate
Token bucket	two numbers	$O(1)$	allows a bounded burst	approximate window
Leaky bucket	two numbers	$O(1)$	no burst; smooths to a constant rate	queues requests instead of refusing

The choice is a trade between precision and memory. A fixed window is what you write in an afternoon and reject in a review; a sliding window is what you ship when correctness matters and the rate is low enough to afford the queue; a token bucket is what sits in front of an API at scale, tolerating small bursts and refusing the rest.

The same move at production scale

A rate limiter is the algorithms-past-the-interview move wearing a small costume. The “select the structure” decision is the whole game: the fixed window’s counter is a number that needs to be zeroed on a schedule, the sliding window’s log is a queue, and the bucket’s refill arithmetic is a rate expressed as a slope. The “name the bound” move is the guarantee itself - three per ten seconds is a statement about a rate, and every one of these algorithms is a different way to turn that statement into a running program.

One detail ties it to a structure you already know. In a real system the limiter is usually keyed per client - “this IP has had its share” - which means the counter or bucket is a value in a hash table, one entry per client, with the same $O(1)$ average lookup and the same fine print the hash tables article describes. The timestamp is the thing being windowed, and the window arithmetic is the same boundary problem the time and monotonicity: JavaScript vs. Elixir article walks through.

Where to go next

Rate limiter - the fixed-window project this article upgrades. If you have not finished it, do; the sliding-window version here is the natural next step.
Bounded job queue - the admission-control sibling. A rate limiter refuses at the door; a bounded queue refuses at the inbox. Both are the same “say no before the middle drowns” idea.
What O(n) actually promises - the notation behind “three per ten seconds” and why the fixed window’s error is a bound that is wrong across two windows.
Hash tables: the O(1) that has fine print - the per-client keyed limiter, and the fine print on the lookup.
Stacks, queues, and associative arrays - the queue that makes the sliding window $O(1)$ per timestamp.
Algorithms past the interview - the four moves, of which “name the bound” and “select the structure” are the rate limiter’s entire job.

A rate limiter is a bound with a memory. The fixed window forgets at the boundary, the sliding window remembers the last ten seconds exactly, and the bucket remembers only a running total. All three answer the same question - has this client had its share - and the difference between them is the difference between a limit that is true and a limit that is only true until the next boundary.

Rate limiting: the window that expires before it floods