5 ms·

Consistent Hash Ring

73 points by jcartw 1y ago

packetlost 1y ago
If you're looking for an application of these, the DynamoDB paper is a really great read: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf https://www.allthingsdistributed.com/files/amazon-dynamo-sos...
eulenteufel 1y ago
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/common/hash_ring.html https://docs.openstack.org/ironic/latest/_modules/ironic/com...
samwho 1y ago
Love this.
__turbobrew__ 1y ago
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.
- swinglock 1y ago
  Add enough random nodes and eventually it will be even, so it helps.
  - __turbobrew__ 1y ago
    Why not just make the nodes even from the start? Place new nodes in the largest existing gap between any pair of nodes.
    - lsecondario 1y ago
      In a distributed system all clients would need to agree on the largest existing gap under various messaging anomalies. If you have a mechanism to reach that agreement then you can probably use a simpler deterministic load balancing algo. Consistent hashing gives you eventually consistent routing without (synchronous) agreement.
      - __turbobrew__ 1y ago
        You don’t need agreement. A newly added node can try best effort to find the optimal placement based upon the known state of the cluster and then advertise that it is going to a specific place in the hash ring. When clients learn about the new node they will also learn where that node has decided to put itself into the ring. No coordination is needed. There are probably moments that a client learns about the node they also atomically learn about where that nodes is placed. There are probably other issues where simultaneously added nodes may try to insert themself into the same position in the ring, you could add some jitter in the placement to compensate for this, but then I guess you are now introducing randomness which is one step closer to just having vnodes again.
    - remram 1y ago
      Whatever balanced configuration you make, it will become imbalanced if you add or remove a node.
    - sfilipov 1y ago
      Worth mentioning that virtual nodes also ensure that the order of servers is random. Which helps when a server is removed - the keys that need to be moved will be spread across all other servers. If we were to evenly chop up the hash ring, server B will always be after server A. And when we remove server A, all keys residing on it will need to be moved exclusively to server B.
      - __turbobrew__ 1y ago
        That makes sense, thank you.
- jauntywundrkind 1y ago
  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/architecture/archDataDistributeVnodesUsing.html https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/arc...
  - __turbobrew__ 1y ago
    Sounds like placement groups in ceph.
- croemer 1y ago
  Yes, they reduce variance.
rad_gruchalski 1y ago
This is how Apache Cassandra works: https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/architecture/archDataDistributeHashing.html https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/arc....
meling 1y ago
I think the Chord DHT uses this. https://en.wikipedia.org/wiki/Chord_(peer-to-peer) https://en.wikipedia.org/wiki/Chord_(peer-to-peer)
pyfon 1y ago
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.
ryuuseijin 1y ago
Shameless plug of my consistent hashing implementation in about 50 lines of clojure: https://github.com/ryuuseijin/consistent-hashing https://github.com/ryuuseijin/consistent-hashing
hinkley 1y ago
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.
charleshn 1y ago
See also Rendezvous hashing [0], which is simpler and more general. [0] https://en.m.wikipedia.org/wiki/Rendezvous_hashing https://en.m.wikipedia.org/wiki/Rendezvous_hashing
jcartw 1y ago
Interactive Consistent HashRing Visualization

73 points by jcartw 1y ago

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

eulenteufel 1y ago

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/common/hash_ring.html https://docs.openstack.org/ironic/latest/_modules/ironic/com...

samwho 1y ago

Love this.

__turbobrew__ 1y ago

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.

swinglock 1y ago
Add enough random nodes and eventually it will be even, so it helps.
- __turbobrew__ 1y ago
  Why not just make the nodes even from the start? Place new nodes in the largest existing gap between any pair of nodes.
  - lsecondario 1y ago
    In a distributed system all clients would need to agree on the largest existing gap under various messaging anomalies. If you have a mechanism to reach that agreement then you can probably use a simpler deterministic load balancing algo. Consistent hashing gives you eventually consistent routing without (synchronous) agreement.
    - __turbobrew__ 1y ago
      You don’t need agreement. A newly added node can try best effort to find the optimal placement based upon the known state of the cluster and then advertise that it is going to a specific place in the hash ring. When clients learn about the new node they will also learn where that node has decided to put itself into the ring. No coordination is needed. There are probably moments that a client learns about the node they also atomically learn about where that nodes is placed. There are probably other issues where simultaneously added nodes may try to insert themself into the same position in the ring, you could add some jitter in the placement to compensate for this, but then I guess you are now introducing randomness which is one step closer to just having vnodes again.
  - remram 1y ago
    Whatever balanced configuration you make, it will become imbalanced if you add or remove a node.
  - sfilipov 1y ago
    Worth mentioning that virtual nodes also ensure that the order of servers is random. Which helps when a server is removed - the keys that need to be moved will be spread across all other servers. If we were to evenly chop up the hash ring, server B will always be after server A. And when we remove server A, all keys residing on it will need to be moved exclusively to server B.
    - __turbobrew__ 1y ago
      That makes sense, thank you.
jauntywundrkind 1y ago
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/architecture/archDataDistributeVnodesUsing.html https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/arc...
- __turbobrew__ 1y ago
  Sounds like placement groups in ceph.
croemer 1y ago
Yes, they reduce variance.

rad_gruchalski 1y ago

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

meling 1y ago

I think the Chord DHT uses this. https://en.wikipedia.org/wiki/Chord_(peer-to-peer) https://en.wikipedia.org/wiki/Chord_(peer-to-peer)

pyfon 1y ago

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.

ryuuseijin 1y ago

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

hinkley 1y ago

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.

charleshn 1y ago

See also Rendezvous hashing [0], which is simpler and more general. [0] https://en.m.wikipedia.org/wiki/Rendezvous_hashing https://en.m.wikipedia.org/wiki/Rendezvous_hashing

jcartw 1y ago

Interactive Consistent HashRing Visualization