Rendezvous hashing is an algorithm to solve the distributed hash table problem - a common and general pattern in distributed systems. There are three parts of the problem:
Keys: unique identifiers for data or workloads Values: data or workloads that consume resources Servers: entities that manage data or workloads
For example, in a distributed storage system, the key might be a filename, the value is the file data, and the servers are networked data servers that collectively store all of the files. Given a key and a dynamic list of servers, the task is to map keys to servers while preserving:
Load Balancing: Each server is responsible for (approximately) the same number of loads. Scalability: We can add and remove servers without too much computational effort. Lookup Speed: Given a key, we can quickly identify the correct server.
The set of servers is dynamic in the sense that we are allowed to add or remove servers at any time during the operation of the system.
Introduction to Rendezvous Hashing
When confronted with a load balancing problem, most engineers will pick an algorithm based on consistent hashing. Rendezvous hashing is much less well-known, despite being older than consistent hashing and providing different technical advantages. Why is this so?
The simple answer is that computer science courses often cover consistent hashing without introducing rendezvous hashing, but I think there is a deeper underlying reason for the popularity difference. In 1999, Akamai Technologies hosted the ESPN March Madness games and the movie trailer for Star Wars: The Phantom Menace. The trailer was so popular that the traffic crashed the film studio’s website - Akamai’s webcaches were the only way to access the video for several days. This event generated substantial public interest in Akamai, and the core component of Akamai’s content delivery network was consistent hashing. Then, the 2007 DynamoDB paper from Amazon touted consistent hashing as an integral part of Amazon’s successful commercial database. I suspect that rendezvous hashing is less popular because it never had the same kind of “killer app” moments.
However, rendezvous hashing is far from obsolete - engineering teams have quietly used the algorithm with great success since 1996. In fact, there seems to be a renewed interest in rendezvous hashing as an alternative to consistent hashing. Consistent hashing trades load balancing for scalability and lookup speed, but rendezvous hashing provides an alternative tradeoff that emphasizes equal load balancing. Over the last few years, rendezvous hashing has re-emerged as a good algorithm to load balance medium-size distributed systems, where an \(O(N)\) lookup cost is not prohibitive.
Why is it called “Rendezvous Hashing”? The motivation of the original 1996 paper was to provide a way for a data provider to communicate data to a client through a proxy server. To exchange the data, the client and provider meet - or rendezvous - at a selected proxy server. Rendezvous hashing is a distributed way for the client and provider to mutually agree on the meeting location.
... continue reading