Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1998-04-10
2004-08-10
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
Reexamination Certificate
active
06775739
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to mass storage systems, and in particular, to mass storage systems in which stored logical volumes are duplicated in mirrored form.
Mass storage systems have grown significantly in capacity over the past years while maintaining a lower cost per stored byte. Accordingly, various methods and systems have been developed for increasing the reliability of the systems and to protect against failures. One such policy includes the storage of two or more copies of the data in what are called mirrored drives. This system operates to maintain all copies up to date. Most typically, there are two copies.
In a typical system, each physical drive is often divided into a plurality of units, one unit often being a logical volume. Under these circumstances, each logical volume appears to the host computer or computers to be a separate drive and operations take place with regard to the logical volume as if it were a physical volume. Some logical volumes are accessed substantially more often for read and/or write operations, and the nature of the operations can vary from random accesses to sequential accesses during any particular sequence of read or write operations. As a result, with larger disk drives, the risk of having concurrent jobs, each pertaining to a relatively small file (local activity) interfering with each others' disk activity increases. The use of striping techniques further increases the risk. Depending upon the nature and variety of the read and write operations to a physical drive containing many logical volumes, the disk read/write heads may be severely worked and the access time can, on average, be increased if sequential read and write locations are not located near one another.
One method for combating such problems is to set a mirror service policy, statically or preferably dynamically (as described in U.S. Ser. No. 08/936,122, filed Sep. 24, 1997, now U.S. Pat. No. 6,112,257, issued Aug. 29, 2000 and entitled Dynamic Mirror Service Policy, the contents of which are incorporated herein, by reference), which attempts to optimize the reading and writing of data. Such a policy may, for example, assume that most data transfers are sequential in nature, or that they are random. The policies can include, for example, interleaved, mixed, dedicated, or other policies which appear, after reviewing the manner in which a drive is, or is to be, used, to provide the best average access time to the data.
One such policy is to only service requests that fall within the first half of a logical volume. Another policy might be to only service requests that fall in odd groups with a group being defined in terms of a number of blocks. For instance the first group (blocks
0
-
959
) will be serviced by copy
1
and the next group by copy
2
, etc. These policies, when implemented statically, are limited because the policies are chosen at system configuration time and never change. A dynamic mirror policy can substantially improve performance as the policies for the system change periodically, for example, every ten minutes. But even with a dynamically changing mirror policy, it is still important to select the correct (best) policy for each logical volume.
SUMMARY OF THE INVENTION
The invention relates to a method and apparatus for dynamically adjusting the loading in a system of physical disk drives for reading mirrored logical volumes. The method features the steps of collecting statistics describing at least reading data from the mirrored volumes during successive time periods, determining from the statistics an activity level for each of the mirrored logical volumes, and maximizing separation of the logical volumes using a matching algorithm to minimize seek times for the physical drives. In one aspect, the matching algorithm is a weighted matching algorithm, the weighting depending upon activity level, and in another instance, the matching algorithm is unweighted, matching the logical volumes in order of activity level.
In particular aspects, the method features periodically repeating the determining and maximizing steps for dynamically and periodically updating the logical volume access. The method can feature sorting the activity levels of the volumes before performing the maximizing step, removing from consideration those logical volumes which the matching algorithm associates with a single disk drive, and repeating the maximizing step on the unmatched logical volumes. The repeating step and the removing step can be repeated until either the number of logical volumes is exhausted or a selected threshold is reached. The threshold will typically be based upon an activity level of the sorted logical volumes.
The apparatus of the invention typically resides in a stored computer program, in magnetic memory, the program instituting the steps of collecting statistics describing at least reading data from the mirrored volumes during successive time periods, determining from the statistics an activity level of the mirrored logical volumes, and maximizing separation of the logical volumes using a matching algorithm to more evenly balance the loading of the disk drives and to minimize average seek time for the disk drives. The matching algorithm can be either a weighted or an unweighted matching algorithm. The program further institutes the step of periodically repeating the determining and maximizing steps for dynamically and periodically updating the logical volume mirror policy.
The apparatus of the invention further incorporates a program which institutes the steps of sorting the activity levels of the volumes prior to the maximizing step, removing those logical volumes which the matching algorithm associates with a single physical disk drive, and repeating the maximizing step upon the unmatched logical volumes. When the matching algorithm reaches a point wherein no further matches can be obtained, the program institutes the steps of removing from consideration those logical volumes which have already been matched and repeating the maximizing step on the remaining sorted logical volumes.
In another aspect of the invention, the method and apparatus of the invention provide for removing stress upon any disk adaptor associated with particular physical drive members.
The invention thus advantageously, adaptively selects, using a matching algorithm, the best mirror service policy for at least the most active logical volumes of a system. While this can only occur efficiently with regard to read operations, wherein no change of the data stored on a logical volume is made, the adjustment decreases the seek time within which data is recalled from a physical drive. The method and apparatus also advantageously better balance the load across the system by determining which disk drives have the highest level of activity and choosing policies to alleviate any existing high load conditions.
REFERENCES:
patent: 5819310 (1998-10-01), Vishlitzky et al.
patent: 5835938 (1998-11-01), Yamamoto et al.
patent: 5937428 (1999-08-01), Jantz
patent: 6112257 (2000-08-01), Mason et al.
patent: 6173306 (2001-01-01), Raz et al.
Chen et al., “Performance of a Mirrored Disk in a Real-Time Transaction System,” University of Massachusetts publication No. XP-000989675, 1991.
Golubchik et al. “Load Balancing and Robustness to Skew and Failures,” University of California publication No. XP-002141666, 1992.
Arnon Dan
Bachmat Eitan
Choi Woo H.
EMC Corporation
Hale and Dorr LLP
Kim Matthew
LandOfFree
Mirrored drive performance using matching algorithms does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mirrored drive performance using matching algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mirrored drive performance using matching algorithms will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3283816