On the Modification of Ring Consistent Hash Uniformity: A Case Study
Muhammad Waqas, Sian-Jheng Lin, Bin Liu, Adnan Fazi · 2024
Distributed systems' applications employ distributed hashing for minimal dispersal, load balancing, and efficient lookups. One such scheme is Ring Consistent Hashing (RCH), which was initially proposed to tackle the issue of web hotspots. Later, it gained popularity in numerous practical ap-plications due to its structured node placement and$O(\log(N))$asymptotic complexity. Despite its popularity, RCH's uniformity is usually worse than other hashing schemes, such as the Highest Random Weight (HRW) and Anchor Hash (AH). For this reason, virtual nodes are introduced in RCH, which increases the memory footprint of the original scheme and restricts its scalability. In this paper, we propose a modification to the existing mapping rule between nodes and keys in the RCH scheme. We develop theoretical arguments and conduct several simulations on the conventional RCH algorithm using modified rule. The results show that the modified rule utilizes only half the number of virtual nodes compared to the original R CH for the same performance, resulting in significantly improved uniformity. Moreover, the memory footprint of the modified RCH is nearly halved compared to the original RCH, owing to the reduced number of virtual nodes. Additionally, the simulation results demonstrate that the modified scheme surpasses HRW and AH in lookup rate and memory usage, making it a superior choice for large-scale distributed systems.