Single-disk redundant array of independent disks (RAID)

• US 20060253730A1
• Filed: 05/09/2005
• Published: 11/09/2006
• Est. Priority Date: 05/09/2005
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Manasse, Mark Steven
• Application Number:
  US11/125,051
• Publication Number:
  US 20060253730A1
• Time in Patent Office: Days
• US Class Current: 714/6
• 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
• CPC Class Codes: G06F 2211/1092 Single disk raid, i.e. RAID with parity on a single disk

Abstract

The vulnerable interval between the occurrence of a localized or spot failure and the occurrence of a detectable disk failure is reduced by providing redundancy within a single disk. Sectors of the disk may be grouped into independent sets. Error-correcting or erasure-correcting codes may be applied across groups of sectors where the maximum number of failures prior to detectable disk failure is expected to be small. It is desirable to place all sectors in adjacent tracks in different redundancy groups. This provides a lower bound on the number of redundancy groups needed.

Claims

1. An erasure correction method comprising:

determining a plurality of erasure groups on a single disk, each erasure group comprising a plurality of data values and erasure codes; and

computing checksums of the data values of the erasure groups.

2. The method of claim 1, further comprising storing the checksums in storage as erasure correction values.

3. The method of claim 1, further comprising maintaining the checksums as the data values are updated.

4. The method of claim 3, wherein maintaining the checksums comprises storing the checksums in nonvolatile memory.

5. The method of claim 3, further comprising detecting an error at a location on the disk.

6. The method of claim 5, further comprising correcting the error by reconstructing the value of the location on the disk using an erasure code in the erasure group corresponding to location on the disk.

7. The method of claim 6, wherein correcting the error comprises using an error correction technique corresponding to RAID-5 parity encoding.

8. The method of claim 7, wherein correcting the error comprises reading the values of the erasure group except for the failed value, exclusive or'"'"'ing the values, and computing a check value.

9. The method of claim 6, wherein correcting the error comprises using an error correction technique corresponding to Reed-Solomon encoding.

10. A method for reducing redundancy in a storage system, comprising:

grouping a plurality of sectors of a single disk into independent sets; and

applying erasure-correcting codes across the sets of sectors.

11. The method of claim 10, wherein grouping the sectors comprises placing the sectors in adjacent tracks in different ones of the independent sets.

12. The method of claim 10, further comprising reading the disk, and using checksum values to reduce the probability of undetected read errors.

13. The method of claim 10, further comprising storing redundancy blocks of data in non-volatile memory.

14. An erasure correction system comprising:

a processor for determining a plurality of erasure groups on a single disk, each erasure group comprising a plurality of data values and erasure codes, and for computing checksums of the data values of the erasure groups; and

a storage device for storing the checksums in storage as erasure correction values.

15. The system of claim 14, wherein the storage device comprises nonvolatile memory.

16. The system of claim 15, wherein the storage device maintains the checksums as the data values are updated.

17. The system of claim 16, wherein the processor is capable of detecting an error at a location on the disk.

18. The system of claim 17, wherein the processor is adapted to correct the error by reconstructing the value of the location on the disk using an erasure code in the erasure group corresponding to location on the disk.

19. The system of claim 18, wherein correcting the error comprises using an error correction technique corresponding to RAID-5 parity encoding or Reed-Solomon encoding.

20. The system of claim 18, wherein correcting the error comprises reading the values of the erasure group except for the failed value, exclusive or'"'"'ing the values, computing a check value, and storing the exclusive or'"'"'ed computation as the recovered value.