Detection and correction of block-level data corruption in fault-tolerant data-storage systems

• US 20080115017A1
• Filed: 10/31/2006
• Published: 05/15/2008
• Est. Priority Date: 10/31/2006
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Jacobson, Michael B.
• Granted Patent: US 8,145,941 B2
• Time in Patent Office: Days
• US Class Current: 714/710
• 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/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

Various embodiments of the present invention provide fault-tolerant, redundancy-based data-storage systems that rely on disk-controller-implemented error detection and error correction, at the disk-block level, and RAID-controller-implemented data-redundancy methods, at the disk and disk-stripe level, in order to provide comprehensive, efficient, and system-wide error detection and error correction. Embodiments of the present invention use disk-level and stripe-level data redundancy to provide error detection and error correction for stored data objects, obviating the need for certain costly, intermediate levels of error detection and error correction commonly employed in currently available fault-tolerant, redundancy-based data-storage systems.

Claims

1. A data-storage system comprising:

a number of data-storage devices; and

at least one data-storage-system controller that maps logical-block device interfaces provided by the data-storage devices to a virtual logical-device interface,

employs a data-redundancy scheme to store sufficient redundant data within each stripe of each stored data object within the data-storage system, as two or more parity blocks, to recover data contained in at least two failed data-storage devices of a data-redundancy disk group, and

uses the data-redundancy scheme to monitor stored data objects for block-level data corruption.

2. The data-storage system of claim 1 wherein the number of data-storage devices is a number of magnetic disks that each provides a logical-block disk interface to accessing entities.

3. The data-storage system of claim 1 wherein the redundancy scheme is an erasure-coding-redundancy-based RAID scheme in which at least two parity blocks are generated and stored for each of a fixed-size group of data blocks that, together with the at least two parity blocks, comprise a stripe.

4. The data-storage system of claim 3 wherein the at least one data-storage-system controller uses the data-redundancy scheme to monitor stored data objects for block-level data corruption by:

iteratively,

for each stripe of each stored data object,

reading the stripe into memory,

recomputing the parity blocks in memory,

comparing the recomputed parity blocks to the parity blocks of the stripe store in memory, and

when the recomputed parity blocks do not match the parity blocks of the stripe,

handling a parity-block-match error.

5. The data-storage system of claim 4 wherein the at least one data-storage-system controller handles a parity-block-match error by:

when the parity-block-match error indicates that a single block of the stripe is corrupted,

locating the single corrupted block,

regenerating data for the corrupted block from remaining blocks of the stripe, and

rewriting the regenerated data back to a replacement block; and

when the parity-block-match error indicates that multiple blocks of the stripe are corrupted, flagging the stripe as corrupted.

6. The data-storage system of claim 5 wherein locating the single corrupted block further comprises computing a syndrome for the stripe and computing an error-locating polynomial from the syndrome.

7. The data-storage system of claim 5 wherein regenerating data for the corrupted block from remaining blocks of the stripe further includes computing the data for the corrupted block by matrix inversion from the remaining blocks in the stripe.

8. The data-storage system of claim 5 wherein locating the single corrupted block further comprises:

considering each block in the stripe in turn,

recomputing the stripe from all but the currently considered block of the stripe; and

when a parity check of the recomputed stripe succeeds, determining that the currently considered block is corrupted.

9. A method for monitoring stored data objects for block-level data corruption in a data-storage system that employs a data-redundancy scheme to store sufficient redundant data within each stripe of each stored data object within the data-storage system, as two or more parity blocks, to recover data contained in at least two failed data-storage devices of a data-redundancy disk group, the method comprising:

iteratively,

for each stripe of each stored data object,

reading the stripe into memory,

recomputing parity blocks of the stripe in memory,

comparing the recomputed parity blocks to the parity blocks of the stripe, and

when the recomputed parity blocks do not match the parity blocks of the stripe,

handling a parity-block-match error.

10. The method of claim 9 wherein the at least one data-storage-system controller handles a parity-block-match error by:

when the parity-block-match error indicates that a single block of the stripe is corrupted,

locating the single corrupted block,

regenerating data for the corrupted block from remaining blocks of the stripe, and

rewriting the regenerated data back to a replacement block; and

when the parity-block-match error indicates that multiple blocks of the stripe are corrupted, flagging the stripe as corrupted.

11. The method of claim 10 wherein locating the single corrupted block further comprises computing a syndrome for the stripe and computing an error-locating polynomial from the syndrome.

12. The method of claim 10 wherein regenerating data for the corrupted block from remaining blocks of the stripe further includes computing the data for the corrupted block by matrix inversion from the remaining blocks in the stripe.

13. The method of claim 10 wherein locating the single corrupted block further comprises:

considering each block in the stripe in turn,

recomputing the stripe from all but the currently considered block of the stripe; and

when a parity check of the recomputed stripe succeeds, determining that the currently considered block is corrupted.

14. Processor instructions stored in a computer readable memory that implement the method of claim 9.

15. Firmware instructions stored in a computer readable memory that implement the method of claim 9.