# Consistent Hashing with Bounded Loads

arXiv: https://arxiv.org/abs/1608.01350 · HTML: https://mlsanity.com/paper/1608.01350/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2016.

## Built on by (most cited first, 2 of 2)

- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [CacheRoute: Planned Prefix-Affinity Routing for Large-Scale LLM Serving](https://mlsanity.com/paper/2608.19677/) (2026)

## Abstract (arXiv)

Designing algorithms for balanced allocation of clients to servers in dynamic settings is a challenging problem for a variety of reasons. Both servers and clients may be added and/or removed from the system periodically, and the main objectives of allocation algorithms are: the uniformity of the allocation, and the number of moves after adding or removing a server or a client. The most popular solution for our dynamic settings is Consistent Hashing. However, the load balancing of consistent hashing is no better than a random assignment of clients to servers, so with n of each, we expect many servers to be overloaded with Theta(log n/ loglog n) clients. In this paper, with n clients and n servers, we get a guaranteed max-load of 2 while only moving an expected constant number of clients for each update. We take an arbitrary user specified balancing parameter c=1+ε>1. With m balls and n bins in the system, we want no load above lceil cm/nrceil. Meanwhile we want to bound the expected number of balls that have to be moved when a ball or server is added or removed. Compared with general lower bounds without capacity constraints, we show that in our algorithm when a ball or bin is inserted or deleted, the expected number of balls that have to be moved is increased only by a multiplicative factor O(1over ε2) for ε ≤ 1 (Theorem 4) and by a factor 1+O(fraclog cc) for ε≥ 1 (Theorem 3). Technically, the latter bound is the most challenging to prove. It implies that we for superconstant c only pay a negligible cost in extra moves. We also get the same bounds for the simpler problem where we instead of a user specified balancing parameter have a fixed bin capacity C for all bins.