Load Balancing of Requests with Keys Whose Frequencies Exhibit a Big-Head and Long-Tail Distribution

Consistent hashing is known as a load balancing method for cases where a large number of requests are to be handled by multiple servers. However, if the frequencies of the requested keys, which are used for the hash calculation, are unbalanced, this causes an uneven distribution of the load to the servers. To solve this problem, this paper presents a load balancing method in which keys are classified into groups according to the frequency at which they are requested, and a different load balancing method is applied to each key group based on a single parameter. An evaluation of the proposed method using simulation has confirmed that the system can successfully balance the load with a reasonable number of commodity, low cost servers in cases where consistent hashing cannot be applied.