Rendezvous Hashing Explained (2020)
3 days ago
- #hashing-algorithms
- #load-balancing
- #distributed-systems
- Rendezvous hashing is an algorithm for distributed hash table problems in dynamic server environments.
- It provides an alternative to consistent hashing, emphasizing equal load balancing over scalability and lookup speed.
- The algorithm was introduced in 1996 for client and provider to agree on a proxy server for data exchange.
- Keys generate a randomly sorted list of servers, selecting the first as the primary to maintain a 'first choice' invariant.
- Rendezvous hashing avoids cascaded failures by distributing load evenly when a server fails.
- It supports weighted servers for biased load balancing by adjusting server selection based on capacity.
- The algorithm is memory-efficient, requiring only a list of server identifiers for key-value pair location.
- Adding servers is challenging for distributed storage but manageable in cache systems due to eventual consistency.
- Lookup time is O(N), making it suitable for small to medium-sized distributed caches.
- Rendezvous hashing is regaining interest as a viable alternative to consistent hashing for certain use cases.