Storage system with incremental multi-dimensional RAID

• US 8,341,342 B1
• Filed: 03/23/2012
• Issued: 12/25/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., Moore, William H.
• Primary Examiner(s): CHOE, YONG J
• Application Number:
  US13/428,817
• Time in Patent Office: 277 Days
• Field of Search: 711/114, 711/103, 711/111, 711/156, 711/E12.001
• US Class Current: 711/103
• 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

Abstract

A method for storing data including receiving a request to write data and in response the request, selecting a RAID grid location in a RAID grid to write the data. The method further includes writing the data to memory, updating a data structure to indicate that the RAID grid location is filled, identifying a parity value in the RAID grid to update, where the parity value is associated with a second RAID grid location in the RAID grid, updating the parity value using the data and the parity value to obtain an updated parity value and storing the updated parity value in the memory. Prior to the first data grid being filled determining a physical address in persistent storage corresponding to the RAID grid location and writing the data to the first physical address.

Claims

1. A method for storing data comprising:

receiving a first request to write first data;

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

writing the first data to memory;

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

identifying a first parity value in the first RAID grid to update in response to the first RAID grid location being filled, wherein the first parity value is associated with a second RAID grid location in the first RAID grid;

updating the first parity value using the first data and the first parity value to obtain an updated first parity value, wherein the updated first parity value is stored in the memory, and wherein the updated first parity value is associated with the second RAID grid location;

prior to the first data grid being filled;

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

writing the first data to a first physical location in persistent storage corresponding to the first physical address.

2. The method of claim 1, further comprising:

receiving a second request to write second data;

in response the second request, selecting, a third RAID grid location in the first RAID grid to write the second data, wherein the third RAID grid location is in the first data grid;

writing the second data to the memory;

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

identifying the updated first parity value in the first RAID grid to update in response to the third RAID grid location being filled;

updating the updated first parity value using the second data and the updated first parity value to obtain an updated second parity value, wherein the updated second parity value is stored in the memory, and wherein the updated second parity value is associated with the second RAID grid location;

prior to the first data grid being filled;

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

writing the second data to a second physical location in persistent storage corresponding to the second physical address.

3. The method of claim 2, further comprising:

after the first data grid is filled;

writing the updated second parity value to the persistent storage.

4. The method of claim 1, further comprising:

identifying a second parity value in a Parity RAID grid to update in response to the first RAID grid location being filled, wherein the second parity value is associated with a third RAID grid location in the Parity RAID grid;

updating the second parity value using the first data and the second parity value to obtain an updated second parity value, wherein the updated second parity value is stored in the memory, wherein the updated second parity value is associated with the third RAID grid location.

5. The method of claim 4, further comprising:

after the data grid is filled;

writing the updated first parity value to the persistent storage; and

writing the updated second parity value to the persistent storage.

6. The method of claim 4, wherein the Parity RAID grid is one selected from a group consisting of a P Parity RAID grid and a Q Parity RAID grid.

7. The method of claim 1, further comprising:

receiving a second request to write second data;

in response the second request, selecting, a third RAID grid location in a second RAID grid to write the second data, wherein the third RAID grid location is in a second data grid in the second RAID grid, and wherein the first RAID grid and the second RAID grid and a Parity grid are associated with a RAID cube;

writing the second data to memory;

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

identifying a second parity value in the second RAID grid to update in response to the second RAID grid location being filled, wherein the second parity value is associated with a fourth RAID grid location in the second RAID grid;

updating the second parity value using the second data and the second parity value to obtain an updated second parity value, wherein the updated second parity value is stored in the memory, and wherein the updated second parity value is associated with the fourth RAID grid location;

identifying a third parity value in the Parity RAID grid to update in response to the third RAID grid location being filled, wherein the third parity value is associated with a fifth RAID grid location in the Parity RAID grid;

updating the third parity value using the second data and the third parity value to obtain an updated third parity value, wherein the updated third parity value is stored in the memory, wherein the updated third parity value is associated with the fifth RAID grid location;

prior to the second data grid being filled;

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

writing the second data to a second physical location in persistent storage corresponding to the second physical address.

8. The method of claim 1, wherein the RAID grid is associated with a RAID cube, 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.

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, the second independent fault domain, and the third independent fault domain.

10. The method of claim 8, 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.

11. The method of claim 1, wherein the first parity value comprises at least one selected from a group consisting of a P parity value, a Q parity value, and an intersection parity value.

12. A system, comprising:

a control module comprising;

an Input/Output module (IOM);

a processor;

a first memory connected to the processor;

a switch fabric, wherein the IOM and the processor are connected to the switch fabric;

a first storage module connected to the control module using the switch fabric and comprising;

a second memory;

a first persistent storage;

a second storage module connected to the control module using the switch fabric and comprising;

a third memory;

a second persistent storage;

wherein the control module is configured to;

receive a first request to write first data;

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

write the first data to the second memory;

update a data structure in the first memory to indicate that the first RAID grid location is filled;

identify a first parity value in the first RAID grid to update in response to the first RAID grid location being filled, wherein the first parity value is associated with a second RAID grid location in the first RAID grid;

update the first parity value using the first data and the first parity value to obtain an updated first parity value, wherein the updated first parity value is stored in the second memory, and wherein the updated first parity value is associated with the second RAID grid location;

prior to the first data grid being filled;

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

write the first data to a first physical location in the first persistent storage corresponding to the first physical address.

13. The system of claim 12, wherein the switch fabric implements Peripheral Component Interconnect Express (PCIe) protocol.

14. The system of claim 12, wherein the first persistent storage comprises NAND flash.

15. The system of claim 12, wherein the first persistent storage is a solid state memory module.

16. The system of claim 15, wherein the solid state memory module comprises a plurality of NAND dies.

17. The system of claim 12, wherein the request to write the data is received from the client via a client switch, wherein the client communicates with the client switch using Peripheral Component Interconnect Express (PCIe), and the storage appliance communicates with the client switch using PCIe.

18. The system of claim 12, wherein the second memory comprises vaulted memory, wherein contents of the vaulted memory are automatically written to the first persistent storage in the event of a power failure in the first storage module.

19. A non-transitory computer readable medium comprising instructions, which when executed by a processor perform a method, the method comprising:

receiving a first request to write first data;

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

writing the first data to memory;

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

identifying a first parity value in the first RAID grid to update in response to the first RAID grid location being filled, wherein the first parity value is associated with a second RAID grid location in the first RAID grid;

updating the first parity value using the first data and the first parity value to obtain an updated first parity value, wherein the updated first parity value is stored in the memory, and wherein the updated first parity value is associated with the second RAID grid location;

prior to the first data grid being filled;

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

writing the first data to a first physical location in persistent storage corresponding to the first physical address.

20. The non-transitory computer readable medium of claim 19, the method further comprising:

receiving a second request to write second data;

in response the second request, selecting, a third RAID grid location in the first RAID grid to write the second data, wherein the third RAID grid location is in the first data grid;

writing the second data to the memory;

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

identifying the updated first parity value in the first RAID grid to update in response to the third RAID grid location being filled;

updating the updated first parity value using the second data and the updated first parity value to obtain an updated second parity value, wherein the updated second parity value is stored in the memory, and wherein the updated second parity value is associated with the second RAID grid location;

prior to the first data grid being filled;

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

writing the second data to a second physical location in persistent storage corresponding to the second physical address.