System and method for reconstructing lost data in a storage system

• US 7,853,823 B2
• Filed: 08/06/2009
• Issued: 12/14/2010
• Est. Priority Date: 11/22/2004
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Deenadhayalan, Veera W., Hafner, James Lee, Surugucchi, Krishnakumar Rao
• Primary Examiner(s): Chung; Phung M
• Application Number:
  US12/537,067
• Publication Number:
  US 20090313499A1
• Time in Patent Office: 495 Days
• Field of Search: 714/2, 714/5, 714/6, 714/742, 714/703, 714/764, 714/774, 714/54, 714/20, 714/770
• US Class Current: 714/6.12
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

A system (and method) for determining reconstruction formulas for partial strip reconstruction in a storage system in which a plurality of lost strips have been detected, includes using a combination of a direct reconstruction method and a sequential reconstruction method.

Claims

1. A method for partial strip reconstruction in a storage system in which a plurality of lost strips have been detected, said method comprising:

using a combination of a direct reconstruction method and a sequential reconstruction method to reconstruct said partial strip, as executed by a processor of a computer,

wherein said sequential reconstruction method reconstructs a data element, from an input set of data elements to reconstruct, by collapsing said sequential reconstruction method to reduce cost,

wherein said collapsing said sequential reconstruction method comprises at least one of;

using implicit intermediate results to reconstruct said data element;

determining whether any unnecessary data elements exist in at least one strip of the plurality of lost strips that are not part of said partial strip, and combining at least a portion of steps in said sequential reconstruction method to eliminate reconstruction of said unnecessary data elements;

avoiding unnecessary use of data elements that are not lost;

avoiding duplicate use of data elements that are not lost; and

avoiding multiple use of data elements that are not lost.

2. The method according to claim 1, wherein said direct reconstruction method determines at least one initialization point for said sequential reconstruction method.

3. The method according to claim 1, wherein said storage system includes at least one of a parity scheme and an XOR-based RAID scheme.

4. The method according to claim 1, wherein said direct reconstruction method determines a most cost effective starting point for said sequential reconstruction method.

5. The method according to claim 1, further comprising:

from an input set of data elements to reconstruct, identifying at least one data element which has a lowest reconstruction cost using said direct reconstruction method;

reconstructing said data element using said direct reconstruction method; and

removing said data element from the input set of data elements to reconstruct.

6. The method according to claim 5, further comprising:

from said input set of data elements to reconstruct, determining if at least one data element from the input set is sequentially reconstructable by no more than a predetermined number of steps using available data and parity elements;

reconstructing said data element using said sequential reconstruction method; and

removing said data element from the input set of data elements to reconstruct.

7. The method according to claim 6, wherein, if at least one data element from the input set is not sequentially reconstructable by no more than a predetermined number of steps using available data and parity elements, identifying at least one other data element, from said input set of data elements to reconstruct, which has a lowest reconstruction cost using said direct reconstruction method;

reconstructing said at least one other data element using said direct reconstruction method; and

removing said at least one other data element from the input set of data elements to reconstruct.

8. The method according to claim 5, further comprising:

collapsing said sequential reconstruction method to reduce cost.

9. The method according to claim 1, further comprising:

from an input set of data elements to reconstruct, determining if at least one data element from the input set is sequentially reconstructable by no more than a predetermined number of steps using available data and parity elements;

reconstructing said data element using said sequential reconstruction method; and

removing said data element from the input set of data elements to reconstruct.

10. The method according to claim 9, wherein, if at least one data element from the input set is not sequentially reconstructable by no more than a predetermined number of steps using available data and parity elements, identifying at least one other data element, from said input set of data elements to reconstruct, which has a lowest reconstruction cost using said direct reconstruction method;

reconstructing said at least one other data element using said direct reconstruction method; and

removing said at least one other data element from the input set of data elements to reconstruct.

11. A system for partial strip reconstruction in a storage system, said system comprising:

a storage unit of said storage system including an input set of data elements to reconstruct; and

means for reconstructing a data element from said input set of data elements to reconstruct based on a combination of a direct reconstruction method and a sequential reconstruction method,

wherein said means for reconstructing reconstructs a data element, from an input set of data elements to reconstruct, by collapsing said sequential reconstruction method to reduce cost, and

wherein said means for reconstructing collapses said sequential reconstruction method by at least one of;

using implicit intermediate results to reconstruct said data element;

determining whether any unnecessary data elements exist in at least one strip of the plurality of lost strips that are not part of said partial strip, and combining at least a portion of steps in said sequential reconstruction method to eliminate reconstruction of said unnecessary data elements;

avoiding unnecessary use of data elements that are not lost;

avoiding duplicate use of data elements that are not lost; and

avoiding multiple use of data elements that are not lost.

12. The system according to claim 11, wherein said means for reconstructing uses said direct reconstruction method to determine at least one initialization point for said sequential reconstruction method.

13. The system according to claim 11, wherein said storage system includes at least one of a parity scheme and an XOR-based RAID scheme.

14. The system according to claim 11, wherein said means for reconstructing determines a most cost effective starting point for said sequential reconstruction method using said direct reconstruction method.

15. A tangible signal-bearing storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for determining reconstruction formulas for partial strip reconstruction in a storage system, using, selectively, a combination of a direct reconstruction method and a sequential reconstruction method, said method comprising:

determining, using a processor on a computer, a reconstruction cost for executing said reconstruction, respectively, using said direct reconstruction method, using said sequential reconstruction method, and using a combination of said direct reconstruction method and said sequential reconstruction method; and

using a reconstruction formula for said partial strip reconstruction for whichever said reconstruction method is determined to have a lowest reconstruction cost,

wherein said sequential reconstruction method reconstructs a data element, from an input set of data elements to reconstruct, by collapsing said sequential reconstruction method to reduce cost,

wherein said collapsing said sequential reconstruction method comprises at least one of;

using implicit intermediate results to reconstruct said data element;

determining whether any unnecessary data elements exist in at least one strip of the plurality of lost strips that are not part of said partial strip, and combining at least a portion of steps in said sequential reconstruction method to eliminate reconstruction of said unnecessary data elements;

avoiding unnecessary use of data elements that are not lost;

avoiding duplicate use of data elements that are not lost; and

avoiding multiple use of data elements that are not lost.