Reliability & Scale · Lesson 03

Rate Limiting Algorithms

Every public API eventually gets hammered — by a runaway client loop, a DDoS, or just unexpected success. Rate limiting is how you protect capacity and enforce fair use. The algorithm you pick shapes whether bursts are allowed, how much memory you spend, and how precisely the limit holds.

Why rate limiting is hard to get right

A rate limit sounds simple: "no more than 100 requests per minute." But the moment you ask "per minute starting when?" or "what if the same client fires 99 requests in the last millisecond of minute one and 99 more in the first millisecond of minute two?" you discover the problem is genuinely subtle. Different algorithms make different trade-offs between burst tolerance, memory cost, and accuracy. Picking the wrong one can mean either blocking legitimate clients or letting a determined abuser slip through.

Think of rate limiting like a nightclub bouncer. A simple bouncer counts tickets for the hour and stops at capacity — but two groups can each cram in at 11:59 and 12:00, filling the place twice over in two minutes. A smarter bouncer has a sliding memory of who came in over the last 60 minutes, not the current clock-aligned block. Even smarter: a token dispenser that gives out admission tokens at a steady drip, letting crowds absorb small bursts without overwhelming the dance floor.

Algorithm 1 — Fixed window counter

How it works

Divide time into fixed, non-overlapping buckets (e.g., "the minute 14:07:00–14:07:59"). Keep one counter per (client, window). On each request: compute the current window key, increment the counter, and reject if it exceeds the limit. At the start of a new window, the counter resets to zero.

The window key is typically floor(now / window_seconds). This is a single integer operation, which is why it's trivially cheap: one integer stored per client.

# Fixed window counter — pseudo-code
function is_allowed(client_id, limit, window_seconds):
  now         = current_unix_timestamp()
  window_key  = floor(now / window_seconds)
  redis_key   = "rl:" + client_id + ":" + window_key

  count = INCR(redis_key)          # atomic; returns new value
  if count == 1:
    EXPIRE(redis_key, window_seconds * 2)  # clean up old keys

  return count <= limit

Pros and cons

Best for: coarse-grained quota enforcement where a 2× burst at boundaries is acceptable — e.g., "no more than 10,000 API calls per day per account" for billing purposes.

Algorithm 2 — Sliding window log

How it works

Instead of a single counter, keep a log (sorted set) of every request's timestamp for each client. On every request, evict entries older than the window, count the remaining entries, and reject if over the limit. The window is always the last N seconds ending right now — it slides with real time.

# Sliding window log — pseudo-code (Redis sorted set)
function is_allowed(client_id, limit, window_ms):
  now      = current_unix_ms()
  key      = "rl:" + client_id
  cutoff   = now - window_ms

  # Atomic Lua script (all-or-nothing, no race condition)
  lua_script = """
    local key     = KEYS[1]
    local now     = tonumber(ARGV[1])
    local cutoff  = tonumber(ARGV[2])
    local limit   = tonumber(ARGV[3])
    local window  = tonumber(ARGV[4])

    redis.call('ZREMRANGEBYSCORE', key, '-inf', cutoff)  -- evict old
    local count = redis.call('ZCARD', key)               -- count current
    if count < limit then
      redis.call('ZADD', key, now, now)                  -- log this request
      redis.call('EXPIRE', key, window / 1000)
      return 1   -- allowed
    end
    return 0     -- rejected
  """

  return EVAL(lua_script, key, now, cutoff, limit, window_ms) == 1

Pros and cons

Best for: low-to-medium volume APIs where precision is critical — security-sensitive endpoints, payment flows — and per-client limits are not enormous.

Algorithm 3 — Sliding window counter

How it works

This is the sweet spot between fixed window (cheap but imprecise) and log (precise but heavy). Keep two fixed-window counters: the current window and the previous window. When evaluating a request at time t, compute a weighted estimate of how much of the previous window's traffic still falls inside the last N seconds:

estimated_count = prev_count × (1 − elapsed_fraction) + curr_count

If elapsed_fraction = 0.3 (30% through the current window), then 70% of the previous window's requests are still "recent." The approximation error is at most ~1/limit of the true rate — negligible for limits above ~10.

# Sliding window counter — pseudo-code
function is_allowed(client_id, limit, window_seconds):
  now              = current_unix_timestamp()
  curr_window      = floor(now / window_seconds)
  prev_window      = curr_window - 1
  elapsed_fraction = (now % window_seconds) / window_seconds

  curr_key = "rl:" + client_id + ":" + curr_window
  prev_key = "rl:" + client_id + ":" + prev_window

  curr_count = GET(curr_key) OR 0
  prev_count = GET(prev_key) OR 0

  # Weighted estimate: how many requests in the last window_seconds?
  estimate = prev_count × (1.0 - elapsed_fraction) + curr_count

  if estimate >= limit:
    return REJECTED

  INCR(curr_key)
  if curr_count == 0:
    EXPIRE(curr_key, window_seconds * 2)
  return ALLOWED

Pros and cons

Best for: general-purpose API rate limiting at scale. This is the algorithm used by most production API gateways because it balances accuracy and storage cost well. Cloudflare uses a variant of this approach.

Algorithm 4 — Token bucket

How it works

Imagine a physical bucket that holds up to B tokens. Tokens drip in at a constant refill rate r (tokens per second). Each request consumes one token. If the bucket is empty, the request is rejected. If you haven't made any requests, tokens accumulate — up to the bucket's maximum capacity — which means you can legitimately absorb a short burst whenever you've been idle.

The key insight: the bucket capacity B controls the maximum burst size; the refill rate r controls the sustained rate. They're independently configurable.

# Token bucket — pseudo-code (lazy refill, no background thread needed)
function is_allowed(client_id, capacity, refill_rate):
  # Load persisted state {tokens, last_refill_time}
  state = LOAD(client_id) OR { tokens: capacity, last_refill: now() }

  now_ts       = current_unix_timestamp()
  elapsed      = now_ts - state.last_refill
  new_tokens   = elapsed × refill_rate

  # Refill up to capacity (lazy — computed at request time, not on a timer)
  state.tokens = MIN(capacity, state.tokens + new_tokens)
  state.last_refill = now_ts

  if state.tokens < 1:
    SAVE(client_id, state)
    return REJECTED  # bucket empty

  state.tokens -= 1
  SAVE(client_id, state)
  return ALLOWED

Pros and cons

Best for: APIs with naturally bursty clients — mobile apps, SDKs with retry logic, batch importers. The AWS API Gateway, Stripe, and many payment APIs use token-bucket semantics because clients doing legitimate bulk operations earn burst capacity through prior quiet periods.

Algorithm 5 — Leaky bucket

How it works

Flip the mental model: instead of tokens dripping in and requests consuming them, requests drip in and a drain processes them at a constant rate. Imagine a physical bucket with a hole at the bottom. Water (requests) pours in at any rate; it drips out at a fixed rate. If the bucket overflows (queue is full), excess requests are dropped. The key property: the output is always at a constant, predictable rate regardless of the input shape.

# Leaky bucket — pseudo-code (queue-based)
function handle_request(client_id, request, queue_capacity, drain_rate):
  queue = GET_QUEUE(client_id)  # in-memory or Redis list

  if len(queue) >= queue_capacity:
    return REJECTED  # bucket overflowed

  ENQUEUE(queue, request)
  return QUEUED  # will be drained at drain_rate

# Background drain loop (runs at drain_rate)
function drain_loop(client_id, drain_rate):
  interval = 1.0 / drain_rate  # seconds between each drain
  while True:
    request = DEQUEUE(GET_QUEUE(client_id))
    if request:
      FORWARD_TO_BACKEND(request)
    SLEEP(interval)

Pros and cons

Best for: network egress shaping or protecting downstream services (databases, third-party APIs) that have strict throughput limits and cannot tolerate any burstiness. Less common for public API rate limiting, more common at the infrastructure level.

Algorithm comparison

Where to enforce rate limits

Rate limiting can live at several layers. Each layer has a different view of the traffic and different failure modes.

Most production systems stack layers: CDN for IP-based abuse, API gateway for authenticated quota enforcement, and application-level logic for fine-grained per-operation limits.

Distributed rate limiting

In a single-server deployment, an in-memory counter is sufficient. In a horizontally scaled fleet, every instance needs to see the same counter — otherwise "limit 100 req/min" becomes "limit 100 per node" and your actual limit is 100 × number of nodes. The canonical solution is a shared external store, almost universally Redis in practice.

Atomic operations: INCR and Lua scripts

Redis is single-threaded for command execution. A simple INCR is guaranteed atomic: two simultaneous calls from different nodes will both succeed, and the counter will reach exactly 2 — no lost increments. For operations that need to read and conditionally write (like token bucket's "check tokens, decrement if allowed"), a Lua script is atomic as a unit because Redis executes the entire script without yielding:

-- Redis Lua: atomic fixed-window check-and-increment
local key     = KEYS[1]
local limit   = tonumber(ARGV[1])
local window  = tonumber(ARGV[2])

local count   = redis.call('INCR', key)
if count == 1 then
  redis.call('EXPIRE', key, window)  -- set TTL only on first write
end
if count > limit then
  return 0   -- rejected
end
return 1     -- allowed

Clock skew

In a distributed fleet, different nodes have slightly different wall-clock readings — usually milliseconds to tens of milliseconds apart due to NTP drift. For fixed-window counters this means a request arriving at 14:07:59.998 on one node and 14:08:00.003 on another (due to network latency + clock drift) will be counted in different windows. The practical impact is small — it's essentially an additional source of the boundary-burst error — but it means you should not rely on rate limiters for exact second-level enforcement. If you need millisecond precision, use a centralized Redis with timestamps from the Redis server itself (TIME command) rather than trusting the application node's clock.

-- Use Redis server time, not application node time
local time   = redis.call('TIME')         -- {seconds, microseconds}
local now_ms = tonumber(time[1]) * 1000 + math.floor(tonumber(time[2]) / 1000)

The HTTP response contract for rate limits

When a request is rejected for exceeding the rate limit, the server must return HTTP 429 Too Many Requests. Simply returning 429 is not enough — clients need machine-readable information to implement proper backoff. The standard headers are:

Client behavior: the right way to handle 429

# Client-side rate limit handling — pseudo-code
function api_call(endpoint, max_retries=5):
  for attempt in range(max_retries):
    response = HTTP_GET(endpoint)

    # On every response: track remaining quota
    remaining = response.headers['X-RateLimit-Remaining']
    reset_at  = response.headers['X-RateLimit-Reset']

    if response.status == 200:
      return response.body

    if response.status == 429:
      retry_after = response.headers.get('Retry-After', 60)
      wait_seconds = float(retry_after) + jitter()  # add jitter!
      LOG("Rate limited. Waiting " + wait_seconds + "s")
      SLEEP(wait_seconds)
      continue

    raise UnexpectedError(response.status)

  raise MaxRetriesExceeded()

How to debug & inspect it

Rate limit bugs come in two flavours: clients hitting 429 they did not expect, and limits that are not enforcing at all (clients sending far more than the limit without being stopped). Both are diagnosable with a handful of curl commands and a careful read of the response headers.

Read the headers on every response

A well-behaved API sends X-RateLimit-* on every 2xx, not just on 429. The fastest diagnostic is to add -I or -v and read the state of the window before you hit the wall:

Reproduce a 429 with a tight request loop

When debugging whether a client is the source of its own 429s, fire a controlled burst and read the Retry-After value exactly as a client would:

Diagnose a distributed-counter race

If your API fleet uses a shared Redis counter but clients consistently hit more than the stated limit, the likely cause is a non-atomic read-modify-write instead of an atomic Lua script or INCR:

Diagnose clock skew

In a distributed fleet, windows computed from wall-clock time on different nodes will not align perfectly. The symptom is a fixed-window counter that resets a few milliseconds earlier on some nodes, allowing a small extra burst. Verify by comparing the Redis TIME against the application node's clock:

Worked numeric token-bucket trace

Capacity B = 10 tokens, refill rate r = 2 tokens/second. Starting state: full bucket (10 tokens). Five events over 6 seconds:

Key observations: the burst at t=0.3 drained the bucket; the 2.5-second idle at t=2.8 earned 5 tokens back; capping at capacity means idle time never accumulates past the burst maximum, so a client cannot "save up" an unbounded burst by staying quiet for hours.

Symptom → cause → fix

1. On every 429, read Retry-After and wait that many seconds plus jitter before retrying — never retry immediately.
2. Add the rate-limit headers (X-RateLimit-Remaining, X-RateLimit-Reset) to your client wrapper so your code can self-throttle before hitting 429.
3. In staging, force-expire the Redis key and re-run the request to confirm the counter starts fresh: redis-cli DEL "rl:user_42:28333".
4. Verify atomicity: grep your Lua script or check that you use INCR (not GET + SET) — a non-atomic read-modify-write will under-count under concurrency.
5. Check that your key includes both the client identifier and the window key — a key that omits the window component never resets.

In production: how leading APIs do it

Rate limiting is not a configuration toggle — it is an architectural decision that shapes how clients build integrations and how support teams debug outages. Five platforms that handle billions of API calls daily each made different algorithm choices, and those choices are reflected in the headers they return and the client behaviours they encourage.

Deep-dive: Stripe's four cooperating limiters

Stripe's publicly documented architecture runs not one but four rate limiters simultaneously on every inbound request. Each limiter targets a different failure mode, and a request is rejected if any single one of them trips.

The first is a request-rate limiter: a token bucket per account key that enforces the per-second ceiling most developers think of as "the" rate limit. The second is a concurrent-request limiter: it counts in-flight requests for a given key at any instant, regardless of rate. This catches the pattern where a client opens hundreds of connections simultaneously — each individually slow, but collectively exhausting connection pool capacity. The third is a fleet usage load shedder: when the overall fleet utilisation crosses a threshold, a portion of non-critical requests is shed to protect capacity for write operations and webhook delivery. This is not per-account — it is a global signal that fires during traffic spikes or partial outages. The fourth is a worker utilisation load shedder: individual compute workers monitor their own CPU and memory saturation and shed requests locally before they queue deeply. The practical consequence for integrators is that a well-behaved account observing the published req/s limits can still see a 429 during a platform-wide traffic event — and Retry-After is the correct response in all four cases.

This layered approach is worth understanding when designing your own API: a single rate limit rarely covers all the ways a client can overwhelm a system. Concurrent connections, burst depth, and fleet-level health are distinct axes.

How leading APIs do it

By the numbers: what Redis stores, the write, and the delay

Make it concrete. The limiter is capacity B = 100 tokens, refill r = 50 tokens/second (so a sustained 50 req/s, with bursts up to 100). Per account, Redis stores just two fields in a hash rl:{account}:

Every request runs this read → compute → write as ONE atomic Lua script (atomic so two app servers can't both spend the last token):

The key formula is the delay a throttled client must wait. When the bucket holds t tokens (0 ≤ t < 1), the next token arrives in (1 − t) / r seconds, so:

Trace a burst that drains the bucket — B = 100, r = 50/s, starting full, a client fires 130 requests at t = 0 then keeps polling:

The decision math (sizing the bucket): capacity B is the maximum burst you tolerate; refill r is the sustained rate you guarantee. To let a client briefly burst to 2× their steady rate for up to 2 seconds, set B = r + (2r − r)·2 = 3r. And the worst-case extra load a full fleet of C clients can dump in one instant is C × B requests — size your backend so a synchronized burst (C × B) doesn't tip it over, or add the concurrency limiter and load shedders from the Stripe section below.

Sources & further reading

• Cloudflare — Rate Limiting Rules documentation
• Stripe — API Rate Limits (token bucket semantics, headers)
• MDN — HTTP 429 Too Many Requests
• RFC 6585 §4 — Additional HTTP Status Codes: 429 Too Many Requests
• Redis — Lua scripting for atomic operations
• AWS Builders' Library — Using load shedding to avoid overload