Convolution-encoded raid with trellis-decode-rebuild

• US 7,370,261 B2
• Filed: 05/09/2005
• Issued: 05/06/2008
• Est. Priority Date: 05/09/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haustein, Nils, Klein, Craig A., Winarski, Daniel J.
• Primary Examiner(s): Chase; Shelly A.
• Application Number:
  US11/125,288
• Publication Number:
  US 20060253767A1
• Time in Patent Office: 1,093 Days
• Field of Search: 714/770
• US Class Current: 714/770
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks

Abstract

A Redundant Array of Independent Devices uses convolution encoding to provide redundancy of the striped data written to the devices. No parity is utilized in the convolution encoding process. Trellis decoding is used for both reading the data from the RAID and for rebuilding missing encoded data from one or more failed devices, based on a minimal, and preferably zero, Hamming distance for selecting the connected path through the trellis diagram.

Claims

1. A method, comprising:

receiving coded data from a plurality of storage devices;

producing decoded data by decoding said coded data using a trellis decoder;

determining if there is a failed storage device;

in response to determining that there is a failed storage device;

allocating storage space for the storage of reconstructed data, said reconstructed data comprising coded data previously stored on said failed storage device;

processing said decoded data to produce said reconstructed data; and

storing said reconstructed data on said allocated storage space.

2. The method of claim 1, where said determining step further comprises:

measuring a quantity of errors in said decoded data;

comparing said quantity of errors to an error limit for each of said plurality of storage devices; and

in response to said quantity of errors exceeding said error limit for a storage device, identifying said storage device as said failed storage device.

3. The method of claim 1, where said determining step further comprises:

receiving self monitoring analysis and reporting technology information from said plurality of storage devices; and

in response to said self monitoring analysis and reporting technology information indicating a failure for a storage device, identifying said storage device as said failed storage device.

4. The method of claim 1, further comprising:

processing metadata associated with said coded data, said metadata comprising encoder information specifying the type of encoding for said coded data.

5. The method of claim 1, further comprising:

charging a customer a fee for said allocating storage space.

6. The method of claim 1, further comprising:

charging a customer a fee for said storing said reconstructed data on said allocated storage space.

7. The method of claim 1, wherein said coded data comprises one or more words, each said word comprising n bits, where n is greater than zero, each said word produced from a convolution encoder processing a portion of said information and where none of said plurality of storage devices has two or more consecutive words.

8. A method for deploying computing infrastructure, comprising integrating computer readable code into a system, wherein the code in combination with said system is capable of performing the following:

receiving coded data from a plurality of storage devices;

producing decoded data by decoding said coded data using a trellis decoder;

determining if there is a failed storage device;

in response to determining that there is a failed storage device;

allocating storage space for the storage of reconstructed data, said reconstructed data comprising coded data previously stored on said failed storage device;

processing said decoded data to produce said reconstructed data; and

storing said reconstructed data on said allocated storage space.

9. The method of claim 8, where said determining step further comprises:

measuring a quantity of errors in said decoded data;

comparing said quantity of errors to an error limit for each of said plurality of storage devices; and

in response to said quantity of errors exceeding said error limit for a storage device,

identifying said storage device as said failed storage device.

10. The method of claim 8, where said determining step further comprises:

receiving self monitoring analysis and reporting technology information from said plurality of storage devices; and

in response to said self monitoring analysis and reporting technology information indicating a failure for a storage device, identifying said storage device as said failed storage device.

11. The method of claim 8, further comprising:

processing metadata associated with said coded data, said metadata comprising encoder information specifying the type of encoding for said coded data.

12. The method of claim 8, further comprising:

charging a customer a fee for said allocating storage space.

13. The method of claim 8, further comprising:

charging a customer a fee for said storing said reconstructed data on said allocated storage space.