Redundant storage of computer data

• US 20060282716A1
• Filed: 05/24/2005
• Published: 12/14/2006
• Est. Priority Date: 05/24/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pomerantz, Ori
• Granted Patent: US 7,360,143 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/108 RAIT, i.e. RAID on tape drive

Abstract

Redundant storage of computer data including encoding N data values through M linear expressions into M encoded data values and storing each encoded data value separately on one of M redundant storage devices where M is greater than N and none of the linear expressions is linearly dependent upon any group of N−1 of the M linear expression.

Claims

1. A method for redundant storage of computer data, the method comprising:

encoding N data values through M linear expressions into M encoded data values; and

storing each encoded data value separately on one of M redundant storage devices;

wherein M is greater than N and none of the linear expressions is linearly dependent upon any group of N−

1 of the M linear expressions.

2. The method of claim 1 wherein one of the M linear expressions e* is linearly dependent upon a group of N−

1 of the M linear expressions if;

$e^{*}=\underset{i=1}{\overset{n-1}{\sum <br><br>}}<br><br>a_i<br><br>e_i,$

wherein a_i is any linear coefficient, e_i is one of the M linear expressions, and N is the number of data values to be encoded.

3. The method of claim 1 further comprising:

testing each of the M linear expressions for linear dependence upon each group of N−

1 of the M linear expressions; and

excluding from the M linear expressions any expression found to be linearly dependent upon any group of N−

1 of the M linear expressions.

4. The method of claim 1 wherein encoding N data values through M linear expressions into M encoded data values further comprises calculating values for the M linear expressions with Galois arithmetic.

5. The method of claim 1 wherein encoding data values further comprises encoding data values in units of four bits per value.

6. The method of claim 1 wherein storing further comprises storing by a redundant storage controller to a redundant storage device in a computer coupled for data communications through a network to the redundant storage controller.

7. The method of claim 1 further comprising receiving in a redundant storage controller from a communicatively coupled computer an indication of a portion of unused storage space on a redundant storage device.

8. The method of claim 1 wherein storing further comprises writing the encoded data to an unused portion of storage media on a redundant storage device, the redundant storage device controlled by an operating system, the writing implemented without recording in the operating system that the portion of storage media now has encoded data stored upon the portion of storage media.

9. The method of claim 1 wherein storing further comprises:

writing the encoded data to an unused portion of storage media on a redundant storage device that is controlled by an operating system, including recording in the operating system that the portion of storage media is now in use for storage of encoded data;

monitoring the amount of free storage space on the redundant storage device; and

reducing encoded storage on the redundant storage device when free storage space is less than a predetermined threshold amount.

10. A system for redundant storage of computer data, the system comprising a computer processor and a computer memory operatively coupled to the computer processor, the computer memory having disposed within it computer program instructions capable of:

encoding N data values through M linear expressions into M encoded data values; and

storing each encoded data value separately on one of M redundant storage devices;

wherein M is greater than N and none of the linear expressions is linearly dependent upon any group of N−

1 of the M linear expressions.

11. The system of claim 10 wherein storing further comprises storing by a redundant storage controller to a redundant storage device in a computer coupled for data communications through a network to the redundant storage controller.

12. The system of claim 10 further comprising computer program instructions capable of receiving in a redundant storage controller from a communicatively coupled computer an indication of a portion of unused storage space on a redundant storage device.

13. The system of claim 10 wherein storing further comprises writing the encoded data to an unused portion of storage media on a redundant storage device, the redundant storage device controlled by an operating system, the writing implemented without recording in the operating system that the portion of storage media now has encoded data stored upon the portion of storage media.

14. The system of claim 10 wherein storing further comprises:

writing the encoded data to an unused portion of storage media on a redundant storage device that is controlled by an operating system, including recording in the operating system that the portion of storage media is now in use for storage of encoded data;

monitoring the amount of free storage space on the redundant storage device; and

reducing encoded storage on the redundant storage device when free storage space is less than a predetermined threshold amount.

15. A computer program product for redundant storage of computer data, the computer program product disposed upon a signal bearing medium, the computer program product comprising computer program instructions capable of:

encoding N data values through M linear expressions into M encoded data values; and

storing each encoded data value separately on one of M redundant storage devices;

wherein M is greater than N and none of the linear expressions is linearly dependent upon any group of N−

1 of the M linear expressions.

16. The computer program product of claim 15 wherein the signal bearing medium comprises a recordable medium.

17. The computer program product of claim 15 wherein the signal bearing medium comprises a transmission medium.

18. The computer program product of claim 15 wherein encoding N data values through M linear expressions into M encoded data values further comprises calculating values for the M linear expressions with Galois arithmetic.

19. The computer program product of claim 15 wherein encoding data values further comprises encoding data values in units of four bits per value.

20. The computer program product of claim 15 wherein storing further comprises storing by a redundant storage controller to a redundant storage device in a computer coupled for data communications through a network to the redundant storage controller.