--- title: 'Load Balancing Algorithms' source: 'https://academia.sh/en/courses/network-operations/load-balancing-algorithms' course: 'Network Operations and Automation' language: en updated: '2026-08-17T18:07:16+00:00' license: 'CC BY-SA 4.0' --- # Load Balancing Algorithms Four distribution rules are run on the same forty subjects at two separate loads; at load 1200 overrunning subjects come out 6 / 0 / 0, at load 2600 23 / 40 / 40 and overrun units 533 / 245 / 264, 1160 units sit idle at 1200, and what makes the proportional rule's overrun column look clean is the 19 units it never distributes. The previous lesson held the rule constant and changed only the unit of distribution: request instead of connection. The gain across the forty-subject set was a single subject. So the real question is not in the unit but in **the rule itself.** Does a rule that splits load by capacity, or picks the least-loaded subject at every step, actually remove the tail? This is what this lesson measures, and the answer comes in a single table at two separate loads. A rule being "good" turns out true at one load and misleading at another. ## Four Rules A distribution rule is a function that binds an incoming job to one of forty subjects. Four rules are measured, and all four differ from each other in **what they read.** **Round robin** reads nothing. It cycles through the subjects in turn and gives every job to the next one. It keeps no state, does not know capacity, does not know instantaneous load. **Proportional** distribution allocates each subject a share proportional to its capacity. It reads capacity but not instantaneous load: it computes the shares up front and distributes accordingly. **Least connections** picks the currently least-loaded subject at every step. The form measured here is weighted: the comparison looks not at the raw connection count but at **the ratio of connection count to capacity.** It reads both capacity and instantaneous load, which makes it the most expensive of the four rules — it has to see all forty subjects' state for every decision. **Consistent hashing** drops a key of the job — a session ID, a client address — onto a ring and gives it to the first subject clockwise on the ring. It reads neither capacity nor instantaneous load; the only thing it reads is the key. The same key always goes to the same subject. Comparing these rules was done in the Traffic Layer course of the System Design and Distributed Systems curriculum, and the algorithm list is not repeated here. The difference is one sentence: **there the rules' design criteria were compared, here the tail a single rule leaves on forty subjects with unequal capacity is counted.** A rule is a configuration line, and all four are written in the same place: ```text # taught rule syntax, not run pool main { rule round-robin } pool main { rule proportional weight subject-01 22 weight subject-09 99 } pool main { rule least-connections metric open-connections / weight } pool main { rule consistent-hashing key session-id virtual 128 } ``` ## Two Loads, One Set The forty subjects' total capacity is **2336** units. The measurement runs on both sides of this number. **Load 1200** is a bit more than half the total capacity. Here the system has plenty of room, and overrun is entirely distribution's fault: if split correctly, no subject would overrun. **Load 2600** is above total capacity. Here overrun is unavoidable, and no rule can zero it out. The only question that can be asked is **who** the overrun falls on and **how much.** In between, **load 2000** is also measured; it is below capacity, but congestion has begun. The measurement's assumptions: - **TM7** — The forty subjects are the course's fixed set and are not changed in this lesson; capacities are between **22** and **99**, and the oracle is the set itself. - **TM8** — The load consists of divisible units; one unit consumes one unit of capacity on a subject. The load's class or delay does not enter distribution in this lesson. - **TM9** — All four rules run on **the same load and the same set.** The only difference between the rules is the field they read. - **TM10** — Proportional distribution's shares **round down** to whole numbers; the remaining units are not redistributed. This is part of the rule's own definition and is counted as a separate column in the measurement. - **TM11** — The least-connections rule picks the lower-numbered subject on a tie; the selection is deterministic and gives the same result when the run is repeated. - **TM12** — Consistent hashing represents every subject with **128** virtual points on the ring and uses the job's sequence number as the key. The hash function is deterministic. - **TM13** — The measurement is not a network measurement; no connection is opened, no request is sent. What is counted is the distribution in the fiction itself. ## The Measurement ```python """Four distribution rules on the same forty subjects: the tail moves, it does not vanish.""" import bisect SEED = 20260812 CLASSES = ("interactive", "batch", "standby") RING = 1 << 20 def generator(seed): d = seed % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r def subjects(count=40, seed=SEED): r, result = generator(seed), [] for i in range(count): result.append({"no": i + 1, "capacity": 20 + r(81), "delay": 5 + r(45), "class": CLASSES[r(3)], "special": r(9) == 0}) return result def ring_hash(x): x = (x * 2654435761) & 0xFFFFFFFF x ^= x >> 16 x = (x * 2246822507) & 0xFFFFFFFF x ^= x >> 13 return x % RING def distribute(load, subs, rule, virtual=128): """A single rule distributes load across forty subjects; also returns key -> subject.""" share, mapping = {s["no"]: 0 for s in subs}, {} if rule == "round-robin": for i in range(load): mapping[i + 1] = subs[i % len(subs)]["no"] share[mapping[i + 1]] += 1 elif rule == "proportional": total = sum(s["capacity"] for s in subs) for s in subs: share[s["no"]] = load * s["capacity"] // total elif rule == "least-connections": for i in range(load): least = min(subs, key=lambda s: (share[s["no"]] / s["capacity"], s["no"])) mapping[i + 1] = least["no"] share[least["no"]] += 1 elif rule == "consistent-hashing": ring = sorted((ring_hash(s["no"] * 7919 + k), s["no"]) for s in subs for k in range(virtual)) points = [p for p, _ in ring] for a in range(1, load + 1): mapping[a] = ring[bisect.bisect_left(points, ring_hash(a)) % len(ring)][1] share[mapping[a]] += 1 return share, mapping def overrun(share, subs): n = units = 0 for s in subs: over = share[s["no"]] - s["capacity"] if over > 0: n, units = n + 1, units + over return n, units RULES = ("round-robin", "proportional", "least-connections", "consistent-hashing") subs = subjects() print(f"subjects {len(subs)} | total capacity {sum(s['capacity'] for s in subs)} | " f"smallest {min(s['capacity'] for s in subs)} largest {max(s['capacity'] for s in subs)}") print() print(f"{'rule':<19s} {'load':>5s} {'over':>10s} {'over units':>11s} " f"{'idle':>12s} {'undistributed':>13s} {'no load at all':>16s}") for rule in RULES: for load in (1200, 2000, 2600): share, _ = distribute(load, subs, rule) n, units = overrun(share, subs) print(f"{rule:<19s} {load:5d} {n:10d} {units:11d} " f"{sum(max(0, s['capacity'] - share[s['no']]) for s in subs):12d} " f"{load - sum(share.values()):13d} " f"{sum(1 for s in subs if share[s['no']] == 0):16d}") remaining = [s for s in subs if s["no"] != 20] print() print(f"{'rule':<19s} {'share of subject 20':>20s} {'moved when removed':>19s}") for rule in ("round-robin", "least-connections", "consistent-hashing"): share, before = distribute(1200, subs, rule) _, after = distribute(1200, remaining, rule) print(f"{rule:<19s} {share[20]:20d} " f"{sum(1 for k in before if before[k] != after[k]):19d}") ``` ``` subjects 40 | total capacity 2336 | smallest 22 largest 99 rule load over over units idle undistributed no load at all round-robin 1200 6 24 1160 0 0 round-robin 2000 14 239 575 0 0 round-robin 2600 23 533 269 0 0 proportional 1200 0 0 1156 20 0 proportional 2000 0 0 357 21 0 proportional 2600 40 245 0 19 0 least-connections 1200 0 0 1136 0 0 least-connections 2000 0 0 336 0 0 least-connections 2600 40 264 0 0 0 consistent-hashing 1200 7 66 1202 0 0 consistent-hashing 2000 13 277 613 0 0 consistent-hashing 2600 22 559 295 0 0 rule share of subject 20 moved when removed round-robin 30 1181 least-connections 15 1181 consistent-hashing 29 29 ``` ## A Good Rule Did Not Remove the Tail The load-1200 rows say improving the rule works. Round-robin distribution overruns **6** subjects; proportional distribution and least-connections overrun **none.** Overrun units drop from **24** to **0.** A reading that stopped here would conclude the correct rule removed the tail. The load-2600 rows reverse this. Round-robin distribution overruns **23** subjects; proportional distribution and least-connections overrun **all forty of the forty.** The two rules said to be good took the overrunning-subject count from zero to forty. The overrun-units column reads in exactly the opposite direction: round-robin **533**, proportional **245**, least-connections **264**. That is, the round-robin rule overruns a small number of subjects a lot; the others overrun all subjects a little. **The tail did not lift; the pain spread to everyone.** Which of these two readings is correct is not the measurement's call. The choice between twenty-three subjects' heavy overrun and forty subjects' light overrun is a **policy** decision: should forty subjects slow down a little, or should seventeen of them go untouched while twenty-three take a heavy hit? The measurement does not answer this question, it only puts the two options' numbers side by side. Where load is above total capacity, there is also a lower bound. Total capacity is **2336**, load is **2600**; the difference is **264** units, and no rule that places all of the load can go below this. The least-connections rule's overrun units are exactly **264** — meaning this rule has found the best possible distribution of what can be placed. There is nothing better. ## What the Overrun Column Does Not See So what is proportional distribution's **245**? A number below the lower bound can only come up when not all of the load gets placed. The **undistributed** column to the right says this. The proportional rule rounds each subject's share down to a whole number and gives the remaining units to no one: **19** units at load 2600, **21** at 2000, **20** at 1200 never reach any subject. These units do not show up in the overrun column, nor in the idle column — because they were never distributed at all. The conclusion is this: what makes proportional distribution's overrun column look its best is **the work the rule does not do.** If this column were absent while the measurement put the two rules side by side, the comparison **245 < 264** would lead to a wrong conclusion. **Undistributed units are a tail too, and they never show up in the lever's overrun gauge.** The same column has another reading. At load 1200, while round-robin distribution overruns **6** subjects, **1160** units sit idle in the system — half of total capacity. Overrun and idleness exist at the same time. **A gauge that counts only overrun cannot see that half of capacity went unused**, and a gauge that counts only utilization cannot see that six subjects overran. The two columns have to be read separately. ## What Least Connections Cannot See The least-connections rule gave the measurement's best result, but that result depends on two conditions, and both sit outside the measurement. The first is cost. Round-robin increments a counter, consistent hashing computes a hash; least connections compares all forty subjects' instantaneous state for every decision and repeats this for every incoming job. The decision itself turns into work. The second, and heavier, is this: **least loaded within which set?** The rule in the measurement sees all forty subjects and every unit distributed up to that instant. In operations, the balancer is usually not a single one; more than one balancer stands in front of the same pool, and each can count only the connections **it itself** opened. Each balancer picks the least-loaded subject by its own view, all of them pick the same subject at the same time, and that subject overruns without showing up in anyone's gauge. This is another form of the previous lesson's flat gauge. There the lever measured the **wrong dimension**; here it measures the right dimension over an **incomplete set.** The table's best result of **264** units rests on the assumption that the rule sees all forty subjects — `TM9`. When the assumption falls, so does the result, and there is no column in the table that says it fell. ## Where Consistent Hashing Pays The consistent-hashing rows are not good for distribution: at load 1200, **7** subjects overrun, one more than round-robin; at 2600, overrun units are **559**, above round-robin's **533**. This is an expected result, because this rule also does not read capacity, and on top of that it adds the hash distribution's own variability. Where the rule pays off is in the lower table. When a single subject is removed from the pool, **1181** keys change place under round-robin, and again **1181** under least-connections — nearly all of twelve hundred. Under consistent hashing, the number of keys that change place is **29**, and that is exactly the removed subject's own share. The remaining thirty-nine subjects' keys stay in place. Why does the difference matter? Because a key moving does not just mean one request going to a different subject. Whatever had been accumulated on that subject depending on the key — session state, a warmed cache — is not on the new subject. Under round-robin, one subject leaving the pool invalidates this accumulation on all forty of the forty subjects. **Consistent hashing does not improve distribution; it bounds the tail's length when membership changes.** Removing a subject from the pool is also a lever move — and one of the most frequently pulled ones in this course, because maintenance, failure, and version changes all pass through here. The rule's choice determines up front how many of the forty subjects that move will disturb. ## Summary - At load 1200, round-robin distribution overruns **6** subjects by **24** units, proportional distribution and least-connections overrun **none**; improving the rule genuinely pays off here. - At load 2600, the same two rules overrun **all forty of the forty** subjects, round-robin only **23**; overrun units are **533**, **245**, and **264** respectively. The tail did not lift, the pain spread to everyone, and which is correct is a policy decision. - When total capacity is **2336** and load is **2600**, overrun's lower bound is **264** units; the least-connections rule finds exactly this number, and there is nothing better. - Proportional distribution's **245** is below the lower bound because the rule rounds shares down and never distributes **19** units; undistributed units show up in neither the overrun column nor the idle column. - At load 1200, while six subjects overrun, **1160** units sit idle in the system; overrun and idleness exist at the same time, and no single gauge says both. - Consistent hashing is not better than round-robin for distribution, but when a subject is removed, the keys that move are **29** instead of **1181** — where the rule pays off is not distribution, it is membership change. ## Next Step In these two lessons, the balancer stood in the same place throughout: in front of the forty subjects, deciding on their behalf. Whoever sent the load, the lever was on the subjects' side, and its purpose was to protect them. The same intermediary can be turned around: it can stand in front of the clients and decide **on their behalf.** The next lesson puts these two stances — reverse proxy and forward proxy — side by side, and counts how a single number, the same limit, produces two separate tails depending on which side it stands on.