System and method for recovery of data for a lost sector in a storage system

• US 7,870,464 B2
• Filed: 11/02/2004
• Issued: 01/11/2011
• Est. Priority Date: 11/02/2004
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Tomlin, John Anthony, Hafner, James Lee
• Primary Examiner(s): Alphonse; Fritz
• Application Number:
  US10/978,389
• Publication Number:
  US 20060107091A1
• Time in Patent Office: 2,261 Days
• Field of Search: 714/770, 714/710, 714/758, 714/704, 714/718, 714/723, 714/42, 714/5
• US Class Current: 714/770
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A system (and method) for a recovery of data from a lost sector in a storage system, which includes a set of readable and lost sectors in a plurality of disks in the storage system, includes identifying a lost sector of at least one disk of the storage system, determining whether the data from the lost sector is capable of being recovered, and, if the data from the lost sector is capable of being recovered, generating a recovery formula for the lost sector and recovering the data from the lost sector based on the recovery formula.

Claims

1. A method for a lost sector data recovery in a storage system employing an exclusive-OR erasure code across a plurality of disks, the method comprising:

determining, using a processor, a set of readable sectors and a set of lost sectors in said plurality of disks in said storage system;

identifying, using said processor, a first lost sector in said set of lost sectors; and

determining, using said processor, whether data from said first lost sector is capable of being recovered from the data stored on the readable sectors or is not capable of being recovered, based on a binary parity check matrix of said exclusive-OR erasure code.

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

if the data from said first lost sector is capable of being recovered, generating a first recovery formula for recovering the data from said first lost sector.

3. The method according to claim 2, wherein said generating said first recovery formula implements a binary matrix pseudo-inverse algorithm.

4. The method according to claim 2, further comprising:

if the data from said first lost sector is capable of being recovered, generating said first recovery formula using a pseudo-inverse construction; and

recovering the data from the first lost sector.

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

generating a second recovery formula for data from a second lost sector based at least in part on said recovered data from said first lost sector.

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

replacing the data from said first lost sector based on a result of said recovery.

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

identifying a second lost sector of at least one disk of said storage system; and

determining whether data of said second lost sector is capable of being recovered based on said replaced data from said first lost sector.

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

if data of said second lost sector is capable of being recovered, generating a second recovery formula for the data of said second lost sector.

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

generating said second recovery formula for said data from said second lost sector based at least in part on said recovered data from said first lost sector.

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

recovering the data of said second lost sector based on said second recovery formula for said data of said second lost sector.

11. The method according to claim 10, further comprising:

replacing the data from said second lost sector based on a result of said recovery of said data of said second lost sector.

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

if the data from said first lost sector is determined as capable of being recovered, using said processor to recover the data from said first lost sector.

13. The method according to claim 1, wherein said first lost sector includes lost data comprising at least one of recoverable lost data and unrecoverable lost data.

14. The method according to claim 13, wherein, if said first lost sector includes unrecoverable lost data, said method further comprises declaring a data loss event.

15. The method according to claim 1, wherein said storage system comprises at least one of a storage device, a plurality of storage nodes, a storage network, and a disk array.

16. The method according to claim 1, wherein said storage system comprises a redundant array of inexpensive disks (RAID) disk array.

17. The method according to claim 1, wherein said first lost sector includes a plurality of lost sectors.

18. A lost sector data recovery system in a storage system employing an exclusive-OR erasure code across a plurality of disks, the lost sector data recovery system comprising:

means for determining a set of readable sectors and lost sectors in a plurality of disks in said storage system;

means for identifying a first lost sector of at least one disk of said storage system; and

means for determining whether data from said first lost sector is capable of being recovered from the data stored on the readable sectors or is not capable of being recovered, as based on a binary parity check matrix of said exclusive-OR erasure code.

19. The system according to claim 18, further comprising:

means for recovering the data from said first lost sector which is determined to be capable of being recovered.

20. A lost sector data recovery system in a storage system employing an erasure code across a plurality of disks, the lost sector data recovery system comprising:

a first determining unit that determines a set of readable sectors and lost sectors in a plurality of disks in said storage system,

an identifying unit that identifies a first lost sector of at least one disk of said storage system;

a second determining unit that determines whether data from said first lost sector comprises recoverable data or, alternatively, cannot be recovered, as based on a parity check matrix of said erasure code;

a generating unit that generates a first recovery formula for recovering the data from said first lost sector;

a recovering unit that recovers said data from said first lost sector based on said first recovery formula; and

a replacing unit that replaces said data from said first lost sector based on a result of said recovering,

wherein said identifying unit identifies a second lost sector of at least one disk of said storage system,

wherein said second determining unit determines whether data from said second lost sector comprises recoverable data based at least in part on said recovered data from said first lost sector wherein said generating unit generates a second recovery formula for recovering the data from said second lost sector based at least in part on said recovered data from said first lost sector,

wherein said recovering unit recovers said data from said second lost sector based on said second recovery formula, and

wherein said replacing unit replaces said data from said second lost sector based on a result from said recovering unit.

21. The system according to claim 20, wherein said storage system comprises at least one of a storage device, a plurality of storage nodes, a storage network, and a disk array.

22. The system according to claim 20, wherein said storage system comprises a redundant array of inexpensive disks (RAID) disk array.

23. The system according to claim 20, wherein said identifying unit identifies a plurality of lost sectors.

24. 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 a lost sector data recovery in a storage system employing an exclusive-OR erasure code across a plurality of disks, the method comprising:

determining a set of readable sectors and lost sectors in a plurality of disks in said storage system,

identifying a lost sector of at least one disk of said storage system; and

determining whether data from said lost sector is capable of being recovered from the data stored on the readable sectors or, alternately, cannot be recovered, as based from a binary parity check matrix of said exclusive-OR erasure code.

25. The signal-bearing storage medium according to claim 24, further comprising:

if said data from said lost sector is capable of being recovered, recovering said data from said lost sector.

26. A method of deploying computing infrastructure in which computer-readable code is integrated into a computing system employing an exclusive-OR erasure code across a plurality of disks, and combines with said computing system to perform a method for a lost sector data recovery in a storage system, the method comprising:

determining a set of readable sectors and lost sectors in a plurality of disks in said storage system;

identifying a lost sector of at least one disk of said storage system; and

determining whether data from said lost sector is capable of being recovered from the data stored on the readable sectors or, alternately, cannot be recovered, as based on a binary parity check matrix of said exclusive-OR erasure code.

27. The method according to claim 26, further comprising:

if said data from said lost sector is capable of being recovered, recovering said data from said lost sector.