Managing removable media in raid and rail environments

• US 5,864,655 A
• Filed: 09/09/1996
• Issued: 01/26/1999
• Est. Priority Date: 09/09/1996
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dewey, Douglas William, Means, Rodney Jerome
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Wright, Norman M.
• Application Number:
  US08/709,970
• Time in Patent Office: 869 Days
• Field of Search: 395/182.03, 395/182.04, 395/185.02, 395/183.18, 395/185.01, 395/185.05, 395/185.07, 371/21.6, 371/49.1, 371/40.4, 371/69.1, 371/40.2
• US Class Current: 714/6.32
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

Parity updates are performed in an efficient manner after data is modified on removable media in a RAID or RAIL array, within or outside the array, without requiring that all of the data on all of media in a parity group be read. Instead, a list is maintained identifying those blocks of data were which modified on the media. Only the corresponding blocks on the remaining media in the parity group are read to calculate the new parity. Alternatively, a list can be maintained identifying the bits which were changed on the media. Consequently, only the corresponding bits of the parity block(s) need be changed.

Claims

1. A storage system for removable storage media, comprising:

a plurality m of data storage devices for storing blocks of data;

a parity storage device;

a storage controller interconnected with said m storage devices, said parity storage device and a host device, said storage controller including;

means for receiving a plurality of logical volumes V₁ -V_m of user data to be recorded onto corresponding pieces of removable media R₁ -R_m, each of the logical volumes V₁ -V_m having a plurality of data blocks including at least a first data block B_q, where "q" is a logical volume number between 1 and m, inclusive;

means for computing a first parity block P₁ from the first data blocks B₁ -B_m such that any first data block B_j can be reconstructed from the remaining m-1 first data blocks and the first parity block P₁, the blocks B₁ -B_m and P₁ forming a first parity group; and

means for directing that each of the first data blocks be recorded onto a corresponding one of m pieces of removable media R₁ -R_m mounted in said m data storage devices and that the parity block P₁ be recorded onto a corresponding piece of media R_p mounted in said parity storage device, each of said pieces of media R₁ -R_m and R_p being capable of storing a plurality of blocks of data;

means for detecting when one of the first data blocks B_j recorded on one of the m pieces of removable media R_j has been modified;

means, in response to said means for detecting, for recording the identity of those bits in the modified first data block B_j which were modified; and

means for updating the parity block P₁ using data stored on the media R_j without re-computing the parity block P₁ from all blocks of data on all of the pieces of media R₁ -R_m, said means for updating further including means for changing the state of only those bits in the parity block P₁ which correspond to the modified bits in the modified first data block B_j.

2. The storage system of claim 1, wherein:

said storage controller further comprises means for, in response to said means for detecting, recording the identity of the modified first data block B_j in a delta list; and

said means for updating the parity block P₁ comprises;

means for reading the delta list from the media R_j to identify the modified first data block B_j ;

means for directing that a modified parity block P₁ '"'"' be calculated from each first data block B₁ -B_m, including B_j, in the first parity group; and

means for recording the modified parity block P₁ '"'"' onto the media R_p.

3. The storage system of claim 1, further comprising:

a plurality of media storage cells;

a media accessor for transporting media between said storage cells and said data and parity storage devices.

4. The storage system of claim 1, further comprising:

a plurality m of automated storage libraries, each comprising;

a first plurality of media storage cells for retaining removable media, including one of the pieces of removable media R₁ -R_m ;

a first media accessor for transporting media between said first plurality of storage cells and said one of said m data storage devices housed within said library; and

another automated storage library, comprising;

a second plurality of media storage cells for retaining removable parity media on which parity data, including the parity block P₁, is recordable;

a second media accessor for transporting the parity media between said second plurality of storage cells and said parity storage device housed within said other automated storage library.

5. An array of automated library systems for removable storage media, comprising:

a plurality m of automated storage and retrieval libraries;

a plurality m of data storage devices, one of said data storage devices housed in each of said m libraries;

a parity storage device housed in an m+1th library;

a storage controller interconnected to each of said m+1 libraries and a host device, said storage controller including;

means for receiving a plurality of logical volumes V₁ -V_m of user data to be recorded onto corresponding pieces of removable media R₁ -R_m, each of the logical volumes V₁ -V_m having a plurality of data blocks including at least a first data block B_q, where "q" is a logical volume number between 1 and m, inclusive;

means for computing a first parity block P₁ from the first data blocks B₁ -B_m such that any first data block B_j can be reconstructed from the remaining m-1 first data blocks and the first parity block P₁, the blocks B₁ -B_m and P₁ forming a first parity group; and

means for directing that each of the first data blocks be recorded onto a corresponding one of m pieces of removable media R₁ -R_m mounted in said m data storage devices and that the parity block P₁ be recorded onto a corresponding piece of media R_p mounted in said parity storage device, each of said pieces of media R₁ -R_m and R_p being capable of storing a plurality of blocks of data;

means for detecting when one of the first data blocks B_j recorded on one of the m pieces of removable media R_j has been modified;

means, in response to said means for detecting, for recording the identity of those bits in the modified first data block B_j which were modified; and

means for updating the parity block P₁ using data stored on the media R_j without re-computing the parity block P₁ from all blocks of data on all of the pieces of media R₁ -R_m, said means for updating further including means for changing the state of only those bits in the parity block P₁ which correspond to the modified bits in the modified first data block B_j.

6. The storage system of claim 5, wherein:

said storage controller further comprises means for, in response to said means for detecting, recording the identity of the modified first data block B_j in a delta list; and

said means for updating the parity block P₁ comprises;

means for reading the delta list from the media R_j to identify the modified first data block B_j ;

means for directing that a modified parity block P₁ '"'"' be calculated from each first data block B_1-Bm, including B_j, in the first parity group; and

means for recording the modified parity block P₁ '"'"' onto the media R_p.

7. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer, to perform steps for updating parity in a removable media RAID device, the RAID device having:

a plurality m of data storage devices;

a parity storage device;

a storage controller interconnected with the m storage devices, the parity storage device and a host device;

the instructions comprising steps for;

receiving a plurality of logical volumes V₁ -V_m of user data to be recorded onto corresponding pieces of removable media R₁ -R_m, each of the logical volumes V₁ -V_m having a plurality of data blocks including at least a first data block B_q, where "q" is a logical volume number between 1 and m, inclusive;

computing a first parity block P₁ from the first data blocks B₁ -B_m such that any first data block B_j can be reconstructed from the remaining m-1 first data blocks and the first parity block P₁, the blocks B₁ -B_m and P₁ forming a first parity group;

recording each of the first data blocks onto a corresponding one of m pieces of removable media R₁ -R_m mounted in said m data storage devices and recording the parity block P₁ onto a corresponding piece of media R_p mounted in said parity storage device, each of said pieces of media R₁ R_m and R_p being capable of storing a plurality of blocks of data;

detecting when one of the first data blocks B_j recorded on one of the m pieces of removable media R_j has been modified;

updating the parity block P₁ using data stored on the media R_j without re-computing the parity block P₁ from all blocks of data on the media R₁ -R_m ;

in response to said detecting step, recording the identity of those bits in the modified first data block B_j which were modified; and

changing the state of only those bits in the parity block P₁ which correspond to the modified bits in the modified first data block B_j.

8. The program storage device of claim 7, wherein:

the instructions further comprise the step of, in response to said detecting step, recording the identity of the modified first data block B_j in a delta list; and

said updating step comprises;

reading the delta list from the media R_j to identify the modified first data block B_j ;

directing that a modified parity block P₁ '"'"' be calculated from each first data block B₁ -B_m, including B_j, in the first parity group; and

recording the modified parity block P₁ '"'"' onto the media R_p.

9. In a machine-executed method of operating a RAID device for removable media, the RAID device having:

a plurality m of data storage devices;

a parity storage device;

a storage controller interconnected with the m storage devices, the parity storage device and a host device;

including the machine-executed steps of;

receiving a plurality of logical volumes V₁ -V_m of user data to be recorded onto corresponding pieces of removable media R₁ -R_m, each of the logical volumes V₁ -V_m having a plurality of data blocks including at least a first data block B_q, where "q" is a logical volume number between 1 and m, inclusive;

computing a first parity block P₁ from the first data blocks B₁ -B_m such that any first data block B_j can be reconstructed from the remaining m-1 first data blocks and the first parity block P₁, the blocks B₁ -B_m and P₁ forming a first parity group;

recording each of the first data blocks onto a corresponding one of m pieces of removable media R₁ -R_m mounted in said m data storage devices and recording the parity block P₁ onto a corresponding piece of media R_p mounted in said parity storage device, each of said pieces of media R₁ -R_m and R_p being capable of storing a plurality of blocks of data;

detecting when one of the first data blocks B_j recorded on one of the m pieces of removable media R_j has been modified;

updating the parity block P₁ using data stored on the media R_j without re-computing the parity block P₁ from all blocks of data on the media R₁ -R_m ;

in response to said detecting step, recording the identity of those bits in the modified first data block B_j which were modified; and

changing the state of only those bits in the parity block P₁ which correspond to the modified bits in the modified first data block B_j.

10. In the machine-executed method of claim 9, wherein:

in response to said detecting step, recording the identity of the modified first data block B_j in a delta list; and

said updating step comprises;

reading the delta list from the media R_j to identify the modified first data block B_j ;

directing that a modified parity block P₁ '"'"' be calculated from each first data block B₁ -B_m, including B_j, in the first parity group; and

recording the modified parity block P₁ '"'"' onto the media R_p.

11. In the machine-executed method of claim 9, further comprising the steps of, after said recording step:

removing the piece of removable media R_j from one of the m storage devices;

mounting the piece of removable media R_j in a storage device outside of the RAID device;

modifying the first data block B_j ; and

returning the piece of removable media R_j to one of the m storage devices.

12. A storage system for removable optical media, comprising:

a plurality m of optical storage devices for storing blocks of data;

a parity storage device;

a storage controller interconnected with said m optical storage devices, said parity storage device and a host device, said storage controller including;

means for receiving a plurality of logical volumes V₁ -V_n of user data to be recorded onto corresponding pieces of optical media R₁ -R_n, each of the logical volumes V₁ -V_n having a plurality of data blocks including at least a first data block B_q, where n<

m and "q" is a logical volume number between 1 and n, inclusive;

means for computing a first parity block P₁ from the first data blocks B₁ -B_n and from an erased first data block B_m such that any first data block B_j can be reconstructed from the remaining m-1 first data blocks and the first parity block P₁, the blocks B₁ -B_m and P₁ forming a first parity group;

means for directing that each of the first data blocks B₁ -B_m be recorded onto a corresponding one of m pieces of optical media R₁ -R_m mounted in said m data storage devices and that the parity block P₁ be recorded onto a corresponding piece of media R_p mounted in said parity storage device, each of said pieces of media R₁ -R_m and R_p being capable of storing a plurality of blocks of data;

means for receiving an m-th logical volume V_m of user data to be recorded onto the m-th piece of removable media R_m, the logical volume V_m having at least a first data block B_m ; and

means for updating the parity block P₁ using the parity block P₁ and a bit map comprising bits in the m-th logical volume V_m without re-computing the parity block P₁ from all blocks of data on all of the pieces of media R₁ -R_m, the bit map identifying those bits in the first data block B_m which were modified, said means for updating further including means for changing the state of only those bits in the parity block P₁ which correspond to the modified bits in the modified first data block B_m.