SYSTEM AND METHOD FOR RECONSTRUCTING LOST DATA IN A STORAGE SYSTEM

• US 20090313499A1
• Filed: 08/06/2009
• Published: 12/17/2009
• Est. Priority Date: 11/22/2004
• Status: Active Grant

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Hafner, James Lee, Surugucchi, Krishnakumar Rao, Deenadhayalan, Veera W.
• Granted Patent: US 7,853,823 B2
• Time in Patent Office: Days
• US Class Current: 714/6
• 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.

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 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.

5. The method according to claim 4, 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.

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

7. 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.

8. The method according to claim 7, 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.

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

collapsing said sequential reconstruction method to reduce cost.

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

12. The method according to claim 11, 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.

13. 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.

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

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

16. The system according to claim 13, 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.

17. The system according to claim 16, 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.

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

19. 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, the method comprising a combination of a direct reconstruction method and a sequential reconstruction method.