Consistent Hashing
Difficulty: Medium | Topic #9
What to Learn
Hash ring concept, virtual nodes, how it minimizes data redistribution when nodes join/leave, applications in distributed caches and databases.
Resources
- Hello Interview: Consistent Hashing ↗
- Gaurav Sen: What is Consistent Hashing? ↗
- ByteByteGo: Consistent Hashing | Algorithms You Should Know ↗
Covered by Problems
| Problem | Difficulty | Link |
|---|---|---|
| Distributed Cache | Medium | → |
| Live Comments (FB Live) | Medium | → |
| Top K System | Hard | → |
| Ride Sharing (Uber) | Hard | → |
| Online Chess | Hard | → |
Key Concepts to Master
- Hash ring and clockwise key assignment
- Virtual nodes for even distribution
- How adding/removing a node affects ~1/N keys instead of all keys
- Rendezvous hashing as an alternative
- Real-world use in Cassandra, DynamoDB, and Memcached