LESSON 24.1
The hash ring in depth
How a consistent hash ring is implemented, why virtual nodes are needed and how many, how replicas are placed, and what happens step by step when nodes join and leave.
7 min read
The partitioning module introduced consistent hashing: when a cluster grows from N to N+1 nodes, only about 1/(N+1) of keys move. This lesson opens the box: how the ring is built, how evenly it spreads load, how replicas are placed, and what a real join looks like.
Remove a host and compare the moved keys with mod-N placement.
Building the ring
- Hash each node's id (or each of its virtual node ids) to a 64-bit number: its token.
- Keep the tokens in a sorted array.
- To place a key, hash it and binary-search for the first token greater than or equal to the key's hash, wrapping around to the start. That token's node owns the key.
A lookup is O(log T) for T tokens, a few hundred nanoseconds in memory. Clients or routers keep their own copy of the ring and update it when membership changes.
Why virtual nodes
With one token per node, arc lengths vary wildly. Give each physical node many tokens, and each node's share becomes the sum of many small arcs, which averages out.
- 1 token per nodefor tens of nodes
- largest node can own 3–5× the average
- ~100 tokens per node
- about ±10% spread
- ~1,000 tokens per nodea bigger ring to store and gossip
- about ±3% spread
Virtual nodes also help in two other ways:
- Heterogeneous hardware: give a machine twice the memory twice the tokens.
- Spread-out rebalancing: when a node joins, it takes small ranges from many existing nodes, so no single node has to stream all the data.
Cassandra historically used 256 tokens per node; newer versions use fewer, chosen by an allocation algorithm rather than at random, to get even load with less overhead.
Replicas on the ring
The list of nodes collected walking clockwise is the key's preference list. Two refinements:
- Skip tokens belonging to nodes already in the list, since virtual nodes mean the next token may be the same machine.
- Rack and zone awareness: keep walking until replicas are in different racks or availability zones.
A node joins, step by step
- The new node picks its tokens and announces itself (through gossip, or a coordination service).
- For each of its new ranges, it streams data from the nodes that currently own those ranges.
- During streaming, writes for those ranges go to both old and new owners, so nothing is missed.
- Once caught up, ownership flips: the ring now routes those ranges to the new node.
- Old owners clean up data for ranges they no longer own.
Leaving is the reverse: the departing node's ranges are streamed to the next owners clockwise. A crashed node's data is rebuilt from replicas, not from the node itself.
Where it's used
Distributed caches
- Adding a cache node invalidates only ~1/N of keys
- Hot keys still land on one node
Pick it when: Memcached client libraries, Redis client sharding.
Leaderless databases
- No central directory
- Smooth scaling
- Rebalancing streams data
Pick it when: Cassandra, DynamoDB's original Dynamo design, Riak.
Load balancers and CDNs
- The same client or object goes to the same server, keeping caches warm
- Uneven popularity needs bounded loads
Pick it when: Sticky routing, cache affinity.
Try it
Distributed Cache HLD
Partition a shared cache and handle nodes joining and failing.