Load balancing and consistent hashing

intermediateCommon atAnthropicGoogleAmazonMetaRead firstHash mapsBinary searchSorted containersPractise in the Sandbox →

There are two different jobs here. Balancing requests picks a server for each request (round robin, least connections, two random choices); load-aware choices beat blind ones when work is uneven. Placing keys (caches, shards, sticky sessions) needs the same key to land on the same server: hash(key) % N does that but reshuffles almost everything when N changes, while a consistent hash ring moves only about 1/N of the keys, with O(log V) lookups by binary search over V virtual-node points.

The idea in plain words

A supermarket with five checkout lanes has a request problem: each shopper should join the shortest line. A blind rule (“every third shopper goes to lane 3”) works until lane 3’s cashier is slow. Looking at the lines, or at least at two of them, works far better.

A cloakroom has a placement problem: your coat must be on the same rack when you come back. Numbering racks and using ticket % racks works, until a rack is added and almost every coat is now “on the wrong rack”.

Consistent hashing fixes the cloakroom. Put the racks and the tickets on a clock face by hashing them. Each ticket belongs to the next rack clockwise. Add a rack and it takes over only the arc just before it; every other ticket stays put.

See it

Start with three servers and 1 virtual node each. Look at how uneven the arcs (and the “keys owned” bars) are. Raise the virtual-node count. Then add a server or remove one with ×, and compare the two strips: the ring moves a handful of keys; hash % N moves most of them. Type a key in the lookup box to see the clockwise walk to its owner.

Hash ring: add or remove a server and watch keys move

sandbox

look up a key

virtual nodes / server = 1

servers (keys owned)

A

6×

B

6×

C

28×

+ add serverreset

busiest server holds 2.10× its fair share

the same 40 keys (add or remove a server to compare)

hash ring

–

hash mod N

–

Each key (inner dots) belongs to the first server point clockwise from it; the ring is coloured by owner. With 1 virtual node the arcs are lopsided. Drag the slider up and watch the bars even out.

Now balancing requests. Every card gets the same request stream. Run the clock, then tick server 0 is 3× slower and run it again. Then try one user sends 45% and watch sticky routing.

Five balancing strategies, same traffic

run the clock

server 0 is 3× slower one user sends 45% of traffic

round robin

1

s0

0

s1

0

s2

peak 1
avg time 5.0

random

1

s0

0

s1

0

s2

peak 1
avg time 5.0

least connections

1

s0

0

s1

0

s2

peak 1
avg time 5.0

two random choices

1

s0

0

s1

0

s2

peak 1
avg time 5.0

sticky (hash of user)

0

s0

0

s1

1

s2

peak 1
avg time 5.0

Bars are open connections per server at t = 0; a green border marks the lowest peak so far. Every strategy gets the identical request stream. Turn on the slow server or the heavy user to see where blind strategies break and load-aware ones adapt.

↺◀▶ Run▶tick 0 / 60

When to reach for it

The problem says…	Why this fits
“requests are stateless”, servers are identical	Round robin. Cheap, fair when work per request is similar.
“requests vary a lot in cost” / “one server is slower”	Least connections, or two random choices: look at load, not just turn order.
“servers have different capacities”	Weighted round robin (smooth, as below) or weighted least connections.
“the same user/object must hit the same server”	Affinity (sticky sessions): a map or a hash from key to server, plus a plan for when that server leaves.
“cache / shard keys across N nodes, nodes come and go”	Consistent hashing (ring with virtual nodes), or rendezvous hashing.
“minimise data movement on resize”	Consistent hashing moves ~K/N keys instead of ~K·(N−1)/N.

How it works

Balancing requests

• Round robin: server i % N for the i-th request. No state but a counter. Blind to load.
• Random: similar on average, worse in the short run, needs no shared counter.
• Least connections: send to the server with the fewest open requests. Needs live counts; adapts to slow servers and long requests.
• Power of two random choices: pick two servers at random, send to the less loaded one. Mitzenmacher showed this cuts the maximum load from about log n / log log n to about log log n, an exponential improvement over one random choice, while reading only two counters. Many production balancers (Envoy, NGINX’s random two) use it.
• Weighted: if server A is twice as big, give it twice the turns, but spread them out (below).

Smooth weighted round robin

Naive weighting sends A five requests in a row, then B, then C. NGINX’s smooth algorithm interleaves them: every server earns credit equal to its weight each round, the richest server is picked and pays back the total.

Python

smooth_wrr.py

# Smooth weighted round robin (the nginx algorithm): weights 5:1:1 give
# a a b a c a a instead of the bursty a a a a a b c.


def smooth_wrr(weights: dict[str, int], picks: int) -> list[str]:
    current = {name: 0 for name in weights}
    total = sum(weights.values())
    out: list[str] = []
    for _ in range(picks):
        for name, w in weights.items():
            current[name] += w  # 1. everyone earns credit equal to their weight
        best = max(current, key=lambda n: current[n])  # 2. richest server wins (first on ties)
        current[best] -= total  # 3. winner pays the whole round's total
        out.append(best)
    return out  # 4. credits sum to 0 after every pick, so the cycle repeats every `total` picks


if __name__ == "__main__":
    assert smooth_wrr({"a": 5, "b": 1, "c": 1}, 7) == ["a", "a", "b", "a", "c", "a", "a"]
    seq = smooth_wrr({"x": 3, "y": 2}, 10)
    assert seq.count("x") == 6 and seq.count("y") == 4  # exact share over full cycles
    assert seq[:5] == ["x", "y", "x", "y", "x"]  # interleaved, not xxx yy
    print("ok")

TypeScript

smooth_wrr.ts

import assert from "node:assert/strict";

// Smooth weighted round robin (the nginx algorithm): weights 5:1:1 give
// a a b a c a a instead of the bursty a a a a a b c.
export function smoothWrr(weights: Map<string, number>, picks: number): string[] {
  const current = new Map([...weights.keys()].map((n) => [n, 0]));
  const total = [...weights.values()].reduce((a, b) => a + b, 0);
  const out: string[] = [];
  for (let i = 0; i < picks; i++) {
    let best = "";
    for (const [name, w] of weights) {
      current.set(name, current.get(name)! + w); // 1. everyone earns credit equal to their weight
      if (best === "" || current.get(name)! > current.get(best)!) best = name; // 2. richest wins
    }
    current.set(best, current.get(best)! - total); // 3. winner pays the whole round's total
    out.push(best);
  }
  return out; // 4. credits sum to 0 after every pick, so the cycle repeats every `total` picks
}

assert.deepEqual(smoothWrr(new Map([["a", 5], ["b", 1], ["c", 1]]), 7), ["a", "a", "b", "a", "c", "a", "a"]);
const seq = smoothWrr(new Map([["x", 3], ["y", 2]]), 10);
assert.equal(seq.filter((s) => s === "x").length, 6); // exact share over full cycles
assert.deepEqual(seq.slice(0, 5), ["x", "y", "x", "y", "x"]); // interleaved, not xxx yy
console.log("ok");

C#

smooth_wrr.cs

// Smooth weighted round robin (the nginx algorithm): weights 5:1:1 give
// a a b a c a a instead of the bursty a a a a a b c.
static List<string> SmoothWrr(List<(string Name, int Weight)> servers, int picks)
{
    var current = new int[servers.Count];
    int total = servers.Sum(s => s.Weight);
    var outList = new List<string>();
    for (int p = 0; p < picks; p++)
    {
        int best = 0;
        for (int i = 0; i < servers.Count; i++)
        {
            current[i] += servers[i].Weight; // 1. everyone earns credit equal to their weight
            if (current[i] > current[best]) best = i; // 2. richest wins (first on ties)
        }
        current[best] -= total; // 3. winner pays the whole round's total
        outList.Add(servers[best].Name);
    }
    return outList; // 4. credits sum to 0 after each pick, so it cycles every `total` picks
}

var got = string.Join("", SmoothWrr([("a", 5), ("b", 1), ("c", 1)], 7));
if (got != "aabacaa") throw new Exception($"got {got}");
var seq = SmoothWrr([("x", 3), ("y", 2)], 10);
if (seq.Count(s => s == "x") != 6) throw new Exception("x should get 6 of 10");
if (string.Join("", seq.Take(5)) != "xyxyx") throw new Exception("should interleave");
Console.WriteLine("ok");

Consistent hashing with virtual nodes

1. Choose a stable hash (MD5, xxHash, Murmur). Never the language’s built-in string hash: Python and .NET randomise it per process, so two machines would disagree.
2. For each server, hash server#0, server#1, … server#V-1 onto the ring. Keep all points in a sorted array.
3. To place a key, hash it and binary-search for the first point strictly greater.
4. If you ran off the end, wrap around to index 0. The owner of that point owns the key.

Python

hash_ring.py

# Consistent hashing: servers and keys hash onto the same circle; a key belongs to the
# first server point clockwise from it. Virtual nodes give each server many points.
import bisect
import hashlib


def h32(s: str) -> int:
    # 1. a stable hash (Python's hash() is salted per process, so never use it here)
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:4], "big")


def build_ring(servers: list[str], vnodes: int) -> tuple[list[int], list[str]]:
    # 2. one point per (server, replica); sorted so lookups can binary-search
    points = sorted((h32(f"{s}#{i}"), s) for s in servers for i in range(vnodes))
    return [p for p, _ in points], [s for _, s in points]


def owner(ring: tuple[list[int], list[str]], key: str) -> str:
    hashes, owners = ring
    i = bisect.bisect_right(hashes, h32(key))  # 3. first point strictly clockwise
    return owners[i % len(owners)]  # 4. past the last point, wrap to the first


if __name__ == "__main__":
    keys = [f"user:{n}" for n in range(2000)]
    before = build_ring(["a", "b", "c"], vnodes=100)
    after = build_ring(["a", "b", "c", "d"], vnodes=100)
    moved = [k for k in keys if owner(before, k) != owner(after, k)]
    assert all(owner(after, k) == "d" for k in moved)  # keys only move TO the new server
    assert 0.15 < len(moved) / len(keys) < 0.35  # about 1/4 of keys move

    mod_moved = sum(1 for k in keys if h32(k) % 3 != h32(k) % 4)  # naive hash mod N
    assert mod_moved / len(keys) > 0.6  # about 3/4 of keys move
    print("ok")

TypeScript

hash_ring.ts

import assert from "node:assert/strict";
import { createHash } from "node:crypto";

// Consistent hashing: servers and keys hash onto the same circle; a key belongs to the
// first server point clockwise from it. Virtual nodes give each server many points.
const h32 = (s: string): number => createHash("md5").update(s).digest().readUInt32BE(0); // 1. stable

interface Ring { hashes: number[]; owners: string[] }

export function buildRing(servers: string[], vnodes: number): Ring {
  // 2. one point per (server, replica); sorted so lookups can binary-search
  const points = servers.flatMap((s) => Array.from({ length: vnodes }, (_, i) => [h32(`${s}#${i}`), s] as const));
  points.sort((x, y) => x[0] - y[0]);
  return { hashes: points.map((p) => p[0]), owners: points.map((p) => p[1]) };
}

export function owner(ring: Ring, key: string): string {
  const k = h32(key);
  let lo = 0, hi = ring.hashes.length; // 3. first point strictly clockwise (upper bound)
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (ring.hashes[mid] <= k) lo = mid + 1; else hi = mid;
  }
  return ring.owners[lo % ring.owners.length]; // 4. past the last point, wrap to the first
}

const keys = Array.from({ length: 2000 }, (_, n) => `user:${n}`);
const before = buildRing(["a", "b", "c"], 100);
const after = buildRing(["a", "b", "c", "d"], 100);
const moved = keys.filter((k) => owner(before, k) !== owner(after, k));
assert.ok(moved.every((k) => owner(after, k) === "d")); // keys only move TO the new server
assert.ok(moved.length / keys.length > 0.15 && moved.length / keys.length < 0.35); // ~1/4

const modMoved = keys.filter((k) => h32(k) % 3 !== h32(k) % 4).length; // naive hash mod N
assert.ok(modMoved / keys.length > 0.6); // ~3/4 of keys move
console.log("ok");

C#

hash_ring.cs

// Consistent hashing: servers and keys hash onto the same circle; a key belongs to the
// first server point clockwise from it. Virtual nodes give each server many points.
using System.Security.Cryptography;
using System.Text;

var keys = Enumerable.Range(0, 2000).Select(n => $"user:{n}").ToList();
var before = new HashRing(["a", "b", "c"], vnodes: 100);
var after = new HashRing(["a", "b", "c", "d"], vnodes: 100);
var moved = keys.Where(k => before.Owner(k) != after.Owner(k)).ToList();
if (!moved.All(k => after.Owner(k) == "d")) throw new Exception("keys must only move to d");
double frac = moved.Count / (double)keys.Count;
if (frac is < 0.15 or > 0.35) throw new Exception($"expected ~1/4 moved, got {frac}");

int modMoved = keys.Count(k => HashRing.H32(k) % 3 != HashRing.H32(k) % 4); // naive mod N
if (modMoved / (double)keys.Count <= 0.6) throw new Exception("expected ~3/4 moved");
Console.WriteLine("ok");

sealed class HashRing
{
    readonly uint[] hashes;
    readonly string[] owners;

    // 1. a stable hash (string.GetHashCode() is randomized per process in .NET)
    public static uint H32(string s) =>
        System.Buffers.Binary.BinaryPrimitives.ReadUInt32BigEndian(MD5.HashData(Encoding.UTF8.GetBytes(s)));

    public HashRing(IEnumerable<string> servers, int vnodes)
    {
        // 2. one point per (server, replica); sorted so lookups can binary-search
        var points = servers.SelectMany(s => Enumerable.Range(0, vnodes).Select(i => (H: H32($"{s}#{i}"), S: s)))
                            .OrderBy(p => p.H).ToArray();
        hashes = points.Select(p => p.H).ToArray();
        owners = points.Select(p => p.S).ToArray();
    }

    public string Owner(string key)
    {
        uint k = H32(key);
        int lo = 0, hi = hashes.Length; // 3. first point strictly clockwise (upper bound)
        while (lo < hi)
        {
            int mid = (lo + hi) >>> 1;
            if (hashes[mid] <= k) lo = mid + 1; else hi = mid;
        }
        return owners[lo % owners.Length]; // 4. past the last point, wrap to the first
    }
}

The demo asserts the two properties that matter: when d joins, every key that moves, moves to d; and about a quarter move, versus about three quarters with hash % N.

Why virtual nodes?

With one point per server, arc lengths are random and the biggest arc is typically about ln N times the fair share. With V points per server the load evens out (relative spread shrinks roughly like 1/√V); 100 to 200 points per server is a common choice. Virtual nodes also let you weight servers: give a bigger machine more points. And when a server leaves, its many small arcs are absorbed by many different neighbours, not dumped on one.

Sticky sessions

Affinity means “keep sending this user (or document, or connection) to the same server”, usually because the server holds state for it. Two ways:

• A lookup table (key → server), filled the first time a key is seen. Exact control, but the table is state the balancer must keep and share.
• A hash of the key (cookie, client IP, object id). No state, but you lose control of balance: one heavy key is one hot server, as the simulation shows.

Either way, decide what happens when the pinned server goes away (re-pin elsewhere and lose the state, or migrate it) and when it is full (reject, or break affinity).

What it costs

Method	Pick a server	Keys moved when N → N+1	State
Round robin	O(1)	n/a (no affinity)	a counter
Least connections	O(N) scan, O(log N) with a heap	n/a	live counts per server
Two random choices	O(1)	n/a	live counts, read only two
hash(key) % N	O(1)	about N/(N+1) of all keys	none
Hash ring, V points per server	O(log(N·V))	about 1/(N+1) of all keys	sorted array of N·V points
Rendezvous (highest random weight)	O(N) per key	about 1/(N+1)	none
Jump consistent hash	O(log N)	about 1/(N+1)	none, but servers must be numbered 0..N−1 and only removed from the end

Why % N is so bad: a key stays put only if h % N == h % (N+1), which holds for about 1 in N+1 hashes. Going from 3 to 4 servers moves roughly 75% of the keys, which for a cache means a 75% miss storm.

Variations you’ll meet

• Rendezvous hashing (HRW): for each key, score every server with hash(key, server) and take the highest. Simple, perfectly even, O(N) per lookup.
• Jump consistent hash (Lamping and Veach, Google, 2014): a few lines of arithmetic, no memory, but only for numbered buckets.
• Bounded-load consistent hashing (Google, 2016): if a key’s ring owner is above (1+ε) × average load, walk on to the next server. Vimeo used it to cut cache bandwidth.
• Replication on a ring: store a key on the next R distinct servers clockwise (Dynamo, Cassandra). Skip points belonging to a server you already picked.
• Health checks and draining: take a server out of rotation before shutdown; let open connections finish, then move or drop what’s left.
• L4 vs L7: a layer-4 balancer routes TCP connections without reading them; layer 7 reads HTTP and can route by path, header or cookie.

Pitfalls

• Unstable hashes. hash() in Python (for str) and GetHashCode() in .NET are randomised per process. Two balancer instances would route the same key differently.
• Off-by-one at the wrap. Keys hashing beyond the last point belong to the first point. Forgetting the modulo gives an index-out-of-range on a few percent of keys.
• Equal hashes on the ring. Two virtual nodes can collide. Break ties deterministically (e.g. by server name) so every instance builds the same ring.
• Too few virtual nodes. Three servers with one point each can easily give one server half the keys.
• Least connections with stale counts. Several balancer instances each see only their own connections; this is where two random choices shines, as it degrades gracefully with stale data.
• Treating stickiness as free. It fights balance, and a pinned server leaving forces a decision about every key it owned.

In the interview

• Ask: are requests stateless, or does something need affinity? Are servers identical? How often do servers join or leave? Is there a capacity limit per server, and what happens when it’s hit?
• Name the trade-off: blind strategies are cheap and stateless; load-aware ones need fresh load data; affinity costs balance.
• For consistent hashing, say the invariant: “A key belongs to the first ring point at or after its hash, wrapping around; adding a server only steals keys from the arc just before each of its points.”
• Expected follow-ups: weighted servers; a server is removed, where do its keys go; replicas on the next R distinct servers; what if a single key is hot (split it, or replicate reads).

Check yourself

Check yourself

pick one

A cache cluster uses hash(key) % N with N = 9. You add a 10th node. Roughly what fraction of keys now map to a different node?

AAbout 10%BAbout 50%CAbout 90%DExactly 0%; only new keys go to the new node

Check yourself

pick one

One backend is quietly 3× slower than the others. Which strategy keeps the slow server's queue from growing without bound under steady load near capacity?

ARound robinBRandomCLeast connectionsDHashing the client IP

Check yourself

pick one

Why add virtual nodes instead of one point per server?

ALookups become O(1)BArcs even out, so load is balanced, and a leaving server spreads its keys over many neighboursCIt removes the need for a stable hash function

Practice on your own

These are classic exercises, not gym questions:

• Implement rendezvous hashing and measure how many of 10,000 keys move when you add a fifth server.
• Add replication to a hash ring: return the first R distinct servers clockwise from a key.
• Simulate 100,000 balls into 1,000 bins with one random choice vs two; plot the fullest bin.
• Implement jump consistent hash from the paper and check it against your ring’s movement numbers.

Go deeper

• Karger et al. (1997), Consistent Hashing and Random Trees, the original paper.
• Mitzenmacher, The Power of Two Choices in Randomized Load Balancing (PhD thesis, 1996).
• Lamping and Veach (2014), A Fast, Minimal Memory, Consistent Hash Algorithm (jump hash).
• DeCandia et al. (2007), Dynamo: Amazon’s Highly Available Key-value Store, SOSP, section 4.2 on partitioning with virtual nodes.

Related

Distributed systems reasoningSharding, replication and quorums built on top of key placement.

Hash mapsHash functions, distribution and collisions.

Binary searchThe upper-bound search behind every ring lookup.

CachingWhy moving keys hurts: every moved key is a cache miss.