./ahmedhashim

Imagine you have some sort of thumbnail generation service. Someone submits an image and a desired thumbnail size, and it takes some CPU time (a few hundred ms) to resize the image. You then save it to disk for future thumbnail requests. Now say you have 8 workers and a small gateway in front of them. Every request coming into your gateway needs to be handled somewhere.

Now you’re going to have to figure out which worker will handle which request. Distributing requests equally among workers will cause the benefit of each worker’s cache to be diminished since you will be sending each thumbnail to a different location. If you were to always send a certain thumbnail to the same worker you could have one worker being overwhelmed with work while other workers sit idle. Now you want to add a ninth worker during your busiest week. You now have to worry about the previous 8 workers losing their cached thumbnails. All this without taking into account a worker that is underperforming.

Here are 4 options you can take when deciding which worker to use, going from the least amount of information to the most.

Round robin

Round robin will keep track of the current worker it has given the request to. It will send each request to the next worker and reset when it reaches the end of the list.

  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)

Each worker will be assigned the same number of requests. State is only an int. When you add a new worker it will begin taking traffic. You can use weighted round robin to account for machines of different sizes. Giving larger machines more rounds per rotation. This is what NGINX does out of the box.

The counter has no idea what requests are coming in or what workers are available. So if a request takes 2 seconds it will be the same count as a request that takes 2ms. Meaning that equal counts are not equal work load. If a worker is stuck on garbage collection it will continue to receive its fair share. Also because there is no connection between a request and a worker all workers in the service will end up with a cache of every thumbnail. Meaning each cache is only warmed by 1/8th of the requests.

Round robin works best as the default if your requests are cheap and similar in complexity, and your workers have no state between them.

Consistent hashing

You may want to assign the same thumbnail to the same worker, to allow for better cache locality. You can simply take the hash of your key and use it to select the worker. hash(key) % N is the simplest method and will work until you change N. If you have 8 workers and increase it to 9, nearly all of your keys will be sent to new workers, meaning all your workers will have cold caches.

Consistent hashing solves this issue by taking all of your workers and hashing them into the same space as the keys. You then sort the hashes. Any key belongs to the first worker that has a hash greater than it, or if we run off the end of our list, we wrap around to the beginning. This is why you see most consistent hash tables represented as a ring.

Adding and removing workers is cheap because of this order. This is an example of a small hash space with 3 workers and 3 keys. When w4 joins at 60, it takes dog.jpg off of w3 and no other keys move. If we remove w4 from the picture, dog.jpg goes back to w3:

  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]

As you can see, there’s a points=100 in the example. There will be a point on the ring for each worker hash. In the image above we have 1 point for each worker, which is why the shares between workers are so uneven: w1 has 40 of the space and w2 has 25. w4 will take all of its space from w3. By hashing our worker 100 times with different names, we give it 100 points on the ring. This spreads the shares out more, and when we add a worker it takes a little from each worker instead. The downside is that your sorted list will be as big as your total number of points, and you’ll need to do a binary search.

The downside to locality is that you sacrifice even distribution. Hashing gives us even distribution, but if an image is extremely popular, it’s still going to be 1 key, which will always be assigned to 1 worker regardless of how many points you have. A slow worker doesn’t get any relief either. If you want locality but also want to cap any one worker’s share, consistent hashing with bounded loads adds an overflow rule on top of the ring.

Rendezvous hashing

Rendezvous hashing is an older and simpler algorithm that achieves the same goal. With less code and no state, we can hash the key against each worker’s name and choose the worker that has the highest 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

So we would assign cat.jpg to w2 since it had the highest value and w4 would be our backup.

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

Scores only depend on the key and worker, so as long as you don’t change your list of workers, you won’t get any new winners. Remove w2 and cat.jpg will now be assigned to w4. All other keys remain the same. If you add a worker, it will only grab keys where it scores higher than what’s currently assigned. Same as with the ring, but without needing a sorted list.

It’s not necessary to have 100 points per worker. Each worker gets a new hash for each key, so no worker can end up with a bigger slice of the space than the others.

You can order the workers by score too. This will give you an ordered list of workers for that key. The first k workers in that list would be where the key would be stored if you had k replicas. If one fails you know where the next copies are. The ring does not provide you with this. You would have to travel clockwise from your key and pass over all points that are associated with a worker that you already have.

The downside is that you have a loop. You’re hashing the key once per worker, so your lookup is O(N) versus O(log N) for a ring. It’s not going to be an issue with 8 or 80 workers. Once you have thousands of workers the loop becomes noticeable, and using a ring is probably better. Similar to a ring, you’ll still have hot keys that go to one worker.

Two random choices

So everything up to this point makes its decision without looking at the workers. The final one looks, but only picks 2 workers at random and gives the request to the one with fewer in-flight requests.

  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 has the fewest requests in flight, but since it wasn’t sampled, we don’t care. We’ll give the request to w5 because it has fewer in-flight requests.

import random


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

This ends up being much more effective than you’d think based on how small the change is. Michael Mitzenmacher showed this with as many requests as workers, meaning each worker has 1 on average. If you put each request on a random worker, your most loaded worker scales as log n / log log n. But if you pick 2 random workers and put the request on the least loaded one, it scales as log log n. I did a quick test with 1 million requests and 1 million workers. My most loaded worker had 9 when picking 1, and 4 when picking 2. So by picking 2 you eliminate most of your hot spots. Picking 3 doesn’t do much more.

Always sending to the single least loaded worker sounds better, but it’s worse in practice. When you have multiple gateways, each one has a slightly stale view of the counts, so they all send their next chunk of requests to the same least loaded worker. Now that worker is the most loaded one when the counts update. If you pick 2 at random, each gateway picks different workers, so it evens itself out. The in-flight count also tells you something round robin ignores. If a worker is slow, it will have more requests and start losing comparisons. Same with a request that takes longer to complete, since it takes up a slot longer.

So this is what random two least_conn does in NGINX. Envoy’s least request balancer also does this by default, with a choice count of 2.

We need some kind of load information about each worker, and we already have the number of in-flight requests if we’re proxying the traffic. Locality is thrown out the window, so our thumbnail caches are back to warming up from 1/8th of the traffic each. If any worker can do the work equally well, then choosing two at random is a good bet.

Picking one

So which one does the thumbnail service get? The caches are what let you do it cheaply, so the choice has to be deterministic per key, and eight workers is so far from the scale where the loop in rendezvous hashing matters.

So I’d probably hash the source image + size with rendezvous, take the second choice in the list when the winner is down, and monitor the per-worker hit count of a heavily requested image before getting fancier than that. If the resize were fast enough that caching didn’t matter, I’d probably just skip the hashing and use two random choices, letting the in-flight count steer around the slow worker.

The code for each possible gateway choice is just a few lines. The difference between them is what each one gets to know: the counter knows nothing, the hashes know the key, and the two random choices know the workers. Figure out what information your service needs the gateway to know, and the answer becomes clear.