EFFECTIVE RANGE PARTITION SPLITTING IN SCALABLE STORAGE

摘要

A method for load balancing includes determining a reference key within a partition key range of a partition of scalable storage, the partition key range being divided into buckets that have boundaries defining sub ranges of the partition key range. The reference key is determined based on traffic values that correspond to tracked traffic within the buckets. The traffic values are updated based on additional traffic within the buckets and the boundaries are adjusted based on the updated traffic values. A reference key speed is determined that corresponds to a rate of change of a distribution of the tracked traffic with respect to the reference key. Reference key drop-off time may be determined for reference keys. Reference keys can be utilized to determine where to split the partition and reference key speed and reference key drop-off time can be utilized to determine whether or not to split the partition.

主权项

1. A computer-implemented method for load balancing a scalable storage, the method comprising:
determining a reference key within a partition key range of a partition of the scalable storage, the partition key range being divided into buckets that have boundaries defining sub ranges of the partition key range, wherein the reference key is determined based on traffic values that correspond to tracked traffic within the buckets; updating the traffic values based on additional traffic within the buckets; adjusting the boundaries of the buckets based on the updated traffic values; determining a reference key speed that corresponds to a rate of change of a distribution of the tracked traffic with respect to the reference key; splitting the partition into multiple partitions based on the reference key speed.