Highest Random Weight in Elixir(jola.dev)
jola.dev
Highest Random Weight in Elixir
https://jola.dev/posts/highest-random-weight-in-elixir
5 comments
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.
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.
There's plenty of scale below FAANG where efficiency matters.
Why must O(n) be a problem? Sometimes people want to just have fun.
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.