Consistent Hashing

The problem with modulo hashing

3 cache nodes, key "user:42"
  slot = hash("user:42") % 3  →  node 1

Add node 4:
  slot = hash("user:42") % 4  →  node 2   ← MOVED! cache miss storm

When StreamHub expanded Redis from 4 to 6 nodes using naive modulo, cache hit ratio dropped from 92% to 41% until keys repopulated — a classic cache stampede on the database.

The hash ring

Only keys in the affected arc move — typically 1/N of total keys when adding one of N nodes.

Virtual nodes (vnodes)

Physical machines get multiple positions on the ring for even distribution:

Physical node A → vnode A0, A1, A2, A3 on ring
Physical node B → vnode B0, B1, B2, B3 on ring

Without vnodes, uneven key density clusters on a few nodes. Redis Cluster and Dynamo use vnode-style partitioning.

# Redis Cluster — key must include hash tag for multi-key ops
SET user:{42}:session abc123
GET user:{42}:profile
# {42} ensures both keys land on same slot

The {...} hash tag forces related keys to the same slot — required for atomic multi-key operations.

Consistent hashing use cases

Adding and removing nodes

Adding a node:

Before:  keys K1–K5 → nodes A, B, C
Add D between B and C:
  Only keys that mapped to C and fall between B and D now map to D
  ~1/(N+1) keys move

Removing a node:

Keys owned by the removed node transfer to its clockwise successor. Plan capacity so successors absorb the load.

# StreamHub cache expansion runbook
steps:
  - add_new_node_with_vnodes
  - wait_for_key_migration_background
  - monitor_hit_ratio_recovery
  - remove_old_node_if_replacing
expected_hit_ratio_dip: temporary_5-10_pct

Comparison with alternatives

Hot keys and mitigation

Consistent hashing does not fix hot keys — if every request hits video:viral_001, one node still melts.

# Hot key fan-out read (pseudocode)
def get_view_count(video_id: str) -> int:
    if is_viral(video_id):
        replica = random.randint(0, 7)
        return cache_get(f"views:{video_id}:r{replica}")
    return cache_get(f"views:{video_id}")

Rendezvous hashing (alternative)

Highest Random Weight (HRW) hashing picks the node with the highest hash(node, key) score. Simpler than a ring for small node counts; consistent hashing scales better for large dynamic clusters.