Highest Random Weight in Elixir

jola.dev

77 points·shintoist··5 comments

The hierarchical (log(n)) approach to bucketing here is fine for an "I just want to shard this N ways, N will never change" but is extremely intolerant of bucket mutations.

Part of the point of rendezvous hash and consistent hashing is that adding and removing elements minimizes the amount of things reassigned. That is, if you add nodes, the only items being reassigned are those that are moving to the new nodes. If you remove nodes, the only items being reassigned are those leaving the departing nodes.

If you know your set of nodes never changes, or you don't care about the cost of reassignment, you don't need a rendezvous hash or consistent hash, you just need a plain old hash function.

There's a really, really interesting talk on a project called Waterpark, which features Rendezvous Hashing (also known as Highest Random Weight, or HRW, hashing) as a stateless alternative to Consistent Hashing for routing and distributing data across distributed nodes. https://www.youtube.com/watch?v=hdBm4K-vvt0

Unless you are operating at FAANG scale or are in HFT I really struggle to see how O(n) would ever be a problem for you here.

Why must O(n) be a problem? Sometimes people want to just have fun.

To pull the example of Discord since the ExHashRing was mentioned in the OP: Needing to hash a few hundred things instead of one thing adds up when you do it a lot of times. They went with consistent hash ring over rendezvous hash because of that; every message needs to do one of these hash ring lookups, also whenever someone connects, they need to do a lot of these hash ring lookups to find all of their servers and friends.

There's plenty of scale below FAANG where efficiency matters.

Reply on news.ycombinator.com