Convolution-Encoded RAID with Trellis-Decode-Rebuild

• US 20080209304A1
• Filed: 05/05/2008
• Published: 08/28/2008
• Est. Priority Date: 05/09/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haustein, Nils, Klein, Craig A., Winarski, Daniel J.
• Granted Patent: US 8,245,113 B2
• Time in Patent Office: Days
• US Class Current: 714/763
• 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 system, comprising:

a plurality of storage devices;

a trellis decoder coupled to said plurality of storage devices, said decoder adapted to process coded data received from said plurality of storage devices to produce decoded data, said coded data comprising error correction coded data produced by the convolution of present and past bits of information;

where said system is adapted to;

determine 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 system of claim 1, where said system is further adapted to:

measure a quantity of errors in said decoded data;

compare said quantity of errors to an error limit for 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 system of claim 1, where said system is further adapted to:

receive 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 system 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 a plurality of storage devices has two or more consecutive words.

5. The system 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 more than one of said n bits of each said word.

6. The system of claim 1, further comprising:

a metadata controller adapted to process metadata associated with said coded data, said metadata comprising storage location information specifying a storage location for said coded data

7. The system of claim 1, further comprising:

a metadata controller adapted to process metadata associated with said coded data, said metadata comprising encoder information specifying the type of encoding for said coded data.

8. A storage area network comprising:

a least one host computer;

a plurality of storage devices;

a trellis decoder coupled to said plurality of storage devices, said decoder adapted to process coded data received from said plurality of storage devices to produce decoded data, said coded data comprising error correction coded data produced by the convolution of present and past bits of information;

where said system is adapted to;

determine 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 storage area network of claim 8, where said network is further adapted to:

measure a quantity of errors in said decoded data;

compare 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 storage area network of claim 8, where said system is further adapted to:

receive 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 storage area network of claim 8, 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 a plurality of storage devices has two or more consecutive words.

12. The storage area network of claim 8, 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 more than one of said n bits of each said word.

13. The storage area network of claim 8, wherein said plurality of storage devices are disbursed to separate physical locations.

14. (canceled)

15. (canceled)

16. (canceled)

17. (canceled)

18. (canceled)

19. (canceled)

20. (canceled)

21. A computer program product encoded in an information storage medium, wherein the computer readable program when executed on a computer causes said computer to:

receive coded data from a plurality of storage devices;

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

determine if there is a failed storage device;

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

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

process said decoded data to produce said reconstructed data; and

store said reconstructed data on said allocated storage space.

22. The computer program product of claim 21, wherein the computer readable program when executed on said computer Luther causes said computer to:

measure a quantity of errors in said decoded data;

compare 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, identify said storage device as said failed storage device.

23. The computer program product of claim 21, wherein the computer readable program when executed on said computer further causes said computer to:

receive 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, identify said storage device as said failed storage device.

24. The computer program product of claim 21, wherein the computer readable program when executed on said computer further causes said computer to:

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

25. The computer program product of claim 21, wherein the computer readable program when executed on said computer further causes said computer to:

charge a customer a fee for said allocating storage space.

26. The computer program product of claim 21, wherein the computer readable program when executed on said computer further causes said computer to:

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

27. The computer program product of claim 21, 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.

28. (canceled)

29. (canceled)

30. (canceled)

31. (canceled)

32. (canceled)

33. (canceled)