Amazon.com, Inc.
Consistent hashing using the power of k choices in server placement

Abstract:

Systems and methods are described for load balancing requests in a distributed system using consistent hashing. Specifically, systems and methods are described for using "the power of k choices" when placing new servers on a consistent hash ring used to load balance requests. Rather than placing each new server at a fixed point determined by a hashing algorithm, a load balancer can identify multiple potential points on the hash ring for the new server. The load balancer can then compare these points to determine a preferred location, and place the server at the preferred location. Techniques described herein can substantially improve placement of servers, which in turn results in better load balancing.