Highest Random Weight in Elixir | jola.dev

Home

About

Blog

Projects

Talks

Consistent hashing is a common building block for distributed Elixir and enables fairly low complexity and high value design patterns, like the distributed rate limiter or cache. I’ve written about it before.

The most common way of assigning keys to nodes, ensuring that any node participating in the cluster can figure out which node owns the given key, is Discord’s ExHashRing. This is an incredibly battle-tested and reliable library with excellent performance characteristics, and I’ve only had good experiences with it.

That said, it does have a downside. You have to start and manage the ring processes. It’s not a huge downside, you can give them global names and it’s trivial to look them up, but you still want them set up under your supervision tree and they are stateful persistent things that hang around. That state has to be managed. It’s not a big deal at all, but when I found a stateless alternative it did immediately catch my attention.

Rendezvous hashing

As described by the Wikipedia page: Rendezvous hashing is both much simpler and more general than consistent hashing. Also called HRW or Highest Random Weight. In practice, you can use it very much like you would ExHashRing.

ExHashRing example.

{:ok, ring} = ExHashRing.Ring.start_link()<br>Ring.add_nodes(ring, ["a", "b", "c"])

Ring.find_node(ring, "key1")<br>=> "b"

HRW example.

HRW.owner("key1", ["a", "b", "c"])<br>=> "b"

That’s it. No stateful process, no setup. Just pure functional programming with inputs and outputs. Consistent across multiple machines. Avoids unnecessary drift when changing the list of nodes. You can see why it caught my eye!

There’s a downside of course. The big O notation for HRW.owner is linear (O(n)), or in other words, it doesn’t do well with larger lists of nodes. That’s definitely something to take into account when considering using it. But to be honest, looking back at the times I’ve used ExHashRing I’ve never had more than ~14 nodes to worry about. Here’s a comparison of how each algorithm does on my machine for 14 nodes.

Name ips average deviation median 99th %<br>ExHashRing.Ring.find_node 2.67 M 375.20 ns ±1375.85% 334 ns 500 ns<br>HRW.owner 2.39 M 418.13 ns ±1317.18% 375 ns 541 ns

Comparison:<br>ExHashRing.Ring.find_node 2.67 M<br>HRW.owner 2.39 M - 1.11x slower +42.93 ns

ExHashRing is extremely fast, and stays fast as the number of nodes grow. But at a smaller number of nodes, even on a fairly hot path, there’s not much difference here. You’re free to pick whichever one you think reads better.

Basic HRW algorithm

Let’s dig a bit deeper into rendezvous hashing. The basic implementation is actually incredibly small. What you want to do is apply a scoring function on the key together with each of the nodes separately and then return the highest value. Highest Random Weight. For a scoring function you can use any fast hashing function really. :erlang.phash2 is an obvious candidate in the BEAM ecosystem.

Here’s what that looks like.

defmodule HRW do<br>def owner(key, nodes) do<br>Enum.max_by(nodes, fn node -><br>:erlang.phash2({key, node})<br>end)<br>end<br>end

It’s pretty ingenious!

Linear growth

Just to demonstrate how that affects performance as nodes grows, here’s a benchmark run with 10K nodes. 4200x times slower than ExHashRing. Although to put things into perspective, it’s still just taking ~2 ms on my machine. Depending on your use case, that might actually be just fine. It’s hard to beat the convenience of a pure function.

##### With input D: 10_000 #####<br>Name ips average deviation median 99th %<br>ExHashRing.Ring.find_node 1.91 M 0.00052 ms ±1515.88% 0.00046 ms 0.00063 ms<br>HRW.owner 0.00046 M 2.20 ms ±5.29% 2.17 ms 2.62 ms

Comparison:<br>ExHashRing.Ring.find_node 1.91 M<br>HRW.owner 0.00046 M - 4204.94x slower +2.20 ms

But let’s see if we can do better.

HRW skeleton

Our basic HRW implementation, although actually quite fast, doesn’t behave well as the number of nodes grows. This is because it, for every lookup, has to hash the key against every node. That same Wikipedia page describes a way around that by arranging the nodes into an efficient data structure and bringing the big O notation of owner to O(log n).

At a very (very) high level what we want to do is sort the list of nodes and then chunk them into clusters. Each cluster gets an address and instead of hashing the key against every node, we now just need to calculate the address of the cluster, and then we can hash the key against the nodes inside that cluster to find the correct one. This means significantly less effort, bringing us to a much nicer logarithmic complexity.

Using it looks something like this.

skeleton = HRW.build(nodes)<br>HRW.owner(key, skeleton)

Running the same benchmark as above, but with the skeleton created in advance, just like we do for ExHashRing, this is what we get.

##### With input D: 10_000 #####<br>Name ips average deviation median 99th %<br>ExHashRing.Ring.find_node 2.17...