Method and system for multi-dimensional raid

1. A method for storing data comprising:

receiving a request to write data;

in response the request, selecting, a grid location in a 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 grid location is filled;

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

based on a determination that the data grid is filled:

calculating parity values for the grid using the data, wherein the 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 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 cube is filled, wherein the data portion comprises a plurality of grids, wherein the grid is one of the plurality of grids;

based on a determination that the data portion is filled:

calculating parity values for a parity portion of the 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 grid and a Q Parity grid.

4. The method of claim 2 , wherein the 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 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 grid location corresponding to the first physical address;

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

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

making a first attempt to reconstruct the first data using at least one value in the first 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 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 grid location corresponding to the second physical address;

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

making a third attempt to reconstruct the second data using at least one value in the first 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 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 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 grid and at least one value associated with the second grid.

16. The method of claim 12 ,

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

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

17. The method of claim 12 , wherein the at least one value in the first grid is one selected from a group consisting of a value corresponding to a grid location in a data grid, a value corresponding to a grid location associated with a Row Q Parity Group for the first grid, a value corresponding to a grid location associated with a Row P Parity Group for the first grid, a value corresponding to a grid location associated with a Column Q Parity Group for the first grid, and a value corresponding to a grid location associated with a Column P Parity Group for the first grid, wherein the first 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 grid location corresponding to the physical address;

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

making a first attempt to reconstruct the data using a first value in a second grid location, wherein the second grid location is located in at least one selected from a group consisting of a first row and a first column in the grid, wherein the first 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 grid to obtain a reconstructed portion of the grid, wherein the reconstructed portion of the 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 grid location, wherein the third grid location is part of the reconstructed portion of the grid, and wherein the third 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.