Split View: 레이트 리밋 알고리즘 고르기 — 고정 윈도우, 슬라이딩, 토큰 버킷의 실제 차이

Choosing a Rate Limiting Algorithm — What Really Separates Fixed Window, Sliding, and Token Bucket

Introduction — the limit was 100 per minute and 200 came in

You added a rate limit. 100 per minute per key. Then monitoring shows a client that pushed 200 requests through in the space of 200 milliseconds. You dig through the logs and there is nothing wrong with the code.

It is not a bug. It is the defined behaviour of the fixed window counter. And a limit deployed without knowing this fails to protect exactly the thing it was meant to protect.

Rate limiting looks like a one-line middleware, but it is really a bundle of four decisions. Which algorithm to use, what to key on, where to keep the counter in a distributed setup, and what to tell a client that has been blocked. Let us take them one at a time.

Four algorithms and their tradeoffs

The table alone narrows the choice. The sliding log is exact but expensive, and the fixed window is cheap but inaccurate. What is left in practice is the sliding window counter and the token bucket.

The fixed window boundary problem, in numbers

Say the limit is 100 per minute and the window resets at second zero of every minute. The client sends this.

10:00:59.900  100 requests   → 10:00 window counter 0 → 100. all pass
10:01:00.100  100 requests   → 10:01 window counter 0 → 100. all pass

200 requests passed in 200 milliseconds. Measured over any arbitrary continuous 60-second span, that is twice the limit. This is the fixed window ceiling. In any 60-second span, up to 2x can pass.

The larger the limit, the larger the absolute damage. With a limit of 6000 per minute, 12000 arrive in an instant. That is enough to take down the very backend you were protecting.

Chopping the window shorter mitigates it. Switching from 100 per minute to 2 per second makes the boundary overshoot smaller in absolute terms. But it also clips legitimate bursts, which degrades the user experience.

The sliding window counter adds the previous window count weighted by how much of the current window has elapsed.

current time is 10:01:15 (25% into the window)
previous window (10:00) count = 100
current window (10:01) count = 20

estimate = 100 * (1 - 0.25) + 20 = 95
95 < 100 so it passes. 5 more requests and it blocks

It is an approximation that assumes the previous window's requests were evenly distributed. Even when the assumption is off, the error is small. Cloudflare published an evaluation of this approach against its own traffic, and the share of requests wrongly allowed or wrongly blocked came out around 0.003 percent. In effect you get close to sliding-log accuracy with two counters.

The cost of the sliding log is worth pinning down too. If you put a timestamp per request into a Redis sorted set, a single element actually takes tens of bytes up to close to 100 bytes. With a limit of 100 and one million active keys, that is 100 million entries and several gigabytes. Compared with an approach that needs two counters, that is a three-order-of-magnitude difference.

Token bucket — why allowing bursts is the right fit for an API

A token bucket is defined by two numbers: bucket size and refill rate per second. When a request arrives you take one token out, and if there is none you reject it. Tokens refill in proportion to time but never exceed the bucket size.

Refilling is not done with a timer. You compute it from the elapsed time when a request arrives. That is why there are only two things to store, the token count and the last refill time.

function consume(state, now, capacity, refillPerSec, cost = 1) {
  const elapsed = (now - state.updatedAt) / 1000
  const tokens = Math.min(capacity, state.tokens + elapsed * refillPerSec)

  if (tokens < cost) {
    const wait = (cost - tokens) / refillPerSec
    return { allowed: false, retryAfter: Math.ceil(wait), state: { tokens, updatedAt: now } }
  }
  return { allowed: true, state: { tokens: tokens - cost, updatedAt: now } }
}

What matters here is that the burst is defined explicitly. With a bucket size of 20 and a refill of 10 per second, staying quiet and then firing 20 at once is allowed, while the long-run average stays pinned at 10 per second.

The reason that property fits APIs is that real clients do not send requests evenly. Opening one page fires eight parallel requests at once. A user opening a list and applying a filter bunches requests into a short interval. Enforcing 10 per second with a strict sliding window clips these perfectly normal screen loads. The user feels the service is broken while the server is idle.

The purpose of a rate limit is not to even out the spacing between requests but to keep long-run load under a ceiling. The token bucket expresses that purpose precisely. That is why most public APIs use it and publish the bucket size and refill rate directly in their documentation.

Cost weighting attaches naturally too. Charge 1 token for a list query and 20 tokens for report generation, and you end up limiting actual resource consumption rather than call counts. The GitHub API scoring queries differently by complexity is the same idea.

Distributed implementation — atomic operations and the error in local limits

With several nodes you have to share the counter, and the moment you share it you get a race condition. If another node slips in between the read, the decision, and the write, the limit gets exceeded.

Even the combination commonly used in Redis has a trap.

# dangerous — if the process dies right after INCR, a key with no TTL stays forever
INCR rl:user_8812:1784056020
EXPIRE rl:user_8812:1784056020 60

If the key never expires, that user stays blocked permanently with the counter pinned at the limit. It has to be handled atomically.

-- sliding window counter. KEYS[1]=previous window, KEYS[2]=current window
-- ARGV: 1=limit, 2=window length (seconds), 3=elapsed fraction of current window
local prev = tonumber(redis.call('GET', KEYS[1]) or '0')
local curr = tonumber(redis.call('GET', KEYS[2]) or '0')
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local elapsed = tonumber(ARGV[3])

local estimated = prev * (1 - elapsed) + curr
if estimated >= limit then
  return {0, limit, 0}
end

curr = redis.call('INCR', KEYS[2])
if curr == 1 then
  redis.call('EXPIRE', KEYS[2], window * 2)
end
return {1, limit, math.floor(limit - estimated - 1)}

A Lua script executes atomically on a single thread in Redis, so there is no room for anything to slip in between the decision and the increment. A token bucket can be moved over the same way, and recent Redis versions even ship an extension module for this purpose.

So how wrong is the approach of keeping a local counter on each node? With N nodes and a load balancer that distributes perfectly evenly, giving each node one Nth of the limit makes the total add up. There are two problems.

Distribution is not even. When connection reuse or hash-based routing pushes one client's requests onto a particular node, that client gets only one Nth of the total limit before being blocked. The real limit becomes far smaller than the advertised one.

The node count changes. When autoscaling adds nodes, each node's share has to be recomputed, and if it is not, the total allowance grows in proportion to the node count. Set 100 per minute on each of 10 nodes and the real limit is 1000 per minute.

So the practical arrangement is two layers. Keep a loose ceiling node-local to protect the node itself, and make the precise per-user decision in the shared store. If the store round trip is a burden, there is also the approach where a node leases tokens from a central bucket in batches and consumes them locally. That is a compromise that gives up a little accuracy to cut round trips sharply.

What happens when Redis goes down also has to be decided in advance. Blocking everything turns a limiter store outage into a total outage; passing everything removes protection at that exact moment. The usual choice is to pass, keep the node-local ceiling in force, and raise an alert.

What to key on

Keying on IP looks like the default, but it breaks in several directions.

There can be thousands of users behind one IP. Corporate networks, schools, and carrier-grade NAT are like that. Squeeze on IP and an entire group of legitimate users gets blocked wholesale.

Conversely, an attacker changes IP easily. Rotating IPs in the cloud costs almost nothing, and with IPv6 a single host is often assigned a whole prefix, which makes it effectively unlimited. When keying on IPv6, you have to group by the upper prefix rather than the full address for it to mean anything at all.

Reading the client IP behind a proxy also goes wrong often. X-Forwarded-For is a value the client can fill in arbitrarily, so trusting the front of the list verbatim lets an attacker claim a different IP on every request and neutralise the limit. You have to count your trusted proxies and take the value at that position counting from the end.

Set priorities like this. For an authenticated request, the user identifier or API key comes first. Since it ties to the pricing plan, apply a tenant-level quota alongside it. At pre-authentication stages, that is endpoints like login or signup, there is nothing much to use other than IP, so use IP but set the limit generously, and layer a separate account-identifier limit on top. Login attempts need a per-IP limit and a per-account limit at the same time in order to stop credential stuffing and single-account brute force together.

When you layer several keys, check the narrowest one first, and record which limit was hit in the response so debugging is possible.

429 and client retries

When the limit is exceeded, use 429. A 503 means server overload and a 403 means not authorised, so they mean different things. Send information along so the client can work out its situation.

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 12
RateLimit-Limit: 600
RateLimit-Remaining: 0
RateLimit-Reset: 12
Cache-Control: no-store

Retry-After takes seconds or an HTTP date, and the client should prefer this value over its own backoff calculation. The RateLimit family of headers is a set of fields being standardised at the IETF, reporting the remaining count and the time left until reset. The X-RateLimit prefixed versions that existing services have used are still widespread, so emitting both is a reasonable option.

The 429 response itself should be cheap. If a blocked request queries the database or does heavy serialization, attack traffic turns straight into load. Finish the limit decision as far forward as possible and keep the response body short. And do not attach cache headers to a 429. Incidents where an intermediate cache stored a 429 and served it back to a healthy client do happen.

Now the client side. What matters is what happens when a blocked client retries at a fixed interval.

Suppose the server wobbles briefly and 1000 clients fail at once. If they all retry after 1 second, 1000 requests arrive simultaneously one second later. The server wobbles again, they all retry after 2 seconds, and 1000 more arrive simultaneously two seconds later. Even with exponential backoff, deterministic intervals leave retries as a synchronized wave. This is the thundering herd.

The solution is randomness.

// do not do this — every client wakes up at the same instant
const delay = Math.min(cap, base * 2 ** attempt)

// full jitter — draw at random between 0 and the ceiling
const delay = Math.random() * Math.min(cap, base * 2 ** attempt)

In the backoff comparison AWS published, full jitter reduced both the total number of retries and the overall completion time. It even beat the approach that keeps half the ceiling fixed and randomizes only the rest. It looks counterintuitive, but spreading the wait times widely is simply more effective at reducing collisions.

There are other things to observe in a retry implementation. If the server gave a Retry-After, follow that value. Set a maximum attempt count and an overall deadline so retries do not go on forever. Retry on 429 and 5xx, but not on the rest of the 4xx family. And when you retry a non-idempotent request, send an idempotency key so duplicate execution is prevented. Blindly retrying a payment request that failed on a timeout can charge the customer twice.

Closing — what to decide before the algorithm

The first thing to decide when adding a rate limit is not the algorithm but what you are trying to protect. If it is backend capacity, a cost-weighted token bucket is right; if the goal is fair distribution, a tenant-level quota is right; if it is stopping brute force, a narrow limit layering account and IP is right. Different purposes mean different keys and different limits.

A fixed window can always let twice the limit through, and the cost of switching to a two-counter sliding window is close to nothing. After that, what remains is telling the client where it stands. Give it an accurate remaining count and retry time and a well-built client backs off on its own. Tell it nothing and everyone knocks on the door again at the same instant.