IP Library › Granted Patent US 8,464,095
Granted Patent B1
US 8,464,095 · App. 13/677,623 · Granted Jun 11, 2013

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

Inventor: Jeffrey S. Bonwick (Los Altos, CA)
Assignee: DSSD, Inc.
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 8,464,095
App. No.
13/677,623
Filed
Nov 15, 2012
Granted
Jun 11, 2013
Kind
B1
Art Unit
2114
USPC
714/6.22
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 (50)

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.

Assignments (11)
RELEASE OF SECURITY INTEREST IN PATENTS PREVIOUSLY RECORDED AT REEL/FRAME (053546/0001) Recorded Jun 23, 2022
From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
To: DELL MARKETING L.P. (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO CREDANT TECHNOLOGIES, INC.); DELL INTERNATIONAL L.L.C.; DELL PRODUCTS L.P.; DELL USA L.P.; EMC CORPORATION; DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO FORCE10 NETWORKS, INC. AND WYSE TECHNOLOGY L.L.C.); EMC IP HOLDING COMPANY LLC
Reel/Frame 071642/0001 →
RELEASE OF SECURITY INTEREST IN PATENTS PREVIOUSLY RECORDED AT REEL/FRAME (045455/0001) Recorded May 20, 2022
From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
To: DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO ASAP SOFTWARE EXPRESS, INC.); DELL MARKETING L.P. (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO CREDANT TECHNOLOGIES, INC.); DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL PRODUCTS L.P.; DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO FORCE10 NETWORKS, INC. AND WYSE TECHNOLOGY L.L.C.); EMC CORPORATION (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MAGINATICS LLC); EMC IP HOLDING COMPANY LLC (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MOZY, INC.); SCALEIO LLC
Reel/Frame 061753/0001 →
RELEASE OF SECURITY INTEREST IN PATENTS PREVIOUSLY RECORDED AT REEL/FRAME (040136/0001) Recorded Apr 26, 2022
From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
To: DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO ASAP SOFTWARE EXPRESS, INC.); DELL MARKETING L.P. (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO CREDANT TECHNOLOGIES, INC.); DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL PRODUCTS L.P.; DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO FORCE10 NETWORKS, INC. AND WYSE TECHNOLOGY L.L.C.); EMC CORPORATION (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MAGINATICS LLC); EMC IP HOLDING COMPANY LLC (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MOZY, INC.); SCALEIO LLC
Reel/Frame 061324/0001 →
RELEASE OF SECURITY INTEREST Recorded Nov 3, 2021
From: CREDIT SUISSE AG, CAYMAN ISLANDS BRANCH
To: ASAP SOFTWARE EXPRESS, INC.; AVENTAIL LLC; CREDANT TECHNOLOGIES, INC.; DELL USA L.P.; DELL INTERNATIONAL, L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL SYSTEMS CORPORATION; EMC CORPORATION; EMC IP HOLDING COMPANY LLC; FORCE10 NETWORKS, INC.; MAGINATICS LLC; MOZY, INC.; SCALEIO LLC; WYSE TECHNOLOGY L.L.C.
Reel/Frame 058216/0001 →
SECURITY AGREEMENT Recorded Apr 22, 2020
From: CREDANT TECHNOLOGIES INC.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL USA L.P.; EMC CORPORATION; FORCE10 NETWORKS, INC.; WYSE TECHNOLOGY L.L.C.; EMC IP HOLDING COMPANY LLC
To: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A.
Reel/Frame 053546/0001 →
SECURITY AGREEMENT Recorded Mar 21, 2019
From: CREDANT TECHNOLOGIES, INC.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL USA L.P.; EMC CORPORATION; FORCE10 NETWORKS, INC.; WYSE TECHNOLOGY L.L.C.; EMC IP HOLDING COMPANY LLC
To: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A.
Reel/Frame 049452/0223 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 29, 2016
From: EMC CORPORATION
To: EMC IP HOLDING COMPANY LLC
Reel/Frame 040203/0001 →
SECURITY AGREEMENT Recorded Sep 21, 2016
From: ASAP SOFTWARE EXPRESS, INC.; AVENTAIL LLC; CREDANT TECHNOLOGIES, INC.; DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL SYSTEMS CORPORATION; EMC CORPORATION; EMC IP HOLDING COMPANY LLC; FORCE10 NETWORKS, INC.; MAGINATICS LLC; MOZY, INC.; SCALEIO LLC; SPANNING CLOUD APPS LLC; WYSE TECHNOLOGY L.L.C.
To: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
Reel/Frame 040136/0001 →
SECURITY AGREEMENT Recorded Sep 21, 2016
From: ASAP SOFTWARE EXPRESS, INC.; AVENTAIL LLC; CREDANT TECHNOLOGIES, INC.; DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL SYSTEMS CORPORATION; EMC CORPORATION; EMC IP HOLDING COMPANY LLC; FORCE10 NETWORKS, INC.; MAGINATICS LLC; MOZY, INC.; SCALEIO LLC; SPANNING CLOUD APPS LLC; WYSE TECHNOLOGY L.L.C.
To: CREDIT SUISSE AG, CAYMAN ISLANDS BRANCH, AS COLLATERAL AGENT
Reel/Frame 040134/0001 →
MERGER Recorded Sep 10, 2016
From: DSSD, INC.
To: EMC CORPORATION
Reel/Frame 039694/0912 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 29, 2012
From: BONWICK, JEFFREY S.
To: DSSD, INC.
Reel/Frame 029374/0742 →