Effective range partition splitting in scalable storage

Patent metadata

Field	Value
Publication number	US-9286001-B2
Application number	US-201414319758-A
Country	US
Kind code	B2
Filing date	Jun 30, 2014
Priority date	Jun 30, 2014
Publication date	Mar 15, 2016
Grant date	Mar 15, 2016

Abstract

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.

First claim

The invention claimed is:

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.

2. The computer-implemented method of claim 1 , wherein the adjusting the boundaries of the buckets more evenly distributes the updated traffic values amongst the buckets.

3. The computer-implemented method of claim 1 , wherein the determining the reference key is based on identifying one of the buckets that is closest to a mid-point of the traffic values prior to the updating of the traffic values.

4. The computer-implemented method of claim 1 , wherein the splitting the partition into multiple partitions is in response determining that the reference key speed is not exceeding a threshold value.

5. The computer-implemented method of claim 1 , wherein the adjusting the boundaries comprises merging at least some of the buckets into a single bucket.

6. The computer-implemented method of claim 1 , wherein the adjusting the boundaries comprises splitting at least one of the buckets into multiple buckets.

7. The computer-implemented method of claim 1 , wherein the adjusting the boundaries comprises moving a common boundary between adjacent buckets.

8. The computer-implemented method of claim 1 , wherein the traffic values are based on request latency of access requests on the partition.

9. The computer-implemented method of claim 1 , wherein the splitting the partition into multiple partitions is further based on a reference key drop-off time.

10. 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 reference key dividing tracked traffic across the partition key range;
updating the tracked traffic across the partition key range based on additional traffic across the partition key range;
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.

11. The computer-implemented method of claim 10 , wherein the rate of change of the distribution of the tracked traffic is based on a change between the tracked traffic and the updated tracked traffic.

12. The computer-implemented method of claim 10 , wherein the reference key speed is based on a running window of samples.

13. The computer-implemented method of claim 10 , wherein the splitting the partition results in the one of the multiple partitions being assigned to a first server of the scalable storage and another of the multiple partitions being assigned to a second server of the scalable storage.

14. The computer-implemented method of claim 10 , wherein the reference key speed is based on a first time stamp of a first sample of the reference key and a second time stamp of a second sample of the reference key.

15. One or more computer-storage media storing computer-useable instructions that, when executed by a computing device, perform a method for load balancing a scalable storage, the method comprising:
tracking traffic within boundaries that define sub ranges of a partition key range of a partition of the scalable storage;
adjusting the boundaries to more evenly distribute the tracked traffic within the boundaries;
determining a reference key based on the adjusted boundaries;
splitting the partition into multiple partitions based on the reference key.

16. The one or more computer-storage media of claim 15 , wherein the splitting the partition into multiple partitions is at a split-point that is based on the reference key.

17. The one or more computer-storage media of claim 15 , wherein the determining the reference key based on the adjusted boundaries comprises identifying one of the sub ranges that is closest to the mid-point of the tracked traffic.

18. The one or more computer-storage media of claim 15 , wherein the adjusting the boundaries comprises merging adjacent ones of the sub ranges into a composite sub range that is defined by the adjusted boundaries.

19. The one or more computer-storage media of claim 15 , wherein the splitting the partition into multiple partitions is further based on determining a time it takes for a reference key to be outside of a window of traffic.

20. The one or more computer-storage media of claim 15 , comprising maintaining sample keys within the sub ranges, wherein in the adjusting the boundaries, at least one of the boundaries is adjusted to one of the sample keys.

Assignees

• Microsoft Corp
• Microsoft Licensing Technology Llc

Inventors

• Skjolsvold Arild
• Wang Ju
• Calder Bradley Gene

Classifications

• G06F3/0635

  by changing the path, e.g. traffic rerouting, path reconfiguration · CPC title

• G06F9/5077

  Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455) · CPC title

• G06F2206/1012

  Load balancing · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title