Module 6: Load Balancing and Statelessness

3. Load balancing algorithms

Next →

Description

The previous lesson said the balancer "spreads the requests among the servers", but left the black box closed. This lesson opens it: how the balancer decides which server to send each request to. There are three algorithms that cover almost all real cases, and you'll see them run and measured, not described from memory. Round-robin: rotates through the servers in order —the first, the second, the third, and back to the start—; it spreads perfectly when the requests are uniform. Least-connections: sends each request to the server with the fewest active connections at that moment; it wins when requests last different amounts of time, because it doesn't pile long requests on a server that's already busy. By hash: computes hash(key) % N and sends the request to whichever server comes out; the key property is that the same key always falls on the same server, useful when locality matters (for example, for a per-server cache).

You'll run the three. You'll see that round-robin spreads 12 requests as [4, 4, 4]; that least-connections, with requests of unequal duration, lowers the worst server's peak from 13 to 8; and that hash balancing sends aX9kR2q always to app-3. With that you'll be able to choose the correct algorithm for Enlace and defend the choice with the measured distribution, not with intuition.

Connection to the module: this lesson details the spreading mechanism lesson 2 only named. The hash balancing you'll see here is a direct cousin of the consistent hashing from module 5 —the same "the key decides the destination" idea—, and of lesson 5 of this module, where the client's hash is what implements sticky sessions (and that's why it imbalances them). Round-robin and least-connections are the ones the project (lesson 8) will use for Enlace's hot path. Choosing well here is half the design of the balancing layer.

The one directing the supermarket registers

Think of it this way, revisiting the supermarket from the introduction. You have four registers and someone standing directing the customers. There are three ways to direct, and each one is an algorithm:

  • By turns (round-robin): "you to 1, you to 2, you to 3, you to 4, you to 1 again…". The one directing looks at nothing, just rotates. It's very simple and works wonderfully if all customers take roughly the same time to pay. But if register 1 gets three customers in a row with carts full to the top and register 2 gets three with a single item, register 1 gets stuck even though the "by heads" spread was perfect: it spread customers, not work.
  • To the shortest line (least-connections): "go to the register with the fewest people waiting". Now the one directing looks at how many customers are at each register and sends the newcomer to the clearest one. This adapts on its own: if register 1 has a customer with an enormous cart (takes a long time), its line doesn't drop, so the one directing stops sending people there until it frees up. It spreads work, not heads.
  • By identity (by hash): "all customers whose surname starts with A-F, to register 1, always". The one directing uses a fixed rule based on who the customer is, not on the lines. The advantage: the same customer always returns to the same register —and if that register "remembers" something about them (where they left their cart, their coupons), it finds it there—. The disadvantage you'll see: if one surname has a great many customers, its register saturates and the others sit idle.

Three ways to direct, three algorithms. The rest of the lesson runs them.

Round-robin: rotate in order

The simplest and most common. The balancer keeps a pointer that rotates: it sends the first request to server 0, the second to 1, the third to 2, the fourth to 0 again, and so on in a circle. It looks at nothing about the server or the request: it just counts. Here it is, run:

# round_robin.py — round-robin distribution over a pool
from collections import Counter

class RoundRobinBalancer:
    def __init__(self, servers):
        self.servers = servers
        self.next = 0                     # the pointer that rotates

    def pick(self):
        server = self.servers[self.next]
        self.next = (self.next + 1) % len(self.servers)   # advance and wrap
        return server

servers = ["app-0", "app-1", "app-2"]
lb = RoundRobinBalancer(servers)

routed = [lb.pick() for _ in range(12)]     # 12 incoming requests
print("spread order:", " ".join(routed))
print("count per server:", dict(Counter(routed)))

What to expect. With python round_robin.py:

spread order: app-0 app-1 app-2 app-0 app-1 app-2 app-0 app-1 app-2 app-0 app-1 app-2

count per server: {'app-0': 4, 'app-1': 4, 'app-2': 4}

Perfect spread: twelve requests, four to each of the three servers. All the logic is the (self.next + 1) % len(self.servers) —advance the pointer and wrap when reaching the end—. Round-robin is so simple that it's the default algorithm of almost all balancers, and for Enlace's hot path —a resolve is a cheap and uniform request: look up a short_code and return the long_url, they all cost about the same— it's an excellent choice. When the requests are interchangeable in cost, spreading by heads is spreading the work.

The asterisk, which the next section makes explicit: round-robin spreads requests, not work. It takes for granted that all requests cost the same. When that's false —some take 2 ms and others 2 seconds— round-robin can pile several expensive ones on the same server by pure bad luck of the turn, and there the next algorithm is better.

Least-connections: to the one with the least work

Least-connections looks, before spreading, at how many active connections (in-progress requests) each server has, and sends the new one to the one with the fewest. The intuition: a server with many active connections is busy (maybe serving long requests), so avoid it; one with few is free, send it work. It adapts on its own to the requests' real cost, which round-robin doesn't do.

To see it, we simulate a scenario where the requests last different amounts of time: most are short (~2 time units), but 15% are heavy (~120 units). We measure the peak of simultaneous connections each server reaches —the moment of most pressure, which is what determines whether a server goes down—:

# least_conn.py — round-robin against least-connections when requests
# last different amounts of time. We measure the peak simultaneous connections per server.
import random

def simulate(strategy, n_servers, requests):
    """requests = list of (arrival_time, duration). Returns the peak per server."""
    active = [[] for _ in range(n_servers)]   # per server: list of end times
    peak = [0] * n_servers
    rr = 0
    for arrival, duration in requests:
        # 1) free the already-finished connections on each server
        for s in range(n_servers):
            active[s] = [end for end in active[s] if end > arrival]
        # 2) choose server according to the strategy
        if strategy == "round-robin":
            s = rr
            rr = (rr + 1) % n_servers
        else:  # least-connections
            s = min(range(n_servers), key=lambda i: len(active[i]))
        # 3) assign
        active[s].append(arrival + duration)
        peak[s] = max(peak[s], len(active[s]))
    return peak

random.seed(42)
N = 4
# 5000 requests: most short (~2 ticks), 15% VERY long (~120 ticks)
reqs = []
for i in range(5000):
    dur = 120 if random.random() < 0.15 else 2     # 15% are heavy
    reqs.append((i, dur))

for strat in ("round-robin", "least-connections"):
    peak = simulate(strat, N, reqs)
    print(f"{strat:>18}: peak per server = {peak}  ->  worst server = {max(peak)}")

What to expect. With python least_conn.py:

       round-robin: peak per server = [11, 13, 10, 11]  ->  worst server = 13
 least-connections: peak per server = [8, 8, 8, 7]  ->  worst server = 8

There's the difference. With requests of unequal duration, round-robin ends up piling 13 simultaneous connections on its worst server (app-1), because it spreads blindly and, by bad luck of the turn, several heavy requests fall on the same one. Least-connections, which looks at the load before deciding, never lets a server go above 8: when a server accumulates long requests, its active count rises and the balancer stops sending to it until it frees up. The worst server's peak drops from 13 to 8 —almost 40% less pressure at the most critical point— and the spread ends up even ([8, 8, 8, 7] against the uneven [11, 13, 10, 11]). That peak is exactly what determines when a server saturates, so lowering it is money directly.

The lesson: least-connections wins when the requests last different amounts of time; round-robin ties it (and is simpler) when they all cost the same. For Enlace, whose resolve is uniform, round-robin is enough; but if Enlace added an expensive and variable endpoint (for example, generating an analytics report that sometimes takes seconds), least-connections would keep those slow requests from sinking a server while the others idle.

By hash: the same key, always to the same server

The third algorithm doesn't seek to spread evenly by itself, but to guarantee destination consistency: that the same key —the short_code, or the client's IP— always falls on the same server. You compute hash(key) % N and that's the server. Here it is, with the short_code as the key:

# hash_lb.py — hash balancing: the same key ALWAYS falls on the same server
import hashlib
from collections import Counter

def hash_pick(key, servers):
    h = int(hashlib.md5(key.encode()).hexdigest(), 16)
    return servers[h % len(servers)]

servers = ["app-0", "app-1", "app-2", "app-3"]
codes = ["aX9kR2q", "bY0lS3r", "cZ1mT4s", "aX9kR2q", "aX9kR2q", "bY0lS3r"]

for code in codes:
    print(f"{code} -> {hash_pick(code, servers)}")

# spread over 100k distinct short_codes: even among the 4 servers
import string
alphabet = string.digits + string.ascii_letters
def make_code(n):
    s = ""
    while n:
        s, n = alphabet[n % 62] + s, n // 62
    return s.rjust(7, "0")

dist = Counter(hash_pick(make_code(100_000_000 + i), servers) for i in range(100_000))
print("\nspread of 100k codes:", dict(sorted(dist.items())))

What to expect. With python hash_lb.py:

aX9kR2q -> app-3
bY0lS3r -> app-2
cZ1mT4s -> app-3
aX9kR2q -> app-3
aX9kR2q -> app-3
bY0lS3r -> app-2

spread of 100k codes: {'app-0': 25036, 'app-1': 24685, 'app-2': 25307, 'app-3': 24972}

Notice two things. First, the consistency: aX9kR2q falls on app-3 all three times it appears, and bY0lS3r on app-2 both times. The key determines the server, always the same. Second, the spread is still even when there are many distinct keys: 100,000 different short_codes spread ~25,000 per server, because a good hash scatters the keys uniformly. So hash balancing gives you consistency and an even spread —as long as there are many keys and none is disproportionately popular—.

What's destination consistency good for? For locality. If each server has its own local cache, always sending aX9kR2q to app-3 means app-3 caches aX9kR2q once and serves all its visits from its warm cache, without the other three caching the same in duplicate. It's also the mechanism behind sticky sessions (lesson 5): hashing the client's IP or cookie pins them to a server. But careful —and this is the big topic of lesson 5—: if a key is enormously more popular than the rest (a viral link, or a "whale" client), the hash sends all of it to the same server and saturates it. Hash balancing spreads the keys evenly, not the traffic, and when the traffic is concentrated in a few keys, that's a problem.

And a continuity note: hash(key) % N is exactly the formula module 5 dismantled in "the mod-N problem". If you change the number of servers N, almost all the keys change destination —emptying local caches at once—. The solution, if you care about keeping the balancing hash stable when adding servers, is the same as module 5's: consistent hashing (the ring). Many balancers offer it precisely for this. This lesson's hash balancing and that module's consistent hashing are the same family of ideas at two different layers.

The decision table

Let's put the three together in a table you can use to choose:

AlgorithmHow it decidesWins when…For Enlace
Round-robinRotates in order, blind to content and loadThe requests are uniform in costThe choice for the hot path (resolve is uniform)
Least-connectionsTo the server with the fewest active connectionsThe requests last different amounts of time (some short, some long)Useful if Enlace adds expensive and variable endpoints
By hashhash(key) % N, same key → same serverLocality or client→server affinity mattersFor a per-server local cache or sticky sessions (careful of the imbalance)

There's a fourth variant worth naming: weighted round-robin. If your servers aren't equal —some have twice the CPU as others—, you assign them weights and the balancer sends more requests to the more powerful ones (two to the big one for each one to the small one). It's round-robin with quotas, for heterogeneous pools. In Enlace, where the app servers are identical clones, it's not needed; but it's good to know it exists for when the pool is mixed.

Common mistakes

Using round-robin with requests of very unequal cost (algorithm mistake). What happens: someone puts round-robin in a service where some requests take 2 ms and others 2 seconds, and every so often a server saturates while the others idle —because the turn piled, by chance, several slow requests on it—. Why it happens: round-robin spreads heads, not work, and takes for granted that they all cost the same. How to detect it: if the load between servers is uneven despite round-robin, and your requests vary a lot in duration, it's the symptom —you measured it: peak 13 against 8—. How to fix it: switch to least-connections, which looks at the real load and doesn't pile the slow on a busy server.

Hash-balancing a key with a dominant value (distribution mistake). What happens: someone balances by hash of the short_code expecting an even spread, but a link goes viral and concentrates 40% of the traffic; that short_code always falls on one server, which saturates while the other three are at 30%. Why it happens: the hash spreads keys evenly, not traffic; when the traffic is concentrated in a few hot keys, the even spread of keys doesn't translate into an even spread of load. How to detect it: if one server is much more loaded than the rest and you use hash of the key, look for a dominant key. How to fix it: for Enlace's hot path, use round-robin (which does spread a viral link's traffic among all the servers). Reserve the hash for when locality matters and the keys have even traffic.

Forgetting that hash % N breaks when changing N (operational mistake). What happens: someone balances by hash(key) % N with local caches, adds a server (N goes from 4 to 5), and suddenly almost all the keys change server, emptying all the local caches at once —a storm of misses right when you scale—. Why it happens: it's module 5's mod-N problem, now at the balancing layer. How to detect it: if adding a server tanks the local caches' hit ratio, your hash isn't stable under N changes. How to fix it: use consistent hashing (module 5's ring) in the balancer, which when adding a server only remaps ~1/N of the keys, not almost all. Many balancers bring it as an option precisely for this.

Exercises

Exercise 1 — Trace the round-robin. A round-robin balancer with servers [app-0, app-1, app-2] receives 7 requests. The pointer starts at app-0. (a) Which server does each of the 7 go to? (b) How many does each server receive in the end? (c) If an eighth arrived, which would it go to?

See solution

Round-robin rotates app-0 → app-1 → app-2 → app-0 → …:

Request1234567
Serverapp-0app-1app-2app-0app-1app-2app-0
  • (a) The order is app-0, app-1, app-2, app-0, app-1, app-2, app-0.
  • (b) app-0: 3, app-1: 2, app-2: 2. It's not perfectly even because 7 isn't a multiple of 3 —the "leftover" goes to the first in the cycle—. With a multiple of 3 (like the 12 in the example) it comes out exact.
  • (c) The eighth would go to app-1 (the pointer was left pointing there after the seventh, which went to app-0).

Exercise 2 — Choose the algorithm. For each service, say which algorithm (round-robin, least-connections, or by hash) you'd choose and why in one sentence. (a) Enlace's resolve: uniform requests, a GET to a short_code. (b) A "generate PDF" service where some documents take 100 ms and others 30 seconds. (c) A service where each server caches the user's data locally and you want a user to always return to their server to take advantage of that cache.

See solution
  • (a) Round-robin. Requests uniform in cost → spreading by heads is spreading the work. It's simple, fast, and perfect for the case; there's nothing to gain by looking at the load or hashing.
  • (b) Least-connections. Very unequal durations (100 ms against 30 s) → you have to look at the real load to not pile the slow PDFs on one server while the others finish the fast ones. Round-robin, blind, would saturate by chance; least-connections adapts.
  • (c) By hash (of the user identifier). You want user→server affinity to take advantage of the local cache: hashing the user always sends them to the same server, which already has their data warm. Careful of dominant keys (a "whale" user saturates their server) and of stability under N changes (use consistent hashing).

Exercise 3 — The viral link breaks the hash. Enlace balances by hash(short_code) % 4 among four servers. Normally the traffic spreads ~25% each. One day, a short_code goes viral and by itself concentrates 40% of all the visits. (a) What happens to the server where that short_code falls? (b) Would the same have happened with round-robin? (c) What algorithm should Enlace use on the hot path and why?

See solution
  • (a) The viral short_code always falls on the same server (the hash is deterministic), so that server receives 40% of the viral traffic plus its normal share of the rest —it ends up well above 25%, while the other three drop—. It saturates while the others idle. The hash spread the keys evenly, but not the traffic, which was concentrated in one key.
  • (b) No. Round-robin spreads each visit by turns, without looking at which short_code it's for. The visits to the viral link are spread among the four servers equally, so no server gets 40% —the viral traffic dilutes in the pool—. Round-robin is immune to dominant keys because it doesn't route by key.
  • (c) Round-robin for Enlace's hot path. The resolve is uniform in cost (nothing to gain with least-connections) and the traffic can concentrate in viral links (which the hash would worsen). Round-robin spreads blindly, and for uniform requests with possible hot keys, "blind" is exactly what you want: it doesn't give any server more than its turn.

Summary and next step

In this lesson you opened the black box of the spreading and ran the three algorithms that matter. Round-robin rotates in order and spreads perfectly ([4, 4, 4]) when the requests are uniform —the choice for Enlace's resolve—; its limit is that it spreads heads, not work. Least-connections looks at the active connections and sends to the clearest server, and you measured it: with requests of unequal duration it lowers the worst server's peak from 13 to 8, because it doesn't pile the slow on the busy. By hash sends the same key always to the same server (aX9kR2q → app-3 every time) with an even spread among many keys (~25,000 of 100,000 per server), useful for locality and affinity —with two cautions: dominant keys imbalance it, and hash % N breaks when changing N (use consistent hashing)—. And you saw weighted round-robin for heterogeneous pools.

Before moving on you should be able to: describe how each algorithm decides; explain why least-connections wins with requests of unequal cost and round-robin suffices when they're uniform; and say why hash balancing is useful for locality but imbalances with a dominant key.

What comes next is the other half of the module. The three algorithms you just saw take for granted that any server can serve any request —round-robin sends the next one to another server without asking—. That only works if the servers are stateless. In lesson 4 you'll see, run, what happens when they're not: a session kept in one server's RAM makes most requests fail when round-robin spreads them, and the stateless version fixes them all. It's the hidden requirement that makes everything from today possible.

Resources

← Previous2. What is a load balancerNext →4. Stateless versus stateful services