Consistent Hashing (Go)
Topics: consistent hashing, virtual nodes, hash ring
Problem
Distribute keys across a changing set of nodes (cache shards, storage replicas) so that adding or
removing a node moves only ~1/N of the keys, not the whole keyspace. The trick is a hash ring
with virtual nodes.
func New(replicas int) *Ring
func (r *Ring) Add(node string)
func (r *Ring) Remove(node string)
func (r *Ring) Get(key string) (string, bool)
Add places replicas virtual points for the node around the ring (hash(node#i)). Idempotent.Get hashes the key and returns the node of the first virtual node clockwise (wrapping past
the end); false if the ring is empty.Remove drops a node and all its virtual points.
Key concepts
- The ring: node hashes live in a sorted
[]uint32; Get is a binary search (sort.Search)
for the first hash ≥ the key's, wrapping to index 0.
- Virtual nodes: each real node gets many points so its share of the ring is even — more
replicas → smoother distribution.
- Minimal disruption: because a key only depends on the next point clockwise, adding a node
steals keys only from the arcs it lands on; everything else is untouched.
The struct, New, and hashKey are provided; you implement Add, Remove, and Get.
Run
go test -v -race ./challenges/consistent-hashing/go/
Sign in to submit your solution.