System and method for identifying inconsistent parity in an array of storage
First Claim
1. A method for storing data in an array of storage devices, including processor and memory comprising the steps of:
- (A) logically arranging a plurality of block locations on the storage devices as a plurality of parity groups wherein a parity block stored in a block location as part of a parity group is logically derived from the combination of data blocks stored in the block locations of the parity group, and each parity and data block in a parity group is stored on a different storage device;
(B) grouping a set of the plurality of parity groups into a parity group set; and
(C) when writing a new data block to a data block location on a storage device;
(i) reading an old data block stored at the data block location;
(ii) writing the new data block to the data block location;
(iii) identifying a parity group and a parity group set to which the block location belongs;
(iv) only when the identified parity group set is in an unmodified state prior to writing the new data block, writing to the storage device an indicator that the identified parity group set is in a modified state indicating that during a recovery process, all parity groups in the identified parity group set will be checked for inconsistent parity; and
(D) using a parity group set counter to track whether the parity group set is in an unmodified state and when there are no longer any write operations currently modifying the parity group set, an indicator is set that the parity group set is in an unmodified state.
1 Assignment
0 Petitions
Accused Products
Abstract
A system and method are provided that is used by software implemented Redundancy Array of Inexpensive Disk (RAID) arrays to achieve adequate performance and reliability, as well as to improve performance or low cost hardware Raids. The enhancements to the basic RAID implementation speeds up recovery time for software RAIDS. A method is provided for storing data in an array of storage devices. A plurality of block locations on the storage devices are logically arranged as a parity group wherein a parity block stored in a block location as part of a parity group is logically derived from the combination of data blocks stored in the parity group, and each block in a parity group is stored on a different storage device. A plurality of parity groups are grouped into a parity group set. A request is received to write a new data block location on a storage device. The old data block stored at the block location is read. The new data block is written to the block location. When the parity set is in an unmodified state prior to the current write, an indicator is written to the storage device that the parity group set is in a modified state. In a preferred embodiment, this enhancement uses a bit map stored on disk, called Parity Group Set, (PGS) bit map, to mark inconsistent parity groups, replacing the Non-Volatile Random Access Memory, (NVRAM) used for similar purposes by hardware RAIDs. Further enhancements optimized sequential input/output, (I/O) data stream.
-
Citations
19 Claims
-
1. A method for storing data in an array of storage devices, including processor and memory comprising the steps of:
-
(A) logically arranging a plurality of block locations on the storage devices as a plurality of parity groups wherein a parity block stored in a block location as part of a parity group is logically derived from the combination of data blocks stored in the block locations of the parity group, and each parity and data block in a parity group is stored on a different storage device; (B) grouping a set of the plurality of parity groups into a parity group set; and (C) when writing a new data block to a data block location on a storage device; (i) reading an old data block stored at the data block location; (ii) writing the new data block to the data block location; (iii) identifying a parity group and a parity group set to which the block location belongs; (iv) only when the identified parity group set is in an unmodified state prior to writing the new data block, writing to the storage device an indicator that the identified parity group set is in a modified state indicating that during a recovery process, all parity groups in the identified parity group set will be checked for inconsistent parity; and (D) using a parity group set counter to track whether the parity group set is in an unmodified state and when there are no longer any write operations currently modifying the parity group set, an indicator is set that the parity group set is in an unmodified state. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. In a storage array system including plurality of storage devices, each storage device comprising a plurality of block locations, wherein a group of block locations are designated as a parity group, each parity group including a plurality of data blocks and a parity block stored in the parity group block locations, the parity block being logically derived from the combination of data blocks of the parity group, a method for writing a new data block to a designated block location in an array of storage devices without first storing the data blocks and parity block in a cache memory, comprising the ordered steps of:
-
(A) determining an old parity block corresponding to a parity group of the designated block location; (B) locking the designated block location; (C) reading an old data block stored at the designated block location; (D) writing the new data block to the designated block location; (E) unlocking the designated block location; (F) locking a block location of the old parity block for the designated parity group to which the designated block location belongs; (G) reading the old parity block; (H) calculating a new parity block for the designated parity group based on the old data block, the old parity block and the new data block; (I) writing the new parity block to the block location of the old parity block; and (J) unlocking the block location of the old parity block.
-
-
13. A storage array system comprising:
-
a plurality of storage devices, wherein each storage device comprises a plurality of block locations; a plurality of parity groups logically organized from said plurality of block locations on the storage devices, said parity groups comprising a parity block stored in one of the parity group block locations, said parity block logically derived from a combination of the data blocks stored in the parity group block locations, wherein each data and parity block in a parity group is stored on a different storage device; a plurality of parity group sets, each parity group set comprising a set of said plurality of parity groups; means for writing a new data block to one of said parity group block locations on one of said storage devices; means for reading an old data block stored at said one of said parity group block locations; means for identifying one of said parity group sets to which said one of said parity group block locations belongs; means for determining when said one of said parity group sets does not have an indicator that said one of said parity group sets is in an unmodified state; and means for writing to the storage devices, an indicator that said one of said parity group sets is in a modified state. - View Dependent Claims (14, 15, 16, 17)
-
-
18. An article of manufacture for use in a computer system for storing data in a computer system having an array of storage devices, the computer system having means to write data blocks to the storage devices, said article of manufacture comprising a computer-readable storage medium having a computer program code embodied in said medium which may cause the computer to:
-
(A) logically arrange a plurality of block locations on the storage devices as a plurality of parity groups wherein a parity block stored in a block location as part of a parity group is logically derived from the combination of data blocks stored in the block locations of the parity group, and each parity and data block in a parity group is stored on a different storage device; (B) group a set of the plurality of parity groups into a parity group set; and (C) when writing a new data block to a data block location on a storage device; (i) read an old data block stored at the data block location; (ii) write the new data block to the data block location; (iii) identify a parity group and a parity group set to which the block location belongs; (iv) only when the identified parity group set is in an unmodified state prior to writing the new data block, write to the storage device an indicator that the identified parity group set is in a modified state so that during a recovery process, all parity groups in the identified parity group set will be checked for inconsistent parity; (v) incrementing a parity group set counter for the identified parity group set when the identified parity group becomes modified; (vi) decrementing the parity group set counter for the identified parity group when the identified parity group becomes unmodified; and (vii) when the parity group set counter for the parity group set becomes zero, setting an indicator that the parity group set is in an unmodified state. - View Dependent Claims (19)
-
Specification