Redundant arrays of independent libraries of dismountable media with parity logging

• US 5,497,457 A
• Filed: 10/17/1994
• Issued: 03/05/1996
• Est. Priority Date: 10/17/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ford, Daniel A.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): HUA, LY
• Application Number:
  US08/324,428
• Time in Patent Office: 505 Days
• Field of Search: 395/575, 395/425, 395/600, 395/182.04, 395/182.13, 371/40.4, 371/10.1, 371/40.1
• US Class Current: 714/6.24
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1014 Compression, i.e. RAID systems with parity using compression techniques

Abstract

A redundant array of independent data storage libraries of dismountable media units includes parity logging and unique parity update reintegration techniques to improve system performance by reducing the number of media mounts. The media units are arranged into redundancy groups that store the data as sets or parity groups of data blocks and a corresponding parity block. When new data is to be written parity updates are computed and stored in a parity log in nonvolatile storage, such as a magnetic fixed disk drive. The new data blocks are then written onto the media units, but the corresponding new parity blocks are not written if the media units containing the old parity blocks are not mounted at the time the parity updates are computed. If a media unit containing an old parity block is already mounted at the time the parity update is computed, then a new parity block is computed based on the parity update and the new parity block is written to the media unit without logging the parity update. When the media unit containing the old parity block is later mounted on a drive for doing a read or write operation, then the parity update is retrieved from the parity log and the new parity block computed and written to that media unit. The reintegration of parity updates is enhanced by parity pursuit striping wherein successive striping increments of data blocks are mapped across the media units such that a striping increment is located on the same media unit that contains the parity block corresponding to the prior striping increment.

Claims

1. A data storage library system for storing data to and retrieving data from media units, the system comprising:

a computer;

a plurality of data storage drives coupled to the computer;

a plurality of media units greater in number than the number of drives and mountable to and dismountable from the drives, the media units being arranged into redundancy groups;

a nonvolatile computer-readable memory;

a computer-readable memory encoded with a computer program for causing the computer to (a) organize the data to be stored into data sets, each data set including data blocks and an associated parity block, the number of data blocks plus the parity block in a set being equal to the number of media units in a redundancy group;

(b) write the data by striping the data blocks and the parity block in a set across all of the media units in the redundancy group, and by distributing the parity blocks for different sets among different media units in the redundancy group;

(c) log into the nonvolatile memory parity updates computed when the data blocks previously written to the media units in the redundancy group are to be modified;

(d) write modified data blocks onto the media units without writing a corresponding new parity block if the media unit containing the corresponding parity block to be updated is not mounted on a drive;

(e) retrieve the parity update from the log; and

(f) write a new parity block based on the retrieved parity update to the media unit containing the parity block to be updated when the media unit containing the parity block to be updated is later mounted on a drive.

2. The data storage library system according to claim 1 wherein the computer-readable memory encoded with a computer program causes the computer to write a new parity block based on the retrieved parity update by exclusive or'"'"'ing the retrieved parity update with the parity block to be updated.

3. The data storage library system according to claim 1 wherein the computer-readable memory encoded with a computer program also causes the computer to write the new parity block to the media unit containing the parity block to be updated without logging the parity update if the media unit containing the parity block to be updated is already mounted at the time the parity update is computed.

4. The data storage library system according to claim 1 wherein all the data blocks and parity blocks in the data sets for the media units in a redundancy group are mapped across the media units in successive striping increments so that a striping increment is located on the same media unit that contains the parity blocks corresponding to the prior striping increment.

5. The data storage library system according to claim 1 wherein all the data blocks in a redundancy group are organized into a set of striping increments, each striping increment containing the same number of fixed data blocks.

6. The data storage library system according to claim 1 wherein the parity updates stored in the parity log of the nonvolatile memory are organized as a linked list of parity update blocks, one parity update block for each media unit in the redundancy group.

7. The data storage library system according to claim 1 wherein the nonvolatile memory for logging updated parity blocks is a magnetic fixed disk drive.

8. The data storage library system according to claim 1 wherein the system includes a plurality of independent data storage libraries, each library including at least one of said plurality of data storage drives, at least two of said media units, and a picker for mounting the media units to and dismounting the media units from said at least one drive.

9. An array of independent optical disk libraries for connection to a computer having a nonvolatile memory and a computer-readable memory, the libraries enabling data to be stored to and retrieved from a plurality of dismountable optical disks, the array comprising:

a plurality of optical disk libraries, each library including at least one optical disk drive, at least two disks associated with each drive and a picker for mounting the disks to and dismounting the disks from the drives;

wherein the disks in the plurality of libraries are arranged into redundancy groups, each disk in a redundancy group being associated with a unique drive; and

a computer program encoded into the computer-readable memory, the computer program comprising;

(a) computer program code for organizing the data to be stored into parity groups assigned to redundancy groups, each parity group including data striping increments and an associated parity stripe, the number of data striping increments plus the parity stripe in a parity group being equal to the number of disks in a redundancy group;

(b) computer program code for causing the data to be written by striping the data striping increments and the parity stripe in a parity group across all of the disks in the assigned redundancy group, and by distributing the parity stripes for different parity groups among different disks in the assigned redundancy group;

(c) computer program code for causing to be logged into the nonvolatile memory parity updates computed when the data striping increments previously written to the disks in any of the redundancy groups are to be modified;

(d) computer program code for causing modified data striping increments to be written onto the disks in any of the redundancy groups without writing a corresponding new parity stripe when the disk containing the corresponding parity stripe to be updated is not mounted on a drive;

(e) computer program code for causing the parity update to be retrieved from the log and a new parity stripe based on the retrieved parity update to be written to the disk containing the parity stripe to be updated when the disk containing the parity stripe to be updated is mounted on a drive; and

(f) computer program code for causing a new parity stripe to be written to the disk containing the parity stripe to be updated without logging the parity update if the disk containing the parity stripe to be updated is already mounted at the time the parity update is computed.

10. The array according to claim 9 wherein all the data striping increments in the parity groups for the disks in a redundancy group are mapped across the disks in successive striping increments so that a striping increment is located on the same disk that contains the parity stripe protecting the prior striping increment.

11. The array according to claim 9 wherein the parity updates stored in the parity log of the nonvolatile memory are organized as a linked list of parity update blocks, one parity update block for each disk in each of the redundancy groups.

12. The array according to claim 9 wherein the nonvolatile memory for logging parity updates is a magnetic fixed disk drive.

13. In a data storage library system of the type having a nonvolatile storage, a plurality of data storage drives and a plurality of media units mountable to and dismountable from the drives, the media units being arranged into redundancy groups, a method for managing the writing of data and redundant parity information to the media units in the redundancy groups comprising the steps of:

organizing the data to be written into data sets, each data set including data blocks and a corresponding parity block, the number of data blocks plus the parity block in a set being equal to the number of media units in a redundancy group;

writing the data blocks by striping the data blocks and the parity block in a set across all of the media units in the redundancy group, including distributing the parity blocks for different sets among different media units in the redundancy group;

prior to writing a new data block over a previously written data block, computing a parity update by exclusive or'"'"'ing the previously written data block with the new data block not yet written;

if the media unit containing the corresponding previously written parity block is mounted on a drive when the parity update is computed, reading the previously written parity block, exclusive or'"'"'ing the computed parity update with the previously written parity block to compute a new parity block, and then writing the new data block over the previously written data block and the computed new parity block over the previously written parity block;

if the media unit containing the corresponding previously written parity block is not mounted on a drive when the parity update is computed, writing the new data block over the previously written data block without writing a corresponding new parity block and logging the computed parity update in a parity log in the nonvolatile storage; and

when the media unit containing the corresponding previously written parity block later becomes mounted on a drive, retrieving the parity update from the parity log, reading the previously written parity block, exclusive or'"'"'ing the retrieved parity update with the previously written parity block to compute a new parity block, and then writing the computed new parity block over the previously written parity block.

14. The method according to claim 13 further comprising the step of mapping all the data blocks and parity blocks in the data sets for the media units in a redundancy group across the media units in a redundancy group in successive striping increments by locating a striping increment on the same media unit that contains the parity block corresponding to the prior striping increment.

15. The method according to claim 13 wherein the step of logging the parity updates includes organizing the parity updates in the parity log as a linked list of parity update blocks, one parity update block for each media unit in the redundancy group.

16. The method according to claim 13 further comprising compressing the logged parity updates.