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 dynamically adjusting to the addition or removal of servers. A popular and widely adopted solution is Consistent Hashing (CH). Recently, an 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. To overcome this, we propose Random Jump Consistent Hashing (RJ-CH), a 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 the AOL search dataset and Indiana University Clicks dataset, RJ-CH reduces cache misses by several magnitudes.

The Challenge of Cascaded Overflow

Distributed systems, such as Discord, Amazon Dynamo, and Akamai, rely on Consistent Hashing (CH) to map data objects to servers. CH is valued for its ability to handle server membership changes with minimal data reshuffling. However, real-world servers have finite capacity.

The previous state-of-the-art solution, Consistent Hashing with Bounded Loads (CH-BL), manages capacity by sending "overflow" objects to the next available server in a clockwise direction on the hash ring. This study identifies a critical flaw in this approach: cascaded overflow.

The standard Consistent Hashing with Bounded Loads (CH-BL) mechanism, illustrating initial placement and clockwise assignment.

When a server reaches its capacity, it effectively "lengthens" the arc of the subsequent server on the ring, causing that neighbor to fill up faster. This creates an avalanche effect where a single popular data spike can knock down a series of neighboring servers, leading to poor load balancing and increased latency.

Methodology: Random Jump Consistent Hashing (RJ-CH)

To address the spatial correlation of overflows, we introduce Random Jump Consistent Hashing (RJ-CH). Unlike the linear probing used in CH-BL, RJ-CH utilizes a hash function that incorporates both the object and the number of failed attempts as arguments.

  1. Initial Mapping: An object is hashed to a target server.
  2. The "Jump": If the target server is at capacity, the algorithm increments an "attempt" counter and re-hashes the object.
  3. Uniform Distribution: Leveraging the properties of universal hashing, each "jump" lands the object in a new, randomized location on the ring.
Visualizing the reassignment logic where overflows are distributed across the system rather than to immediate neighbors.

By treating the distributed system as a global pool rather than a local neighborhood for overflows, RJ-CH breaks the cascading failure chain. Two objects overflowing from the same full server are highly unlikely to land on the same secondary server. We provide a rigorous theoretical framework proving that RJ-CH stochastically dominates previous methods, ensuring a more even load distribution.

Empirical Evaluation

We evaluated RJ-CH using synthetic simulations and real-world user activity logs, including the AOL Search Dataset (3.8 million clicks) and the Indiana University Clicks Dataset (1 million clicks).

Key Results

  • Reduction in Cache Misses: In real-world tests on the AOL dataset, RJ-CH reduced additional cache misses by several orders of magnitude. In one configuration, CH-BL recorded approximately 35,000 misses, while RJ-CH recorded only 312.
  • Performance Gains: RJ-CH achieved a 2x to 7x speedup in wall-clock time for object insertion, as it identifies available servers much faster than the linear "walking" method.
  • Optimized Load Balancing: Under identical load conditions, RJ-CH resulted in 20% to 40% fewer full bins compared to CH-BL.
  • Stateless Addressing: RJ-CH maintains the requirement for stateless addressing, allowing the system to assign objects without global knowledge of every server's exact load.

Conclusion

RJ-CH demonstrates that the "ring" structure, while useful for initial mapping, is the root of cascading failures when used for overflow management. By restoring uniform distribution through randomized jumps, we achieve a system that is both faster and more resilient. Future work will explore the integration of RJ-CH with multi-tier caching hierarchies and machine-learning-based index structures to further optimize server discovery.

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. One essential requirement is that the addition or removal of small servers should not require us to recompute the complete assignment. A popular and widely adopted solution 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