./ahmedhashim

Say you run a thumbnail generator service. Someone sends it an image with a target size, and the service spends a couple hundred milliseconds of CPU shrinking it. It then stores the result on local disk so the next person asking for the same thumbnail gets it right away. You’ve got eight workers behind a small gateway, and every request that arrives at the gateway needs to route somewhere.

The hard part is deciding which worker gets each request. If you spread the work evenly, the cache on each worker stops paying off, because the same thumbnail lands somewhere different each time. Pinning each thumbnail to one worker means a popular image can overload that worker while the others sit idle. Adding a ninth worker during a busy week means the caches on all eight of the old ones might empty out. None of that even accounts for the one worker that’s running slow.

Here are four ways to make the choice, from the one that knows the least about the request to the one that knows the most about the workers.

Round robin

Round robin keeps a counter of the current worker. Each request goes to the next worker in the list, and the counter wraps around at the end.

  flowchart LR
    W1["<strong style='color:#16181a'>w1</strong><br/><span class='mermaid-detail' style='color:#16181a'>request 1, request 5</span>"]
    W2["<strong>w2</strong><br/><span class='mermaid-detail'>request 2</span>"]
    W3["<strong>w3</strong><br/><span class='mermaid-detail'>request 3</span>"]
    W4["<strong>w4</strong><br/><span class='mermaid-detail'>request 4</span>"]
    W1 --> W2 --> W3 --> W4
    W4 -.->|"wraps"| W1
    classDef wrap fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class W1 wrap

from itertools import cycle

workers = cycle(["w1", "w2", "w3", "w4"])


def pick():
    return next(workers)

Every worker sees the same number of requests. There’s no state beyond one integer, and a new worker takes traffic the moment it’s added to the list. Weighted round robin extends the concept to a fleet of mixed machine sizes by handing the bigger ones more turns per cycle, which is what NGINX does by default.

The counter knows nothing about the requests or the workers. A request that takes two seconds counts the same as one that takes two milliseconds, so equal counts don’t necessarily mean equal load. A worker that’s stalled on garbage collection keeps getting its turn. And since nothing ties a request to a worker, every worker in the service ends up caching every thumbnail, so each cache only warms up from the eighth of the traffic it happens to see.

Round robin is the right default when requests are cheap and roughly the same size, and when the workers don’t remember anything between them.

Consistent hashing

If instead you want the same thumbnail to land on the same worker for better cache locality, you can hash the request key and use that to choose the worker. The obvious way is hash(key) % N, and it works right up until N changes. Once you go from eight workers to nine, nearly every key maps to a new worker, which for a caching fleet means every cache goes cold at once.

Consistent hashing fixes that problem by hashing the workers into the same space as the keys and sorting those hashes. A key then belongs to the first worker whose hash comes after its own, wrapping around to the start when it runs off the end. That wraparound is why it’s usually drawn as a ring.

Membership changes are cheap because of that ordering. Here’s a small hash space with three workers and three keys. When w4 joins at 60 it takes dog.jpg from w3 and nothing else moves. Take w4 back out and dog.jpg returns to w3 while the others stay put:

  flowchart LR
    subgraph B["Three workers"]
        direction TB
        B1["<strong>w1</strong><br/><span class='mermaid-detail'>at 20, owns 40</span>"] --> BK1["<strong>cat.jpg</strong><br/><span class='mermaid-detail'>33</span>"] --> B2["<strong>w2</strong><br/><span class='mermaid-detail'>at 45, owns 25</span>"] --> BK2["<strong>dog.jpg</strong><br/><span class='mermaid-detail'>50</span>"] --> B3["<strong>w3</strong><br/><span class='mermaid-detail'>at 80, owns 35</span>"] --> BK3["<strong>owl.jpg</strong><br/><span class='mermaid-detail'>90</span>"]
        BK3 -.->|"wraps at 100"| B1
    end
    subgraph A["Four workers"]
        direction TB
        A1["<strong>w1</strong><br/><span class='mermaid-detail'>at 20, owns 40</span>"] --> AK1["<strong>cat.jpg</strong><br/><span class='mermaid-detail'>33</span>"] --> A2["<strong>w2</strong><br/><span class='mermaid-detail'>at 45, owns 25</span>"] --> AK2["<strong style='color:#16181a'>dog.jpg</strong><br/><span class='mermaid-detail' style='color:#16181a'>50</span>"] --> A4["<strong style='color:#16181a'>w4</strong><br/><span class='mermaid-detail' style='color:#16181a'>at 60, owns 15</span>"] --> A3["<strong>w3</strong><br/><span class='mermaid-detail'>at 80, owns 20</span>"] --> AK3["<strong>owl.jpg</strong><br/><span class='mermaid-detail'>90</span>"]
        AK3 -.->|"wraps at 100"| A1
    end
    B ~~~ A
    classDef key stroke:#5ea1ff,stroke-width:2px
    classDef new fill:#5eff6c,stroke:#5eff6c,color:#16181a
    classDef moved fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class BK1,BK2,BK3,AK1,AK3 key
    class A4 new
    class AK2 moved
    style A fill:transparent
    style B fill:transparent

import bisect
from hashlib import md5


def h(s):
    return int(md5(s.encode()).hexdigest(), 16)


class Ring:
    def __init__(self, workers, points=100):
        self.ring = sorted(
            (h(f"{w}:{i}"), w) for w in workers for i in range(points)
        )
        self.hashes = [p for p, _ in self.ring]

    def pick(self, key):
        i = bisect.bisect(self.hashes, h(key)) % len(self.ring)
        return self.ring[i][1]

That points=100 default is where the magic lies. Each worker’s hash is a point on the ring, and the diagram above has one per worker. That’s why the shares are so uneven: w1 owns 40 units of the space, w2 only 25, and w4 takes its entire share from w3. The fix is to hash each worker a hundred times under different names, giving it a hundred points, which evens out the shares and means a new worker takes a little from everyone instead of a lot from one. The cost is a sorted list that grows with the total number of points, and a binary search per lookup.

Locality also comes at the expense of balance. The hash spreads keys evenly, but a very popular image is still one key, and it lands on exactly one worker no matter how many points are on the ring. A slow worker doesn’t get any relief either, since its share is fixed by where its points fall. If you need locality and a cap on any one worker’s share, consistent hashing with bounded loads adds an overflow rule on top of the ring.

Rendezvous hashing

Rendezvous hashing, an older algorithm, gets the same result as the ring with less code and no state. For each request, hash the key together with every worker’s name and pick the worker that produced the largest value.

  flowchart LR
    K["<strong>cat.jpg</strong>"]
    S1["<strong>w1</strong><br/><span class='mermaid-detail'>h(w1, cat.jpg) = 41</span>"]
    S2["<strong style='color:#16181a'>w2</strong><br/><span class='mermaid-detail' style='color:#16181a'>h(w2, cat.jpg) = 87</span>"]
    S3["<strong>w3</strong><br/><span class='mermaid-detail'>h(w3, cat.jpg) = 12</span>"]
    S4["<strong>w4</strong><br/><span class='mermaid-detail'>h(w4, cat.jpg) = 63</span>"]
    K --> S1
    K --> S2
    K --> S3
    K --> S4
    classDef win fill:#5eff6c,stroke:#5eff6c,color:#16181a
    classDef second stroke:#5ea1ff,stroke-width:2px
    class S2 win
    class S4 second

w2 scored highest, so it owns cat.jpg, and w4 is the runner-up.

def pick(key, workers):
    return max(workers, key=lambda w: h(f"{w}:{key}"))

Each score depends only on the key and the worker, so the winner doesn’t change unless the set of workers does. Remove w2 and cat.jpg falls to w4 while every other key stays where it was. Add a worker and it takes only the keys where its new score beats the current best. That’s the same guarantee the ring gives, without the sorted list.

It also doesn’t need a hundred points per worker to stay balanced. Every worker gets a fresh hash for every key, so no worker can end up with a bigger slice of the space than the others.

You can also sort the workers by score instead of taking the highest, which gives you a ranked list for that key: the top k are where a key with k replicas lives, so when one of them fails the other copies are already in place. The ring has no such list. To get one you have to walk clockwise from the key and skip every point that belongs to a worker you’ve already collected.

The tradeoff here is the loop. Every pick hashes the key once per worker, so a lookup is O(N) where the ring is O(log N). For eight or eighty workers, that’s mostly noise. With thousands of workers the loop is slow enough to matter, and at that point the ring’s binary search is worth its extra setup. Just like the ring, a popular key will still land on a single worker.

Two random choices

Everything so far decides without looking at the workers. The last approach looks, but only a little: pick two workers at random, then send the request to whichever of the two has fewer requests in flight.

  flowchart LR
    G["<strong>Gateway</strong>"]
    W1["<strong>w1</strong><br/><span class='mermaid-detail'>4 in flight</span>"]
    W2["<strong>w2</strong><br/><span class='mermaid-detail'>1 in flight</span>"]
    W3["<strong>w3</strong><br/><span class='mermaid-detail'>5 in flight</span>"]
    W4["<strong>w4</strong><br/><span class='mermaid-detail'>3 in flight</span>"]
    W5["<strong style='color:#16181a'>w5</strong><br/><span class='mermaid-detail' style='color:#16181a'>2 in flight</span>"]
    G ~~~ W1
    G ~~~ W2
    G -.->|"sampled"| W3
    G ~~~ W4
    G -.->|"sampled"| W5
    classDef sampled stroke:#5ea1ff,stroke-width:2px
    classDef chosen fill:#5eff6c,stroke:#5eff6c,color:#16181a
    class W3 sampled
    class W5 chosen

w2 is the least loaded worker in the fleet, but it wasn’t sampled, so it doesn’t matter. Of the two that were, w5 has fewer requests in flight and gets this one.

import random


def pick(workers, inflight):
    a, b = random.sample(workers, 2)
    return a if inflight[a] <= inflight[b] else b

The result is far better than the size of the change suggests. Michael Mitzenmacher demonstrated this with a setup where the number of requests equals the number of workers, so the average worker holds exactly one. Place each request on a random worker and the busiest one’s load scales as log n / log log n. If instead you pick two random workers per request and send it to the emptier one, the busiest scales as log log n. In a quick simulation with a million requests on a million workers, the busiest worker held nine requests with one random choice and four with two. Sampling two removes most of the imbalance, while adding a third has diminishing returns.

Sending every request to the single least loaded worker sounds better but is worse in practice. Once there’s more than a single gateway, each has a slightly stale view of the counts and sends its next burst of requests to the same idle worker, which then becomes the most loaded one in the fleet by the time the counts catch up. Two random choices avoid that because different gateways draw different pairs, so a burst spreads out on its own. The in-flight count also carries information that round robin throws away. A slow worker accumulates requests and starts losing comparisons, and an expensive request occupies a slot for longer, so both get routed around without anyone writing a rule for it.

This is what NGINX does with random two least_conn and what Envoy’s least request balancer does by default with a choice count of two.

The gateway needs a load signal per worker, and in-flight requests is the one it already has if it’s proxying the traffic. It gives up locality entirely, so the thumbnail caches are back to warming up from an eighth of the traffic each. Two random choices is the strategy for work that any worker can do equally well.

Picking one

So which one does the thumbnail service get? The caches are what make it cheap, so the pick has to be stable per key, and eight workers is nowhere near the count where rendezvous hashing’s loop matters.

I’d hash the source image and size with rendezvous and take the second entry in the ranking when the winner is down. Then I’d watch the per-worker traffic for a popular image before doing anything more clever than that. If the resize were fast enough that the cache didn’t matter, I’d drop the hashing and go with two random choices, and let the in-flight counts route around the slow worker.

Each version of the gateway’s choice is a handful of lines. What differs is what each version is allowed to know: the counter knows nothing, the hashes know the key, and the two random choices know the workers. Decide what your service needs the gateway to know, and the choice becomes evident.