A New Weight Function for Highest Random Weight Scheme and its Efficient Lookup Implementations

Cloud infrastructures have become increasingly popular among distributed applications in the modern era due to their efficient failure recovery, global reach, mobility, and service integration. Highest Random Weight (HRW) is one of the Consistent Hashing (CH) schemes that offers indefinite scalability while maintaining consistency, lookup, minimal dispersal, and load balancing for cloud environments. However, current versions of HRW and other CH algorithms offer high memory costs, exchange excessive messages for TCP connections, and sacrifice performance when considering large scalable distributed systems due to extensive rehashing or O(w) comparisons among $w$ working nodes. This paper suggests a weight function for the Highest Random Weight (HRW) scheme, termed as Multiplication Modulo-based Highest Random Weight (MM-HRW) scheme. In the MM-HRW scheme, the entire key range can be divided into several nonoverlapping ranges, and each range corresponds to a working node. By applying binary search on the ranges, we can find out the working node of a key with O(log (w)) comparisons. Additionally, we present the corresponding algorithms, implementations, and mathematical validation to support the experimental findings. The results demonstrate that MM-HRW consistently achieves an optimal memory footprint, validating its scalability across various scenarios. Additionally, by considering large cluster size, MM-HRW scheme achieves the highest lookup rate while maintaining O(log (w)) comparisons across all scenarios.

Submitted, IEEE Transactions on Network and Service Management