Consistent Hashing Architecture & Implementation

In distributed databases and caching tiers, mapping data keys to server nodes using standard modulo hashing (hash(key) % N) is disastrous when servers are added or removed, because changing $N$ forces almost 100% of keys to move, triggering a catastrophic cache stampede.

1. The Consistent Hashing Ring

• Both nodes and data keys are mapped onto a fixed circular space (e.g. $[0, 2^{32}-1]$) using a cryptographic hash function like MD5 or MurmurHash3.
• To locate a key, traverse the ring clockwise until encountering the first node token.

Minimal Key Migration Property

When a node is added or removed, only $1/N$ of keys are relocated to adjacent neighbors, while the remaining $(N-1)/N$ keys stay exactly where they are!

2. Virtual Nodes (V-Nodes)

• The Hotspot Flaw: In a naive 3-node ring, hash points might cluster together, leaving one server with 70% of keys and another with 5%.
• The Solution: Assign each physical machine 100–300 "virtual nodes" scattered randomly across the ring (e.g. NodeA#1, NodeA#2, etc.).
• Guarantees statistically uniform load distribution and seamless capacity scaling.

Key Architecture Trade-Offs & Decision Matrix