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

• US 8,924,776 B1
• Filed: 12/04/2013
• Issued: 12/30/2014
• 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: Bonwick, Jeffrey S., Mollov, Todor Ivanov
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): Mehrmanesh, Elmira
• Application Number:
  US14/096,708
• Time in Patent Office: 391 Days
• Field of Search: 714/6.24
• US Class Current: 714/6.24
• 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 method for calculating parity values, comprising:

performing, 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 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 a 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;

performing, 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;

performing, 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;

performing, 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

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

2. The method of claim 1, further comprising:

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

performing, 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 method of claim 1, further comprising:

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

performing, 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 a second PCB in the RAID Grid, and wherein the second PCB is adjacent to the first PCB.

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

5. The method 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 Q parity value.

6. The method 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 method 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 method 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 method 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 method 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 method for calculating parity values, comprising:

calculating 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;

calculating 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

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

12. The method 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 method 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 method 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 method 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 method of claim 11, wherein a size of the cache is less than a size of the RAID Grid.

17. A method for calculating parity values, comprising:

calculating 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 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 a cache is configured to store only 2N+1 values, wherein each of the 2N+1 values is one selected from a group consisting of datum and a parity value;

calculating 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

storing at least a portion of the first set of parity values and the second set of parity values in at least one selected from a group consisting of the cache, memory, and 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. A method for calculating parity values, comprising:

calculating 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 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, and 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 a cache is configured to store only 4N+1 values, wherein each of the values is one selected from a group consisting of datum and a parity value;

calculating 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

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