Load Balancing Algorithms

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:

# 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

"""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.