Making a cache cluster more effective

Getting the most out of Varnish at Runway with rendezvous hashing

Recently I left my job at Runway. Something I’d always wanted to post about on the Runway engineering blog was a project I worked on early in my time there, but which wasn’t really substantive enough to justify posting. I thought it was cool, though, and it was a gratifying project to work on.

Let me talk you through it.

Running and scaling Varnish for caching

When I joined Runway, it was primarily a web-based video editor¹. The engineering complexity of the video editor was initially what drew me to learn more about Runway: the idea that you could get near-realtime video editing, in the browser, doing AI on the back-end was incredible. I wanted to know how it was done.

When I spoke to some of the engineers at Runway during the interview process back in 2022, they told me the secret behind it. To paraphrase:

It’s just a bunch of layers of caching in a trenchcoat.

The client fetches video (of any variety) from a streaming back-end. The back-end does some work to pull in the necessary assets from object storage, runs them through whatever processing is needed (transcoding, AI modifications, etc.) and streams back the results.

Where this falls down is latency. Pulling video from object storage isn’t easy or fast. S3 Express One Zone didn’t exist at the time, but the cost of hosting all user assets on it wouldn’t be feasible. The solution to bringing down this latency is to use an in-memory cache (we used Varnish) that sits in front of the object store.

Here’s the problem with that setup: Varnish, being in-memory, can only scale so large before it becomes cost-prohibitive. You also don’t want one giant Varnish cache box with enough memory for everything, since it’s going to become an IO bottleneck and if goes down, everything goes down. So you need to run many Varnish instances.

The problem with many Varnish instances

Let’s say you run these in Kubernetes, and they’re exposed on a hostname that resolves to each of the underlying instances IPs. That means that when you make a request, if you resolve the IP each time, it chooses one of the instances ~randomly.

Here’s the trouble: if you have N instances, you have a one in N chance of hitting a box that already has the file you are requesting. The more you scale up, the lower the odds are that you have a cache hit.

Varnish actually has a solution to this: Varnish Enterprise has a feature called Cluster that figures this out. Here’s a diagram from their docs:

A diagram showing how clients hit any Varnish Cluster instance, and the instances route requests between each other to (hopefully) successfully serve a cache hit.

This is a good solution to the problem, but it requires you to be running Varnish Enterprise, and it involves a fair amount of setup and configuration. If that works for you, Cluster is probably the right way to go. For us, it made a little more sense to do something simpler.

Something simpler

Really what Varnish is doing under the hood is routing on behalf of the clients. The client isn’t aware of which server it should use, so the Varnish instances figure that out and forward the client requests. Avoiding this involves doing what Varnish is doing, but in your client.

The tricky part here is how to choose which Varnish instance to direct a request to. Here’s some pseudocode:

from urllib.parse import urlsplit

VARNISH_CLUSTER_HOSTNAME = 'varnish.cluster.hostname.here'

varnish_instance_ips = sorted(resolve_dns_as_ips(VARNISH_CLUSTER_HOSTNAME))

path = urlsplit(url).path
path_hash = int(hash_function(path))

ip_to_use = varnish_instance_ips[path_hash % len(varnish_instance_ips)]

return make_request(
  hostname=ip_to_use,
  path=path,
  headers={'Host': VARNISH_CLUSTER_HOSTNAME},
)

This actually works great in the happy path. You deterministically point each request at an instance based on a hash² of the path (the object store key). The problems start to rear their head when the cluster changes size.

As soon as you add or remove a node, there’s a fair chance that you’re busting the cache for nearly every request. That’s because len(varnish_instance_ips) changes.

The fix is small and somewhat non-obvious. It’s called rendezvous hashing.

from urllib.parse import urlsplit

VARNISH_CLUSTER_HOSTNAME = 'varnish.cluster.hostname.here'

varnish_instance_ips = resolve_dns_as_ips(VARNISH_CLUSTER_HOSTNAME)
path = urlsplit(url).path

hashes = [
  (int(hash_function(f'{ip}|{path}')), ip)
  for ip
  in varnish_instance_ips
]
# This will choose the ip with the largest hash, breaking ties with the ip itself
_, ip_to_use = max(hashes)

return make_request(
  hostname=ip_to_use,
  path=path,
  headers={'Host': VARNISH_CLUSTER_HOSTNAME},
)

Instead of hashing the path, converting the hash to an integer, and using modulus to choose an instance index, we compute the hash of an instance identifier (in this case, the IP) in conjunction with the path. We then find the instance whose hash has the maximum value and choose that one.

First: why does this work?

We use the IP plus the hash together because it changes per path. If you just hash on the IP, you get the same answer for each path. If you just hash on the path, all of the instances get the same hash.

When you hash them together, you don’t know whether the hash for any IP-path pair is going to be big or small—but one of them has to be the biggest. When you pick the max(), you’re going to get back one consistent IP for each unique path.

Second: why does it address our problem well?

The cool part about this is that it handles the edge cases as gracefully as you could hope for.

Let’s say someone kicks the power cord on one of the instances. varnish_instance_ips no longer contains that instance. hashes no longer contains a pair for that instance. Importantly, the only paths where the output of this function changes are ones where that instance had the maximum hash value.

An example showing how an instance is chosen from a set of four IPs, then how an instance is chosen when the original choice is eliminated.

Above is an example. In the “Before” section you can see that the second instance wins: its hash is the highest. If that instance then dies, the next highest (the fourth) wins. The hash didn’t change, what changed is that the other one went away.

With the modulus-based approach, ~all of the resulting indexes change. With this approach, only the outputs mapping to the unreachable instance change.

This approach has three really desirable properties:

1. If an instance goes down, only the paths that resolve to that instance change instances. The minimum number of paths see a potentially cold cache.

2. If an instance comes online, exactly the set of paths that should resolve to that instance start resolving to it. The exact maximum fair share of paths that should belong to the new instance start using it.

3. The cost of computing which instance a path goes to is essentially free. There’s no state to manage or distribute. There’s no consensus or gossip protocol. The algorithm involves just a little bit of math per instance per request.

One small, annoying consideration

Doing a DNS lookup to get the list of instances on each request isn’t fun, but you need to know when the set of instances behind the scenes changes. It’s important to cache the DNS lookup yourself³, but not for too long: you still want to find out new instances might be added.

One or two minutes of caching (plus jitter) is just fine. If a request fails because one of the IPs in the cached DNS lookup failed to connect, you can remove the failed IP from the cached result, retry the request, and trigger a fresh lookup in the background. Using the stale results with the failed IP removed saves the cost of the lookup by betting (with very low stakes) that a new server hasn’t come up that would have the max hash⁴.

Why do this?

If you go with Varnish Enterprise, N-1 out of N requests end up getting forwarded between Varnish instances. If you have 8 instances, you have a one in eight chance of getting lucky and the instance you choose is the one that can respond with the file directly. Otherwise, you have a 7 in 8 chance that the instance will forward your request to the right server. This has two effects:

1. Additional latency. It’s another hop.

2. You’re increasing the amount of network IO that’s being performed. In the worst case, the file is transferred from object storage to the correct instance, then to the instance the client contacted, then to the client. That might be a lot of data and have other consequences.

Using rendezvous hashing on the client doesn’t suffer from either of these downsides. The cost is that your clients need to be aware of implementation details of your caching infrastructure.

Unfortunately, I don’t have numbers for the improvement that we saw after implementing this. Moreover, the benefit here is caches end up being warm more often. The measurable improvement in latency is entirely dependent on the cost of fetching from object storage directly versus fetching through Varnish, which is going to vary by environment. It’s also going to matter more for folks with large Varnish clusters (a cluster of two instances will see four times less benefit than a cluster of eight).

Said another way: your mileage will vary, but “rarely a cache hit when you’re lucky” versus “often a cache hit” at no substantial cost is almost always worth it.

Why not do this?

There’s two important notes here which can cause you grief, both stemming from the same reason: this is about routing, not load balancing.

1. If you have one extremely hot object, it’s now on one singular server. Without rendezvous hashing, requests for that object are being sprayed across instances—probably with a fairly high cache hit rate. With rendezvous hashing, you’re putting all of that load on a single node.

2. All objects are treated equally. But in practice, file size is going to vary a lot. Routing like this isn’t memory-aware, which can mean that sending a request for a big file at an instance that doesn’t have room for it can cause contention.

The first problem can be mitigated with rate limiting. If you put simple token bucket rate limiting in place, you can detect when objects become very hot (for some predefined definition of “hot”) and simply choose a random instance.

The second problem is harder to solve, and my recommendation is to instead fetch files in chunks (using a Content-Range request) where the maximum chunk size is reasonably small, and where you include the chunk offset in the hash for the object. This means memory use stays more consistent across instances⁵.

Why not consistent hashing?

Some of you may know about consistent hashing, which solves the same problem as rendezvous hashing in a different way for a special case. Here’s what it looks like:

from urllib.parse import urlsplit

VARNISH_CLUSTER_HOSTNAME = 'varnish.cluster.hostname.here'
VIRTUAL_NODE_COUNT = 100

# NOTE: This bit can be hoisted so it's not done on every client call
varnish_instance_ips = resolve_dns_as_ips(VARNISH_CLUSTER_HOSTNAME)
virtual_nodes = sorted(flatten([
  [(int(hash_function(f'{ip}|{i}')), ip) for i in range(VIRTUAL_NODE_COUNT)]
  for ip in varnish_instance_ips
]))


path = urlsplit(url).path
path_hash = int(hash_function(path))

_, ip_to_use = (
  binary_search(virtual_nodes, where=lambda node: node[0] > path_hash)
  or virtual_nodes[0]
)

return make_request(
  hostname=ip_to_use,
  path=path,
  headers={'Host': VARNISH_CLUSTER_HOSTNAME},
)

Consistent hashing works very similarly to what we do previously, but it’s not quite perfect. We create VIRTUAL_NODE_COUNT “virtual node” entries in a list for each of our cache instances. Each one has a hash value. When we go to make a client request, we hash the path, then find the virtual node entry with a hash value greater than the path’s hash (wrapping around to the first one).

At a high level, this functions very similarly to what we accomplished with rendezvous hashing:

1. When an instance is removed, it just means that any paths whose hash would find one of the instance’s virtual nodes will find another virtual node instead. When an instance is added, some paths will start finding its instead.

2. We can create the list of virtual nodes ahead of time. We only have to do one hash per request.

Where this gets a little hokey is VIRTUAL_NODE_COUNT. Imagine if this value is very small. Let’s pretend it’s 1 for a moment, and we have three instances. virtual_nodes, in turn, has only three items. We can be really confident that those hashes aren’t evenly spaced out. If int(hash_function(x)) can return values from, say, [0,65536), we might end up with these three values: [ 1, 65530, 65534 ]. No bueno! That second instance is going to receive the overwhelming majority of traffic.

Increasing VIRTUAL_NODE_COUNT means that on average the spacing becomes nearly uniform.

So why would you choose one over the other? Well there’s a few trade-offs:

1. Time complexity. With consistent hashing, you compute the hashes ahead of time, and you can do a binary search (O(log(NV)), where N is the number of instances and V is VIRTUAL_NODE_COUNT) to find the virtual node. With rendezvous hashing, you have to perform a hash for every instance (O(N)).

2. Evenness. Consistent hashing is essentially guaranteed to be a little bit unbalanced because you need enough virtual nodes for the ranges between the virtual node hashes to even out. Rendezvous hashing doesn’t need virtual nodes because each path is hashed. The more paths you hash, the more uniformly they spread out across instances.

The tough part here is getting VIRTUAL_NODE_COUNT right. You want it to be high enough that the evenness is acceptable, but not so high that you’re keeping megabytes of data in memory. If you have 16 nodes, finding the max of sixteen hashes per request might be a lot better than doing a binary search on 1600 hashes (because of data locality). If you have hundreds or thousands of nodes (which was far outside the scope of what Runway was doing), consistent hashing makes some more sense—especially when a client is making many concurrent requests.

1. Generative video models like Gen-1 and Gen-2 hadn’t come out yet.

2. I use a hypothetical hash_function here. Don’t use Python’s hash, use something like xxhash or murmur3: a non-cryptographic hash function with a good avalanche effect.

3. If you rely on your runtime, your OS, or something upstream to reliably cache DNS for the amount of time you expect, you’re setting yourself up for a conversation with your therapist about trust issues.

4. Let’s say my cached lookup results in the IP set { A, B, C } and the hashes ordered descending are [ C, A, B ]. If C is unreachable, we fire off a fresh DNS lookup in the background, and pare { A, B, C } down to { A, B } and try again. So now our sorted hashes are [ A, B ] and so we attempt A. This is the more efficient choice unless A is also unreachable (because we then have to fall back on B) or the fresh DNS lookup will result in { A, B, D } where the sorted hashes end up as [ D, A, B ] (because routing to A essentially ensures the cached result never gets used in the future).

5. Worth noting that chunking does also help with hot objects as well: you’re spreading the cost of hot objects across potentially multiple instances.