Consistent Hashing Deep Dive: Virtual Nodes and Rebalancing

When you distribute data across N servers using hash(key) % N, adding or removing a single server remaps nearly every key. If you have 100 servers and add one, roughly 99 percent of keys move to a different server. For a distributed cache, that means a near-total cache miss storm. Consistent hashing reduces this to approximately K/N keys moved (where K is the total number of keys), making scaling operations dramatically less disruptive.

The Hash Ring

Consistent hashing maps both keys and servers onto a circular hash space (typically 0 to 2^32 - 1). A key is assigned to the first server encountered when walking clockwise around the ring from the key’s hash position.

               Server A (hash=50)
                    *
                 /     \
               /         \
    Server D  *           * Server B
   (hash=250) |           | (hash=120)
               \         /
                 \     /
                    *
              Server C (hash=180)

  Key "user:42" hashes to position 90
  Walking clockwise from 90: first server is B (at 120)
  -> "user:42" is stored on Server B

  Key "order:7" hashes to position 200
  Walking clockwise from 200: first server is D (at 250)
  -> "order:7" is stored on Server D

Adding and Removing Nodes

When Server E joins at position 160, only keys between Server B (120) and the new Server E (160) move from Server C to Server E. All other keys stay where they are.

Before adding E:
  Keys in range (120, 180] -> Server C

After adding E at position 160:
  Keys in range (120, 160] -> Server E  (moved from C)
  Keys in range (160, 180] -> Server C  (unchanged)
  All other ranges: unchanged

When a server is removed, its keys move to the next server clockwise. Only that one range is affected.

The Problem: Uneven Distribution

With only a few physical servers, the hash ring is poorly balanced. Some servers own large arcs and handle disproportionate load, while others own small arcs.

Unbalanced ring with 3 servers:

  A at 10     -> owns range (230, 10]   = tiny arc
  B at 100    -> owns range (10, 100]   = large arc
  C at 230    -> owns range (100, 230]  = huge arc

  Server C handles ~50% of all keys
  Server A handles ~10% of all keys

Virtual Nodes

The solution is to place each physical server at multiple positions on the ring. Instead of one point per server, create V virtual nodes per server (typically 100 to 256).

Physical servers: A, B, C
Virtual nodes per server: 4 (for illustration; production uses 100+)

Ring positions:
  A-1: 25,   A-2: 95,  A-3: 170, A-4: 240
  B-1: 40,   B-2: 110, B-3: 190, B-4: 270
  C-1: 60,   C-2: 130, C-3: 210, C-4: 300

Sorted ring: 25(A) 40(B) 60(C) 95(A) 110(B) 130(C)
             170(A) 190(B) 210(C) 240(A) 270(B) 300(C)

With 12 virtual nodes distributed around the ring, the arc sizes become much more uniform. Each physical server owns multiple small arcs rather than one potentially large arc.

How many virtual nodes?

V (vnodes)    |  Load std deviation (relative)
--------------+-------------------------------
1             |  ~50% imbalance
10            |  ~15% imbalance
50            |  ~7% imbalance
100           |  ~5% imbalance
256           |  ~3% imbalance

More virtual nodes mean better balance, but also more entries in the ring lookup table and more metadata to manage during node additions. Cassandra defaults to 256 virtual nodes (configurable via num_tokens).

Implementation

import hashlib
from bisect import bisect_right

class ConsistentHashRing:
    def __init__(self, nodes=None, vnodes=150):
        self.vnodes = vnodes
        self.ring = {}        # hash_value -> physical_node
        self.sorted_keys = [] # sorted hash positions
        if nodes:
            for node in nodes:
                self.add_node(node)

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node: str):
        for i in range(self.vnodes):
            vnode_key = f"{node}:vnode{i}"
            h = self._hash(vnode_key)
            self.ring[h] = node
            self.sorted_keys.append(h)
        self.sorted_keys.sort()

    def remove_node(self, node: str):
        for i in range(self.vnodes):
            vnode_key = f"{node}:vnode{i}"
            h = self._hash(vnode_key)
            del self.ring[h]
            self.sorted_keys.remove(h)

    def get_node(self, key: str) -> str:
        if not self.ring:
            raise ValueError("Ring is empty")
        h = self._hash(key)
        idx = bisect_right(self.sorted_keys, h)
        if idx == len(self.sorted_keys):
            idx = 0  # wrap around
        return self.ring[self.sorted_keys[idx]]

ring = ConsistentHashRing(["server-1", "server-2", "server-3"])

ring.get_node("user:42")      # "server-2"
ring.get_node("order:1001")   # "server-1"

# Add a fourth server: only ~25% of keys remap
ring.add_node("server-4")
ring.get_node("user:42")      # might still be "server-2" or moved to "server-4"

Replication with Consistent Hashing

In distributed databases, data is replicated to N nodes for fault tolerance. With consistent hashing, the replicas are the next N-1 distinct physical servers walking clockwise from the primary.

Replication factor = 3

Key "user:42" hashes to position 90.
Walking clockwise (skipping vnodes of the same physical server):
  Primary:  Server B (position 110)
  Replica 1: Server C (position 130)
  Replica 2: Server A (position 170)

The “skipping same physical server” rule is important. Without it, consecutive virtual nodes belonging to the same physical server would waste replication (all copies on one machine).

Rebalancing During Scale Events

Adding a node

When a new node joins, it takes ownership of some ranges from existing nodes. In systems like Cassandra, the new node streams data from its neighbors:

1. New node N joins, calculates its vnode positions
2. For each vnode, identify the predecessor and successor
3. Stream the relevant key ranges from the successor (old owner)
4. Once streaming completes, update the ring membership
5. The old owner deletes the transferred data

During streaming, reads for the affected ranges can be served by either the old or new owner. The system uses hinted handoff or read-repair to handle the transition.

Removing a node

When a node leaves (gracefully), it streams its data to the next nodes clockwise before departing. If a node crashes, the remaining replicas serve reads, and the system re-replicates the data to maintain the replication factor.

Weighted Nodes

Not all servers are equal. A machine with 64 GB of RAM should handle more keys than one with 16 GB. Weight virtual nodes proportionally:

Server A (64 GB): 256 vnodes
Server B (32 GB): 128 vnodes
Server C (16 GB):  64 vnodes

Server A gets four times the ring presence of Server C, and therefore roughly four times the traffic.

Consistent Hashing in Production

Amazon DynamoDB

DynamoDB uses consistent hashing to partition data across storage nodes. Each table’s partition key is hashed, and the hash determines which partition owns the item. Virtual nodes enable automatic splitting and merging of partitions as throughput changes.

Apache Cassandra

Cassandra uses consistent hashing with configurable virtual nodes (num_tokens). Each node owns multiple token ranges. The Murmur3Partitioner hashes partition keys to 64-bit values distributed across the ring.

Memcached / Redis cluster

Client libraries for Memcached (like ketama) implement consistent hashing to distribute keys across cache servers. Redis Cluster uses a related concept (hash slots: 16,384 fixed slots distributed across nodes) rather than a continuous ring.

Consistent Hashing vs Hash Slots

Aspect	Consistent Hashing	Hash Slots (Redis)
Ring size	Continuous (2^32 or 2^64)	Fixed (16,384 slots)
Rebalancing	Move ranges between nodes	Reassign slots between nodes
Granularity	Arbitrary	16,384 discrete slots
Implementation	More complex (sorted ring)	Simpler (slot-to-node map)

Hash slots are simpler to implement and reason about, but consistent hashing with virtual nodes provides finer-grained control over load distribution.

Key Takeaways

Consistent hashing minimizes key redistribution when the number of servers changes, making it foundational for distributed caches, databases, and load balancers. Virtual nodes solve the uneven distribution problem inherent in placing few physical servers on a hash ring. Size your virtual node count based on the balance you need (100 to 256 is typical). In production systems like Cassandra and DynamoDB, consistent hashing combined with replication and streaming rebalancing enables clusters to scale smoothly from a handful of nodes to hundreds.