LOAD BALANCING WHEN REPLICATING ACCOUNT DATA

• US 20140258499A9
• Filed: 05/23/2011
• Published: 09/11/2014
• Est. Priority Date: 10/24/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Calder, Bradley Gene, Nilakantan, Niranjan, Srivastav, Shashwat, Wu, Jiesheng, Abbasi, Abdul Rafay, Mainali, Shane, Uddaraju, Padmanabha Chakravarthy, Skjolsvold, Arild Einar, Khatri, Hemal, Wang, Ju
• Granted Patent: US 8,886,796 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: G06F 2206/1012 Load balancing
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

Embodiments of the present invention relate to invoking and managing load-balancing operation(s) applied to partitions within a distributed computing environment, where each partition represents a key range of data for a storage account. The partitions affected by the load-balancing operation(s) are source partitions hosted on a primary storage stamp and/or destination partitions hosted on a secondary storage stamp, where the primary and secondary storage stamps are located in geographically distinct areas and are equipped to replicate the storage account'"'"'s data therebetween. The load-balancing operation(s) include splitting partitions into child partitions upon detecting an increased workload as a result of active replication, merging partitions to form parent partitions upon detecting a reduction in workload as a result of decreased processing-related resource consumption, or offloading partitions based on resource consumption. A service within a partition layer of the storage stamps is responsible for determining when to invoke these load-balancing operation(s).

Claims

1. A computer-implemented method in a distributed computing environment utilizing a processor and memory for identifying when to balance at least one processing load between nodes of the distributed computing environment, the method comprising:

monitoring a workload assigned to a subject partition being hosted on a first node of a storage stamp, wherein the subject partition represents a key range of data for a particular storage account;

detecting a level of the subject partition'"'"'s workload has overcome a predefined threshold;

identifying the subject partition as a candidate for receiving a load-balancing operation, wherein the load-balancing operation comprises at least one of splitting, merging, or load balancing the subject partition; and

storing in a record, at least temporarily, an indication that the subject candidate is identified as a candidate for receiving a load-balancing operation.

2. The method of claim 1, wherein monitoring a workload assigned to a subject partition comprises measuring a rate of traffic conveying requests targeting the subject partition or measuring rate of overload-related timeouts experienced by the subject partition.

3. The method of claim 1, wherein detecting a level of the subject partition'"'"'s workload has overcome a predefined threshold comprises:

recognizing a number of source partitions hosted on nodes of a primary storage stamp;

recognizing a number of destination partitions hosted on nodes of a secondary storage stamp;

comparing the number of source partitions against the number of destination partitions; and

upon comparison, invoking the load-balancing operation when the number of source partitions exceeds the number of destination partitions by a predefined factor

4. The method of claim 3, wherein the load-balancing operation comprises:

splitting the candidate partition into two or more child partitions; and

placing one or more of the child partitions on the first node of the storage stamp that hosted the subject partition.

5. The method of claim 6, wherein the load-balancing operation further comprises placing one or more of the child partitions on a second node of the storage stamp.

6. The method of claim 1, wherein the storage stamp represents at least one of a primary storage stamp that includes the nodes configured for hosting a number of source partitions or a secondary storage stamp that includes the nodes configured for hosting a number of destination partitions, and wherein the primary storage stamp and the secondary storage stamp are each configured to individually maintain sufficient replicas of the data for the particular storage account to ensure that, upon the occurrence of a failover, there exists readily accessible data internal to the primary storage stamp and the secondary storage stamp, respectively, in order to remedy the failover without relying upon external support.

7. The method of claim 6, wherein the subject partition represents a source partition, and wherein detecting a level of the subject partition'"'"'s workload has overcome a predefined threshold comprises deriving a value of the subject partition'"'"'s log size as a function of pending transactions within a log, associated with the subject partition, that remain undelivered to one or more destination partitions.

8. The method of claim 7, wherein, upon comparison of the subject partition'"'"'s log size against the average value of log sizes, invoking the load-balancing operation when the subject partition'"'"'s log size exceeds the average value of log sizes by a predefined factor.

9. The method of claim 6, wherein the subject partition represents a destination partition, and wherein detecting a level of the subject partition'"'"'s workload has overcome a predefined threshold comprises deriving a value of the destination partition'"'"'s log size as a function of pending transactions within a geo message log (GML), associated with the subject partition, that remain unexecuted;

10. The method of claim 9, further comprising:

deriving an average value of GML sizes for destination partitions hosted on the secondary storage stamp, wherein the destination partitions and the subject partition represent data of a common storage account;

comparing the destination partition'"'"'s log size against the average value of GML sizes derived from the destination partitions; and

upon comparison of the subject partition'"'"'s GML size against the average value of GML sizes, invoking the load-balancing operation when the subject partition'"'"'s GML size exceeds the average value of GML sizes by a predefined factor.

11. One or more computer-storage media having computer-executable instructions embodied thereon, that when executed by a computing system having a processor and memory, cause the computing system to perform a method for triggering load-balancing operations on partitions of a storage account, the method comprising:

calculating a log size for a subject partition, wherein the subject partition represents a key range of the storage account hosted on a first partition server;

calculating an average value of log sizes for one or more partitions within a common storage stamp as the subject partition, wherein the one or more partitions and the subject partition represent data of a common storage account;

comparing the subject partition'"'"'s log size against the average value of log sizes calculated for the one or more partitions;

upon comparison, invoking a load balancing operation when the subject partition'"'"'s log size meets the average value of log sizes adjusted by a predefined factor, wherein invoking the load-balancing operation comprises;

(a) when the subject partition'"'"'s log size overcomes the average value of log sizes adjusted upward by the predefined factor, triggering a split of the subject partition into two or more child partitions;

or

(b) when the subject partition'"'"'s log size falls below the average value of log sizes reduced by the predefined factor, triggering a merge between the subject partition and the one or more partitions to form a child partition.

12. The media of claim 11, wherein the pending transactions within the subject partition'"'"'s log represent at least one of transactions that remain undelivered to one or more destination partitions, or transactions that remain uncommitted to the subject partition.

13. The media of claim 12, wherein the split of the subject partition into two or more child partitions involves placing one or more of the child partitions on the first partition server and placing one or more of the child partitions on a second partition server of a storage stamp that hosts the first partition server.

14. The media of claim 13, wherein the two or more child partitions serve to divide execution or delivery of the pending transactions listed within the subject partition'"'"'s log.

15. The media of claim 11, wherein the method further comprises recognizing that a primary storage stamp is actively bootstrapping data of the storage account to a secondary storage stamp, wherein the first partition server resides on either the primary storage account or the secondary storage account.

16. The media of claim 15, wherein the method further comprises abstaining from triggering a merge upon recognizing that the primary storage stamp is actively bootstrapping data to the secondary storage stamp.

17. The media of claim 16, wherein invoking the load-balancing operation further comprises at least one of abstaining triggering a merge between the subject partition and the one or more partitions or triggering a split of the subject partition upon determining the calculated log size for the subject partition overcomes a maximum limit.

18. A computer system within a distributed networking environment for controlling load balancing of partitions, the system comprising:

a primary storage stamp that includes one or more first partition servers that host one or more source partitions, wherein the one or more source partitions represent a key range of initial data associated with a storage account;

a secondary storage stamp that includes one or more second partition servers that host one or more destination partitions, wherein the one or more destination partitions represent a key range of replicated data associated with the storage account, wherein the replicated data substantially minors content of the initial data, and wherein the one or more source partitions and the one or more destination partitions disagree in number; and

a service within a partition layer of either the primary storage stamp or the secondary storage stamp, wherein the service acts to increase or decrease instances of the one or more source partitions or one or more destination partitions such that they more closely correspond in number.

19. The system of claim 18, wherein the service is further configured to increase or decrease instances of the one or more source partitions or one or more destination partitions based on at least one of an amount of data to be applied to a particular partition or overall size of the particular partition, wherein the amount of data to be applied is a function of transactions presently enqueued within a log associated with the particular partition and a checkpoint data stream targeting the log.

20. The system of claim 18, wherein the service is further configured to increase or decrease instances of the one or more source partitions or one or more destination partitions based upon monitoring a flow of networking traffic and triggering load-balancing operations based upon the monitored flow, or where throttling of the networking traffic flow invokes the service to initiate splitting, merging, or offloading with regard to the one or more source partitions or one or more destination partitions.