---
title: 'Balancing Algorithms'
source: 'https://academia.sh/en/courses/traffic-layer/balancing-algorithms'
course: 'The Traffic Layer'
language: en
updated: '2026-08-23T07:01:36+00:00'
license: 'CC BY-SA 4.0'
---

# Balancing Algorithms

Changing the distribution rule itself: comparing the round-robin and least-connections rules by wait time and queue length under equal and slowed replicas, counting the fraction of keys that move under modulo hashing and consistent hashing when a node changes, the effect of virtual node count on distribution, and tracing that movement back to the introductory course's computation through the cache hit ratio.

The three lessons so far held the distribution rule fixed: replicas were picked in sequence. The
round-robin rule assumes two things — that the replicas are each other's equals, and that every
request does the same amount of work. Neither is always true. A replica can slow down, one
request can cost ten times more than another, and which replica a request lands on may need to
stay stable in a way that serves that replica's cache.

This lesson changes the rule itself. Three rules are covered: **round robin**, **least
connections**, and **consistent hashing**. The first two target how the load is split; the third
targets making the same key always land on the same replica.

## The Queue Model

The first two rules are compared with an in-process model. The model is a queue in which requests
arrive at fixed intervals and each replica is a single sequential server. A round is an abstract
step; arrival interval, request cost, and replica slowdown are model parameters, not measured
durations. Costs come from a fixed-seed generator, so both rules face the **same** request
sequence.

```js
// alg/queue.mjs — comparing the round-robin and least-connections rules under the same load.
// This is a MODEL: a round is an abstract step, and arrival interval, request cost, and replica
// slowdown are model parameters, not measured durations.
const REPLICAS = 3, REQUESTS = 300, ARRIVAL = 2;   // arrival interval (rounds)
const SEED = 20240730;

function costs(n) {                 // fixed-seed generator: same sequence on every run
  let s = SEED;
  const c = [];
  for (let i = 0; i < n; i += 1) { s = (s * 1103515245 + 12345) % 2147483648; c.push(1 + (s >>> 8) % 10); }
  return c;
}

function run(rule, cost, multiplier) {
  const reps = Array.from({ length: REPLICAS }, () => ({ freeAt: 0, work: 0, done: [], p: 0 }));
  let totalWait = 0, maxQueue = 0;
  for (let i = 0; i < cost.length; i += 1) {
    const t = i * ARRIVAL;
    for (const r of reps) while (r.p < r.done.length && r.done[r.p] <= t) r.p += 1;
    const queued = reps.map((r) => r.done.length - r.p);
    maxQueue = Math.max(maxQueue, ...queued);
    const target = rule === "round-robin" ? i % REPLICAS : queued.indexOf(Math.min(...queued));
    const r = reps[target];
    const start = Math.max(t, r.freeAt);
    totalWait += start - t;
    r.freeAt = start + cost[i] * multiplier[target];
    r.work += cost[i] * multiplier[target];
    r.done.push(r.freeAt);
  }
  return { wait: totalWait / cost.length, maxQueue,
    work: reps.map((r) => r.work), finish: Math.max(...reps.map((r) => r.freeAt)) };
}

const cost = costs(REQUESTS);
const totalWork = cost.reduce((a, b) => a + b, 0);
console.log(`${REQUESTS} requests, ${REPLICAS} replicas, arrival interval ${ARRIVAL} rounds, total work ${totalWork} rounds`);
console.log(`model utilization with equal replicas = ${((totalWork / (REQUESTS * ARRIVAL)) / REPLICAS).toFixed(3)}\n`);

for (const [name, multiplier] of [["equal replicas", [1, 1, 1]], ["k1 three times slower", [3, 1, 1]]]) {
  console.log(`scenario: ${name}`);
  console.log("  rule               average wait  max queue  finish round  work per replica");
  for (const rule of ["round-robin", "least-connections"]) {
    const r = run(rule, cost, multiplier);
    console.log(`  ${rule.padEnd(18)} ${r.wait.toFixed(2).padStart(13)} ` +
      `${String(r.maxQueue).padStart(10)} ${String(r.finish).padStart(13)}  ${r.work.join("/").padStart(16)}`);
  }
  console.log();
}
```

```
300 requests, 3 replicas, arrival interval 2 rounds, total work 1679 rounds
model utilization with equal replicas = 0.933

scenario: equal replicas
  rule               average wait  max queue  finish round  work per replica
  round-robin                 4.04          4           614       545/581/553
  least-connections           1.90          2           610       589/567/523

scenario: k1 three times slower
  rule               average wait  max queue  finish round  work per replica
  round-robin               170.97         63          1635      1635/581/553
  least-connections          56.99         18           843       843/697/701
```

With equal replicas, the two rules do the same total work and finish in nearly the same round: 614
versus 610. The difference shows up in waiting: average wait drops from 4.04 rounds to 1.90, and
the max queue drops from 4 to 2. Round robin can send a request to a busy replica while another
sits idle, because it counts its turn without looking at the replicas' state.

The work-per-replica column carries a reversed result: least connections' work distribution is
**more unbalanced** (589/567/523 versus 545/581/553). The rule is not trying to equalize work; it
equalizes the number of pending requests. Wherever the expensive requests land, the total work
piles up there. **Least connections is a waiting rule, not a fairness rule.**

The second scenario widens the gap. When one replica slows down threefold, round robin keeps
sending it a third of the requests: average wait climbs to 170.97 rounds, the max queue to 63, and
the finish round to 1635. Under least connections at the same slowdown, wait is 56.99, the queue
is 18, and the finish round is 843 — all three roughly three times lower. The rule sees the slow
replica's queue lengthen and, because of it, sends fewer requests there. This is the failure mode
the health check does not catch: the replica is responding, just slowly, so it is never dropped
from the pool.

## The Same Key, Always the Same Replica

The third rule answers a different question. If each replica keeps a local cache, having the same
tracking number always land on the same replica serves that cache; if the number lands on a
different replica every time, the same record ends up held in as many places as there are
replicas. A mapping from key to replica is needed, and its simplest form is the remainder of the
key's hash divided by the replica count.

The hash function was built in the Hash Tables lesson and is not re-derived here; below it is used
only as a tool. What is measured is **how many keys move when the node count changes**. The
numbers are deterministic and machine-independent, so this falls in the **computation** class, not
the measurement class.

```js
// alg/hash.mjs — comparing modulo hashing with consistent hashing: the fraction of keys that
// move when the replica count changes, distribution by virtual node count, and the C01 effect
const KEYS = 100_000;              // number of tracking numbers
const READ = 416.67;               // C01 Back-of-the-Envelope Estimation: peak read requests/s
const WRITE = 97.22;               // C01: peak write requests/s
const HIT = 0.90;                  // C01 assumption V9: fraction served from cache
const BASE_STORE = 138.89;         // C01: requests/s reaching the store
const WARMUP_S = 60;               // assumption W5: cache warmup window

function hash(text) {              // FNV-1a plus a final mix step; avalanche effect defined in
  let h = 2166136261;               // the Hash Tables lesson: similar keys must give distant values
  for (let i = 0; i < text.length; i += 1) h = Math.imul(h ^ text.charCodeAt(i), 16777619) >>> 0;
  h ^= h >>> 15; h = Math.imul(h, 2246822507) >>> 0; h ^= h >>> 13;
  return h >>> 0;
}

const keys = Array.from({ length: KEYS }, (_, i) => `G${1_000_000 + i}`);

const modulo = (a, replicas) => replicas[hash(a) % replicas.length];

function ring(replicas, virtual) {  // virtual node positions per replica, sorted by position
  const h = [];
  for (const k of replicas) for (let v = 0; v < virtual; v += 1) h.push([hash(`${k}#${v}`), k]);
  return h.sort((x, y) => x[0] - y[0]);
}
function onRing(a, h) {             // first position after the key's hash, wrapping to the start
  const c = hash(a);
  let lo = 0, hi = h.length - 1;
  if (c > h[hi][0]) return h[0][1];
  while (lo < hi) { const m = (lo + hi) >> 1; if (h[m][0] < c) lo = m + 1; else hi = m; }
  return h[lo][1];
}

const imbalance = (placement, replicas) => {
  const s = new Map(replicas.map((k) => [k, 0]));
  for (const k of placement) s.set(k, s.get(k) + 1);
  return (Math.max(...s.values()) / keys.length) * replicas.length;
};
const moved = (a, b) => a.filter((k, i) => k !== b[i]).length / a.length;

const THREE = ["k1", "k2", "k3"], FOUR = [...THREE, "k4"];
const result = {};

console.log("rule                           3 replicas imbalance   4 replicas imbalance  3->4 moved  4->3 moved");
{
  const u = keys.map((a) => modulo(a, THREE));
  const d = keys.map((a) => modulo(a, FOUR));
  result["modulo hashing"] = moved(u, d);
  console.log(`${"modulo hashing".padEnd(29)} ${imbalance(u, THREE).toFixed(3).padStart(21)}  ` +
    `${imbalance(d, FOUR).toFixed(3).padStart(21)}  ${moved(u, d).toFixed(4).padStart(10)}  ` +
    `${moved(d, u).toFixed(4).padStart(10)}`);
}
for (const virtual of [1, 10, 100, 1000]) {
  const hu = ring(THREE, virtual), hd = ring(FOUR, virtual);
  const u = keys.map((a) => onRing(a, hu));
  const d = keys.map((a) => onRing(a, hd));
  if (virtual === 1000) result["consistent hashing"] = moved(u, d);
  console.log(`${`consistent hashing (v=${virtual})`.padEnd(29)} ${imbalance(u, THREE).toFixed(3).padStart(21)}  ` +
    `${imbalance(d, FOUR).toFixed(3).padStart(21)}  ${moved(u, d).toFixed(4).padStart(10)}  ` +
    `${moved(d, u).toFixed(4).padStart(10)}`);
}

console.log(`\nimbalance under perfect distribution 1.000, perfect-move 3->4 ratio = ${(1 / 4).toFixed(4)}\n`);
console.log("rule                   moved   misses during warmup   reads behind cache/s   requests reaching store/s   x base   extra store requests");
for (const [name, ratio] of Object.entries(result)) {
  const miss = ratio + (1 - ratio) * (1 - HIT);
  const behind = READ * miss, store = behind + WRITE;
  console.log(`${name.padEnd(20)}${ratio.toFixed(4).padStart(8)}  ${miss.toFixed(4).padStart(21)}  ` +
    `${behind.toFixed(2).padStart(21)}  ${store.toFixed(2).padStart(26)}  ` +
    `${(store / BASE_STORE).toFixed(2).padStart(7)}  ${((store - BASE_STORE) * WARMUP_S).toFixed(0).padStart(21)}`);
}
console.log(`base (no warmup): reads behind cache ${(READ * (1 - HIT)).toFixed(2)} req/s, ` +
  `reaching store ${BASE_STORE} req/s`);
```

```
rule                           3 replicas imbalance   4 replicas imbalance  3->4 moved  4->3 moved
modulo hashing                                1.008                  1.004      0.7485      0.7485
consistent hashing (v=1)                      2.021                  2.231      0.5577      0.5577
consistent hashing (v=10)                     1.548                  1.722      0.1557      0.1557
consistent hashing (v=100)                    1.122                  1.204      0.2563      0.2563
consistent hashing (v=1000)                   1.010                  1.059      0.2648      0.2648

imbalance under perfect distribution 1.000, perfect-move 3->4 ratio = 0.2500

rule                   moved   misses during warmup   reads behind cache/s   requests reaching store/s   x base   extra store requests
modulo hashing        0.7485                 0.7736                 322.35                      419.57     3.02                  16841
consistent hashing    0.2648                 0.3383                 140.96                      238.18     1.71                   5957
base (no warmup): reads behind cache 41.67 req/s, reaching store 138.89 req/s
```

## Two Metrics That Do Not Improve Together

The first table carries two separate metrics, and the rules rank in opposite order on each.

**Distribution.** Modulo hashing splits keys almost perfectly: imbalance 1.008 and 1.004.
Consistent hashing with a single virtual node distributes very poorly — 2.021 at three replicas,
2.231 at four, meaning one replica carries more than twice a perfect share. Because ring positions
fall randomly, the gaps between them are not equal length. As the virtual node count rises, the
number of gaps rises and distribution improves: 1.122 and 1.204 at 100, 1.010 and 1.059 at 1000.
**Virtual node count is consistent hashing's distribution knob**, and its cost is the ring's size:
four replicas and 1000 virtual nodes means 4000 positions.

**Movement.** The ranking reverses. Moving from three replicas to four, modulo hashing moves
74.85 percent of the keys; the ratio that **needs** to move is 0.2500 — the new replica's share.
Modulo hashing moves three times more than it needs to, because changing the divisor changes every
remainder. Consistent hashing at 1000 virtual nodes moves 0.2648, close to the theoretical 0.2500;
with fewer virtual nodes the deviation grows in both directions at once (imbalance 2.021 at v=1,
moved 0.5577). The remove-a-node column gives the same number, because what is counted is the keys
that differ between the two placements, and the difference is the same in both directions.

What the two tables say together: modulo hashing is good at distribution and bad at stability;
consistent hashing is good at stability and buys its distribution with virtual node count.

## Back to the Computation

The fraction of keys that move is not a design outcome by itself; the outcome emerges once it
combines with the cache. C01's V9 assumption said 90 percent of tracking queries were served from
the cache, and that ratio held the request rate reaching the store at 138.89 req/s. In a replica
set routed by key, a moved key's cache does not exist on the new replica; that key's hit ratio is
zero until the cache warms back up.

This calls for one more assumption. **W5 — cache warmup window: 60 seconds.** Rationale: the time
needed for moved keys to be queried again and re-enter the cache; this number is this topic's own
assumption and is not added to C01's table. Its sensitivity is linear — if the window doubles, the
extra store requests double too.

The last table gives the state during the warmup window as a **computation**. Adding a replica
with modulo hashing pushes the miss ratio to 0.7736: the moved 74.85 percent never hits at all, and
the remaining 25.15 percent comes with the normal 10 percent miss ratio. Reads behind the cache
climb from 41.67 req/s to 322.35 req/s, and the request rate reaching the store climbs from 138.89
to 419.57 — 3.02 times the base value. Over the sixty-second window, the store takes 16,841 extra
requests.

With consistent hashing, the same event holds the miss ratio at 0.3383: reads behind the cache are
140.96, the rate reaching the store is 238.18 req/s, 1.71 times the base, and the window adds 5,957
extra requests. The gap between the two rules is 10,884 requests, and the entire gap is the bill
for adding one replica.

The design implication is direct. Horizontal scaling happens by adding replicas; adding a replica
disrupts the cache; disrupting the cache multiplies the load reaching the store. So a system's
scalability depends not only on the replica count but on **how much moves when a replica is
added**. In a design that chose modulo hashing, the moment of growth is the system's most fragile
moment: the replica added in response to rising load piles three times the load onto the store.

## Summary

- Round robin does not look at the replicas' state; with equal replicas, average wait was 4.04
  rounds and max queue 4, versus 1.90 rounds and 2 under least connections.
- Least connections is a waiting rule, not a fairness rule: it halved the wait while making
  work-per-replica distribution slightly more unbalanced (589/567/523 versus 545/581/553).
- When one replica slows down threefold, wait climbs to 170.97 rounds and the queue to 63 under
  round robin; 56.99 and 18 under least connections. Slowdown is the failure mode the health check
  does not catch.
- Modulo hashing is almost perfect at distribution (imbalance 1.008) but unstable: moving from
  three replicas to four moves 74.85 percent of the keys, when the needed ratio is 0.2500.
- Consistent hashing with 1000 virtual nodes moves 0.2648 and brings imbalance down to 1.010;
  virtual node count is the distribution knob, and with a single node imbalance climbs to 2.021.
- Adding one replica, the request rate reaching the store during the warmup window climbs from
  138.89 to 419.57 with modulo hashing (3.02x) and to 238.18 with consistent hashing (1.71x); over
  a 60-second window the gap between them is 10,884 requests.

## Next Step

All three rules looked at only one thing while binding a request to a replica: turn, queue length,
or key. The decision itself was always made by the same component, the balancer. But there is
another component that does the same kind of work and was already built in earlier courses: the
**reverse proxy**, which forwards a request to one of several backend servers by a rule. The work
of the two components overlaps to a large degree; one process can take on both. The next lesson
takes up that overlap: it compares gathering the two roles into one process against splitting them
across separate processes, measured in hop count and composite service availability, and states
where the distinction actually lies — in responsibility and in location.