Balancing Algorithms

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.

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

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