Method and system for multi-dimensional raid

• US 8,316,260 B1
• Filed: 07/23/2012
• Issued: 11/20/2012
• Est. Priority Date: 03/23/2012
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: DSSD, Inc. (Dell Technologies Inc.)
• Inventors: Bonwick, Jeffrey S.
• Primary Examiner(s): DUNCAN, MARC M
• Application Number:
  US13/555,859
• Time in Patent Office: 120 Days
• Field of Search: 714/6.2, 714/6.22, 714/6.24, 711/114
• 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 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• 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/064 Management of blocks
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method for storing data. The method including receiving a request to write data. In response the request, selecting, a RAID grid location in a RAID grid to write the data, writing the data to memory, updating a data structure to indicate that the RAID grid location is filled. The method further includes determining, using the data structure, whether a data grid in the RAID grid is filled, where the RAID grid location is in the data grid and based on a determination that the data grid is filled: calculating parity values for the RAID grid using the data, determining a physical address in persistent storage corresponding to the RAID grid location, writing the data to a physical location in persistent storage corresponding to the physical address, and writing the parity values to the persistent storage.

Claims

1. A method for storing data comprising:

receiving a request to write data;

in response the request, selecting, a Redundant Array of Independent Disks (RAID) grid location in a RAID grid to write the data;

writing the data to memory, wherein the data is temporarily stored in the memory;

updating a data structure to indicate that the RAID grid location is filled;

determining, using the data structure, whether a data grid in the RAID grid is filled, wherein the RAID grid location is in the data grid;

based on a determination that the data grid is filled;

calculating parity values for the RAID grid using the data, wherein the RAID grid comprises a Row Q Parity Group, a Row P Parity Group, a Column Q Parity Group, a Column P Parity Group, and an Intersection Parity Group, wherein each of the parity values is associated with one selected from a group consisting of the Row Q Parity Group, the Row P Parity Group, the Column Q Parity Group, the Column P Parity Group, and the Intersection Parity Group, and wherein parity values associated with the Intersection Parity Group are calculated using the parity values from at least one selected from a group consisting of the Row Q Parity Group, the Row P Parity Group, the Column Q Parity Group, and the Column P Parity Group;

determining a physical address in persistent storage corresponding to the RAID grid location;

writing the data to a physical location in persistent storage corresponding to the physical address; and

writing the parity values to the persistent storage.

2. The method of claim 1, further comprising:

determining whether a data portion of a RAID cube is filled, wherein the data portion comprises a plurality of RAID grids, wherein the RAID grid is one of the plurality of RAID grids;

based on a determination that the data portion is filled;

calculating parity values for a parity portion of the RAID cube using values in the data portion; and

writing the parity values for the parity portion to persistent storage.

3. The method of claim 2, wherein the parity portion comprises a P Parity RAID grid and a Q Parity RAID grid.

4. The method of claim 2, wherein the RAID cube comprises a first dimension, a second dimension, and a third dimension, wherein the first dimension is associated with a first independent fault domain, the second dimension is associated with a second independent fault domain, and the third dimension is associated with a third independent fault domain.

5. The method of claim 4, wherein the physical location in the persistent storage is specified at least, in part, using the first independent fault domain, the second independent fault domain, and the third independent fault domain.

6. The method of claim 4, wherein the persistent storage comprises a plurality of storage modules, wherein each of the plurality of storage modules comprises solid state memory, and wherein the first independent fault domain is the plurality of storage modules, the second fault domain is a plurality of channels in each of the plurality of storage modules, wherein the third fault domain is a plurality of NAND dies in each of the plurality of storage modules.

7. The method of claim 1, wherein the parity values comprise at least one selected from a group consisting of P parity values, Q parity values, and intersection parity values.

8. The method of claim 1, wherein the RAID Grid comprises a first dimension and a second dimension, wherein the first dimension is associated with a first independent fault domain and the second dimension is associated with a second independent fault domain.

9. The method of claim 8, wherein the physical location in the persistent storage is specified at least, in part, using the first independent fault domain and the second independent fault domain.

10. The method of claim 9, wherein the persistent storage comprises a plurality of storage modules, wherein each of the plurality of storage modules comprises solid state memory, and wherein the first independent fault domain is the plurality of storage modules and the second fault domain is a plurality of channels in each of the plurality of storage modules.

11. The method of claim 9, wherein the persistent storage comprises a plurality of storage modules, wherein each of the plurality of storage modules comprises solid state memory, and wherein the first independent fault domain is a plurality of channels in each of the plurality of storage modules and the second fault domain is a plurality of NAND dies in each of the plurality of storage modules.

12. A method for reconstructing data, comprising:

receiving a request for first data;

obtaining the first data, wherein the first data is obtained from a first physical location in persistent storage and wherein the first physical location is associated with a first physical address;

making a first determination that the first data is one selected from a group consisting of corrupted and not obtained;

based on the first determination;

identifying a first Redundant Array of Independent Disks (RAID) grid location corresponding to the first physical address;

identifying that a first RAID grid is associated with the first RAID grid location;

identifying a RAID cube associated with the first RAID grid, wherein the RAID cube comprises the first RAID grid and a second RAID grid;

making a first attempt to reconstruct the first data using at least one value in the first RAID grid, wherein the first attempt fails;

making a second attempt, after the first attempt fails, to reconstruct the first data using at least one value in the second RAID grid, wherein the second attempt is successful; and

providing the reconstructed first data to the client.

13. The method of claim 12, further comprising:

receiving a request for second data;

obtaining the second data, wherein the second data is obtained from a second physical location in persistent storage and wherein the second physical location is associated with a second physical address;

making a third determination that the second data is corrupted,

based on the third determination;

identifying a second RAID grid location corresponding to the second physical address;

identifying that the first RAID grid is associated with the second RAID grid location;

making a third attempt to reconstruct the second data using at least one value in the first RAID grid, wherein the third attempt fails;

making a fourth attempt, after the third attempt fails, to reconstruct the second data using at least one value in the second RAID grid, wherein the fourth attempt fails; and

making a fifth attempt, after the fourth attempt fails, to reconstruct the second data using at least one value from a parity portion of the RAID cube, wherein the fifth attempt is successful; and

providing the reconstructed second data to the client.

14. The method of claim 13, wherein the parity portion comprises a P parity value and a Q parity value.

15. The method of claim 14, wherein the P parity value is calculated using at least one value associated with the first RAID grid and at least one value associated with the second RAID grid.

16. The method of claim 12,

wherein the first RAID grid comprises at least one selected from a group consisting of a Row Q Parity Group for the first RAID grid, a Row P Parity Group for the first RAID grid, a Column Q Parity Group for the first RAID grid, and a Column P Parity Group for the first RAID grid;

and

wherein the second RAID grid comprises at least one selected from a group consisting of a Row Q Parity Group for the second RAID grid, a Row P Parity Group for the second RAID grid, a Column Q Parity Group for the second RAID grid, and a Column P Parity Group for the second RAID grid.

17. The method of claim 12, wherein the at least one value in the first RAID grid is one selected from a group consisting of a value corresponding to a RAID grid location in a data grid, a value corresponding to a RAID grid location associated with a Row Q Parity Group for the first RAID grid, a value corresponding to a RAID grid location associated with a Row P Parity Group for the first RAID grid, a value corresponding to a RAID grid location associated with a Column Q Parity Group for the first RAID grid, and a value corresponding to a RAID grid location associated with a Column P Parity Group for the first RAID grid, wherein the first RAID grid comprises the data grid.

18. The method of claim 12, wherein the persistent storage is solid state memory.

19. A method for reconstructing data, comprising:

receiving a request for data;

obtaining the data, wherein the data is obtained from a physical location in persistent storage and wherein the physical location is associated with a physical address;

making a first determination that the first data is one selected from a group consisting of corrupted and not obtained,

based on the first determination;

identifying a first Redundant Array of Independent Disks (RAID) grid location corresponding to the physical address;

identifying that a RAID grid is associated with the first RAID grid location;

making a first attempt to reconstruct the data using a first value in a second RAID grid location, wherein the second RAID grid location is located in at least one selected from a group consisting of a first row and a first column in the RAID grid, wherein the first RAID grid location is part of the first row and the first column, wherein the first attempt fails;

making a second attempt, after the first attempt fails, to reconstruct the data, wherein the second attempt is successful and wherein the second attempt comprises;

reconstructing at least one selected from a group consisting of a second row and a second column in the RAID grid to obtain a reconstructed portion of the RAID gird, wherein the reconstructed portion of the RAID grid intersects at least one selected from a group consisting of the first row and the first column;

reconstructing the data using a second value in a third RAID grid location, wherein the third RAID grid location is part of the reconstructed portion of the RAID grid, and wherein the third RAID grid location is located in one selected from a group consisting of the first row and first column; and

providing the reconstructed data to the client.