Method and system using checksums to repair data

• US 20070106925A1
• Filed: 04/19/2006
• Published: 05/10/2007
• Est. Priority Date: 11/04/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Moore, William, Bonwick, Jeffrey
• Granted Patent: US 7,689,877 B2
• Time in Patent Office: Days
• 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
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks

Abstract

A method for reconstructing corrupted data, which includes determining a number of non-parity disks (n), selecting a first combination of n-1 non-parity disks, obtaining a first set of physical blocks from the first combination of n-1 non-parity disks, obtaining a parity block associated with the first set of physical blocks, reconstructing a first physical block using the first set of physical blocks and the parity block, combining the first physical block and the first set of physical blocks to obtain a first reconstructed logical block, checksumming the first reconstructed logical block to obtain a first calculated checksum, and determining whether the first calculated checksum is equal to a stored checksum associated with the first reconstructed logical block.

Claims

1. A method for reconstructing corrupted data, comprising:

determining a number of non-parity disks (n);

selecting a first combination of n-1 non-parity disks;

obtaining a first set of physical blocks from the first combination of n-1 non-parity disks;

obtaining a parity block associated with the first set of physical blocks;

reconstructing a first physical block using the first set of physical blocks and the parity block;

combining the first physical block and the first set of physical blocks to obtain a first reconstructed logical block;

checksuming the first reconstructed logical block to obtain a first calculated checksum; and

determining whether the first calculated checksum is equal to a stored checksum associated with the first reconstructed logical block.

2. The method of claim 1, further comprising:

replacing a corresponding physical block in the storage pool with the first physical block, if the first calculated checksum is equal to the stored checksum associated with the logical block.

3. The method of claim 1, further comprising:

if the first calculated checksum is not equal to the stored checksum associated with the logical block;

selecting a second combination of n-1 non-parity disks;

obtaining a second set of physical blocks from the second combination of n-1 non-parity disks;

reconstructing a second physical block using the second set of physical blocks and the parity block;

combining the second physical block and the second set of physical blocks to obtain a second reconstructed logical block;

checksuming the second reconstructed logical block to obtain a second calculated checksum; and

determining whether the second calculated checksum is equal to the stored checksum associated with the second reconstructed logical block.

4. The method of claim 1, further comprising:

receiving a request for a logical block;

obtaining the logical block;

checksuming the logical block to obtain a third calculated checksum;

if the third calculated checksum is not equal to the stored checksum, then initiating the determination of the number of non-parity disks (n); and

if the third calculated checksum is equal to the stored checksum, then returning the logical block to a process which sent the request.

5. The method of claim 4, wherein the stored checksum is stored in a block pointer referencing the logical block.

6. The method of claim 4, wherein the logical block is stored using a RAID scheme.

7. The method of claim 1, wherein the logical block is a data block.

8. The method of claim 1, wherein the logical block is an indirect block.

9. The method of claim 1, wherein the logical block is associated with a file.

10. A computer readable medium with software instructions stored thereon to:

determine a number of non-parity disks (n);

select a first combination of n-1 non-parity disks;

obtain a first set of physical blocks from the first combination of n-1 non-parity disks;

obtain a parity block associated with the first set of physical blocks;

reconstruct a first physical block using the first set of physical blocks and the parity block;

combine the first physical block and the first set of physical blocks to obtain a first reconstructed logical block;

checksum the first reconstructed logical block to obtain a first calculated checksum; and

determine whether the first calculated checksum is equal to a stored checksum associated with the first reconstructed logical block.

11. The computer readable medium of claim 10, further comprising software instructions to:

replace a corresponding physical block in the storage pool with the first physical block, if the first calculated checksum is equal to the stored checksum associated with the logical block.

12. The computer readable medium of claim 10, further comprising software instructions to:

if the first calculated checksum is not equal to the stored checksum associated with the logical block;

select a second combination of n-1 non-parity disks;

obtain a second set of physical blocks from the second combination of n-1 non-parity disks;

reconstruct a second physical block using the second set of physical blocks and the parity block;

combine the second physical block and the second set of physical blocks to obtain a second reconstructed logical block;

checksum the second reconstructed logical block to obtain a second calculated checksum; and

determine whether the second calculated checksum is equal to the stored checksum associated with the second reconstructed logical block.

13. The computer readable medium of claim 10, further comprising software instructions to:

receive a request for a logical block;

obtain the logical block;

checksum the logical block to obtain a third calculated checksum;

if the third calculated checksum is not equal to the stored checksum, then initiate the determination of the number of non-parity disks (n); and

if the third calculated checksum is equal to the stored checksum, then return the logical block to a process which sent the request.

14. The computer readable medium of claim 13, wherein the stored checksum is stored in a block pointer referencing the logical block.

15. The computer readable medium of claim 13, wherein the logical block is stored using a RAID scheme.

16. The computer readable medium of claim 10, wherein the logical block is a data block.

17. The computer readable medium of claim 10, wherein the logical block is an indirect block.

18. The computer readable medium of claim 10, wherein the logical block is associated with a file.