Consistent vs. rendezvous hashing
- The problem - determining locations of objects in a distributed system, susceptible to nodes going down or new ones appearing
- Variants - just one location / multiple locations
- Two solutions, invented at roughly the same time (1996/7), for distributing content and information on the internet.
Consistent hashing
- The linear hash table (bucket array) - resizing means redistributing everything
- Circular bucket list -> on average only n/m need to be moved => to a single node, load doubles; unfair distribution
- Circular list with multiple entries per node => smoother distribution, on failure even distribution to others
Solves for a single copy, not for k