Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1995-07-21
2001-01-09
Banankhah, Majid (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06173306
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to load balancing in parallel database systems (e.g. a shared nothing database system).
A parallel database system (DBS) employing a shared-nothing architecture distributes the database among several host processors that run the DBS. Conventionally, such a system is implemented by assigning to each host processor its own set of one or more storage devices, e.g. disk assemblies. Each host processor has exclusive access to its own set of storage devices and it cannot access the storage device of another host.
If a portion of the database that is controlled by a specific host processor is accessed much more frequently than other portions of the database, the host processor that is responsible for that portion of the database becomes a bottleneck and the performance of the entire DBS degrades. Since only one host processor is able to process the accesses to the “hot” portion of the database, the other host processors are unable to contribute to completing the processing. Thus, the other processors go partially idle while the busy host processor completes its work. This results in a very inefficient use of resources and poorer performance than what would be possible if all processors could equally contribute to completing the processing.
One solution to this problem has been to rebalance the DBS by redistributing the “hot” portions of the database among the other hosts processors. Thus, the other host processors will be able to contribute to processing the requests to the hot portions of the database and processing efficiency can be improved significantly. The redistribution is typically accomplished by copying portions of the database from host to host, an operation which is generally very resource and time intensive.
SUMMARY OF THE INVENTION
In one embodiment, the data storage system allows multiple hosts to access the same multiple volumes. In accordance with the invention, load rebalancing is accomplished by properly mapping the database files/extents upon the logical storage volumes and then dynamically establishing host/volume ownership as an agreement among the hosts (e.g. by using any convenient communication channel among the hosts). According to the agreement, a logical volume is accessed only by its owner (i.e., the host processor that is responsible for that logical volume). The agreement maintains the database partitioned among the host processors (e.g. a single owner to each subset of the multiple logical volumes). The agreement can be established by a single host processor which makes all of the decisions on host/volume ownership and the other host processors a priori agree to honor those decisions.
In general, in one aspect, the invention is a method of controlling distribution of processing in a system that includes a plurality of host data processors connected to a data storage system. The data storage system includes a digital memory 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 volumes. The concept of ownership means that a host processor is prohibited from sending I/O requests to any of the volumes which are outside of the subset of volumes which it owns. The method also includes monitoring the I/O requests that are sent to each of the volumes by each of the host processors; from the monitoring information, generating workload statistics indicative of the distribution of workload among the host processors; detecting a workload imbalance; and in response to detecting the workload imbalance, reassigning ownership of the volumes to the host processors so as to change the distribution of workload among the host processors.
Preferred embodiments include the following features. The method further includes storing a desired distribution of workload in memory that is accessible to at least one of the host processors, and during the detecting step, comparing the workload statistics to the desired distribution to detect whether the workload statistics diverge from the desired distribution by more than a threshold amount. The generation of workload statistics involves computing a measure of workload for each of the volumes and then using the measure of workload for each volume to generate the workload statistics for each host processor. The reassigning step involves computing a goodness of fit measure to identify which of the volumes are to be reassigned to which of the host processors. The method also includes distributing work to the host processors in accordance with which processors own which volumes.
In general, in another aspect, the invention is a method of operating a data storage system that includes a plurality of host connections for connecting host processors to the data storage system. The data storage system includes digital memory that is partitioned into a plurality of volumes. The method includes the step of mapping the volumes to the host connections so that each of the host connections has associated therewith a corresponding subset of the volumes, wherein a host processor that is connected to any given one of the host connections is able to access only the volumes that are mapped to that given host connection. The method also includes the steps of supporting within the data storage system (1) a connect command which enables a host processor to map a designated one of the volumes to a designated one of the host connections, and (2) a disconnect command which enables a host processor to unmap a designated one of the volumes from a designated one of the host connections.
In preferred embodiments, the method also includes the steps of sending a connect command from one of the host processors to the data storage system, wherein the connect command designates a first volume and a first host connection; and in response to receiving the connect command, remapping the volumes to the host connections by adding the first volume to the first host connection. The method also includes the steps of sending a disconnect command from one of the host processors to the data storage system, wherein the disconnect command designates a first volume and a first host connection; and in response to receiving the first disconnect command, remapping the volumes to the host connections by removing the first volume from the first host connection. The method further includes monitoring I/O requests that are sent to each of the volumes by each of the host processors; from monitoring information, generating workload statistics indicative of the distribution of workload among the host processors; detecting a workload imbalance; and in response thereto, remapping the volumes to the host connections.
One advantage of the invention is that it performs load rebalancing in a very short time and without the requirement of having to copy any data from one location to another location. It is accomplished simply by reassigning at the host level the ownership of logical volumes within the storage system.
Other advantages and features will become apparent from the following description of the preferred embodiment and from the claims.
REFERENCES:
patent: 4716528 (1987-12-01), Crus et al.
patent: 4858116 (1989-08-01), Gillett, Jr. et al.
patent: 4858120 (1989-08-01), Samuelson
patent: 4961134 (1990-10-01), Crus et al.
patent: 5062038 (1991-10-01), Jordan, Jr.
patent: 5063501 (1991-11-01), Jordan, Jr.
patent: 5063502 (1991-11-01), Jordan, Jr.
patent: 5063503 (1991-11-01), Jordan, Jr.
patent: 5063504 (1991-11-01), Jordan, Jr.
patent: 5101488 (1992-03-01), Rosenthal et al.
patent: 5127098 (1992-06-01), Rosenthal et al.
patent: 5142676 (1992-08-01), Fried et al.
patent: 5155851 (1992-10-01), Krishnan
patent: 5161227 (1992-11-01), Dias et al.
patent: 5210848 (1993-05-01), Liu
patent: 5226159 (1993-07-01), Henson et al.
patent: 5257366 (1993-10-01), Adair et al.
patent: 5263156 (1993-11-01), Bowen et al.
patent: 5301290 (1994-04-01), Tetzlaff et al.
patent: 5319780 (1994-06-01), Catino et al.
patent: 5327556
Alterescu Bruno
Raz Yoav
Vishlitzky Natan
Banankhah Majid
EMC Corporation
Fish & Richardson P.C.
LandOfFree
Dynamic load balancing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic load balancing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic load balancing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2463961