SD6.2 · LESSON 2 OF 6

Routing policies

Route requests across instances and calculate capacity with headroom, startup time and instance failures.

THE IDEA

Routing policies

A load balancer picks a server per request. Round-robin rotates, least-load chooses the server with the least work, hash-based routing sends the same key to the same server. Each uses a different signal, and request counts can mislead: with costs 10, 1, 10, 1, 10, 1 ms, round-robin gives each server 3 requests but 30 ms of work to one and 3 ms to the other, while least-load keeps the busiest at 21 ms.

cost of a heavy request (ms)10

requests (ms): 10, 1, 10, 1, 10, 1 round-robin → server 1: 30 ms, server 2: 3 ms (3 requests each) least-loaded → server 1: 21 ms, server 2: 12 ms the busiest server finishes at 30 ms under round-robin and 21 ms when work is balanced

Round-robin balances request counts; least-load uses a work signal; hash routing sends the same key to the same server (good for locality, bad for a hot key). Counts misrepresent load when requests cost different amounts.

Change how heavy the heavy requests are.

Predict first. Do two servers with the same request count necessarily have equal work?

Chapter context

Load balancing distributes work among eligible backends. Scaling changes available capacity. Both require the application to manage state and dependencies so adding a process actually adds useful throughput.

TRY IT YOURSELF

Part 1. Do it hands-on

Assign requests by hand, then write round-robin, least-loaded and hash routing.

cost of a heavy request (ms)10

round-robin work on server 1 on server 2 busiest server under least-loaded equal counts mean equal work? (yes/no)

To do: Six requests with work costs 10, 1, 10, 1, 10, 1 ms go to 2 servers by round-robin (1st→server 1, 2nd→server 2, 3rd→server 1, …). Total work on server 1?
To do: And on server 2?
To do: Least-loaded routing sends each request to the server with the least work so far (ties: server 1). The busiest server's total work?
To do: Both servers received 3 requests under round-robin. Do equal request counts mean equal work? Type yes or no

Part 2. Do it in code

round_robin(costs, n): total work per server when requests are assigned 1st → server 0, 2nd → server 1, … cyclically.
least_loaded(costs, n): assign each request to the server with the least total work so far (ties: lowest index); return the loads.
hash_route(key, n): sum(ord(c) for c in key) % n (a deterministic hash).
hash_loads(requests, n): requests is a list of (key, cost); total work per server by hash_route.
imbalance(loads): max load divided by mean load (1.0 means perfectly even; 0 loads give 1.0).
request_counts(assignments, n): number of requests per server from a list of server indexes.

def round_robin(costs, n):
    pass

def least_loaded(costs, n):
    pass

def hash_route(key, n):
    pass

def hash_loads(requests, n):
    pass

def imbalance(loads):
    pass

def request_counts(assignments, n):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Do two servers with the same request count necessarily have equal work?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

With demand R, per-instance capacity c and intended usable fraction u, require $ncu\ge R$ . To keep that same target after one failure, require $(n-1)cu\ge R$ . These are rate constraints, not a complete queueing or availability model.

Worked example

Demand is 900 requests/s. Each instance sustains 400 requests/s, but the target usable fraction is 75%, or 300 requests/s. Three instances meet normal demand. Four are required to maintain the same target capacity after losing one: (4−1)×300=900.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import ceil
demand,capacity,usable=900,400,.75
normal=ceil(demand/(capacity*usable))
resilient=normal+1
assert normal == 3 and resilient == 4
assert (resilient-1)*capacity*usable == demand

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Horizontal scaling can move the bottleneck to a database. Healthy and ready are not identical. A load balancer does not repair session or transaction state lost with a backend.