System and method for load balancing in a distributed system by dynamic migration

Patent metadata

Field	Value
Publication number	US-2016004571-A1
Application number	US-201414322703-A
Country	US
Kind code	A1
Filing date	Jul 2, 2014
Priority date	Jul 2, 2014
Publication date	Jan 7, 2016
Grant date	—

Abstract

A system and method for load balancing between components of a distributed data grid. The system and method support dynamic data migration of selected data partitions in response to detection of hot spots in the data grid which degrade system performance. In embodiments, the system and method relies upon analysis of per-partition performance statistics for both the identification of data nodes which would benefit from data migration and the selection of data nodes for migration. Tuning of the data migration thresholds and method provides for optimizing throughput of the data grid to avoid degradation of performance resulting from load-induced hot spots.

First claim

What is claimed is:

1 . A method for load balancing in a cluster storage system comprising a plurality of nodes, the method comprising:
identifying a source node within the cluster storage system from which to move a plurality of data objects, wherein the source node comprises a node with exceptional wait times compared to other nodes, and homogeneous wait times among its partitions; analyzing the partitions on the source node to identify hot partitions wherein a hot partition is a partition with a disproportionately large share of the execution time load compared to other partitions of the source node; and alleviating load on the source node by migrating one or more partitions from the source node to a target node, wherein the one or more partitions are selected from not hot partitions.

2 . The method of claim 1 , further comprising collecting per-partition performance statistics for each partition of said plurality of nodes wherein said per-partition performance statistics include wait times and execution times.

3 . The method of claim 1 , further comprising identifying the target node by selecting a least loaded node from among the plurality of nodes in the cluster storage system.

4 . The method of claim 1 , further comprising selecting a single non-hot partition for migration from the source node to the target node by assessing load (Lh) on the source node, assessing load (Lc) on the target node, and selecting for migration a non-hot partition having a load closest to (Lh−LC)/2.

5 . The method of claim 1 , further comprising selecting a plurality of non-hot partitions for migration from the source node to the target node by assessing load (Lh) on the source node, assessing load (Lc) on the target node, and selecting for migration a plurality of partitions having a combined load close to (Lh−LC)/2.

6 . The method of claim 1 , further comprising:
determining whether a particular node has exceptional wait times compared to other nodes by comparing aggregated per-partition wait times for said particular node and comparing said aggregated per-partition wait times for said particular node with aggregated per-partition wait times for said other nodes.

7 . The method of claim 1 , further comprising:
determining whether a particular node has homogenous wait times by comparing per-partition wait times for said particular node with mean per-partition wait times for said particular node.

8 . A cluster storage system comprising:
a plurality of nodes each comprising a microprocessor; and a load balancing system wherein the load balancing system is configured to,
identify a source node within the cluster storage system from which to move a plurality of data objects, wherein the source node comprises a node with exceptional wait times compared to other nodes, and homogeneous wait times among its partitions;
analyze partitions on the source node to identify hot partitions wherein a hot partition is a partition with a disproportionately large share of the execution time load compared to other partitions of the source node; and
alleviate load on the source node by migrating one or more partitions from the source node to a target node, wherein the one or more partitions are selected from not-hot partitions on the source node.

9 . The cluster storage system of claim 8 , wherein the load balancing system is further configured to collect per-partition performance statistics for each partition of said plurality of nodes wherein said per-partition performance statistics include wait times and execution times.

10 . The cluster storage system of claim 8 , wherein the load balancing system is further configured to identify the target node by selecting a least loaded node from among the plurality of nodes in the cluster storage system.

11 . The cluster storage system of claim 8 , wherein the load balancing system is further configured to select a single non-hot partition for migration from the source node to the target node by assessing load (Lh) on the source node, assessing load (Lc) on the target node, and selecting for migration a non-hot partition having a load closest to (Lh−LC)/2.

12 . The cluster storage system of claim 8 , wherein the load balancing system is further configured to select a plurality of non-hot partitions for migration from the source node to the target node by assessing load (Lh) on the source node, assessing load (Lc) on the target node, and selecting for migration a plurality of partitions having a combined load close to (Lh−LC)/2.

13 . The cluster storage system of claim 8 , wherein the load balancing system is further configured to determine whether a particular node has exceptional wait times compared to other nodes by comparing aggregated per-partition wait times for said particular node and comparing said aggregated per-partition wait times for said particular node with aggregated per-partition wait times for said other nodes.

14 . The cluster storage system of claim 8 , wherein the load balancing system is further configured to determine whether a particular node has homogenous wait times by comparing per-partition wait times for said particular node with mean per-partition wait times for said particular node.

15 . A non-transitory computer-readable medium including instructions thereon for performing load balancing in a cluster storage system comprising a plurality of nodes, which instructions, when read and executed by a computer, cause the computer to perform steps comprising:
identifying a source node within the cluster storage system from which to move a plurality of data objects, wherein the source node comprises a node with exceptional wait times compared to other nodes, and homogeneous wait times among its partitions; analyzing the partitions on the source node to identify hot partitions wherein a hot partition is a partition with a disproportionately large share of the execution time load compared to other partitions of the source node; and alleviating load on the source node by migrating one or more partitions from the source node to a target node, wherein the one or more partitions are selected from not hot partitions.

16 . The non-transitory computer-readable medium of claim 15 , including further instructions thereon, which instructions, when read and executed by a computer, cause the computer to perform steps further comprising:
collecting per-partition performance statistics for each partition of said plurality of nodes wherein said per-partition performance statistics include wait times and execution times.

17 . The non-transitory computer-readable medium of claim 15 , including further instructions thereon, which instructions, when read and executed by a computer, cause the computer to perform steps further comprising:
identifying the target node by selecting a least loaded node from among the plurality of nodes in the cluster storage system.

18 . The non-transitory computer-readable medium of claim 15 , including further instructions thereon, which instructions, when read and executed by a computer, cause the computer to perform steps further comprising:
selecting a single non-hot partition for migration from the source node to the target node by assessing load (Lh) on the source node, assessing load (Lc) on the target node, and selecting for migration a non-hot partition having a load closest to (Lh−LC)/2.

19 . The non-transitory computer-readable medium of claim 15 , including further instructions thereon, which instructions, when read and executed by a comput

Assignees

• Oracle Int Corp

Inventors

• Smith Randall

Classifications

• G06F9/5088 Primary

  involving task migration · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F17/30598

  Physics · mapped topic

• G06F16/278

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title