Raid-6 computation system and method

• US 8,037,391 B1
• Filed: 05/22/2009
• Issued: 10/11/2011
• Est. Priority Date: 05/22/2009
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Saxena, Nirmal Raj, Jung, Cyndi, Currid, Andrew, Overby, Mark A.
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US12/471,289
• Time in Patent Office: 872 Days
• Field of Search: 714/759, 714/758
• US Class Current: 714/759
• 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/1052 RAID padding, i.e. completing a redundancy group with dummy data
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

One embodiment of the present invention sets forth a technique for performing RAID-6 computations using simple arithmetic functions and two-dimensional table lookup operations. Four lookup tables are computed and saved prior to normal operation of a RAID-6 disk array. During normal operation of the RAID-6 disk array, all RAID-6 related computations may be performed using a small set of simple arithmetic operations and a set of lookup operations to three of the four previously saved lookup tables. Greater computational efficiency is gained by reducing the RAID-6 computations to simple operations that are performed efficiently on a typical central processing unit or graphics processing unit.

Claims

1. A computer-implemented method for computing erasure codes for a redundant array of independent disks (RAID), the method comprising:

storing user data associated with a RAID stripe that is defined by a data block common to each disk in the redundant array, wherein, for each byte offset within the data block, user data associated with only N−

2 disks is stored, N being the number of disks in the redundant array;

for each byte offset within the data block, computing a first erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a first exclusive-or operation based on the byte offset within the data block;

for each byte offset within the data block, computing a second erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a second exclusive-or operation based on a look-up table value, wherein, each disk in the redundant array is associated with a respective disk drive number, and the respective disk drive number is input as an index to the look-up table to generate the look-up table value; and

for each byte offset within the data block, storing the first erasure code and the second erasure code along with the user data associated with the N−

2 disks.

2. The method of claim 1, wherein, for each byte offset within the data block, the index is the respective disk drive number of a first disk in the redundant array and an additional index that is input to the look-up table is a byte value stored on the first disk at the byte offset within the data block.

3. The method of claim 1, wherein the look-up table value is included in a look-up table that stores the results of Galois operations performed on a plurality of eight-bit numbers, wherein a first eight-bit number identifies a disk in the redundant array, and a second eight-bit number comprises a byte of user data stored on the identified disk.

4. The method of claim 3, wherein the look-up table is stored in memory local to a graphics processing unit.

6. The method of claim 3, wherein the look-up table and the user data are stored in system memory.

7. The method of claim 1, wherein the redundant array is configured as a RAID 6 RAID array.

8. The method of claim 1, wherein the first erasure code and the second erasure code are used to recover user data lost when any one disk in the redundant array fails or when any two disks in the redundant array fail.

9. The method of claim 1, further comprising the step of generating a first recovery code value by extracting one or more values from a second look-up table based on the first erasure code and valid stored user data.

10. The method of claim 9, further comprising the step of recovering data lost on a first failed disk in the redundant array via the first recovery code.

11. The method of claim 9, further comprising the step of generating a second recovery code value by extracting one or more values from a third look-up table based on the first recovery code, the second erasure code, and the valid stored user data.

12. The method of claim 11, further comprising the steps of recovering data lost on a first failed disk in the redundant array via the first recovery code, and recovering data lost on a second failed disk in the redundant array via the second recovery code.

5. The method 4, wherein the user data is stored in the memory local to the graphics processing unit or in a frame buffer memory coupled to the graphics processing unit.

13. A computer-readable medium including instructions that, when executed by a processing unit, cause the processing unit to compute erasure codes for a redundant array of independent disks (RAID), by performing the steps of:

storing user data associated with a RAID stripe that is defined by a data block common to each disk in the redundant array, wherein, for each byte offset within the data block, user data associated with only N−

2 disks is stored, N being the number of disks in the redundant array;

for each byte offset within the data block, computing a first erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a first exclusive-or operation based on the byte offset within the data block;

for each byte offset within the data block, computing a second erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a second exclusive-or operation based on a look-up table value wherein, each disk in the redundant array is associated with a respective disk drive number, and the respective disk drive number is input as an index to the look-up table to generate the look-up table value; and

for each byte offset within the data block, storing the first erasure code and the second erasure code along with the user data associated with the N−

2 disks.

14. The computer-readable medium of claim 13, wherein, for each byte offset within the data block, the index is the respective disk drive number of a first disk in the redundant array and an additional index that is input to the look-up table is a byte value stored on the first disk at the byte offset within the data block.

15. The computer-readable medium of claim 13, wherein the look-up table value is included in a look-up table that stores the results of Galois operations performed on a plurality of eight-bit numbers, wherein a first eight-bit number identifies a disk in the redundant array, and a second eight-bit number comprises a byte of user data stored on the identified disk.

16. The computer-readable medium of claim 15, wherein the look-up table is stored in memory local to a graphics processing unit.

18. The computer-readable medium of claim 13, wherein the first erasure code and the second erasure code are used to recover user data lost when any one disk in the redundant array fails or when any two disks in the redundant array fail.

19. The computer-readable medium of claim 13, further comprising the steps of generating a first recovery code value by extracting one or more values from a second look-up table based on the first erasure code and valid stored user data, and/or generating a second recovery code value by extracting one or more values from a third look-up table based on the first recovery code, the second erasure code, and the valid stored user data.

20. The computer-readable medium of claim 19, further comprising the step of recovering data lost on a first failed disk in the redundant array via the first recovery code, or recovering data lost on a first failed disk in the redundant array via the first recovery code, and recovering data lost on a second failed disk in the redundant array via the second recovery code.

17. The computer-readable medium 16, wherein the user data is stored in the memory local to the graphics processing unit or in a frame buffer memory coupled to the graphics processing unit.

21. A computer system, comprising:

a processing unit;

a system memory coupled to the processing unit; and

a redundant array of independent disks (RAID) coupled to the processing unit and the system memory,

wherein the processing unit is configured to compute erasure codes for the redundant array by performing the steps of;

storing user data associated with a RAID stripe that is defined by a data block common to each disk in the redundant array, wherein, for each byte offset within the data block, user data associated with only N−

2 disks is stored, N being the number of disks in the redundant array,

for each byte offset within the data block, computing a first erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a first exclusive-or operation based on the byte offset within the data block,

for each byte offset within the data block, computing a second erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a second exclusive-or operation based on a look-up table value, wherein, each disk in the redundant array is associated with a respective disk drive number, and the respective disk drive number is input as an index to the look-up table to generate the look-up table value, and

for each byte offset within the data block, storing the first erasure code and the second erasure code along with the user data associated with the N−

2 disks.

22. The computer system of claim 21, wherein the processing unit comprises a central processing unit or a graphics processing unit.