Erasure Coding Technique For Scalable And Fault Tolerant Storage System

• US 20070245083A1
• Filed: 04/04/2007
• Published: 10/18/2007
• Est. Priority Date: 04/04/2006
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Permabit Technology Corporation (International Business Machines Corporation)
• Inventors: Jaskiewicz, Thomas, Margolus, Norman
• Granted Patent: US 7,979,771 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2211/1023 Different size disks, i.e. non uniform size of disks in RAID systems with parity
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

A method for encoding a block of data to allow it to be stored or transmitted correctly in the face of accidental or deliberate modifications, the method including constructing a number n greater than one of original components, each of which is derived from the block and each of which is smaller than the block, and combining original components to construct a number m greater than one of new components, wherein each of the new components is smaller than the sum of the sizes of the original components combined to produce it, wherein the block can be reconstructed from any set of n different components selected from the original components and new components, and wherein a set of n different components selected from the original components and new components contains more redundant information about the block than the set of n original components.

Claims

1. A method for encoding a block of data to allow it to be stored or transmitted correctly in the face of accidental or deliberate modifications, the method comprising:

constructing a number n greater than one of original components, each of which is derived from the block and each of which is smaller than the block; and

combining original components to construct a number m greater than one of new components;

wherein each of the new components is smaller than the sum of the sizes of the original components combined to produce it;

wherein the block can be reconstructed from any set of n different components selected from the original components and new components; and

wherein a set of n different components selected from the original components and new components contains more redundant information about the block than the set of n original components.

2. The method of claim 1 wherein the combining further comprises:

scaling original components to determine scaled original components; and

accumulating scaled original components to determine a one of the m new components;

wherein scaling comprises determining from a one of the original components a one of the scaled original components in a manner that allows the one of the original components to be determined from the one of the scaled original components; and

wherein accumulating comprises combining portions of the one of the original components with corresponding portions of another component derived from original components.

3. The method of claim 2 wherein the scaling step comprises performing a non-cyclic shift operation.

4. The method of claim 3 wherein the non-cyclic shift operation is implemented as a memory addressing operation.

5. The method of claim 3 wherein a shift-amount of the non-cyclic shift operation is determined, at least in part, by a multiplication modulo a prime number.

6. The method of claim 2 wherein the scaling step comprises multiplying an integer, which has a binary representation that comprises the bits of the one of the original components or bits from which the one can be determined, by a scaling factor.

7. The method of claim 2 wherein combining portions with corresponding portions in the accumulating step comprises performing a dyadic operation with a first operand taken from the portions and a second operand taken from the corresponding portions.

8. The method of claim 2 wherein the other component derived from original components is a scaled original component.

9. The method of claim 1 wherein at least one of the m new components is larger than at least one of the n original components.

10. The method of claim 1 wherein the sum of the sizes of each of the original components plus the sum of the sizes of each of the new components is less than one percent greater than (1+m/n) times the size of the block.

11. The method of claim 1 wherein a number m of new components are constructed from a fixed set of n original components, wherein m is not chosen until the construction of new components ends, and there is no upper bound on the size of m.

12. The method claim 1 wherein each of the original components and new components is preferentially stored on a storage subsystem that is different than that on which any other of the original components and new components is stored.

13. The method of claim 12 wherein the storage subsystem comprises at least one disk drive.

14. The method of claim 1 wherein the combining step further comprises:

determining an integer from a one of the original components in a manner which allows the one of the original components to be determined from the integer;

scaling the integer to produce a sealed integer, wherein sealing comprises applying a multiplication-like operation to two operands, with a first of the two operands being the integer and a second of the two operands being a scaling factor;

accumulating sealed integers to determine a one of the m new components, wherein the accumulating comprises applying a dyadic operation to combine the scaled integer with another integer derived from original components; and

wherein the multiplication-like operation is the same as integer multiplication whenever one of its two operands is positive and a power of two.

15. The method of claim 7 or 14 wherein the dyadic operation is addition.

16. The method of claim 7 or 14 wherein the dyadic operation is bitwise XOR.

17. The method of claim 6 or 14 wherein the scaling factor is a power of two with an exponent determined by multiplication modulo a prime number.