US4761785A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parity spreading to enhance storage access
Assignee: International Business Machines Corp
•
Filing: 1986-06-12
•
Granted: 1988-08-02
•
Expires: 2006-06-12
Abstract
Abstract A storage management mechanism distributes parity blocks corresponding to multiple data blocks substantially equally among a set of storage devices. N storage units in a set are divided into a multiple of equally sized address blocks, each containing a plurality of records. Blocks from each storage unit having the same address ranges form a stripe of blocks. Each stripe has a block on one storage device containing parity for the remaining blocks of the stripe. Further stripes also have parity blocks, which are distributed on different storage units. Parity updating activity associated with every change to a data record is therefore distributed over the different storage units, enhancing access characteristics of the set of storage devices. The parity updating activity also includes the use of an independent version number stored with each data record and corresponding version numbers stored with the parity record. Each time a data record is changed, its version number is incremented and the corresponding version number in the parity record is incremented with the parity record update.
Inventors
- 👤 Brian E. Clark
- 👤 Francis D. Lawlor
- 👤 Werner E. Schmidt-Stumpf
- 👤 Terrence J. Stewart
- 👤 George D. Timms, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 16:20
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F11/14; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1833; G06F2211/00; G06F2211/10; G06F2211/1002; G06F2211/104
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
118 words
A data protection mechanism for a computer system having multiple independently accessible storage devices which store blocks of data, the data protection mechanism comprising: generator means for generating parity blocks as a function of sets of data blocks, said data blocks in a set corresponding to one parity block being stored on different storage devices; storage management means for managing the storage of data blocks and parity blocks onto the storage devices; and spreading means coupled to the storage management means for identifying a storage device to the storage management means on which each parity block is to be stored such that no one storage device contains the parity blocks for all of the groups of data blocks.
Claim 2
Dependent Claim
118 words
A data protection mechanism for a computer system having multiple independently accessible storage devices which store blocks of data, the data protection mechanism comprising: generator means for generating parity blocks as a function of sets of data blocks, said data blocks in a set corresponding to one parity block being stored on different storage devices; storage management means for managing the storage of data blocks and parity blocks onto the storage devices; and spreading means coupled to the storage management means for identifying a storage device to the storage management means on which each parity block is to be stored such that no one storage device contains the parity blocks for all of the groups of data blocks.
Claim 3
Dependent Claim
20 words
The data protection mechanism of claim 1 wherein the spreading means substantially uniformly distributes the parity blocks to storage devices.
Claim 4
Dependent Claim
20 words
The data protection mechanism of claim 2 wherein the spreading means distributes the parity blocks in a round robin manner.
Claim 5
Dependent Claim
33 words
The data protection mechanism of claim 1 wherein each data block in a set, and its corresponding parity block form a stripe of the same address ranges of each of the storage devices.
Claim 6
Dependent Claim
22 words
The data protection mechanism of claim 4 wherein at least one stripe of same addresses comprises data blocks without a parity block.
Claim 7
Dependent Claim
30 words
The data protection mechanism of claim 4 wherein there are at least as many stripes as there are blocks of data in a group plus one for the parity block.
Claim 8
Dependent Claim
28 words
The data protection mechanism of claim 4 wherein the size of the address range is at least as large as the largest system allocatable contiguous piece of storage.
Claim 9
Dependent Claim
16 words
The data protection mechanism of claim 1 wherein each storage device has the same address size.
Claim 10
Dependent Claim
16 words
The data protection mechanism of claim 1 wherein a set comprises at least three storage devices.
Claim 11
Dependent Claim
35 words
The data protection mechanism of claim 1 wherein the storage devices in a set are selected to minimize the number of storage devices affected by a failure of a single component of the computer system.
Claim 12
Dependent Claim
53 words
The data protection mechanism of claim 1 wherein a block comprises a plurality of predetermined sized records, the mechanism further comprising version generator means for providing independent version numbers to data records having the same address in a set and corresponding version numbers to the parity record covering such set of data records.
Claim 13
Dependent Claim
35 words
The data protection mechanism of claim 11 wherein the version numbers comprise counters, and the version generator means increments the counter in a revised data record and increments the corresponding counter in the parity record.
Claim 14
Dependent Claim
33 words
The data protection mechanism of claim 12 and further comprising data recovery means for recovering records lost on a failed storage device by combining the remaining records in the set of storage devices.
Claim 15
Dependent Claim
40 words
The data protection mechanism of claim 13 wherein the recovery of a lost record from a device is contingent on each remaining record in the one set of records having version numbers matching the versions numbers in the parity record.
Claim 16
Dependent Claim
51 words
The data protection mechanism of claim 1 and further comprising change mask means for producing a change mask for a parity record when a data record in the set is to be changed, said change mask being generated as a function of the original data record and the changed data record.
Claim 17
Independent Claim
105 words
A method of protecting data stored on a plurality of memory devices comprising: dividing addressable memory on each of said memory devices into blocks of memory such that each memory has the same number of blocks, the blocks on each memory having the same address range comprising a stripe; storing parity information for each stripe of memory blocks in a distributed manner across the memory devices to enhance the overall access rate of the memory devices; and changing the parity information for each stripe as a function of a change to a block in its corresponding stripe without reading all the blocks in the stripe.
Claim 18
Independent Claim
105 words
A method of protecting data stored on a plurality of memory devices comprising: dividing addressable memory on each of said memory devices into blocks of memory such that each memory has the same number of blocks, the blocks on each memory having the same address range comprising a stripe; storing parity information for each stripe of memory blocks in a distributed manner across the memory devices to enhance the overall access rate of the memory devices; and changing the parity information for each stripe as a function of a change to a block in its corresponding stripe without reading all the blocks in the stripe.
Claim 19
Dependent Claim
88 words
The method of claim 16 wherein the step of changing the parity information comprises the steps of: reading the data to be changed; making a copy of the data to be changed; making the changes to the data; generating a change mask as a function of the copy of the data to be changed and the changed data; writing the changed data to memory; reading the corresponding parity data; applying the change mask to the parity data to update it; and writing the updated parity data to memory.
Claim 20
Dependent Claim
35 words
The method of claim 16 wherein the step of changing the parity information further comprises the step of generating a version number which is stored with both the block of data and the parity block.
Claim 21
Dependent Claim
108 words
A data protection mechanism for a computer system having multiple independently accessible storage devices which store records of data, the data protection mechanism comprising: generator means for generating parity records as a function of sets of data records, said data records in a set corresponding to one parity record, each of said data and parity records being stored on different storage devices; storage management means for managing the storage of data records and parity records onto the storage devices; and version generator means for providing independent version numbers to data records in a set and corresponding version numbers to the parity record covering such set of data records.
Claim 22
Dependent Claim
108 words
A data protection mechanism for a computer system having multiple independently accessible storage devices which store records of data, the data protection mechanism comprising: generator means for generating parity records as a function of sets of data records, said data records in a set corresponding to one parity record, each of said data and parity records being stored on different storage devices; storage management means for managing the storage of data records and parity records onto the storage devices; and version generator means for providing independent version numbers to data records in a set and corresponding version numbers to the parity record covering such set of data records.
Claim 23
Dependent Claim
41 words
The data protection mechanism of claim 19 wherein the version numbers comprise a 1 bit counter in the data records and a number of one bit counters in the parity record equal to the number of data records in the set.
Claim 24
Dependent Claim
36 words
The data protection mechanism of claim 19 wherein reconstruction of a record in a set is conditional upon the version numbers in the remaining records being consistent with the corresponding version numbers in the parity record.
Claim 25
Dependent Claim
49 words
The data protection mechanism of claim 19 wherein the version numbers comprise a multibit counter in the data records and a number of multibit counters in the parity record equal to the number of data records in the set, wherein said counters count in a predetermined sequence of values.
References Cited (Backward Citations)
US3387261A
Cited
US4092732A
Cited
US4335458A
Cited
US4433388A
Cited
US4653055A
Cited
US4842262A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-08-02 | 1992-02-01 | 1992-08-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-08-02 | 1996-02-01 | 1996-08-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-08-02 | 2000-02-01 | 2000-08-02 | $7700.00 | Window Closed / Lapsed |