Method and system for multi-dimensional raid reconstruction and defect avoidance

• US 8,464,095 B1
• Filed: 11/15/2012
• Issued: 06/11/2013
• Est. Priority Date: 11/15/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): Iqbal, Nadeem
• Application Number:
  US13/677,623
• Time in Patent Office: 208 Days
• Field of Search: 714/6.1, 714/6.11, 714/6.12, 714/6.13, 714/6.2, 714/6.21, 714/6.22, 714/6.23, 714/6.24, 714/6.3, 714/41, 714/42
• US Class Current: 714/6.2
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks

Abstract

In general, embodiments of the invention relate to storing data by receiving a request to write data, in response the request, selecting a first RAID grid location in a RAID grid to write the data, determining a first physical address in persistent storage corresponding to the first RAID grid location, generating a first page comprising the data and first out-of-band (OOB), wherein the first OOB comprises a first grid geometry for the RAID grid, and a first stripe membership for the page within the RAID grid, and writing the first page to a first physical location in persistent storage corresponding to the first physical address.

Claims

1. A method for storing data comprising:

receiving a request to write data;

in response the request, selecting a first RAID grid location in a RAID grid to write the data;

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

generating a first page comprising the data and first out-of-band (OOB), wherein the first OOB comprises a first grid geometry for the RAID grid, and a first stripe membership for the page within the RAID grid; and

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

2. The method of claim 1, further comprising:

calculating a parity value of the RAID grid using the data;

selecting a second RAID grid location in the RAID grid to write the parity value;

generating a second page comprising the parity value and a second OOB, wherein the second OOB comprises a second grid geometry and a second stripe membership;

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

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

3. The method of claim 2, wherein the RAID grid comprises a parity row, wherein the second RAID grid location is in the parity row.

4. The method of claim 3, further comprising:

prior to receiving the request to write the data;

analyzing a number of bad physical locations in each of a plurality of potential locations within the RAID grid; and

selecting one of the plurality of potential locations as a location of the parity row, wherein the selected one of the plurality of potential locations comprises a least number of bad physical locations relative to the other plurality of potential locations.

5. The method of claim 2, wherein the first stripe membership comprises a stripe membership for a first dimension and a stripe membership for a second dimension in the RAID grid, wherein the second stripe membership comprises the stripe membership for the first dimension.

6. The method of claim 5, wherein the first page is in a first row in the RAID grid, wherein the first stripe membership indicates which physical locations in the persistent storage corresponding to the first row are bad.

7. The method of claim 2, wherein the first grid geometry comprises a parity location in the RAID grid and wherein the second grid geometry comprises the parity location in the RAID grid.

8. The method of claim 2, wherein the 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.

9. The method of claim 1, wherein the first stripe membership is a bitmap.

10. The method of claim 1, wherein the OOB further comprises a gridmap and wherein the gridmap identifies a first independent fault domain (IFD) corresponding to a first dimension of the RAID grid and a second IFD corresponding to a second dimension of the RAID grid.

11. The method of claim 10, wherein the first IFD is a storage module and the second IFD is a channel.

12. The method of claim 10, wherein the first physical location in the persistent storage is specified at least, in part, using the first IFD and the second IFD.

13. The method of claim 1, wherein the first grid geometry comprises a self field specifying a relative location of the first page in the RAID grid to a reference RAID grid location in the RAID grid.

14. The method of claim 1, wherein the first grid geometry comprises a last field specifying a first size of a first dimension of the RAID grid and a second size of a second dimension of the RAID grid.

15. The method of claim 1, wherein the first grid geometry comprises an nparity field specifying a first number of parity values in a first dimension of the RAID grid.

16. The method of claim 15, wherein the nparity field further specifies a second number of parity values in a second dimension of the RAID grid.

17. The method of claim 1, wherein the first OOB comprises a version field corresponding to a format of the OOB.

18. The method of claim 1, wherein the first OOB comprises a checksum calculated using all data in the first OOB.

19. A method for reconstructing data, comprising:

receiving a request for first data;

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

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

based on the determination;

identifying a neighbor RAID grid location of the first RAID grid location in the RAID grid, wherein the RAID grid comprises a row, wherein the first RAID grid location and the neighbor grid location are in the row;

obtaining a second page from the neighbor RAID grid location;

obtaining out-of-band (OOB) data from the second page, wherein the OOB comprises a gridmap for the RAID grid, grid geometry for the RAID grid, and stripe membership for the second page within the RAID grid;

identifying RAID grid locations within the row comprising data pages using the grid geometry and the stripe membership;

obtaining the data pages within the row using the gridmap and the grid geometry;

identifying a RAID grid location in the row comprising a parity value using the grid geometry and the stripe membership;

obtaining the parity value within the row using the gridmap and the grid geometry;

reconstructing the first page using the data pages and the parity value to obtain a reconstructed page;

obtaining the data from the constructed page; and

providing the reconstructed data to the client.

20. The method of claim 19,

wherein the gridmap identifies a first independent fault domain (IFD) corresponding to a first dimension of the RAID grid and a second IFD corresponding to a second dimension of the RAID grid,

wherein the stripe membership indicates which physical locations in the persistent storage corresponding to the row are bad, and

wherein the grid geometry comprises a parity location in the row and a self field specifying a relative location of the second page in the RAID grid to a reference page in the RAID grid.