Rate Limiting Algorithms Explained

What to limit, and where

Who is limited (the "key"): the key is the label that the limiter counts requests for.

• per user or per API key (a secret code that identifies a customer's app): the most common choice for APIs where users log in,
• per IP address: for traffic from users who are not logged in, like login pages and sign-up. (But many users can share one IP behind NAT, which lets many devices share one public address.)
• per endpoint: stricter limits on expensive endpoints (search, exports) or sensitive ones (login, OTP, password reset),
• per tenant or plan (a tenant is one customer account): "Free: 100 requests per minute; Pro: 1,000",
• global: protect a weak downstream system (one that you call), for example "at most 500 calls per second to the SMS provider".

Where to enforce:

• the API gateway or edge (post 13; a gateway is the single entry point in front of your services): it stops bad traffic early, before it costs anything,
• the service itself: for limits that know your business ("5 OTP requests per phone number per hour"; an OTP is a one-time password),
• the client: a well-made SDK (a code library for your API) can limit itself to avoid being rejected.

Algorithm 1: Fixed window counter

Count requests in fixed time windows (for example, each calendar minute). Set the count back to zero when the window changes. A window is a block of time.

Limit: 100 requests per minute

12:00:00 ─────────────── 12:01:00 ─────────────── 12:02:00
   count: 0 → 1 → … → 100 ✅   count resets to 0
   request 101 → ❌ 429

key = "rl:user42:" + current_minute   (e.g., rl:user42:202702251200)count = INCR keyif count == 1: EXPIRE key 60if count > 100: reject

• ✅ Very simple and uses little memory (one counter per key per window).
• ❌ The boundary burst problem. A client can send 100 requests at 12:00:59 and another 100 at 12:01:00. That is 200 requests in 2 seconds, double the intended rate.

Algorithm 2: Sliding window log

Store the time of every request (a timestamp). For each new request, remove the timestamps that are older than the window, and count what is left. Allow the request if the count is under the limit.

Limit 5 per 60 s. Log: [12:00:05, 12:00:20, 12:00:41, 12:00:50, 12:00:58]New request at 12:01:10 → drop 12:00:05 (older than 60 s) → 4 left → allow ✅, add 12:01:10

Redis is a fast in-memory data store. In Redis, a sorted set (a list kept in order by a score) works well. The score is the timestamp.

• ✅ Exact. No boundary bursts.
• ❌ Uses a lot of memory. It stores one entry per request. A limit of 10,000 per hour means up to 10,000 timestamps per client.

Algorithm 3: Sliding window counter (approximate)

A good middle way: keep counters for the current and the previous fixed window. Then weight the previous one by how much of it still overlaps the sliding window. (A sliding window is a window that moves with the clock, always covering the last 60 seconds.)

estimated_count = current_window_count                + previous_window_count × (1 − elapsed_fraction_of_current_window)

Example: the limit is 100 per minute. The time is 12:01:15, which is 25% into the current minute. So 75% of the previous minute is still inside the sliding window.

• Previous window (12:00–12:01): 80 requests.
• Current window so far: 30 requests.

• ✅ Reduces boundary bursts, and uses only two counters per key.
• ❌ Approximate. It assumes that requests in the previous window were spread evenly. In practice the result is very close.
• It is widely used at large scale.

Algorithm 4: Token bucket (the most popular for APIs)

Picture a bucket that holds tokens. A token is a permission to make one request:

• It has a maximum capacity (for example, 20 tokens), which is the burst size.
• Tokens are added at a steady rate (for example, 10 per second), which is the sustained rate.
• Each request takes one token. If the bucket is empty, the request is rejected (or waits).

You do not need a timer that adds tokens. Just store tokens and last_refill_time. On each request, work out the new count:

tokens = min(capacity, tokens + (now − last_refill_time) × refill_rate)if tokens >= 1: tokens -= 1 → allowelse: reject (and compute when the next token will arrive → Retry-After)

• ✅ Allows short bursts (good for real users, who click in quick groups) and still enforces an average rate.
• ✅ Uses little memory (two numbers per key) and is easy to understand. It has two settings: burst and rate.
• ❌ Two settings to tune.

This is why token bucket is the most common choice for APIs. It is used in AWS API throttling, many API gateways, and Stripe's request limiter.

Algorithm 5: Leaky bucket

Picture a bucket with a small hole in the bottom:

• Requests pour into the bucket (a queue is a line of waiting items).
• They leak out and are processed at a constant rate.
• If the bucket overflows (the queue is full), new requests are rejected.

• ✅ A perfectly smooth output rate. It is ideal for protecting a downstream system that needs steady traffic (like a partner API or an SMS gateway).
• ❌ Bursts are queued (which adds latency, the waiting time) or dropped. It is less friendly for interactive APIs.
• NGINX (a popular web server) has a limit_req setting that uses the leaky bucket method.

Comparison

Distributed rate limiting

Say you have 20 API servers. Each server cannot keep its own counter. A client could get 20× the limit by spreading requests across servers. You need a shared view of the counts. This is called distributed rate limiting.

Option 1: A central store (usually Redis). Every server checks and updates the counter in Redis. A race condition can happen: two servers read "99" at the same time and both allow the request. To avoid it, make the check-and-update atomic (one step that cannot be split). Use INCR or a Lua script (a small program) that Redis runs as one step:

-- Token bucket in Redis (runs atomically)local key = KEYS[1]local capacity, rate, now = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])local b = redis.call("HMGET", key, "tokens", "ts")local tokens = tonumber(b[1]) or capacitylocal ts = tonumber(b[2]) or nowtokens = math.min(capacity, tokens + (now - ts) * rate)local allowed = 0if tokens >= 1 then tokens = tokens - 1; allowed = 1 endredis.call("HSET", key, "tokens", tokens, "ts", now)redis.call("EXPIRE", key, math.ceil(capacity / rate) * 2)return allowed

• ✅ Accurate and simple.
• ❌ Adds one network call per request (often about a millisecond), and Redis becomes a dependency. Decide what happens if Redis is down. Fail open means allow the traffic. This is usually right for general APIs. Fail closed means block the traffic. This may be right for login or OTP endpoints.

Option 2: Local counters with periodic sync. Each server enforces a share of the limit by itself, and shares its counts with the others every second or so. It is faster, but not exact.

Option 3: A dedicated rate-limit service, like Envoy's global rate-limit service. Gateways and proxies (servers that pass traffic on) call it.

Multi-region: counters in different regions (separate cloud areas) are hard to keep exactly the same (posts 27–28). Common ways are a separate budget for each region, or accepting that clients may go a little over the limit.

Telling clients about limits

Good APIs make limits visible to the client. They do it with HTTP headers (extra lines of information in a response):

HTTP/1.1 429 Too Many RequestsRetry-After: 12RateLimit-Limit: 100RateLimit-Remaining: 0RateLimit-Reset: 12Content-Type: application/problem+json{"title": "Rate limit exceeded", "detail": "100 requests per minute allowed on the Free plan."}

• 429 is the standard status code.
• Retry-After tells the client how long to wait. Well-behaved clients (post 41) honour it.
• RateLimit-* headers show the limit, how many requests remain, and when it resets. The IETF is still working on a standard for them as a draft, and the exact names may change. Many APIs use X-RateLimit-* variants. With these headers, clients can slow down before they hit the limit.
• Document limits clearly per plan and endpoint.

Rate limiting vs throttling vs load shedding

• Rate limiting: limits each client to a fair share. "You are sending too much."
• Throttling: often means slowing requests down (making them wait in a queue) instead of rejecting them.
• Load shedding (post 44): rejects requests because the server is overloaded, no matter who sent them. "We cannot handle more right now."

You usually need both rate limiting and load shedding. Rate limits do not protect you if all clients are within their limits but the total is still too much.