Method and system for mirrored multi-dimensional raid

• US 8,554,997 B1
• Filed: 01/18/2013
• Issued: 10/08/2013
• Est. Priority Date: 01/18/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., Shapiro, Michael W.
• Primary Examiner(s): SONG, HUA JASMINE
• Application Number:
  US13/745,246
• Time in Patent Office: 263 Days
• Field of Search: 711/103, 711/111, 711/114, 711/156, 714/6.2, 714/6.22, 714/6.23
• US Class Current: 711/114
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/2056 by mirroring
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 3/0611 in relation to response time
• 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/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method for storing data. The method includes receiving a request to write data, determining that the storage mode for the data is mirrored mode, selecting a Redundant Array of Independent Devices (RAID) grid location in a RAID grid to write the data based on the storage mode, writing the data to memory, updating a data structure to indicate that the RAID grid location is filled, and determining a data grid is filled. Based on the determination, determining a first physical address and a second physical address in persistent storage corresponding to the RAID grid location; writing the data to a first physical location in the persistent storage corresponding to the first physical address and writing the data to a second physical location in the persistent storage corresponding to the second physical address, and writing the parity values associated with data grid to the persistent storage.

Claims

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

receiving a request to write data;

determining a storage mode for the data, wherein the storage mode for the data is mirrored mode;

selecting a Redundant Array of Independent Devices (RAID) grid location in a RAID grid to write the data based on the storage mode;

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;

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

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

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

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

writing the parity values associated with data grid to the persistent storage.

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

receiving a second request to write second data;

determining a second storage mode for the second data, wherein the storage mode for the second data is non-mirrored mode;

selecting, a second RAID grid location in the RAID grid to write the data based on the second storage mode;

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

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

receiving a third request to write third data;

determining a third storage mode for the third data, wherein the third storage mode for the third data is the non-mirrored mode;

selecting, the second RAID grid location in the RAID grid to write the data using the third storage mode;

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

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

based on the determination that the data grid is filled;

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

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

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

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

4. The non-transitory computer readable medium of claim 1, wherein the RAID grid location is associated with a virtual stripe, wherein the virtual stripe is associated with a first physical stripe and a second physical stripe, wherein the first physical location is part of the first physical stripe and the second physical location is part of the second physical stripe.

5. The non-transitory computer readable medium of claim 1, wherein the RAID grid location is associated with a virtual stripe, and a second virtual stripe.

6. The non-transitory computer readable medium of claim 4, wherein the parity values stored in the first physical stripe are equal to the parity values stored in the second physical stripe.

7. The non-transitory computer readable medium of claim 1, wherein the first physical location is specified using an n-tuple comprising a storage module, a channel, and a chip, wherein the second physical location is specified using the storage module, the channel, and a second chip.

8. The non-transitory computer readable medium of claim 1, wherein the data is written to the first physical location in persistent storage prior to writing the data to the second physical location.

9. The non-transitory computer readable medium 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.

10. The non-transitory computer readable medium 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.

11. The non-transitory computer readable medium of claim 1, 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.

12. The non-transitory computer readable medium of claim 11, wherein the parity values associated with the Intersection Parity Group are calculated using the parity values for 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.

3. The non-transitory computer readable medium of 2, wherein the RAID grid location is associated with a virtual stripe, wherein the virtual stripe is associated with a first physical stripe and a second physical stripe, wherein the first physical location is part of the first physical stripe and the second physical location is part of the second physical stripe, wherein the second RAID grid location is associated with a second virtual stripe, wherein the second virtual stripe is associated with a third physical stripe and a fourth physical stripe, wherein the third physical location is part of the third physical stripe, and wherein the parity values stored in the third physical stripe are different than the parity values stored in the forth physical stripe.

13. A non-transitory computer readable medium comprising instructions, which when executed by a processor perform a method, the method for obtaining reconstructing data, comprising:

receiving a first request for data;

identifying a grid location in a Redundant Array of Independent Devices (RAID) grid associated with the data, wherein the grid location is associated with a first physical location and a second physical location;

making a first determination that a storage mode for the grid location is mirrored mode;

based on the first determination, making a second determination that the first physical location is busy;

based on the second determination, issuing a second request for the data to the second physical location; and

in response to the second request, receiving the data from the second physical location,

wherein the grid location is associated with a virtual stripe,

wherein the virtual stripe is associated with a first physical stripe and a second physical stripe,

wherein the first physical location is part of the first physical stripe and the second physical location is part of the second physical stripe.

14. The non-transitory computer readable medium of claim 13, further comprising:

making a third determination that the data obtained from the second physical location is corrupted;

based on the third determination, issuing a third request for the data to the first physical location.

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

making a fourth determination that the data obtained from the second physical location is corrupted; and

based on the fourth determination, attempting to reconstruct the data using at least one selected from a group consisting of the first physical stripe and the second physical stripe.

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

making a fourth determination that the data obtained from the second physical location is corrupted; and

based on the fourth determination, attempting to reconstruct the data using the first physical stripe.

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

making a fifth determination that the attempt to reconstruct the data using the first physical stripe failed; and

based on the fifth determination, attempting to reconstruct the data using the second physical stripe.

18. The non-transitory computer readable medium of claim 13, wherein the first physical location is on a first chip in a persistent storage and the second physical location is on a second chip in the persistent storage, and wherein the first chip and the second chip may perform Input/Output (I/O) operations in parallel.

19. The non-transitory computer readable medium of claim 18, wherein the I/O operations comprise at least one selected from a group consisting of a read operation, a write operation, and an erase operation.