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, said traffic corresponding to a workload associated with the partition; updating the traffic values based on additional traffic within the buckets; adjusting the boundaries of the buckets based on the updated traffic values; characterised in that: determining a reference key speed that corresponds to a rate of change between a first tracked traffic distribution and a second tracked traffic distribution with respect to the reference key, said reference key speed corresponding to a distance over time, wherein the distance is expressed in terms of buckets or boundaries and wherein said reference key speed is calculated based on the number of buckets the reference key has moved over time between the two tracked traffic distributions; load balancing by splitting the partition into multiple partitions based on the reference key speed and a reference key of the tracked traffic distribution, and wherein the splitting of the partition into multiple partitions is in response of determining that the reference key speed is not exceeding a threshold value. 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, said traffic corresponding to a workload associated with the partition; updating the traffic values based on additional traffic within the buckets; adjusting the boundaries of the buckets based on the updated traffic values; characterised in that: determining a reference key speed that corresponds to a rate of change between a first tracked traffic distribution and a second tracked traffic distribution with respect to the reference key, said reference key speed corresponding to a distance over time, wherein the distance is expressed in terms of buckets or boundaries and wherein said reference key speed is calculated based on the number of buckets the reference key has moved over time between the two tracked traffic distributions; load balancing by splitting the partition into multiple partitions based on the reference key speed and a reference key of the tracked traffic distribution, and wherein the splitting of the partition into multiple partitions is in response of determining that the reference key speed is not exceeding a threshold value. determining a reference key speed that corresponds to a rate of change between a first tracked traffic distribution and a second tracked traffic distribution with respect to the reference key, said reference key speed corresponding to a distance over time, wherein the distance is expressed in terms of buckets or boundaries and wherein said reference key speed is calculated based on the number of buckets the reference key has moved over time between the two tracked traffic distributions; load balancing by splitting the partition into multiple partitions based on the reference key speed and a reference key of the tracked traffic distribution, and wherein the splitting of the partition into multiple partitions is in response of determining that the reference key speed is not exceeding a threshold value.