Revisiting Consistent Hashing with Bounded Loads

John Chen, Benjamin Coleman, Anshumali Shrivastava

Abstract

Dynamic load balancing lies at the heart of distributed caching. The goal is to assign objects (load) to servers (computing nodes) in a way that provides load balancing while at the same time dynamically adjusts to the addition or removal of servers. A popular and widely adopted solution to dynamic load balancing is Consistent Hashing (CH). Recently, an elegant extension was provided to account for server bounds (CH-BL). In this paper, we identify that existing methodologies for CH and its variants suffer from "cascaded overflow," leading to poor load balancing. This cascading effect leads to decreasing performance of the hashing procedure with increasing load. To overcome this, we propose Random Jump Consistent Hashing (RJ-CH), a simple solution based on recent advances in fast minwise hashing. We show, both theoretically and empirically, that our proposed solution is significantly superior for load balancing and is optimal in many senses. On real-world datasets, RJ-CH reduces cache misses by several magnitudes.

Introduction: The Problem of Cascaded Overflow

In distributed systems such as CDN clusters or distributed databases, Consistent Hashing (CH) is the gold standard for assigning data objects to servers. It allows for the dynamic addition or removal of servers without requiring a complete reshuffle of the dataset. However, standard CH does not account for individual server capacities. If a server receives excessive traffic, it risks failure.

Consistent Hashing with Bounded Loads (CH-BL) was introduced to address this by setting a maximum capacity for each server. If a server is full, the system assigns the object to the next available server in a clockwise direction on the hash ring.

Consistent Hashing with Bounded Loads (CH-BL) assignment process.

We have discovered that this "clockwise" rule creates a critical flaw: cascaded overflow. As servers reach capacity, the "effective" arc length of the remaining non-full servers grows exponentially. A non-full bin sitting next to three full bins is four times more likely to receive the next object than a bin with no full neighbors. This creates an "avalanche" effect where servers fail in sequence, leading to poor load distribution and a higher percentage of full bins.

Random Jump Consistent Hashing (RJ-CH)

To address the geometry of failure in CH-BL, we propose Random Jump Consistent Hashing (RJ-CH). Instead of searching for the next available server in a fixed clockwise direction—which is essentially linear probing on a circle—RJ-CH utilizes randomized probing.

Random Jump Consistent Hashing (RJ-CH) mechanism.

The RJ-CH algorithm follows these principles:

  1. Randomized Probing: If the initial server assigned to an object is full, the algorithm rehashes the object using a hash function that incorporates the object ID and the number of failed attempts.
  2. Uniform Distribution: This ensures that when a server overflows, its load is distributed uniformly across all other available servers on the ring, rather than just the immediate neighbor.
  3. Stateless Addressing: The method remains "stateless," meaning it does not need to track the exact load of every server in real-time, which is crucial for high-speed distributed systems.

By using "Random Jumps," we decouple the physical location of servers on the hash ring from their overflow behavior, mathematically eliminating the cascading effect.

Experimental Evaluation

We evaluated RJ-CH using both synthetic simulations and real-world user activity logs:

  • AOL Search Dataset: 3.8 million URL clicks representing real-world web traffic patterns.
  • Indiana University Clicks Dataset: 1 million URL clicks used to validate results on a different distribution.
  • Synthetic Simulations: Used to measure wall-clock time, bin load variance, and the percentage of full bins across varying capacity constraints ($\epsilon$).

Key Results

  • Massive Cache Miss Reduction: On the AOL dataset, RJ-CH reduced additional cache misses from 35,780 down to 312 in one configuration—a reduction of over 100x.
  • Superior Load Distribution: In simulations, RJ-CH resulted in 20% to 40% fewer full bins compared to CH-BL. For example, at a specific capacity setting ($\epsilon = 0.3$), 60% of bins were full under CH-BL, while only 25% were full under RJ-CH.
  • Performance Speedup: RJ-CH achieved a 2x to 7x speedup in wall-clock time for object insertion because it encounters fewer full bins and avoids long, cascaded search paths.

Conclusion

Random Jump Consistent Hashing provides a robust and efficient solution to the cascaded overflow problem in bounded-load hashing. By replacing sequential searching with randomized probing, RJ-CH achieves significantly better load balancing and performance. Future work will involve exploring how to adapt this logic to systems with elastic address spaces and applying these insights to load balancing across GPUs in data-parallel machine learning.

Summary updated

Abstract

Dynamic load balancing lies at the heart of distributed caching. Here, the goal is to assign objects (load) to servers (computing nodes) in a way that provides load balancing while at the same time dynamically adjusts to the addition or removal of servers. Load balancing is a critical topic in many areas including cloud systems, distributed databases, and distributed and data-parallel machine learning. A popular and widely adopted solution to dynamic load balancing is the two-decade-old Consistent Hashing (CH). Recently, an elegant extension was provided to account for server bounds. In this paper, we identify that existing methodologies for CH and its variants suffer from cascaded overflow, leading to poor load balancing. This cascading effect leads to decreasing performance of the hashing procedure with increasing load. To overcome the cascading effect, we propose a simple solution to CH based on recent advances in fast minwise hashing. We show, both theoretically and empirically, that our proposed solution is significantly superior for load balancing and is optimal in many senses. On the AOL search dataset and Indiana University Clicks dataset with real user activity, our proposed solution reduces cache misses by several magnitudes.
BibTeX
@inproceedings{chen2021revisiting,
  author = {John Chen and Benjamin Coleman and Anshumali Shrivastava},
  title = {{Revisiting Consistent Hashing with Bounded Loads}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=A5sH356M0H},
}
Figure