AreaHash: A Balanced and fully scalable consistency hashing algorithm
Yan Zeng, Jinbo Zhang, Meiting Xue, Jian Wan, Jilin Zhang, Li Zhou · 2022
Distributed systems use consistent hashing algorithms to solve load balancing problems because of their good balance, minimal interruptions, and high query rates. However, existing algorithms fail to maintain consistency under changes, require high memory for high query rates, or have poor scaling. Therefore, we propose consistent AreaHash, which virtualizes the hash space into a ring. The logically ordered ring nodes occupy the same area, allowing the AreaHash to expand the nodes without any change. The key calculated using the hashing algorithm can be mapped to a node by a simple shift calculation, reducing memory requirements. We make a reasonable theoretical analysis and perform high-level algorithm implementation with a memory footprint of only a few bytes per node. Experimental results indicate that AreaHash achieves a lookup rate of more than 40 million keys per second, even when the number of nodes on a single CPU exceeds one million. In addition, a lookup rate of more than 20 million keys per second is achieved when more than half of the nodes in the cluster are down.