consistent hashing pattern
Map both keys and nodes onto a ring; each key goes to the next node clockwise. When you add or remove a node, only ~1/N keys move (instead of ~all of them with mod-N hashing). Foundation of distributed caches and Dynamo-style stores.
Map both keys and nodes onto a ring; each key goes to the next node clockwise. When you add or remove a node, only ~1/N keys move (instead of ~all of them with mod-N hashing). Foundation of distributed caches and Dynamo-style stores.
symptoms
- adding a cache node invalidates everything
- rebalancing causes massive traffic spike
causes
- mod-N hashing makes node count part of the key mapping
fixes
- consistent hash ring with virtual nodes
- rendezvous (HRW) hashing as alternative
- token-based partitioning
you might say
- hash ring
- consistent hashing
- ring resharding