Post
Load balancing with… Rendezvous Hashing

About a month ago I wrote about consistent hashing. It’s a neat way for a set of nodes to agree on the placement of something without coordinating with each other. For example, a set of frontend load balancers pinning a user’s session to a particular backend server — without the need for using a component like Redis to store the information.

Rendezvous hashing is an alternative algorithm for this problem. It’s slightly older than consistent hashing, introduced in 1996 (vs. 1997 for consistent hashing).

The algorithms make slightly different trade-offs, so it’s worth knowing about both. Let’s take a look.

How does rendezvous hashing work?

For ease of explanation, we’ll stick to the load balancing use-case. That is, load balancers are choosing backend nodes for given keys.

Consistent hashing conceptually puts backend nodes on a ring with many locations (typically 2^64). A backend node is assigned a location by hashing its name into the location-space of the ring. When a load balancer is accessed, a backend server for a key (eg, user session ID) is selected by hashing the key to get a location for the key on the ring, and then returning the server found next on the ring, wrapping around if needed.

Rendezvous hashing uses hashing in a different way. Instead of giving backends “locations” on a conceptual ring, it does something simpler: when asked to select a backend server, a load balancer calculates hash(key, serverN) for every backend, and returns the server with the highest hash value.

That’s it. Super-simple.

Adding and removing servers

A nice property of rendezvous hashing is that when a server fails:

1. Only the load of that server will be redistributed, and;
2. That load will be evenly redistributed amongst the other servers.

Point (2) intuitively holds: for every key on the failed server, it will be assigned to the next highest hash(key, serverN), which will be evenly distributed across keys.

Similarly, adding a server only moves the set of keys for which the hash function scores hash(key, newServer) highest.

Selecting multiple servers

Selecting multiple servers for a key is also simple: choose the top k hash values, where k is the number of servers you want.

What’s the difference to consistent hashing in practice?

Both rendezvous hashing and consistent hashing have good behaviours when the set of servers change — both move a small set of keys. Selecting multiple servers is simple for both too (for consistent hashing, just choose the next k distinct servers on the ring). So what are the reasons to choose between them?

The biggest practical difference is the simplicity. The second is naturally even load spreading. Finally there’s a nuanced difference in execution time.

Simplicity

The code is much simpler. Adding and removing are trivial list operations rather than adding many virtual nodes to the ring. Server choice is a simple hashing and sorting exercise.

My implementation of rendezvous hashing is about half the lines of code of my consistent hashing implementation, and the code is less complex (no upper/lower bounded binary search). It’s under 50 lines, and there’s no need to break it up into several code blocks to make it easier to digest:

/// Router is a balanced router using rendezvous hashing.
struct Router {
    /// Candidate server pool
    servers: Vec<String>,
}

impl Router {
    /// Create a new Router
    pub fn new() -> Self {
        Self { servers: vec![] }
    }

    /// Add a server to candidate pool
    pub fn add_server(&mut self, name: String) {
        if !self.servers.contains(&name) {
            self.servers.push(name);
        }
    }

    /// Remove a server from candidate pool
    pub fn remove_server(&mut self, name: &str) {
        if let Some(idx) = self.servers.iter().position(|n| n == name) {
            self.servers.swap_remove(idx);
        }
    }

    /// Return the server to use for key
    pub fn get(&self, key: &str) -> Option<&str> {
        // max_by_key tuple sorts by hash then server name to tie-break
        self.servers
            .iter()
            .max_by_key(|s| (hash_server(s, key), *s))
            .map(String::as_str)
    }
}

/// Hashes a server and key
fn hash_server(server: &str, key: &str) -> u64 {
    let mut h = Xxh3::new(); // new uses a consistent seed
    h.write(server.as_bytes());
    h.write_u8(0);
    h.write(key.as_bytes());
    h.finish()
}

Load evenness

Balancing load in consistent hashing relies on the absolute values of the hashes of the server names, as this places them on the ring. At an extreme, if we have servers A, B and C that hash to [A:95, B:200, C:2^64-10] then server C will have far more load than A or B: while A and B “own” 105 locations, C will be assigned every key that hashes between 200 and 18,446,744,073,709,551,606 (2^64-10)!.

In contrast, rendezvous hashing obtains a random ordering of servers for every key via hash_server(server, key). Presuming a good hash function, this ordering will be random for each key, and so balanced.

This evenness is rendezvous’ major strength. Uneven distribution forces you to run larger servers to account for the peaks the unbalanced load will cause. Even loading allows running smaller servers — potentially saving a lot in server costs for large services.

Consistent hashing has to work harder for the same result. As discussed in consistent hashing, it addresses evenness by increasing the number of times each backend server appears in the ring, calling these virtual nodes (rather than physical nodes). As we increase the number of virtual nodes, the evenness of load increases — but it takes a lot of them.

Claude’s ran some experiments and estimated about 8,400(!) virtual nodes per server to match rendezvous hashing’s balancing. But increasing the number of virtual nodes slows down the binary search that consistent hashing uses to select a server. Let’s see if that matters.

Execution time

The hot path is server selection, so let’s focus on that. Let S be the number of servers and V the number of virtual nodes per server, so the consistent hashing ring holds S·V locations.

• Server selection is O(log(S·V)) for consistent hashing: generate hash(key) (O(1)) and then execute a binary search across the S·V ring locations (O(log(S·V))).
• Rendezvous hashing is instead O(S) because hash(key, serverN) is executed for every server.

log(S·V) scales much more slowly than S. So even as we scale V up to improve load evenness, log(S·V) stays much smaller than S.

That means that the number of operations we execute is almost always lower for consistent hashing than rendezvous hashing. In addition, most operations are cheaper: binary search is mostly comparing 64-bit integers whereas rendezvous hashing is calling hash function.

On the other hand, one might expect that adding a lot of nodes decreases the cache-friendliness of consistent hashing vs. rendezvous hashing because the ring becomes large, and binary search is random access rather than sequential. But does that matter?

I used Pi and Claude to write a benchmark that ran over various server counts and virtual node counts. It showed that rendezvous hashing — for my implementations! — was slower for every size (times in nanoseconds):

cons v=1 means: consistent hashing with 1 virtual node per server.

The v=8400 column is the estimated virtual node count that we’d need for consistent hashing to match rendezvous hashing’s balancing — and even then it’s orders of magnitude faster. Rendezvous hashing clearly isn’t going to “catch up” without major optimisations.

Options to speed up rendezvous hashing

Claude’s opinion was that the hashing operation itself was the problem (an obvious guess). To check this, we reworked hash_server to use a shared buffer and the faster xxh3_64 single shot hashing function from the xxh crate. This decreased the time rendezvous hashing took by about half, showing Claude was right about hashing itself being the bottleneck.

We can do two things: reduce the number of hashes we do and make each hash operation faster.

The major win is reducing the number of hashes. There’s a standard way to do this, described as skeleton-based hierarchical rendezvous hashing in Wikipedia. It reduces hash operations by arranging servers into a tree structure to give O(log N) comparisons. Using an array to store the tree would retain the cache-friendliness of rendezvous hashing. This is the step I’d start with.

To decrease the time spent on each hash operation, Claude suggested precomputing the server hash when the server is added and calculating the key’s hash once during get. Both of the hashes are u64 values, and there are good ways to “mix” those two integers extremely quickly when calculating the “score” for each server. This would decrease the constant time factor per server.

But both of these approaches would lose the simplicity of the “naive” rendezvous hashing shown above — and even for 1000 servers, my M5 MacBook Air achieved 10 microsecond server choice times. Probably fine for many use-cases. But it might be fun to hyper-optimise rendezvous hashing sometime…

In summary

To my mind, there’s not much to pull these two algorithms apart. Consistent hashing appears faster, and stays fast even as you add virtual nodes to improve balancing. Rendezvous hashing is slower, but still fast enough for many use-cases even in the naive variant I implemented.

Rendezvous hashing shows its worth in high-load scenarios, however. Its even spread of load can be worth the speed penalty at server-choice time. And techniques like skeleton hierarchy will close that speed gap while retaining the balanced load.

In many ways, my main takeaway is that both of these algorithms are amazingly simple considering that they solve the problem of distributed servers agreeing on a value without those servers ever communicating with each other.

It seems kind of magical that 50-odd lines of code can do that.

Further reading:

• Rendezvous hashing: my baseline “consistent” distribution method shows how to add server weighting to the algorithm.