Consistent Hash Ring

[pyfon]

I had a practical use to learn this: design interview prep.

In the real world some platform team does this (or AWS) and then probably one person in that team for one week implements it. Although good for everyone to understand.

You can use it to ensure a request for a user ends up generally at the same node. If that users workload creates state (even if that is cache) then you get a performance win. By using the same server on each request.

[__turbobrew__]

Do virtual nodes actually help?

From what I can see in the UI, nodes are placed semi randomly on the ring (probably a hash itself determines the node placement) so don’t you still have the same problem that the hashing of virtual nodes onto the ring can still cause imbalances?

To me it seems like you should be trying to put new nodes on the ring within the largest gaps on the ring.

[jauntywundrkind]

Vnodes are amazing for so many reasons. The model here is pretty simple, but even still, it means you can rejuggle work without having to re-hash when adding nodes: just have the new node claim some vnodes. That's just the basics.

In Cassandra's consistent hashing & many others, you can also juggle vnodes around between nodes as you please, which, if you have hotspot vnodes, gives you some chance to add some anti- affinity for the hot vnodes.

https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/arc...

[swinglock]

Add enough random nodes and eventually it will be even, so it helps.

[croemer]

Yes, they reduce variance.

[rad_gruchalski]

This is how Apache Cassandra works: https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/arc....

[meling]

I think the Chord DHT uses this.

https://en.wikipedia.org/wiki/Chord_(peer-to-peer)

[eulenteufel]

Curious, I just learned about hash rings last week when setting up the ironic openstack service [0].

[0] https://docs.openstack.org/ironic/latest/_modules/ironic/com...

[packetlost]

If you're looking for an application of these, the DynamoDB paper is a really great read: https://www.allthingsdistributed.com/files/amazon-dynamo-sos...

[hinkley]

The predecessor to this was running one hash function per cluster member and picking the one with the highest or lowest result.

Personally I still find that a lot easier to reason about. Especially when it’s time to resize the cluster.

[ryuuseijin]

Shameless plug of my consistent hashing implementation in about 50 lines of clojure: https://github.com/ryuuseijin/consistent-hashing

[charleshn]

See also Rendezvous hashing [0], which is simpler and more general.

[0] https://en.m.wikipedia.org/wiki/Rendezvous_hashing

[jcartw]

Interactive Consistent HashRing Visualization

[samwho]

Love this.