Dynamic load balancing

• US 6,173,306 B1
• Filed: 07/21/1995
• Issued: 01/09/2001
• Est. Priority Date: 07/21/1995
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Vishlitzky, Natan, Raz, Yoav, Alterescu, Bruno
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US08/505,089
• Time in Patent Office: 1,999 Days
• Field of Search: 395/650, 395/700, 395/725, 709/100, 709/101, 709/102, 709/103, 709/105, 709/108
• US Class Current: 718/102
• CPC Class Codes: G06F 13/4256 using a clocked protocol
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method of controlling distribution of processing in a system that includes a plurality of host data processors connected to a data storage system which includes a digital storage that is partitioned into a plurality of volumes. The method includes assigning ownership of the volumes to the host processors such that each of the host processors owns a different subset of the plurality of volumes, wherein a host processor is prohibited from sending I/O requests to any of the volumes which it does not own. The method further includes monitoring the I/O requests that are sent to each of the volumes by each of the host processors; from information obtained through monitoring, generating workload statistics indicative of the distribution of workload among the host processors; detecting a workload imbalance in the workload statistics; and in response to detecting a workload imbalance, reassigning ownership of the volumes to the host processors so as to change the distribution of workload among the host processors.

Claims

1. A method of controlling distribution of processing in a system that includes a plurality of external data processors connected to a data storage system, wherein the data storage system includes digital storage that is physical memory partitioned into a plurality of partitions, each of said plurality of partitions being a different corresponding area of the physical memory in which data is storable, said method comprising:

assigning ownership of the plurality of partitions to the plurality of external processors such that each of said processors owns a different subset of said plurality of partitions, wherein each of said external processors is prohibited from sending I/O requests to any of said plurality of partitions which are outside of the subset of partitions which it owns;

monitoring the I/O requests that are sent to each of said plurality of partitions by each of said plurality of external processors;

from information obtained by said monitoring step, generating workload statistics indicative of the distribution of workload among said plurality of external processors;

detecting a workload imbalance in said workload statistics; and

in response to detecting said workload imbalance, reassigning ownership of the plurality of partitions to the plurality of external processors so as to change the distribution of workload among said plurality of external processors.

2. The method of claim 1 further comprising storing a desired distribution of workload in memory that is accessible to at least one of the plurality of external processors, and wherein said detecting step comprises comparing said workload statistics to said desired distribution to detect said imbalance.

3. The method of claim 2 wherein said detecting step comprises detecting whether the workload statistics diverge from said desired distribution by more than a threshold amount.

4. The method of claim 1 wherein the step of generating workload statistics comprises computing a measure of workload for each of said plurality of partition and then using the measure of workload for each partition to generate said work load statistics for each external processor.

5. The method of claim 1 wherein said reassigning step comprises computing a goodness of fit measure to identify which of said partitions are to be reassigned to which of said external processors.

6. The method of claim 4 further comprising distributing work to said external processors in accordance with which processors own which partitions.

7. An apparatus for controlling distribution of processing in a system that includes a plurality of external processors connected to a data storage system, wherein the data storage system includes digital storage that is physical memory partitioned into a plurality of partitions, each of said plurality of partitions being a different corresponding area of the physical memory in which data is storable, said apparatus comprising:

means for assigning ownership of the plurality of partitions to the plurality of external processors such that each of said processors owns a different subset of said plurality of partitions, wherein each of said external processors is prohibited from sending I/O requests to any of said plurality of partitions which are outside of the subset of partitions which it owns;

means for monitoring the I/O requests that are sent to each of said plurality of partitions by each of said plurality of external processors;

means for generating from information obtained by said monitoring means workload statistics indicative of the distribution of workload among said plurality of external processors;

means for detecting a workload imbalance in said workload statistics; and

means for reassigning, in response to detecting said workload imbalance, ownership of the plurality of partitions to the plurality of external processors so as to change the distribution of workload among said plurality of external processors.

8. The apparatus of claim 7 further comprising means for storing a desired distribution of workload in memory that is accessible to at least one of the plurality of external processors, and wherein said detecting means comprises a comparing means for comparing said workload statistics to said desired distribution to detect said imbalance.

9. The apparatus of claim 8 wherein said detecting means detects whether the workload statistics diverge from said desired distribution by more than a threshold amount.

10. The apparatus of claim 7 wherein the generating means comprises means for computing a measure of workload for each of said plurality of partitions and means for using the measure of workload for each partition to generate said workload statistics for each external processor.

11. The apparatus of claim 10 wherein said reassigning means comprises means for computing a goodness of fit measure to identify which of said partitions are to be reassigned to which of said external processors.