Consistent Hashing vs Rendezvous Hashing
What You'll Learn
You'll understand when to choose ring-based consistent hashing versus highest-random-weight (rendezvous) hashing for distributed key assignment.
Two Philosophies, Same Goal
Both consistent hashing and rendezvous hashing (also called Highest Random Weight or HRW) solve the same problem: assigning keys to nodes while minimizing reassignments when nodes join or leave. They just take fundamentally different approaches.
Consistent Hashing: The Ring Model
As you've learned, consistent hashing maps both keys and nodes onto a circular hash space. A key finds its home by "walking clockwise" to the next node. Adding/removing nodes only affects keys between adjacent positions. You need virtual nodes to handle uneven distributions.
Complexity: You maintain a sorted data structure of node positions. Lookup is O(log N) with binary search.
Rendezvous Hashing: The Tournament Model
Rendezvous hashing eliminates the ring entirely. Instead, for each key, you compute a hash score with every available node using a formula like hash(key + node_id). The node with the highest score wins that key.
Complexity: Per-lookup is O(N) — you must check all nodes. No data structure to maintain.
When to Choose Which
Consistent Hashing wins when:
- Node count is large (thousands of cache servers)
- Fast lookups matter more than perfect distribution
- You can tolerate the complexity of virtual nodes
Rendezvous Hashing wins when:
- Node count is small (dozens of database shards)
- Perfect uniform distribution is critical
- Simplicity matters — no ring maintenance, no virtual nodes
- You already know all candidate nodes
Key Takeaway: Consistent hashing trades perfect distribution for fast O(log N) lookups via ring structure; rendezvous hashing guarantees uniform distribution with simpler logic but requires O(N) computation per key—choose based on node count and lookup frequency.