Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 36 ยท Building Blocks

Load Balancing and Distributed Rate Limiting

Compare round robin, least connections and power of two choices, then learn token bucket and sliding window rate limits across nodes, with simulations.

Two jobs sit in front of almost every service. A load balancer spreads incoming requests over many servers so that none is overwhelmed. A rate limiter protects the service from clients that send too much, whether by accident (a retry loop) or on purpose (abuse). Both look simple on a single machine and get interesting as soon as there are many nodes and no single place that sees every request.

In this lesson you will compare the main balancing algorithms in a simulation, and then see why a per-node rate limit does not behave like a global limit. Both ideas connect to resilience patterns later in the course.

What a load balancer decides

Balancing algorithms

Round robin Take turns, ignore the load.
Random Pick any server.
Least connections Send to the least busy server.
Power of two Pick two at random, use the less busy.

Simple rules work until requests differ a lot in cost.

1 / 2

A balancer also needs health checks (to stop sending traffic to dead servers) and sometimes stickiness (so one user keeps hitting the same server, for example to reuse an in-memory session). It must not become a single point of failure itself, so production setups run several balancers behind DNS or anycast addresses.

The algorithms

  • Round robin sends request 1 to server 1, request 2 to server 2, and so on. It is fair about the number of requests and blind to their cost. If every request takes about the same time, it works very well.
  • Random needs no state at all. With many requests the counts even out, but on short timescales some servers receive noticeably more.
  • Least connections keeps a count of in-flight requests per server and picks the minimum. It reacts to slow requests, but it needs accurate, up-to-date counts. With several balancers, each one only sees its own share of the traffic.
  • Power of two choices picks two servers at random and sends the request to the one with fewer in-flight requests. It needs only two lookups instead of a scan of every server, and surprisingly this tiny bit of information removes most of the imbalance that pure random causes.
  • Weighted variants of all of these give more traffic to bigger servers.
  • Consistent hashing maps a key (user ID, URL) to a server so the same key tends to land in the same place, which is useful for caches. See sharding.

Comparing algorithms by simulation

The simulation sends 4,000 requests to 8 servers. Most requests are fast (1 time unit), but 1 in 10 is very slow (60 or 120 units), which is a realistic mix of cheap lookups and heavy reports. We measure the peak number of requests in flight on one server, which is a proxy for the worst overload. A seeded random generator keeps the results identical every time.

Python Four balancing policies under uneven requests

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.

Read both columns. Round robin shares the request count perfectly (spread 0), yet it has a higher peak than least connections, because it keeps feeding servers that are stuck with a slow request. Least connections has the lowest peak (3). Its spread is large, though: when everything is idle, ties go to the first server, so server 0 serves many quick requests while the busy ones are left alone. That is not a flaw, since what matters is load in flight, not request counts. Power of two choices lands close to least connections with far less bookkeeping, and random has the highest peak.

Your numbers will vary with the seed and with the mix of request costs. The lesson is that the right algorithm depends on how uneven your requests are.

Rate limiting

A rate limiter decides, for each request, whether to let it through or reject it (usually with HTTP status 429, Too Many Requests). It protects against overload, keeps one noisy client from hurting others, and caps costs.

Two algorithms cover most needs:

  • Token bucket. A bucket holds up to capacity tokens and refills at rate tokens per second. Each request takes one token; if the bucket is empty, the request is rejected. Bursts up to the capacity are allowed, and the long-run rate is capped at rate.
  • Sliding window. Count the requests in the last window seconds and allow a new one only if the count is below limit. It has no sudden resets at window boundaries (a plain "fixed window" counter lets a client send a full limit just before and just after the boundary, doubling the burst).

The first example runs both against one client that sends 100 requests during one second, with a limit of 10 per second. A load balancer spreads the requests over 4 gateway nodes in turn.

Python Local limits, a shared limit and a 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.

The result shows the central problem. Four nodes with their own local counters each allow 10 requests, so the client gets 40 requests through a "10 per second" limit. A shared counter lets exactly 10 through. Splitting the limit into 2 per node comes close (8 here), but it is unfair when the balancer spreads traffic unevenly: a node with more traffic rejects requests while the others still have room. The token bucket allows the first five requests as an immediate burst and then refills at 10 per second, ending with 14 allowed requests in total, five from the initial burst plus roughly ten refilled during the second.

Rate limiting across nodes

There are three common ways to enforce a global limit:

  1. Central store. Every node increments a counter in a shared store such as Redis (a Lua script or atomic command keeps the check-and-increment together). It is accurate but adds a network call to every request, and the store becomes a dependency.
  2. Sticky routing. Route each client (by API key or IP) to the same limiter node using consistent hashing, so a local counter is enough. It is cheap, but a node failure resets or loses some counters.
  3. Local counters with periodic sync. Each node allows requests locally and shares usage with the others every few hundred milliseconds. It is fast and approximate: you accept a small overshoot to avoid a network call per request.

Which to choose depends on how strict the limit must be. A billing quota should be exact. A "please don't hammer the login page" limit can be approximate.

If the limiter store becomes unavailable, decide in advance whether to fail open (allow traffic, risking overload) or fail closed (reject traffic, risking an outage for everyone). Most public APIs fail open for general limits and closed for security-critical ones.

Rate limiting also has a polite side: tell clients when to come back. A 429 response with a Retry-After header works well with retries and backoff, and it prevents retry storms.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can round robin overload one server even though it shares requests evenly?

    Round robin balances the number of requests, not the work. A server stuck with a few slow requests keeps receiving new ones.
  2. 2. What does power of two choices do?

    Comparing just two random candidates gets most of the benefit of least connections without tracking every server.
  3. 3. Four nodes each enforce a local limit of 10 requests per second per client. What is the effective limit for one client?

    Each node counts only the requests it sees, so the limits add up. A global limit needs a shared counter, sticky routing or synchronization.
  4. 4. What is the main difference between a token bucket and a sliding window?

    A bucket accumulates unused tokens, so a quiet client can burst briefly. A sliding window simply counts recent requests against a fixed limit.

Summary

  • A load balancer spreads requests across servers using algorithms such as round robin, random, least connections and power of two choices; the best choice depends on how uneven request costs are.
  • Health checks keep dead servers out of the pool, and balancers themselves must be redundant.
  • Token buckets allow bursts at a capped average rate; sliding windows count requests in the recent past.
  • Per-node limits add up across nodes, so global limits need a shared store, sticky routing or periodic synchronization, with a decision on fail-open or fail-closed.
  • Return 429 with Retry-After so clients back off.

Next: Gossip Protocols and Probabilistic Structures.