Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 65 ยท Load Balancing and Traffic

Rate Limiting and Its Algorithms

Learn why systems limit traffic and how token bucket, leaky bucket, fixed window, sliding window log and sliding window counter work, with Python code.

Every system has a capacity, and not every caller is friendly. A buggy client in a retry loop, a scraper, a password-guessing attack or one enthusiastic customer can flood a service and starve everyone else. Rate limiting controls how many requests a caller may make in a period of time, and rejects or delays the excess so the system stays healthy for everybody.

Rate limiting is related to, but different from, load balancing: balancing decides where traffic goes; limiting decides whether it is accepted at all. It usually runs at the edge, in an API gateway or reverse proxy, before the traffic reaches expensive services.

Why limit?

  • Protect availability: stop one caller from consuming all capacity (the "noisy neighbor").
  • Security: slow brute-force logins, credential stuffing and scraping.
  • Cost control: some calls cost money (a paid third-party API, an expensive query).
  • Fairness and tiers: free users get 100 requests a minute, paid users 10,000.
  • Stability: prevent overload that causes cascading failure.

Decide first what you limit and by what key: per user, API key, IP address, endpoint, tenant, or globally. Combine them: per-IP limits at the edge and per-user limits for the API.

What to do with excess requests

  • Reject with HTTP 429 Too Many Requests and a Retry-After header saying when to try again. Include X-RateLimit-Limit, X-RateLimit-Remaining and a reset time so well-behaved clients can slow down.
  • Queue or delay the request (smoothing), as in a leaky bucket.
  • Degrade: serve a cheaper response, or drop low-priority work first (load shedding).

Clients should respond to 429 with exponential backoff and jitter, not instant retries.

Five classic algorithms

Token bucket Allows bursts, steady average rate.
Leaky bucket Smooths output to a constant rate.
Fixed window Count per clock window. Simple, edge bursts.
Sliding window Log or counter. More accurate, more state.

Pick by burst tolerance, accuracy and memory.

1 / 2

Token bucket

Picture a bucket that holds up to capacity tokens. Tokens are added at a steady rate (say 5 per second) until the bucket is full. Each request needs one token; if one is available it is removed and the request proceeds, otherwise the request is rejected. A client that has been idle has a full bucket and can send a burst of up to capacity requests at once, but over time it cannot exceed rate.

The bucket is cheap to store: just two numbers per key, the token count and the time of last update. Instead of a timer adding tokens, compute them lazily when a request arrives: tokens = min(capacity, tokens + elapsed * rate).

Python Token bucket

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Five of the eight burst requests get through (the full bucket), three are rejected. Afterwards the steady 4-per-second stream exceeds the refill rate of 2, so about half is rejected until the pace slows. Token bucket is the most widely used algorithm because it matches real traffic: bursty but bounded.

Leaky bucket

Here requests enter a queue (the bucket) and are processed at a constant rate, like water dripping through a hole. If the queue is full, new requests overflow and are dropped. The output is perfectly smooth, which protects a downstream system that cannot tolerate bursts, but bursts are delayed rather than served quickly, and old queued requests can delay new ones. Think of it as a traffic shaper, while token bucket is a traffic policer that allows bursts.

Python Leaky bucket queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A burst of 10 fills the queue of 6 and drops 4. Then the queue drains at exactly 3 per second no matter how spiky the arrivals were.

Fixed window counter

Divide time into windows (for example, each minute). Keep a counter per key per window; if the counter exceeds the limit, reject. It is the simplest and cheapest scheme: one integer per key per window, easy to implement in a shared store with an atomic increment and an expiry.

Its flaw is the boundary problem: a client can send the full limit at the end of one window and the full limit at the start of the next, producing double the intended rate in a short time.

Sliding window log

Store the timestamp of every request in the last window. When a request arrives, drop timestamps older than the window, count what remains and accept only if the count is under the limit. It is exact, with no boundary bursts, but the memory per key grows with the limit (one entry per request), which is costly at scale.

Sliding window counter

A compromise. Keep counters for the current and the previous window, and estimate the rolling count as:

estimate = previous_count * (fraction of the previous window still covered) + current_count

It uses two numbers per key and is close to the exact answer. It is a common choice in large systems.

Comparing the window algorithms

The next simulation sends a worst-case pattern at a limit of 10 requests per 10 seconds: 10 requests at the very end of one window and 10 at the start of the next.

Python Fixed window vs sliding windows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fixed window lets all 20 requests through in two seconds, double the intended limit. The sliding log allows only 10, exactly right, and the sliding counter is close to the exact answer using just two counters.

Choosing an algorithm

Algorithm Allows bursts? Accuracy Memory per key Typical use
Token bucket Yes, up to capacity Good 2 numbers General API limits
Leaky bucket No (smooths) Good Queue Protect a fixed-rate backend
Fixed window At boundaries Rough 1 counter Simple quotas, cheap
Sliding log No Exact One entry per request Small limits needing precision
Sliding counter Slightly Close 2 counters Large-scale APIs

Rate limiting in a distributed system

With many gateway instances, each cannot count only its own traffic, or a client could get N times the limit by hitting different instances. Options:

  • Central store: keep counters in a fast shared store such as Redis, updating them with an atomic script or increment so two instances cannot both see "9 of 10" and both accept. This adds a network call per request.
  • Local limits with periodic sync: each instance gets a share of the limit and exchanges usage periodically. Faster, less exact.
  • Sticky routing: send each client's traffic to the same limiter node (see consistent hashing).
  • Fail open or closed: decide what happens if the limiter store is down. Failing open keeps the service available but unprotected; failing closed protects but may block everyone.

Further practices: return clear headers, document the limits, use different limits per endpoint (login is stricter than reads), allow trusted internal callers higher limits, and monitor how many requests are throttled. A sudden spike in 429s is a signal, either of abuse or of a limit set too low.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which algorithm allows a short burst but keeps a steady long-term average rate?

    A token bucket accumulates tokens while idle, so bursts up to its capacity are allowed, while refill sets the average.
  2. 2. What is the boundary problem of fixed windows?

    The counter resets at the boundary, allowing about twice the limit in a short period.
  3. 3. Which HTTP status code signals that a client exceeded its rate limit?

    429 Too Many Requests, ideally with a Retry-After header.
  4. 4. Why must counters in a shared store be updated atomically?

    A read-then-write race lets concurrent requests overshoot the limit.
  5. 5. How should a well-behaved client react to a 429?

    Backoff with jitter reduces load and avoids synchronized retry storms.

Summary

  • Rate limiting protects availability, security, cost and fairness by rejecting or delaying excess requests.
  • Token bucket allows bursts at a steady average; leaky bucket smooths output; fixed window is cheap but has boundary bursts; sliding log is exact but memory-hungry; sliding counter is a good compromise.
  • Choose the limit key carefully (user, key, IP, endpoint) and return 429 with Retry-After and rate-limit headers.
  • Distributed limiting needs a shared store with atomic updates, or local shares with syncing, and a fail-open or fail-closed decision.
  • Clients should back off with jitter.

Next: Caching Fundamentals and Strategies