James Aspnes, Muli Safra, and Yitong Yin. Ranged hash functions and the price of churn. Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2008, pp. 1066–1075.
Ranged hash functions generalize hash tables to the setting where hash buckets may come and go over time, a typical case in distributed settings where hash buckets may correspond to unreliable servers or network connections. Monotone ranged hash functions are a particular class of ranged hash functions that minimize item reassignments in response to churn: changes in the set of available buckets. The canonical example of a monotone ranged hash function is the ring-based consistent hashing mechanism of Karger et al. (1997). These hash functions give a maximum load of Θ((n/m) log m) when n is the number of items and m is the number of buckets. The question of whether some better bound could be obtained using a more sophisticated hash function has remained open. We resolve this question by showing two lower bounds. First, the maximum load of any randomized monotone ranged hash function is Ω(√((n/m) log m)) when n=o(m log m). This bound covers almost all of the nontrivial case, because when n = Ω(m log m), simple random assignment matches the trivial lower bound of Ω(n/m). We give a matching (though impractical) upper bound that shows that our lower bound is tight over almost all of its range. Second, for randomized monotone ranged hash functions derived from metric spaces, there is a further trade-off between the expansion factor of the metric and the load balance, which for the special case of growth-restricted metrics gives a bound of Ω((n/m) log m), asymptotically equal to that of consistent hashing. These are the first known non-trivial lower bounds for ranged hash functions. They also explain why in ten years no better ranged hash functions have arisen to replace consistent hashing.
@inproceedings{AspnesSY2008,
author = {James Aspnes and Muli Safra and Yitong Yin},
title = {Ranged hash functions and the price of churn},
month = jan,
year = {2008},
booktitle="Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = {1066--1075}
}