Method and system for multi-dimensional raid

• US 9,513,994 B2
• Filed: 03/21/2013
• Issued: 12/06/2016
• Est. Priority Date: 03/23/2012
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Bonwick, Jeffrey S.
• Primary Examiner(s): DUNCAN, MARC M
• Application Number:
  US14/387,326
• Publication Number:
  US 20150095697A1
• Time in Patent Office: 1,356 Days
• 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 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 including calculating: a first set of parity values using the data, a second set of parity values using the first set of parity values, and a third set of parity values using the data, and the first set and second set of parity values. The method further includes storing a portion of the data in a grid, where the grid includes grids locations that are each associated with a physical location, where each physical location is determined using a unique combination of at least a first value determined using a first independent fault domain and a second value determined using a second independent fault domain. The method further includes storing parity values from the first set of parity values and parity values from the second set of parity values in the grid, and storing the third set of parity values in an associated parity grid.

Claims

1. A non-transitory computer readable medium comprising instructions, which when executed perform a method for storing data, the method comprising:

receiving data from a client;

calculating a first set of parity values using the data;

calculating a second set of parity values using the first set of parity values;

calculating a third set of parity values using the data, the first set of parity values, and the second set of parity values;

storing a portion of the data in a grid of a plurality of grids, wherein the grid comprises a plurality of grids locations, wherein each grid location is associated with a physical location in persistent storage, wherein each physical location is determined using a unique combination of at least a first value determined using a first independent fault domain and a second value determined using a second independent fault domain;

storing parity values from the first set of parity values that correspond to the portion of the data in the grid;

storing parity values from the second set of parity values that correspond to the parity values from the first set of parity values in the grid; and

storing, in the persistent storage, each of the third set of parity values in one of a plurality of parity grids in the persistent storage, wherein the one of the plurality of parity grids is associated with the grid.

2. The non-transitory computer readable medium of claim 1, wherein the plurality of grids and the plurality of parity grids are associated with a (Redundant Array of Independent Disks) RAID cube.

3. The non-transitory computer readable medium of claim 2, wherein the RAID cube comprises a first dimension and a second dimension, wherein the first dimension is associated with the first independent fault domain and the second dimension is associated with the second independent fault domain.

4. The non-transitory computer readable medium of claim 3, wherein the RAID cube further comprises a third dimension that is associated with a third independent fault domain, wherein the physical location is further determined using the third independent fault domain.

5. The non-transitory computer readable medium 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 independent fault domain is a plurality of channels in each of the plurality of storage modules, wherein the third independent fault domain is a plurality of NAND dies in each of the plurality of storage modules.

6. The non-transitory computer readable medium of claim 1, wherein the first set of parity values comprises at least one selected from a group consisting of P parity values and Q parity values.

7. The non-transitory computer readable medium of claim 6, wherein the second set of parity values comprises intersection parity values, wherein the intersection parity values are not calculated using any of the data.

8. The non-transitory computer readable medium of claim 1, wherein the third set of parity values comprises at least one selected from a group consisting of P parity values and Q parity values.

9. The non-transitory computer readable medium of claim 1, wherein the plurality of parity grids comprises a P Parity grid and a Q Parity grid.

10. The non-transitory computer readable medium of claim 1, 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 independent fault domain is a plurality of channels in each of the plurality of storage modules.

11. The non-transitory computer readable medium of claim 1, 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 independent fault domain is a plurality of NAND dies in each of the plurality of storage modules.

12. The non-transitory computer readable medium of claim 1, wherein each of the grids comprises a plurality of rows, wherein a location of parity values from the first set of parity values are in different relative locations in at least two of the plurality of rows.

13. The non-transitory computer readable medium of claim 1, wherein the plurality of parity grids do not store any of the plurality of data received from the client.

14. A system, comprising:

a controller;

a non-transitory computer readable medium operatively connected to the controller;

persistent storage operatively connected to the controller and comprising a plurality of storage modules, wherein each of the plurality of storage modules comprises solid state memory;

wherein the non-transitory computer readable medium comprises instructions which when executed by the controller performs a method, the method comprising;

receiving a plurality of data from a client;

calculating a first set of parity values using the plurality of data;

calculating a second set of parity values using the first set of parity values;

calculating a third set of parity values using the plurality of data, the first set of parity values, and the second set of parity values;

storing a portion of the data in a grid of a plurality of grids, wherein the grid comprises a plurality of grids locations, wherein each of the plurality of grid locations is associated with a physical location in the persistent storage, wherein each physical location is determined using a unique combination of at least a first value determined using a first independent fault domain and a second value determined using a second independent fault domain;

storing parity values from the first set of parity values that correspond to the portion of the data in the grid;

storing parity values from the second set of parity values that correspond to the parity values from the first set of parity values in the grid; and

storing, in the persistent storage, each of the third set of parity values in one of a plurality of parity grids in the persistent storage, wherein the one of the plurality of parity grids is associated with the grid.

15. The system of claim 14, further comprising:

a field programmable gate array (FPGA) operatively connected to the controller,

wherein calculating the first set of parity values using the data comprises using the FPGA to calculate at least one of the first set of parity values.

16. The system of claim 14, wherein the controller stores a grid geometry for the grid.

17. The system of claim 16, wherein the grid geometry comprises a size of the grid and specifies independent fault domains associated with each dimension of the grid.

18. The system of claim 14, wherein the controller tracks locations of parity values for the first set of parity values in the grid.

19. The system of claim 14, wherein at least one of the plurality of storage modules comprises a NAND die.

20. The system of claim 14, wherein the controller is configured to reconstruct a corrupted datum in the persistent storage using the first set of parity values, the second set of parity values, and the third set of parity values.