Method and system for calculating parity values for multi-dimensional RAID

• US 9,152,499 B1
• Filed: 10/09/2014
• Issued: 10/06/2015
• Est. Priority Date: 12/04/2013
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: DSSD, Inc. (Dell Technologies Inc.)
• Inventors: Mollov, Todor Ivanov, Bonwick, Jeffrey S.
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): Mehrmanesh, Elmira
• Application Number:
  US14/510,795
• Time in Patent Office: 362 Days
• Field of Search: 714/6.24
• US Class Current: 1/1
• 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/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method for calculating parity values including calculating a first set of parity values using datum stored in RAID Grid locations in a first PCB, where datum associated with the RAID Grid locations in the first PCB is obtained in a first order that is based on a Hilbert curve. The method further includes calculating a second set of parity values using datum stored in RAID Grid locations in a second PCB, where datum associated with the RAID Grid locations in the second PCB is obtained in a second order that is based on the Hilbert curve. The method further includes storing at least a portion of the first set of parity values and a second set of parity values in a cache, memory, or persistent storage, where each of the first parity values and second parity values is associated with a separate RAID Grid location in the RAID Grid.

Claims

1. A system comprising:

a memory, a cache, and a persistent storage; and

a processor that;

performs, using a first datum, a first plurality of parity value calculations to obtain a first plurality of parity values, wherein the first datum is associated with a first Redundant Array of Independent Disks (RAID) Grid location in a first parity calculation block (PCB) in a RAID Grid, wherein the RAID Grid comprises a first dimension and a second dimension, wherein at least one of the first plurality of parity values is associated with the first parity RAID Grid location in the first dimension and at least one of the first plurality of parity values is associated with a second parity RAID Grid location in the second dimension;

performs, using a second datum, a second plurality of parity value calculations to obtain a second plurality of parity values, wherein the second datum is associated with a second RAID Grid location in the first PCB;

performs, using a third datum and at least one selected from a group consisting of at least one of the first plurality of parity values and at least one of the second plurality of parity values, a third plurality of parity value calculations to obtain a third plurality of parity values, wherein the third datum is associated with a third RAID Grid location in the first PCB;

performs, using a fourth datum and at least one selected from a group consisting of at least one of the first plurality of parity values and at least one of the second plurality of parity values, a fourth plurality of parity value calculations to obtain a fourth plurality of parity values, wherein the fourth datum is associated with a fourth RAID Grid location in the first PCB; and

stores each of the fourth plurality of parity values in at least one selected from a group consisting of the cache, the memory, and the persistent storage, wherein each of the fourth plurality of parity values is associated with a separate RAID Grid location in the RAID Grid,

wherein the processor is operatively connected to the memory, the cache, and the persistent storage.

2. The system of claim 1, wherein the processor further:

after performing parity value calculations using data in all of the RAID Grid locations in the first PCB;

performs, using a fifth datum and at least one selected from a group consisting of at least one of the third plurality of parity values and at least one of the fourth plurality of parity values, a fifth plurality of parity value calculations to obtain a fifth plurality of parity values, wherein the fifth datum is associated with a fifth RAID Grid location in a second PCB in the RAID Grid.

3. The system of claim 1, wherein the processor further:

after performing parity value calculations using data in all of the RAID Grid locations in the first PCB;

performs, using a fifth datum, a fifth plurality of parity value calculations to obtain a fifth plurality of parity values, wherein the fifth datum is associated with a fifth RAID Grid location in the second PCB in the RAID Grid, and wherein the second PCB is adjacent to the first PCB.

4. The system of claim 1, wherein the persistent storage comprises solid state memory.

5. The system of claim 1, wherein the first plurality of parity values comprises at least one selected from a group consisting of a P parity value and a Q parity value.

6. The system of claim 1, wherein the first PCB comprises N RAID Grid locations in the first dimension and N RAID Grid locations in the second dimension, wherein N≧

2.

7. The system of claim 1, wherein the first PCB comprises N RAID Grid locations in the first dimension and M RAID Grid locations in the second dimension, wherein N≧

2, M≧

2, and N≠

M.

8. The system of claim 1, wherein the RAID Grid comprises a plurality of PCBs, wherein the first PCB is one of the plurality of PCBs.

9. The system of claim 1, wherein the RAID Grid comprises N PCBs in the first dimension and N PCBs the second dimension, wherein N≧

2.

10. The system of claim 1, wherein the RAID Grid comprises N PCBs in the first dimension and M PCBs the second dimension, wherein N≧

2, M≧

2, and N≠

M.

11. A system, comprising:

a memory, a cache, and a persistent storage; and

a processor that;

calculates a first set of parity values for a RAID Grid using datum stored in each of a plurality of RAID Grid locations in a first parity calculation block (PCB), wherein the datum associated with each of the plurality of RAID Grid locations in the first PCB is obtained in a first order and wherein the first order is based on a Hilbert curve wherein, based on the first order, a first parity value is calculated using a first datum in a first RAID Grid location in the first PCB, and a second parity value is calculated using a second datum in a last RAID Grid location in the first PCB, wherein the last RAID Grid location is adjacent to the first RAID Grid location, wherein the first PCB comprises N RAID Grid locations, wherein N≧

4;

calculates a second set of parity values for the RAID Grid using datum stored in each of a plurality of RAID Grid locations in a second PCB, wherein the datum associated with each of the plurality of RAID Grid locations in the second PCB is obtained in a second order and wherein the second order is based on the Hilbert curve; and

stores at least a portion of the first set of parity values and at least a portion of the second set of parity values in at least one selected from a group consisting of the cache, the memory, and the persistent storage, wherein each of the first set of parity values and the second set of parity values is associated with a separate RAID Grid location in the RAID Grid,

wherein the processor is operatively connected to the memory, the cache, and the persistent storage.

12. The system of claim 11, wherein the RAID Grid comprises a plurality of PCBs, wherein the first PCB is one of the plurality of PCBs and the second PCB is one of the plurality of PCBs.

13. The system of claim 12, wherein the plurality of PCBs are traversed in a third order, wherein the third order is based on the Hilbert curve.

14. The system of claim 12, wherein the plurality of PCBs are traversed in a third order, wherein the third order has the same pattern as the first order.

15. The system of claim 11, wherein the first RAID Grid location is adjacent to the last RAID Grid location when the last RAID Grid location is in one selected from a group consisting of:

in the same row as the first RAID Grid location and in the same column as the first RAID Grid location.

16. The system of claim 11, wherein a size of the cache is less than a size of the RAID Grid.

17. A system, comprising:

a memory, a cache, and a persistent storage; and

a processor that;

calculates a first set of parity values for a RAID Grid using datum stored in each of a plurality of RAID Grid locations in a first parity calculation block (PCB), wherein the datum associated with each of the plurality of RAID Grid locations in the first PCB is obtained in a first order, wherein the first order is based on a Hilbert curve, wherein the first PCB comprises N RAID Grid locations in a first dimension and N RAID Grid locations in a second dimension, wherein N≧

2, wherein the cache is configured to store one selected from a group consisting of only 2N+1 values and only 4N+1 values, wherein each of the values is one selected from a group consisting of datum and a parity value;

calculates a second set of parity values for the RAID Grid using datum stored in each of a plurality of RAID Grid locations in a second PCB, wherein the datum associated with each of the plurality of RAID Grid locations in the second PCB is obtained in a second order and wherein the second order is based on the Hilbert curve; and

stores at least a portion of the first set of parity values and at least a portion of the second set of parity values in at least one selected from a group consisting of the cache, the memory, and the persistent storage, wherein each of the first set of parity values and the second set of parity values is associated with a separate RAID Grid location in the RAID Grid.

18. The system of claim 17, further comprising:

a field programmable gate array (FPGA), operatively connected to the processor, that;

calculates at least one of the first set of parity values.

19. The system of claim 17, wherein the persistent storage comprises flash memory.

20. The system of claim 17, wherein the processor is located within a RAID controller.