US5522032A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Raid level 5 with free blocks parity cache
Assignee: International Business Machines Corp
•
Filing: 1994-05-05
•
Granted: 1996-05-28
•
Expires: 2014-05-05
Abstract
Abstract A system for writing data to a disk array includes a cache memory coupled to the disk array for storing data indicative of locations on the disk array and parity blocks associated with parity groups including the locations. Each of the parity blocks includes an identifier indicative of locations within a particular parity group which are protected by the parity data. Write logic reads the identifier from the parity block, and based thereon, determines whether a disk location is not protected by the parity data. The write logic also writes to the location and updates the parity data and the identifier associated with the parity block to include the location of the data block to indicate that the location is protected.
Inventors
- 👤 Peter A. Franaszek
- 👤 John T. Robinson
- 👤 Alexander Thomasian
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 22:38
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0866; G06F2211/00; G06F2211/10; G06F2211/1002; G06F2211/1009; G06F2211/1033; G06F2211/1059; G06F2212/00; G06F2212/31; G06F2212/312
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
123 words
A system for writing data to a disk array, comprising: a cache memory coupled to the disk array, the cache memory storing one or more parity blocks associated with stripes of disk data blocks, each parity block including parity data for one or more data blocks in its stripe and an identifier identifying protected data blocks in its stripe; and write logic coupled to the cache memory and the disk array, the write logic including: means for determining whether or not a location is protected by the parity data; means for writing data to a selected location; means for computing new parity data and updating the identifier associated with the new parity data if necessary to indicate that the selected location is protected.
Claim 2
Independent Claim
123 words
A system for writing data to a disk array, comprising: a cache memory coupled to the disk array, the cache memory storing one or more parity blocks associated with stripes of disk data blocks, each parity block including parity data for one or more data blocks in its stripe and an identifier identifying protected data blocks in its stripe; and write logic coupled to the cache memory and the disk array, the write logic including: means for determining whether or not a location is protected by the parity data; means for writing data to a selected location; means for computing new parity data and updating the identifier associated with the new parity data if necessary to indicate that the selected location is protected.
Claim 3
Dependent Claim
49 words
The system according to claim 1, further comprising: means for reading from the disk array a block of data after it has been freed; and means for recomputing parity data and updating the identifier associated with the recomputed parity data to reflect the freeing of the block of data.
Claim 4
Dependent Claim
22 words
The system according to claim 2, including means for reading from the disk array a block of data as it is freed.
Claim 5
Dependent Claim
27 words
The system according to claim 2, further comprising means for determining an optimal set of blocks to read from disk so as to recompute the parity data.
Claim 6
Dependent Claim
26 words
The system according to claim 2, further comprising means for reading from the disk array a plurality of blocks of data after they have been freed.
Claim 7
Independent Claim
194 words
A method of writing new data to disk in a redundant array of inexpensive disks, comprising: storing the new data in a cache memory; computing a parity block only for in-use data blocks of a group of data blocks in the disk array; attaching to the parity block an identifier indicating which data blocks of the group of data blocks are in use; choosing a destination data block for the new data; determining whether the destination block belongs to a group of free data blocks, and if so, setting the parity block using only the new data, and writing the set parity block and the new data to disk; otherwise, determining from the identifier whether the destination block is protected by the parity block; if so, using the new data, the destination block and the parity block to compute a new parity block reflecting the new data and writing the new parity block to cache and disk; if not, computing a new parity block reflecting the new data, writing the new parity block to cache and disk and updating the identifier to indicate that the destination block is now protected by the parity block.
Claim 8
Independent Claim
194 words
A method of writing new data to disk in a redundant array of inexpensive disks, comprising: storing the new data in a cache memory; computing a parity block only for in-use data blocks of a group of data blocks in the disk array; attaching to the parity block an identifier indicating which data blocks of the group of data blocks are in use; choosing a destination data block for the new data; determining whether the destination block belongs to a group of free data blocks, and if so, setting the parity block using only the new data, and writing the set parity block and the new data to disk; otherwise, determining from the identifier whether the destination block is protected by the parity block; if so, using the new data, the destination block and the parity block to compute a new parity block reflecting the new data and writing the new parity block to cache and disk; if not, computing a new parity block reflecting the new data, writing the new parity block to cache and disk and updating the identifier to indicate that the destination block is now protected by the parity block.
Claim 9
Dependent Claim
45 words
The method of claim 6, wherein if the destination block is protected by the parity block and if the contents of the destination block are not stored in cache, reading the contents of the destination block from disk prior to computing the new parity block.
Claim 10
Dependent Claim
30 words
The method of claim 7, wherein the parity block and each of the blocks in the group of data blocks are stored on a different disk in the disk array.
Claim 11
Dependent Claim
37 words
The method according to claim 6, wherein if the parity block is not stored in cache, reading the parity block and the identifier from disk prior to the step of determining whether the destination block is protected.
Claim 12
Dependent Claim
22 words
The method of claim 6, wherein the new parity block is computed by XORing the new data block and the parity block.
Claim 13
Independent Claim
97 words
A method of accounting for unused data blocks in a redundant array of inexpensive disks, comprising: computing a parity block for in-use data blocks in a group of data blocks stored on the disks; attaching to the parity block an identifier indicating which blocks of the group are the in-use data blocks; when a block is to be reclassified from in-use to unused, computing a new parity block using the parity block and the data in the block to be reclassified, and updating the identifier to indicate that the block to be reclassified is not in use.
Claim 14
Independent Claim
97 words
A method of accounting for unused data blocks in a redundant array of inexpensive disks, comprising: computing a parity block for in-use data blocks in a group of data blocks stored on the disks; attaching to the parity block an identifier indicating which blocks of the group are the in-use data blocks; when a block is to be reclassified from in-use to unused, computing a new parity block using the parity block and the data in the block to be reclassified, and updating the identifier to indicate that the block to be reclassified is not in use.
Claim 15
Dependent Claim
47 words
The method according to claim 11, wherein the array has an associated cache memory, and wherein if the parity block and identifier are not stored in the cache memory, reading the parity block and identifier from disk prior to the step of computing a new parity block.
Claim 16
Dependent Claim
48 words
The method according to claim 11, wherein the array has an associated cache memory, and if the data block to be reclassified is not stored in the cache memory, reading the data block to be reclassified from disk prior to the step of computing a new parity block.
Claim 17
Dependent Claim
60 words
The method according to claim 11, wherein the identifier comprises a number of bits equal to the number of data blocks in the group, each bit corresponding to a different one of the data blocks in the group, and wherein the step of updating the identifier comprises changing the state of the bit corresponding to the block to be reclassified.
Claim 18
Dependent Claim
28 words
The method according to claim 11, wherein the parity block and each of the data blocks in the group are stored on a different disk in the array.
Claim 19
Dependent Claim
29 words
The method according to claim 11, wherein the step of computing a new parity block comprises XORing the parity block and the data in the block to be reclassified.
References Cited (Backward Citations)
US4419725A
Cited
US5233618A
Cited
US5124987A
Cited
EP0481759A2
Cited
US5359611A
Cited
US5274799A
Cited
US5373512A
Cited
US5333305A
Cited
WO1993013478A1
Cited
US5341381A
Cited
US5410667A
Cited
EP0569755A1
Cited
US5309451A
Cited
US5315602A
Cited
EP0584804A2
Cited
US5392244A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-28 | 1999-11-27 | 2000-05-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-28 | 2003-11-27 | 2004-05-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-28 | 2007-11-27 | 2008-05-28 | $7700.00 | Window Closed / Lapsed |