Consistent Hashing with bounded loads

TY - GEN

T1 - Consistent Hashing with bounded loads

AU - Mirrokni, Vahab

AU - Thorup, Mikkel

AU - Zadimoghaddam, Morteza

N1 - Conference code: 29

PY - 2018

Y1 - 2018

N2 - In dynamic load balancing, we wish to allocate a set of clients (balls) to a set of servers (bins) with the goal of minimizing the maximum load of any server and also minimizing the number of moves after adding or removing a server or a client1. We want a hashing-style solution where we given the ID of a client can efficiently find its server in a distributed dynamic environment. In such a dynamic environment, both servers and clients may be added and/or removed from thesystem in any order. The most popular solutions for such dynamic settings are Consistent Hashing [KLL+97, SML+03] or Rendezvous Hashing [TR98]. However, the load balancing of these schemes is no better than a random assignment of clients to servers, so with n of each, we expect many servers to be overloaded with (log n= log log n) clients. In this paper, we aim to design hashing schemes that achieve any desirable level of load balancing, while minimizing the number of movements under any addition or removal of servers or clients. In particular, we consider a problem with m balls and n bins, and given a user-specified balancing parameter c = 1 + " > 1, we aim to find a hashing scheme with no load above dcm=ne, referred to as the capacity of the bins. Our algorithmic starting point is the consistent hashing scheme where current balls and bins are hashed to the unit cycle, and a ball is placed in the first bin succeeding it in clockwise order. In order to cope with given capacity constraints, we apply the idea of linear probing by forwarding the ball on the circle to the first non-full bin. We show that in our hashing scheme when a ball or bin is inserted or deleted, he expected number of balls that have to be moved is within a multiplicative factor of O( 1 "2 ) of the optimum for " ϵ 1 (Theorem 1.2) and within a factor 1 + O( log c c ) of the optimum for " ϵ 1 (Theorem 1.1). Technically, thelatter bound is the most challenging to prove. It implies that for superconstant c, we only pay a negligible cost in extra moves. We also get the same bounds for the simpler problem where, instead of a user specified balancing parameter, we have a fixed bin capacity C for all bins, and define c = 1 + ϵ = Cn=m.

AB - In dynamic load balancing, we wish to allocate a set of clients (balls) to a set of servers (bins) with the goal of minimizing the maximum load of any server and also minimizing the number of moves after adding or removing a server or a client1. We want a hashing-style solution where we given the ID of a client can efficiently find its server in a distributed dynamic environment. In such a dynamic environment, both servers and clients may be added and/or removed from thesystem in any order. The most popular solutions for such dynamic settings are Consistent Hashing [KLL+97, SML+03] or Rendezvous Hashing [TR98]. However, the load balancing of these schemes is no better than a random assignment of clients to servers, so with n of each, we expect many servers to be overloaded with (log n= log log n) clients. In this paper, we aim to design hashing schemes that achieve any desirable level of load balancing, while minimizing the number of movements under any addition or removal of servers or clients. In particular, we consider a problem with m balls and n bins, and given a user-specified balancing parameter c = 1 + " > 1, we aim to find a hashing scheme with no load above dcm=ne, referred to as the capacity of the bins. Our algorithmic starting point is the consistent hashing scheme where current balls and bins are hashed to the unit cycle, and a ball is placed in the first bin succeeding it in clockwise order. In order to cope with given capacity constraints, we apply the idea of linear probing by forwarding the ball on the circle to the first non-full bin. We show that in our hashing scheme when a ball or bin is inserted or deleted, he expected number of balls that have to be moved is within a multiplicative factor of O( 1 "2 ) of the optimum for " ϵ 1 (Theorem 1.2) and within a factor 1 + O( log c c ) of the optimum for " ϵ 1 (Theorem 1.1). Technically, thelatter bound is the most challenging to prove. It implies that for superconstant c, we only pay a negligible cost in extra moves. We also get the same bounds for the simpler problem where, instead of a user specified balancing parameter, we have a fixed bin capacity C for all bins, and define c = 1 + ϵ = Cn=m.

U2 - 10.1137/1.9781611975031.39

DO - 10.1137/1.9781611975031.39

M3 - Article in proceedings

SP - 587

EP - 604

BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Czumaj, Artur

PB - Society for Industrial and Applied Mathematics

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 7 January 2018 through 10 January 2018

ER -